Cauchy–Binet formula

hbghlyj

柯西-比内公式（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)

2022-3-3 06:29 上传

点击文件名下载附件

Czhang271828

回复 1# hbghlyj

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

isee

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

hbghlyj

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

isee

回复 4# hbghlyj

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

hbghlyj

讲义《行列式入门》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

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

hbghlyj

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.