Cauchy–Binet formula

hbghlyj · 发表于 2022-3-3 06:32

本帖最后由 hbghlyj 于 2023-4-29 02:43 编辑 柯西-比内公式（Cauchy–Binet formula）将行列式的可乘性（两个方块矩阵的行列式等于两个行列式的乘积）推广到非方块矩阵。

假设 A 是一个 m×n 矩阵，而 B 是一个 n×m 矩阵。如果 S 是 { 1, ..., n } 中具有 m 个元素的子集，我们记 A_S 为 A 中列指标位于 S 中的 m×m 子矩阵。类似地，记 B_S 为 B 中行指标位于 S 中的 m×m 子矩阵。柯西-比内公式说
$$\det(AB)=\sum _{S}\det(A_{S})\det(B_{S})$$
这里求遍 { 1, ...,n } 中 m 个元素的所有可能子集 S（共有 $C_n^m$ 个）。

如果 m=n，即 A 与 B 是同样大小的方块矩阵，则只有一个容许集合 S，柯西-比内公式退化为通常行列式的可乘性。如果 m=1 则有 n 容许集合 S，这个公式退化为点积。如果 m>n，没有容许集合 S，行列式 det(AB) 是零（参见空和（empty sum））。

这个公式对矩阵元素取值于任何交换环都成立。证明可将 AB 的列写成系数来自 B 的 A 的列的线性组合，利用行列式的可乘性，将属于一个 det(A_S) 的项收集起来，并利用行列式的反对称性。利用行列式的莱布尼兹公式，得出 det(A_S) 的系数是 det(B_S)。这个证明没有利用行列式的可乘性，相反这个证明建立了它。

如果 A 是一个实 m×n 矩阵，则 det(AA^T) 等于由 A 中行向量在 Rⁿ 中张成的平行多面体 m-维体积的平方。柯西-比内公式说这等于该平行多面体在所有 m-维坐标平面（共有 $C_n^m$ 个）的正交投影的平行多面体的 m-维体积的平方之总和。m=1 的情形是关于一条线段的长度，这恰是毕达哥拉斯定理。

例
如果 ${\displaystyle A={\begin{bmatrix}1&1&2\\3&1&-1\\\end{bmatrix}}}$ 与 ${\displaystyle B={\begin{bmatrix}1&1\\3&1\\0&2\end{bmatrix}}}$ 则柯西-比内公式给出行列式：
${\displaystyle \det(AB)=\left|{\begin{matrix}1&1\\3&1\end{matrix}}\right|\cdot \left|{\begin{matrix}1&1\\3&1\end{matrix}}\right|+\left|{\begin{matrix}1&2\\1&-1\end{matrix}}\right|\cdot \left|{\begin{matrix}3&1\\0&2\end{matrix}}\right|+\left|{\begin{matrix}1&2\\3&-1\end{matrix}}\right|\cdot \left|{\begin{matrix}1&1\\0&2\end{matrix}}\right|=-28.}$

The Cauchy-Binet formula.pdf (43.35 KB, 下载次数: 27)

Czhang271828 · 发表于 2022-3-3 17:11

回复 1# hbghlyj

kuing.cjhb.site/forum.php?mod=viewthread&tid=416&extra=page%3D4

isee · 发表于 2022-3-3 18:55

游客，本帖隐藏的内容需要积分高于 4200 才可浏览，您当前积分为 0

hbghlyj · 发表于 2022-3-3 19:30

回复 3# isee
那个提问者是谁啊

isee · 发表于 2022-3-3 19:34

回复 4# hbghlyj

怎么可能认识呢，
我还以为你在哪个讨论区（群）等讨论的问题呢

hbghlyj · 发表于 2023-4-29 03:08

讲义《行列式入门》30. Binet–Cauchy 公式

或许, (方)阵的行列式与阵的积的定义都是较复杂的 (跟阵的转置、加、减、数乘等对比). 不过, 这二种较复杂的运算有着较不平凡的联系.
设 $A$ 是一个 $m \times n$ 阵, $B$ 是一个 $n \times m$ 阵. 根据阵的积的定义, $BA$ 是一个 $n$ 级阵, 故它有行列式.
Theorem 1 (Binet–Cauchy 公式). 设 $A$, $B$ 分别是 $m \times n$, $n \times m$ 阵.
(1) 若 $n > m$, 则 $\det {(BA)} = 0$.
(2) 若 $n \leq m$, 则
\begin{align*}
& \det {(BA)}
\\
= {} & \sum_{1 \leq j_1 < j_2 < \dots < j_n \leq m}
{
\det {\left(
B\binom{1, 2, \dots, n}{j_1, j_2, \dots, j_n}
\right)}
\det {\left(
A\binom{j_1, j_2, \dots, j_n}{1, 2, \dots, n}
\right)}
}.
\end{align*}
特别地, 若 $n = m$, 则适合条件 $1 \leq j_1 < j_2 < \dots < j_n \leq m$ 的 $j_1, j_2, \dots, j_n$ 只能是 $1, 2, \dots, n$, 故
\begin{align*}
\det {(BA)}
= {} &
\det {\left(
B\binom{1, 2, \dots, n}{1, 2, \dots, n}
\right)}
\det {\left(
A\binom{1, 2, \dots, n}{1, 2, \dots, n}
\right)}
\\
= {} & \det {(B)} \det {(A)}.
\end{align*}
我举二个例, 助您理解, 此定理在说什么.
Example 1. 设
\begin{align*}
A =
\begin{bmatrix}
1 & 3 & 5 \\
2 & 4 & 6 \\
\end{bmatrix},
\quad
B =
\begin{bmatrix}
7 & 10 \\
8 & 11 \\
9 & 12 \\
\end{bmatrix}.
\end{align*}
不难算出,
\begin{align*}
AB =
\begin{bmatrix}
76
& 103 \\
100 & 136 \\
\end{bmatrix},
\quad
BA =
\begin{bmatrix}
27 & 61 & 95
\\
30 & 68 & 106 \\
33 & 75 & 117 \\
\end{bmatrix}.
\end{align*}
直接计算, 可知
\begin{align*}
\det {(AB)} = 76 \cdot 136 - 100 \cdot 103 = 36,
\end{align*}
而
\begin{align*}
\det {(BA)}
= {} & \hphantom{{} + {}}
27 \cdot 68 \cdot 117
+ 30 \cdot 75 \cdot 95
+ 33 \cdot 61 \cdot 106
\\
&
- 27 \cdot 75 \cdot 106
- 30 \cdot 61 \cdot 117
- 33 \cdot 68 \cdot 95
\\
= {} & 0.
\end{align*}
或许, 上面的计算是较复杂的. 我们试用 Binet–Cauchy 公式, 再计算它们.
因为 $A$, $B$ 的尺寸分别是 $2 \times 3$, $3 \times 2$, 而 $3 > 2$, 根据 (1), $\det {(BA)} = 0$
(注意到, $BA$ 是 $3$ 级阵).
因为 $2 \leq 3$, 故, 根据 (2),
\begin{align*}
& \det {(AB)}
\\
= {} &
\hphantom{{} + {}}
\det {\left(A\binom{1,2}{1,2}\right)}
\det {\left(B\binom{1,2}{1,2}\right)}
+ \det {\left(A\binom{1,2}{1,3}\right)}
\det {\left(B\binom{1,3}{1,2}\right)}
\\
&
+ \det {\left(A\binom{1,2}{2,3}\right)}
\det {\left(B\binom{2,3}{1,2}\right)}.
\end{align*}
这里, 要注意到, 适合条件 “$1 \leq j_1 < j_2 \leq 3$” 的 $(j_1, j_2)$ 恰有三组: $(1, 2)$, $(1, 3)$, $(2, 3)$. 不难写出
\begin{align*}
& A\binom{1,2}{1,2}
= \begin{bmatrix} 1&3\\2&4\\ \end{bmatrix},
\quad
B\binom{1,2}{1,2}
= \begin{bmatrix} 7&10\\8&11\\ \end{bmatrix}, \\
& A\binom{1,2}{1,3}
= \begin{bmatrix} 1&5\\2&6\\ \end{bmatrix},
\quad
B\binom{1,3}{1,2}
= \begin{bmatrix} 7&10\\9&12\\ \end{bmatrix}, \\
& A\binom{1,2}{2,3}
= \begin{bmatrix} 3&5\\4&6\\ \end{bmatrix},
\quad
B\binom{2,3}{1,2}
= \begin{bmatrix} 8&11\\9&12\\ \end{bmatrix}.
\end{align*}
从而
\begin{align*}
\det {(AB)}
= (-2) \cdot (-3) + (-4) \cdot (-6) + (-2) \cdot (-3)
= 36.
\end{align*}
Example 2. 设
\begin{align*}
A = \begin{bmatrix}
2 & 5 \\
3 & 7 \\
\end{bmatrix},
\quad
B = \begin{bmatrix}
9 & 6 \\
4 & 8 \\
\end{bmatrix}.
\end{align*}
不难算出
\begin{align*}
AB
= \begin{bmatrix}
38 & 52 \\
55 & 74 \\
\end{bmatrix},
\quad
BA
= \begin{bmatrix}
36 & 87 \\
32 & 76 \\
\end{bmatrix}.
\end{align*}
可以看到, $AB \neq BA$.
不过, $\det {(AB)} = \det {(BA)}$. 一方面, 我们可直接验证:
\begin{align*}
& \det {(AB)} = 38 \cdot 74 - 55 \cdot 52 = -48, \\
& \det {(BA)} = 36 \cdot 76 - 32 \cdot 87 = -48.
\end{align*}
另一方面, Binet–Cauchy 公式指出,
\begin{align*}
\det {(AB)}
= {} & \det {(A)} \det {(B)} \\
= {} & \det {(B)} \det {(A)} \\
= {} & \det {(BA)}.
\end{align*}
毕竟, 数的乘法是可换的.
为较流畅地论证公式, 我们需要三个新事实的帮助.
为证明这三个新事实的前二个, 我们需要一些老的公式.
Theorem 2. 设 $A$ 是 $n$ 级阵 ($n \geq 1$). 设 $j_1$, $j_2$, $\dots$, $j_n$ 是不超过 $n$ 的正整数, 且互不相同. 则
\begin{align*}
& \det {(A)}
\\
= {} &
\sum_{\substack{
1 \leq i_1, i_2, \dots, i_n \leq n \\
i_1, i_2, \dots, i_n\,\text{
互不相同
}
}}
{s(i_1, i_2, \dots, i_n)\,
s(j_1, j_2, \dots, j_n)\,
[A]_{i_1,j_1} [A]_{i_2,j_2} \dots [A]_{i_n,j_n}}.
\end{align*}
取 $j_1$, $j_2$, $\dots$, $j_n$ 为 $1$, $2$, $\dots$, $n$, 并注意到 $s(1, 2, \dots, n) = 1$, 有
\begin{align*}
\det {(A)}
= {} &
\sum_{\substack{
1 \leq i_1, i_2, \dots, i_n \leq n \\
i_1, i_2, \dots, i_n\,\text{
互不相同
}
}}
{s(i_1, i_2, \dots, i_n)\,
[A]_{i_1,1} [A]_{i_2,2} \dots [A]_{i_n,n}}.
\end{align*}
Theorem 3. 设 $n$ 级阵 $A$ 的列 $1$, $2$, $\dots$, $n$ 分别为 $a_1$, $a_2$, $\dots$, $a_n$. 设 $\ell_1$, $\ell_2$, $\dots$, $\ell_n$ 是不超过 $n$ 的正整数,
且互不相同. 则
\begin{align*}
\det {[a_{\ell_1}, a_{\ell_2}, \dots, a_{\ell_n}]}
= s(\ell_1, \ell_2, \dots, \ell_n) \det {(A)}.
\end{align*}
现在, 我要开始展现三个新事实了.
Theorem 4. 设 $C$ 为 $n \times m$ 阵, 且 $m \geq n$. 设 $C$ 的列 $1$, $2$, $\dots$, $m$ 分别为 $c_1$, $c_2$, $\dots$, $c_m$. 设 $k_1$, $k_2$, $\dots$, $k_n$ 是不超过 $m$ 的正整数, 且互不相同. 设 $j_1$, $j_2$, $\dots$, $j_n$ 是 $k_1$, $k_2$, $\dots$, $k_n$ 的自然排列. 则
\begin{align*}
\det {[c_{k_1}, c_{k_2}, \dots, c_{k_n}]}
= s(k_1, k_2, \dots, k_n)
\det {[c_{j_1}, c_{j_2}, \dots, c_{j_n}]}.
\end{align*}
Proof. 设 $k_t$ 在 $k_1$, $k_2$, $\dots$, $k_n$ 的自然排列 $j_1$, $j_2$, $\dots$, $j_n$ 里的位置为 $f(k_t)$ ($t = 1$, $2$, $\dots$, $n$). 注意, $f(j_t) = t$. 并且,
若 $k_t < k_v$, 必有 $f(k_t) < f(k_v)$. 反过来, 若 $f(k_t) < f(k_v)$, 必有 $k_t < k_v$.
(我举一个简单的例助您理解. 设 $m = 9$, $n = 3$. 设 $k_1$, $k_2$, $k_3$ 分别为 $8$, $9$, $6$. 那么, $k_1$, $k_2$, $k_3$ 的自然排列 $j_1$, $j_2$, $j_3$ 是 $6$, $8$, $9$. 故 $f(k_1) = f(j_2) = f(8) = 2$, $f(k_2) = f(j_3) = f(9) = 3$, $f(k_3) = f(j_1) = f(6) = 1$.)
从而 $\operatorname{sgn} {(k_v - k_t)}= \operatorname{sgn} {(f(k_v) - f(k_t))}$.
作阵 $G = [c_{j_1}, c_{j_2}, \dots, c_{j_n}]$. 设 $G$ 的列 $1,2,\dots,n$ 分别是 $g_1$, $g_2$, $\dots$, $g_n$. 则
\begin{align*}
[c_{k_1}, c_{k_2}, \dots, c_{k_n}]
= [g_{f(k_1)}, g_{f(k_2)}, \dots, g_{f(k_n)}].
\end{align*}
故
\begin{align*}
\det {[c_{k_1}, c_{k_2}, \dots, c_{k_n}]}
= {} &
\det {[g_{f(k_1)}, g_{f(k_2)}, \dots, g_{f(k_n)}]}
\\
= {} &
s(f(k_1), f(k_2), \dots, f(k_n))
\det {[g_1, g_2, \dots, g_n]}
\\
= {} &
s(k_1, k_2, \dots, k_n)
\det {[c_{j_1}, c_{j_2}, \dots, c_{j_n}]}.
\end{align*}
Theorem 5. 设 $D$ 为 $m \times n$ 阵, 且 $m \geq n$. 设 $i_1$, $i_2$, $\dots$, $i_n$ 是不超过 $m$ 的正整数, 且 $i_1 < i_2 < \dots < i_n$. 则
\begin{align*}
&
\det {\left(
D\binom{i_1, i_2, \dots, i_n}{1, 2, \dots, n}
\right)}
\\
= {} &
\sum_{\substack{
k_1, k_2, \dots, k_n\,\text{
是
} \\
i_1, i_2, \dots, i_n\,\text{
的排列
}
}}
{s(k_1, k_2, \dots, k_n)\,
[D]_{k_1,1} [D]_{k_2,2} \dots [D]_{k_n,n}}.
\end{align*}
Proof. 设
\begin{align*}
H =
D\binom{i_1, i_2, \dots, i_n}{1, 2, \dots, n}.
\end{align*}
不难看出, $[H]_{u,v} = [D]_{i_u,v}$.
记 $f(i_t) = t$ ($t = 1$, $2$, $\dots$, $n$). 设 $k_1$, $k_2$, $\dots$, $k_n$ 是 $i_1$, $i_2$, $\dots$, $i_n$ 的一个排列.
那么, $f(k_1)$, $f(k_2)$, $\dots$, $f(k_n)$ 一定是 $1$, $2$, $\dots$, $n$ 的一个排列. 反过来, 若 $v_1$, $v_2$, $\dots$, $v_n$ 是 $1$, $2$, $\dots$, $n$ 的一个排列, 则 $i_{v_1}$, $i_{v_2}$, $\dots$, $i_{v_n}$ 一定是 $i_1$, $i_2$, $\dots$, $i_n$ 的一个排列. 并且, 若 $k_t < k_v$, 必有 $f(k_t) < f(k_v)$. 反过来, 若 $f(k_t) < f(k_v)$, 必有 $k_t < k_v$. 从而 $\operatorname{sgn} {(k_v - k_t)}= \operatorname{sgn} {(f(k_v) - f(k_t))}$.
故
\begin{align*}
&
\det {\left(
D\binom{i_1, i_2, \dots, i_n}{1, 2, \dots, n}
\right)}
\\
= {} &
\det {(H)}
\\
= {} &
\sum_{\substack{
k_1, k_2, \dots, k_n\,\text{
是
} \\
i_1, i_2, \dots, i_n\,\text{
的排列
}
}}
{s(f(k_1), f(k_2), \dots, f(k_n))\,
[H]_{f(k_1),1} [H]_{f(k_2),2} \dots [H]_{f(k_n),n}}
\\
= {} &
\sum_{\substack{
k_1, k_2, \dots, k_n\,\text{
是
} \\
i_1, i_2, \dots, i_n\,\text{
的排列
}
}}
{s(k_1, k_2, \dots, k_n)\,
[D]_{k_1,1} [D]_{k_2,2} \dots [D]_{k_n,n}}.
\end{align*}
Theorem 6. 设 $n \leq m$. 设数 $f(k_1, k_2, \dots, k_n)$ (其中 $k_1$, $k_2$, $\dots$, $k_n$ 取遍 $1$, $2$, $\dots$, $m$) 适合: 若 $k_p = k_q$ ($1 \leq p < q \leq n$), 则 $f(k_1, k_2, \dots, k_n) = 0$. 那么
\begin{align*}
&
\sum_{1 \leq k_1, k_2, \dots, k_n \leq m}
{f(k_1, k_2, \dots, k_n)}
\\
= {} &
\sum_{\substack{
1 \leq k_1, k_2, \dots, k_n \leq m \\
k_1, k_2, \dots, k_n\,\text{
互不相同
}
}}
{f(k_1, k_2, \dots, k_n)}
\\
= {} &
\sum_{1 \leq j_1 < j_2 < \dots < j_n \leq m}
{\sum_{\substack{
k_1, k_2, \dots, k_n\,\text{
是
}
\\
j_1, j_2, \dots, j_n\,\text{
的排列
}
}}
{f(k_1, k_2, \dots, k_n)}}.
\end{align*}
Proof. 由 $f$ 的性质可知, 前一个等式成立. 后一个等式也不难. 注意到, 欲从 $m$ 个不同的数里有前后次序地选 $n$ 个不同的数 $k_1$, $k_2$, $\dots$, $k_n$, 我们可以这样: 先从小到大地从这 $m$ 个数里选 $n$ 个不同的数 $j_1$, $j_2$, $\dots$, $j_n$, 再有前后次序地作这 $n$ 个数的排列 $k_1$, $k_2$, $\dots$, $k_n$. 所以后一个等式也成立.
现在, 我们证明 Binet–Cauchy 公式.
Proof. 设 $B$ 的列 $1$, $2$, $\dots$, $m$ 分别是 $b_1$, $b_2$, $\dots$, $b_m$.
设 $A$ 的列 $1$, $2$, $\dots$, $n$ 分别是 $a_1$, $a_2$, $\dots$, $a_n$. 那么
\begin{align*}
BA
= {} & [Ba_1, Ba_2, \dots, Ba_n] \\
= {} &
\left[
\sum_{k_1 = 1}^{m} {[A]_{k_1,1} b_{k_1}},
\sum_{k_2 = 1}^{m} {[A]_{k_2,2} b_{k_2}},
\dots,
\sum_{k_n = 1}^{m} {[A]_{k_n,n} b_{k_n}}
\right].
\end{align*}
利用行列式的多线性, 有
\begin{align*}
& \det {(BA)}
\\
= {} &
\det {\left[
\sum_{k_1 = 1}^{m} {[A]_{k_1,1} b_{k_1}},
\sum_{k_2 = 1}^{m} {[A]_{k_2,2} b_{k_2}},
\dots,
\sum_{k_n = 1}^{m} {[A]_{k_n,n} b_{k_n}}
\right]}
\\
= {} &
\sum_{k_1 = 1}^{m} {[A]_{k_1,1}
\det {\left[
b_{k_1},
\sum_{k_2 = 1}^{m} {[A]_{k_2,2} b_{k_2}},
\dots,
\sum_{k_n = 1}^{m} {[A]_{k_n,n} b_{k_n}}
\right]}}
\\
= {} &
\sum_{k_1 = 1}^{m} {
\sum_{k_2 = 1}^{m} {
[A]_{k_1,1} [A]_{k_2,2}
\det {\left[
b_{k_1},
b_{k_2},
\dots,
\sum_{k_n = 1}^{m} {[A]_{k_n,n} b_{k_n}}
\right]}}}
\\
= {} &
\dots \dots \dots \dots
\dots \dots \dots \dots
\dots \dots \dots \dots
\dots \dots \dots \dots
\dots \dots \dots \dots
\\
= {} &
\sum_{1 \leq k_1, k_2, \dots, k_n \leq m}
{[A]_{k_1,1} [A]_{k_2,2} \dots [A]_{k_n,n}
\det {[b_{k_1}, b_{k_2}, \dots, b_{k_n}]}}.
\end{align*}
记 $f(k_1, k_2, \dots, k_n)= [A]_{k_1,1} [A]_{k_2,2} \dots [A]_{k_n,n}\det {[b_{k_1}, b_{k_2}, \dots, b_{k_n}]}.$
根据行列式的交错性, 当 $k_1$, $k_2$, $\dots$, $k_n$ 中有二个数相同时, $f(k_1, k_2, \dots, k_n) = 0$.
(1) 若 $n > m$, 则 $k_1$, $k_2$, $\dots$, $k_n$ 中总是有二个相同 (抽屉原理). 所以, 每一项都是零. 故 $\det {(BA)} = 0$.
(2) 若 $n \leq m$, 那么 $\det {(BA)}$ 等于
\begin{align*}
\sum_{1 \leq j_1 < j_2 < \dots < j_n \leq m}
{\sum_{\substack{
k_1, k_2, \dots, k_n\,\text{
是
} \\
j_1, j_2, \dots, j_n\,\text{
的排列
}
}}
{[A]_{k_1,1} [A]_{k_2,2} \dots [A]_{k_n,n}
\det {[b_{k_1}, b_{k_2}, \dots, b_{k_n}]}}}.
\end{align*}
因为 $1 \leq j_1 < j_2 < \dots < j_n \leq m$, 且 $k_1$, $k_2$, $\dots$, $k_n$ 是 $j_1$, $j_2$, $\dots$, $j_n$ 的排列, 故
\begin{align*}
\det {[b_{k_1}, b_{k_2}, \dots, b_{k_n}]}
= s(k_1, k_2, \dots, k_n)
\det {[b_{j_1}, b_{j_2}, \dots, b_{j_n}]},
\end{align*}
从而 $\det {(BA)}$ 等于
\begin{align*}
&
\sum_{1 \leq j_1 < j_2 < \dots < j_n \leq m}
{\det {[b_{j_1}, b_{j_2}, \dots, b_{j_n}]}}
\\
& \qquad \qquad \qquad
\cdot
\sum_{\substack{
k_1, k_2, \dots, k_n\,\text{
是
} \\
j_1, j_2, \dots, j_n\,\text{
的排列
}
}}
{s(k_1, k_2, \dots, k_n)\,
[A]_{k_1,1} [A]_{k_2,2} \dots [A]_{k_n,n}}.
\end{align*}
注意到, 内层的求和即为
\begin{align*}
\det {\left(
A\binom{j_1, j_2, \dots, j_n}{1, 2, \dots, n}
\right)}.
\end{align*}
再注意到, 因为 $1 \leq j_1 < j_2 < \dots < j_n \leq m$, 故, 由子阵的定义,
\begin{align*}
[b_{j_1}, b_{j_2}, \dots, b_{j_n}]
= B\binom{1, 2, \dots, n}{j_1, j_2, \dots, j_n}.
\end{align*}
从而
\begin{align*}
& \det {(BA)}
\\
= {} & \sum_{1 \leq j_1 < j_2 < \dots < j_n \leq m}
{
\det {\left(
B\binom{1, 2, \dots, n}{j_1, j_2, \dots, j_n}
\right)}
\det {\left(
A\binom{j_1, j_2, \dots, j_n}{1, 2, \dots, n}
\right)}
}.
\end{align*}

hbghlyj · 发表于 2023-4-29 03:16

搬运的过程:
把公式用verbatim环境包住, paperheight=250cm足够大(使得最终结果在1页上), 用XeLaTeX编译,
然后pdftohtml, 最后Decode HTML Entities
注意verbatim中\text会变成乱码,找着办法解决了.

hbghlyj · 发表于 2025-1-21 19:19

boonsuan.github.io/misc/cauchy_binet.pdf
We present two proofs of the formula. The first proof relies on the exterior algebra, and the second proof makes use of characteristic polynomials.

Via exterior powers
Let $m<n$. The $m \times n$ matrix $A$ can be interpreted as a linear map $L_A: \mathbf{k}^n \rightarrow \mathbf{k}^m$, where $\mathbf{k}$ is a field. We shall investigate what maps the $m \times m$ matrices $A_{[m] \times S}$ and $B_{S \times[m]}$ represent. Denote by $e_1, \ldots, e_n$ the standard basis for $\mathbf{k}^n$ and fix $S=\left\{s_1, \ldots, s_m\right\}$ with $1 \leq s_1<\cdots<s_m \leq n$. We define an $m$-dimensional subspace of $\mathbf{k}^n$ by
\[
V_S:=\operatorname{span}\left\{e_{s_1}, \ldots, e_{s_m}\right\} \subseteq \mathbf{k}^n
\]
A natural way to obtain a map between $m$-dimensional spaces from $L_A$ is by first applying some inclusion $\mathbf{k}^m \hookrightarrow \mathbf{k}^n$ before applying $L_A$. Similarly, since $L_B$ is a map $\mathbf{k}^m \rightarrow \mathbf{k}^n$, it is natural to apply a projection $\mathbf{k}^n \rightarrow \mathbf{k}^m$ after applying $L_B$ to obtain a map between $m$-dimensional spaces. We are thus led to consider the maps
\[
V_S \xrightarrow{\iota_S} \mathbf{k}^n \xrightarrow{L_A} \mathbf{k}^m
\]
where $\iota_S$ denotes the natural inclusion, and
\[
\mathbf{k}^m \xrightarrow{L_B} \mathbf{k}^n \xrightarrow{\pi_S} V_S
\]
where $\pi_S$ denotes the natural projection onto $V_S$. Identifying $\mathbf{k}^m \cong V_S$ by $e_i \mapsto e_{s_i}$, we find that $L_A \circ \iota_S$ and $\pi_S \circ L_B$ are represented by $A_{[m] \times S}$ and $B_{S \times[m]}$ respectively. (This fact is perhaps best appreciated with a concrete example as given in the margin, noting that multiplying a matrix on the right gives linear combinations of columns while multiplying on the left gives linear combinations of rows.) Passing to the $m$-th exterior power for $L_B$, we get
\[
\left(\Lambda^m\left(\pi_S L_B\right)\right)\left(e_1 \wedge \cdots \wedge e_m\right)=\operatorname{det}\left(B_{S \times[m]}\right) e_{S_1} \wedge \cdots \wedge e_{S_m} .
\]
Since $\Lambda^m\left(\pi_S L_B\right)=\Lambda^m \pi_S \circ \Lambda^m L_B$, it follows that
\[
\left(\Lambda^m L_B\right)\left(e_1 \wedge \cdots \wedge e_m\right)=\sum_{\substack{S=\left\{s_1, \ldots, s_m\right\} \\ 1 \leq s_1<\cdots<s_m \leq n}} \operatorname{det}\left(B_{S \times[m]}\right) e_{s_1} \wedge \cdots \wedge e_{s_m} .
\]
Since the $m$-th exterior power for $L_A$ gives
\[
\left(\Lambda^m L_A\right)\left(e_{s_1} \wedge \cdots \wedge e_{s_m}\right)=\operatorname{det}\left(A_{[m] \times S}\right) e_1 \wedge \cdots \wedge e_m
\]
where we have once again identified $\mathbf{k}^m \cong V_S$ as above, we compute
\[
\begin{aligned}
& \left(\Lambda^m L_{A B}\right)\left(e_1 \wedge \cdots \wedge e_m\right) \\
& \quad=\left(\Lambda^m L_A\right) \sum_{\substack{S=\left\{s_1, \ldots, s_m\right\} \\
1 \leq s_1<\cdots<s_m \leq n}} \operatorname{det}\left(B_{S \times[m]}\right) e_{s_1} \wedge \cdots \wedge e_{s_m} \\
& \quad=\sum_{\substack{S=\left\{s_1, \ldots, s_m\right\} \\
1 \leq s_1<\cdots<s_m \leq n}} \operatorname{det}\left(B_{S \times[m]}\right)\left(\Lambda^m L_A\right)\left(e_{S_1} \wedge \cdots \wedge e_{s_m}\right) \\
& \quad=\left(\sum_{\substack{S \subseteq(n]) \\
m}} \operatorname{det}\left(A_{[m] \times S}\right) \operatorname{det}\left(B_{S \times[m]}\right)\right) e_1 \wedge \cdots \wedge e_m .
\end{aligned}
\]
Via the characteristic polynomial
Given an $n \times n$ matrix $X$, we work with the polynomial $\operatorname{det}\left(z I_n+X\right)$ in $z$ whose coefficients are those of the characteristic polynomial, without the signs for convenience. We first show that the coefficient of $z^{n-m}$ in this polynomial is equal to the sum of $m \times m$ principal minors of $X$, where $1 \leq m \leq n$. We compute
\begin{aligned}
\operatorname{det}\left(z I_n+X\right) & =\sum_{\sigma \in \mathfrak{S}_n}(\operatorname{sgn} \sigma) \prod_{1 \leq m \leq n}\left(z \delta_{m, \sigma(m)}+X_{m, \sigma(m)}\right) \\
& =\sum_{\sigma \in \mathfrak{S}_n}(\operatorname{sgn} \sigma) \sum_{S \subseteq[n]} \prod_{i \in S} X_{i, \sigma(i)} \prod_{j \in[n]-S} z \delta_{j, \sigma(j)} \\
& =\sum_{S \subseteq[n]} \sum_{\sigma \in \mathfrak{S}_n}(\operatorname{sgn} \sigma) \prod_{i \in S} X_{i, \sigma(i)} \prod_{j \in[n]-S} z \delta_{j, \sigma(j)} \\
& =\sum_{S \subseteq[n]} z^{n-|S|} \sum_{\sigma \in \mathfrak{S}_S}(\operatorname{sgn} \sigma) \prod_{i \in S} X_{i, \sigma(i)} \\
& =\sum_{S \subseteq[n]} z^{n-|S|} \operatorname{det}\left(X_{S \times S}\right) \\
& =\sum_{0 \leq m \leq n} z^{n-m} \sum_{S \in\binom{m}{[n]}} \operatorname{det}\left(X_{S \times S}\right) .
\end{aligned}Before proving the Cauchy-Binet formula, we will need the identity
\[
\operatorname{det}\left(z I_n+B A\right)=z^{n-m} \operatorname{det}\left(z I_m+A B\right)
\]
where $m \leq n$, and $A$ and $B$ are $m \times n$ and $n \times m$ matrices respectively. We first show the result for when $z=1$ and $m=n$. In this case, the identity reads $\operatorname{det}\left(I_m+B A\right)=\operatorname{det}\left(I_m+A B\right)$. We may consider the identity $\operatorname{det}\left(\left(I_m+B A\right) B\right)=\operatorname{det}\left(B\left(I_m+A B\right)\right)$ as a polynomial identity in the domain $\mathbf{Z}\left[a_{i j}, b_{i j}\right]$, where we may cancel $\operatorname{det} B$ from both sides to obtain the result. We may then apply the result over any field via the universal property of polynomial rings, sending each indeterminate $a_{i j}$ to the field element $a_{i j} \in \mathbf{k}$. We may then extend the result to when $m<n$ by padding the rectangular matrices with zeroes to form square matrices. In detail, we get
\[
\left(\begin{array}{ll}
B & 0_{n \times(n-m)}
\end{array}\right)\binom{A}{0_{(n-m) \times n}}=B A
\]
and
\[
\binom{A}{0_{(n-m) \times n}}\left(\begin{array}{ll}
B & 0_{n \times(n-m)}
\end{array}\right)=\left(\begin{array}{cc}
A B & 0_{m \times(n-m)} \\
0_{(n-m) \times m} & 0_{(n-m) \times(n-m)}
\end{array}\right)
\]
and the result follows since
\[
\operatorname{det}\left(\begin{array}{cc}
I_m+A B & 0 \\
0 & I_{n-m}
\end{array}\right)=\operatorname{det}\left(I_m+A B\right) \operatorname{det}\left(I_{n-m}\right)
\]
which can be seen by using the Leibniz permutation expansion of the determinant. Finally, for $z \neq 1$, we employ a scaling argument. The case for $z=0$ is left as an exercise; consider $z \neq 0$. We set $A^{\prime}:=z^{-1} A$, and compute
\begin{aligned}
\operatorname{det}\left(z I_n+B A\right) & =\operatorname{det}\left(z I_n+z B A^{\prime}\right) \\
& =z^n \operatorname{det}\left(I_n+B A^{\prime}\right) \\
& =z^n \operatorname{det}\left(I_m+A^{\prime} B\right) \\
& =z^{n-m} \operatorname{det}\left(z I_m+z A^{\prime} B\right) \\
& =z^{n-m} \operatorname{det}\left(z I_m+A B\right) .
\end{aligned}
The Cauchy-Binet formula is now within our reach. Comparing the coefficients of $z^{n-m}$ in $\operatorname{det}\left(z I_n+B A\right)=z^{n-m} \operatorname{det}\left(z I_m+A B\right)$, we find that the sum of principal $m \times m$ minors of $B A$ is equal to $\operatorname{det}(A B)$; that is,
\[
\operatorname{det}(A B)=\sum_{S \in\binom{[n]}{m}} \operatorname{det}\left((B A)_{S \times S}\right)
\]
If $S=\left\{s_1, \ldots, s_m\right\}$, then
\[
\begin{aligned}
\left((B A)_{S \times S}\right)_{i j} & =(B A)_{s_i, s_j} \\
& =\sum_{1 \leq k \leq m} B_{s_i, k} A_{k, s_j} \\
& =\sum_{1 \leq k \leq m}\left(B_{S \times[m]}\right)_{i, k}\left(A_{[m] \times S}\right)_{k, j} \\
& =\left(B_{S \times[m]} A_{[m] \times S}\right)_{i j}
\end{aligned}
\]
proving the result.

		自动登录	找回密码
密码			快速注册

Cauchy–Binet formula

两个证明