Binet-Cauchy

0x00前置

Laplace expansion

将常见的行列式行展开拓展一下，同时展开多行的Laplace展开为：

$ \left|A\right| = \sum_{1\leq j_1\leq j_2\leq \ldots \leq j_k\leq n} A \left( \begin{matrix} i_1 & i_2 & \ldots & i_k\ j_1 & j_2 & \ldots & j_k \end{matrix} \right) \cdot (-1)^{\sum_{t=1}^k i_t+\sum_{t=1}^k j_t}\cdot \left[ \begin{matrix} i_1 & i_2 & \ldots & i_k\ j_1 & j_2 & \ldots & j_k \end{matrix} \right] $

其含义为，取定第$1\leq i_1\leq \ldots \leq i_k\leq n$行，$\det A$ 等于这 $k$ 行形成的所有 $k$ 阶子式与它自己的代数余子式的乘积之和.

其中, $A\left( \begin{matrix} i_1 & i_2 & \ldots & i_k\\ j_1 & j_2 & \ldots & j_k \end{matrix} \right)$表示$A$矩阵保留第$i_1\ldots i_k$行，第$j_1\ldots j_k$列的子式

$A\left[ \begin{matrix} i_1 & i_2 & \ldots & i_k\\ j_1 & j_2 & \ldots & j_k \end{matrix} \right]$表示$A$矩阵去除第$i_1\ldots i_k$行，第$j_1\ldots j_k$列的子式

证明略了，可以上网自学/感性理解一下

0x01描述

$ \left|AB\right| = \sum_{1\leq v_1\leq v_2\leq \ldots \leq v_s\leq n} A\left( \begin{array}{} 1 & 2 & \ldots & s\ v_1 & v_2 & \ldots & v_s \end{array} \right)\cdot B\left( \begin{array}{} v_1 & v_2 & \ldots & v_s\ 1 & 2 & \ldots & s \end{array} \right) $

0x02证明

1. 代数证明

构造一个行列式:$ \left|\begin{matrix} A & 0\ I_n & B\ \end{matrix}\right| $,对其进行初等行变换：

\[ \left| \begin{matrix} A & 0\\ I_n & B \end{matrix} \right| = \]

\[ \left|\begin{matrix} 0 & -AB\\ I_n & B \end{matrix}\right| = \]

\[ (-1)^{ns} \left|\begin{array}{} -AB & 0\\ B & I_n \end{array}\right| = \]

\[ (-1)^{ns} \left|\begin{array}{} -AB \end{array}\right|\left|\begin{array}{} I_n \end{array}\right| = \]

\[ (-1)^{ns} \left|\begin{array}{} AB \end{array}\right| (-1)^s = \]

\[ \left|\begin{array}{} AB \end{array}\right| (-1)^{s+ns} \]

得到$\left| AB \right|$相关的形式

接下来计算行列式的值：

\[ \left|\begin{array}{} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots & 0 \\ a_{s1} & a_{s2} & \cdots & a_{sn} \\ 0 & 0 & \cdots & 0\\ 1 & 0 & \cdots & 0\\ 0 & 1 & \cdots & 0\\ \vdots & \vdots& \ddots& \vdots& B\\ 0 & 0 & \cdots & 1\\ \end{array}\right| \]

固定了矩阵的前$s$行，从前$n$列中选取任意$s$列($v_1\cdots v_s$)，进行Laplace展开：

$$ =\sum_{1\leq v_1\leq\cdots\leq v_s\leq n} A\left( \begin{array}{l} 1 & 2 & \cdots & s \\ v_1 & v_2 & \cdots & v_s \end{array}\right) \cdot(-1)^{\sum_s+\sum_{v_s}}\cdot \left|\begin{array}{l} 0 & 0 & \cdots & 0 \\ 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots& \ddots& \vdots& B \\ 0 & 0 & \cdots & 1 \end{array}\right| $$ 即可得到我们想要的前半部分.

有注意到剩余行列式中的$1$只存在于与$v_1\cdots v_s$互补的$u_1\cdots u_{n-s}$列中，则固定前$n-s$列，选取指定的第$u_1\cdots u_{n-s}$行继续展开。

而$B$中剩下的行与第$u_1\cdots u_{n-s}$行互补，所以剩下的就是第$v_1\cdots v_s$行。

\[ \sum_{1 \leq v_1 \leq \cdots \leq v_s \leq n}^{}A\left(\begin{array}{} 1 & 2 & \ldots & s\\ v_1 & v_2 & \ldots & v_s \end{array}\right) \cdot (-1)^{\sum_s+\sum_{v_s} } \cdot \left|I_{n-s}\right|\cdot (-1)^{\sum_{n-s}+\sum_{u_{n-s}}}\cdot B\left( \begin{array}{} v_1 & v_2 & \ldots & v_s\\ 1 & 2 & \ldots & s\\ \end{array} \right) \]

整理一下就有

\[ =\sum_{1\leq v_1\leq\cdots\leq v_s\leq n} A\left( \begin{array}{} 1 & 2 & \ldots & s\\ v_1 & v_2 & \ldots & v_s \end{array} \right)\cdot(-1)^{\sum_s+\sum_{v_s}+\sum_{n-s}+\sum_{u_{n-s}}}\cdot B\left( \begin{array}{} v_1 & v_2 & \ldots & v_s\\ 1 & 2 & \ldots & s\\ \end{array}\right) \]

因为$v_s$与$u_{n-s}$互补，所以他们的和就是$1+\cdots+n$

\[ \sum_s+\sum_{v_s}+\sum_{n-s}+\sum_{u_{n-s}}\\=(1+\cdots+s)+(1+\cdots+n-s)+(1+\cdots+n) \\=s^2+n^2+n-sn \]

现在有

\[ \left|\begin{array}{} AB \end{array}\right| (-1)^{s+ns}\\=\sum_{1\leq v_1\leq\cdots\leq v_s\leq n} A\left( \begin{array}{} 1 & 2 & \ldots & s\\ v_1 & v_2 & \ldots & v_s \end{array} \right)\cdot(-1)^{s^2+n^2+n-sn}\cdot B\left( \begin{array}{} v_1 & v_2 & \ldots & v_s\\ 1 & 2 & \ldots & s\\ \end{array} \right) \]

吧$-1$挪到右边，为$(-1)^{s(s+1)+n(n+1)}$,看到$s(s+1)+n(n+1)$是偶数，则这一项为$1$

最终有:

$$ \left|\begin{array}{} AB \end{array}\right| =\sum_{1\leq v_1\leq\cdots\leq v_s\leq n} A\left( \begin{array}{} 1 & 2 & \ldots & s\ v_1 & v_2 & \ldots & v_s \end{array} \right)\cdot B\left( \begin{array}{} v_1 & v_2 & \ldots & v_s\ 1 & 2 & \ldots & s\ \end{array} \right) $$ 证毕.