浅谈 Cauchy-Binet 公式
ref_rainT
·
·
算法·理论
零、前言 / 观前提示
前情提要：
矩阵的若干运算及其性质 - ref_rainT
行列式入门 - ref_rainT
这应该是我在线性代数方面写的第三篇学习笔记，由于我水平很菜，不能保证全部内容特别严谨，如果出锅请评论或者私信找我，我会第一时间修改；
相较于前两篇文章，这篇文章的内容较难理解，请做好心理准备，必要时请在草稿纸上推演，这会有很大帮助。
在阅读本文之前，你需要掌握如下内容：
部分题目极具启发性，请先自行思考再看解析。
一、约定记号
为方便表示，在本文中的未声明情况下，我们约定 A 为 m\times n 矩阵，B 为 n\times m 矩阵。
其次，我们引入子式表示法如下：
A\begin{pmatrix}
i_1 &i_2 &\cdots & i_s\\
j_1 & j_2&\cdots &j_s
\end{pmatrix}
上面的式子表示由矩阵 A 的第 i_1,i_2,\cdots,i_s 行和第 j_1,j_2,\cdots,j_s 列交点元素按原本顺序组成的 s 阶行列式。
注意，不同于矩阵的概念，行列式代表了一个数值。因此，子式表示法最后得到的 s 阶行列式（即定义中表粗的部分）所代表的也是一个数值而非矩阵。
可能有些抽象，我们举个例子。
::::info[例 1 - Description]{open}
已知
A=\begin{pmatrix}
2 & 5 & 3 & 7\\
1 & 4 & 2 & 5\\
4 & 10 & 6 & 14\\
3 & 8 & 4 &
11\end{pmatrix}
求
A\begin{pmatrix}
1&2&3\\2&3&4
\end{pmatrix}
::::
::::info[例 1 - Solution]{open}
根据定义，我们选取的是矩阵 A 第 1 到 3 行和第 2 到 4 列。
这三行三列形成了九个相交的点，按照最初的顺序，我们把它们写成一个三阶行列式如下：
\begin{vmatrix}
A_{12} &A_{13} &A_{14} \\
A_{22} & A_{23} & A_{24}\\
A_{32} &A_{33} &A_{34}
\end{vmatrix}
代入，得
\begin{vmatrix}
5&3&7\\4&2&5\\10&6&14
\end{vmatrix}
发现第 3 行是第 1 行的二倍，因此该行列式的值为 0，则
A\begin{pmatrix}
1&2&3\\2&3&4
\end{pmatrix}=0
::::
二、公式内容
::::info[Cauchy-Binet公式]{open}
设 A=(a_{ij})_{m\times n}，B=(b_{ij})_{n\times m}。由于 A 的列数等于 B 的行数，因此矩阵 AB 可以相乘得到一个 m\times m 的方阵。
Cauchy-Binet 公式告诉了我们 |AB| 的值：
-
情形一：若 m>n，则必有 |AB|=0。
-
情形二：若 m\le n，则必有
|AB|=\sum_{1\le j_1<j_2<\cdots<j_m\le n} A\begin{pmatrix}
1 &2 &\cdots &m \\
j_1 &j_2 &\cdots &j_m
\end{pmatrix}
B\begin{pmatrix}
j_1 &j_2 &\cdots &j_m \\
1 &2 &\cdots &m
\end{pmatrix}
::::
证明相当复杂，本文不做展开，感兴趣的同学请移步知乎学习，这里给出我觉得相对易懂的版本：Link。
三、例题与应用
::::info[例 2 - Description]{open}
给定矩阵 M，求 |M|。
M=\begin{pmatrix}
1 & 2 & 1 & 0\\
0 &1 &2 &1 \\
1 &3 &3 &1 \\
2 &4 &5 &2
\end{pmatrix}
::::
::::info[例 2 - Solution1]{open}
使用行列式的初等行变换。将第一行乘上 -1 加到第三行，原行列式变为
\begin{vmatrix}
1 & 2 & 1 & 0\\
0 &1 &2 &1 \\
0 &1 &2 &1 \\
2 &4 &5 &2
\end{vmatrix}
| 不难注意到第二行和第三行相同，于是行列式的值等于 0。 |
::::info[例 2 - Solution2]{open}
一个考察注意力的做法。考虑将 M 分解为两个矩阵的乘积，可以构造出（虽然我不知道是怎么构造出的）
A_{4\times 3}=\begin{pmatrix}
1&0&0\\
0&1&0\\
1&1&0\\1&1&1
\end{pmatrix},B_{3\times 4}=\begin{pmatrix}
1&2&1&0\\
0&1&2&1\\
1&1&2&1
\end{pmatrix}
这里 AB=M，而 m=4>n，故套用 Cauchy-Binet 公式的情形一，AB=0。
形象点地说，M=AB 是 4 阶方阵，由 Cauchy-Binet 公式，我们需要从 A 中选出 4 列，而 A 仅有 3 列，故无法选取，所有 4 阶子式均为 0。
因此，|AB|=\sum 0=0。
::::
::::info[例 3 - Description]{open}
设 n\ge 3，求证下列行列式的值为 0：
\begin{vmatrix}A\end{vmatrix}=
\begin{vmatrix}
1+x_1y_1&1+x_1y_2&\cdots &1+x_1y_n\\
1+x_2y_1&1+x_2y_2&\cdots &1+x_2y_n\\
\vdots &\vdots&\ddots& \vdots\\
1+x_ny_1&1+x_ny_2&\cdots& 1+x_ny_n
\end{vmatrix}
::::
::::info[例 3 - Solution1]{open}
这是一个简单行列式做法。考虑做初等行变换，把第一行乘 -1 加到第 2 到 n 行上，观察结果。
1+x_1y_1&1+x_1y_2&\cdots &1+x_1y_n\\
x_2y_1-x_1y_1&x_2y_2-x_1y_2&\cdots &x_2y_n-x_1y_n\\
\vdots &\vdots&\ddots& \vdots\\
x_ny_1-x_1y_1&x_ny_2-x_1y_2&\cdots& x_ny_n-x_1y_n
\end{vmatrix}
合并同类项化简：
1+x_1y_1&1+x_1y_2&\cdots &1+x_1y_n\\
(x_2-x_1)y_1&(x_2-x_1)y_2&\cdots &(x_2-x_1)y_n\\
\vdots &\vdots&\ddots& \vdots\\
(x_n-x_1)y_1&(x_n-x_1)y_2&\cdots& (x_n-x_1)y_n
\end{vmatrix}
然后，对于所有 2\le i\le n，都可以提出一个公因式 (x_i-x_1)。
|A|=\begin{vmatrix}
1+x_1y_1&1+x_1y_2&\cdots &1+x_1y_n\\
y_1&y_2&\cdots &y_n\\
\vdots &\vdots&\ddots& \vdots\\
y_1&y_2&\cdots&y_n
\end{vmatrix}
\prod_{i=2}^n(x_i-x_1)
发现第 2 到 n 行都相同，于是 |A|=0。
::::
::::info[例 3 - Solution2]{open}
将 A 看作一个矩阵之后，使用例 2 Solution2 的做法，构造 A=BC。这个相对例 2 容易多了，构造如下：
A=\begin{pmatrix}1 &x_1\\1&x_2\\\vdots&\vdots\\1&x_n \end{pmatrix}
\begin{pmatrix}1&1&\cdots& 1\\y_1&y_2&\cdots&y_n
\end{pmatrix}
那现在要求 |A| 就可以直接套用 Cauchy-Binet 公式的情形 1 了，A 是一个 n 阶方阵，而我们构造出的 B 只有两列，无法选取，故 |A|=0。
::::
::::info[例 4 - Description]{open}
证明 Lagrange 恒等式（n\ge 2）：
\left ( \sum_{i=1}^n a_i^2 \right )\left ( \sum_{i=1}^nb_i^2 \right )-\left (\sum_{i=1}^n a_ib_i \right )^2 =\sum_{1\le i<j\le n}(a_ib_j-a_jb_i)^2
::::
::::info[例 4- Solution]{open}
首先我们知道二阶行列式的计算方式：
\begin{vmatrix}a&b\\c&d\end{vmatrix}=ad-cb
那再看看等式左边，是不是跟这个很像？因此，左边的式子就等于
|M|=\begin{vmatrix}
\sum\limits_{i=1}^n a_i^2&\sum\limits_{i=1}^na_ib_i\\
\sum\limits_{i=1}^n a_ib_i& \sum\limits_{i=1}^n b_i^2
\end{vmatrix}
再把这个矩阵拆成 M=AB 的形式，构造得：
M=\begin{pmatrix}
a_1&a_2&\cdots&a_n\\b_1&b_2&\cdots&b_n
\end{pmatrix}
\begin{pmatrix}
a_1&b_1\\a_2&b_2\\\vdots&\vdots\\a_n&b_n
\end{pmatrix}
然后由 Cauchy-Binet 公式得：
\begin{aligned}
|M|&=\sum_{1\le i<j\le n} A\begin{pmatrix}1&2\\i&j\end{pmatrix}B\begin{pmatrix} i&j \\1&2\end{pmatrix}\\
&=\sum_{1\le i<j\le n} \begin{vmatrix}a_i&a_j\\b_i&b_j\end{vmatrix}
\begin{vmatrix}a_i&b_i\\a_j&b_j\end{vmatrix}\\
&=\sum_{1\le i<j\le n} (a_ib_j-a_jb_i)^2
\end{aligned}
::::info[例 5 - Description]{open}
设 a_i,b_i 都是实数，证明 Cauchy-Schwarz 不等式：
\left ( \sum_{i=1}^n a_i^2\right )\left (\sum_{i=1}^n b_i^2 \right )\ge \left ( \sum_{i=1}^n a_ib_i\right )^2
::::
::::info[例 5 - Solution]{open}
这个和例 5 基本一样，考虑移项成例 5 的形式，然后因为例 5 的右式是平方和，非负，所以就证毕了。
::::
四、进行推广
上面的部分主要解决了两矩阵相乘取行列式的问题，接下来我们来求 AB 的 k 阶子式。
::::info[一个命题]{open}
设 A=(a_{ij})_{m\times n}，B=(b_{ij})_{n\times m}，r 是一个正整数且 r\le m。
类似 Cauchy-Binet 公式的概念，分两种情况讨论。
AB\begin{pmatrix}
i_1&i_2&\cdots&i_r\\j_1&j_2&\cdots&j_r
\end{pmatrix}=\sum_{1\le k_1<k_2<\cdots<k_r\le n} A\begin{pmatrix}
i_1&i_2&\cdots&i_r\\k_1&k_2&\cdots&k_r
\end{pmatrix}B\begin{pmatrix}
k_1&k_2&\cdots&k_r\\j_1&j_2&\cdots&j_r
\end{pmatrix}
::::
为了讲解下面的例题，这里引入 主子式 的概念。
矩阵 A 的 r 阶主子式记号如下：
A\begin{pmatrix}
i_1&i_2&\cdots&i_r\\i_1&i_2&\cdots&i_r
\end{pmatrix}
即选取第 i_1,i_2,\cdots,i_r 行与 i_1,i_2,\cdots,i_r 列构成子矩阵的行列式。
特殊地，当 i_1 至 i_r 连续递增时，称该主子式为 顺序主子式。
::::info[例 6 - Description]{open}
设 A 是 m\times n 实矩阵，求证：矩阵 AA^\mathrm{T} 的任意主子式都非负。
::::
::::info[例 6 - Solution]{open}
由上面的命题，写出目标矩阵的 r 阶主子式。
若 r\le n，则
M\begin{pmatrix}
i_1&i_2&\cdots&i_r\\i_1&i_2&\cdots&i_r
\end{pmatrix}=\sum_{1\le k_1<k_2\cdots<k_r\le n} A\begin{pmatrix}
i_1&i_2&\cdots&i_r\\
k_1&k_2&\cdots&k_r
\end{pmatrix}A^\mathrm{T}\begin{pmatrix}
k_1&k_2&\cdots&k_r\\
i_1&i_2&\cdots&i_r
\end{pmatrix}
手摸一下转置的过程，我们发现求和后面的两个东西是一定相等的，所以：
M\begin{pmatrix}
i_1&i_2&\cdots&i_r\\i_1&i_2&\cdots&i_r
\end{pmatrix}=\sum_{1\le k_1<k_2\cdots<k_r\le n} A\begin{pmatrix}
i_1&i_2&\cdots&i_r\\
k_1&k_2&\cdots&k_r
\end{pmatrix}^2
::::info[例 7 - Description]{open}
设 A 是 m\times n 实矩阵，求证：矩阵 A\overline{A}^\mathrm{T} 的任意主子式都非负。
::::
::::info[例 7 - Solution]{open}
由上面的命题，写出目标矩阵的 r 阶主子式。
若 r\le n，则
M\begin{pmatrix}
i_1&i_2&\cdots&i_r\\i_1&i_2&\cdots&i_r
\end{pmatrix}=\sum_{1\le k_1<k_2\cdots<k_r\le n} A\begin{pmatrix}
i_1&i_2&\cdots&i_r\\
k_1&k_2&\cdots&k_r
\end{pmatrix}\overline{A}^\mathrm{T}\begin{pmatrix}
k_1&k_2&\cdots&k_r\\
i_1&i_2&\cdots&i_r
\end{pmatrix}
我们知道，行列式转置后的值不变。因此我们直接把转置扔掉。
M\begin{pmatrix}
i_1&i_2&\cdots&i_r\\i_1&i_2&\cdots&i_r
\end{pmatrix}=\sum_{1\le k_1<k_2\cdots<k_r\le n} A\begin{pmatrix}
i_1&i_2&\cdots&i_r\\
k_1&k_2&\cdots&k_r
\end{pmatrix}\overline{A\begin{pmatrix}
i_1&i_2&\cdots&i_r\\
k_1&k_2&\cdots&k_r
\end{pmatrix}}
对于复数 a+bi，考虑乘上他的共轭，有 (a+bi)(a-bi)=a^2+b^2。
因此上面的式子就是若干个平方和，非负，证毕。
::::