线性代数与图论小记

yyyyxh / 2023-05-04 / 原文

因为一些契机翻了翻潘家奇的论文，觉得很有意思……开始不务正业。

行列式定义

\[|A|=\sum_p (-1)^{\text{inv}(p)} \prod_{i=1}^n a_{i,p_i} \]

很基本也很重要，感性理解就是通过类似容斥的方式计算了一个 \(n\) 维体的体积或者说缩放率？

如果 \(A\) 中有若干条行向量/列向量线性相关体积自然是 \(0\)。或者说可以用下面的交换性和倍加性消元。

行列式几个简单性质

可以在网上搜证明。

可乘性：

可倍加性：一行加上另一行的若干倍值不变。

行/列交换性：交换两行/两列值取反。

可转置性：转置后值不变。

可加性：

\[\begin{vmatrix} a_{1,1}+b_{1,1} & \cdots & a_{1,n}+b_{1,n}\\ a_{2,1} & \cdots & a_{2,n} \\ \vdots & \ddots & \vdots \\ a_{n,1} & \cdots & a_{n,n} \\ \end{vmatrix} = \begin{vmatrix} a_{1,1} & \cdots & a_{1,n}\\ a_{2,1} & \cdots & a_{2,n} \\ \vdots & \ddots & \vdots \\ a_{n,1} & \cdots & a_{n,n} \\ \end{vmatrix} + \begin{vmatrix} b_{1,1} & \cdots & b_{1,n}\\ a_{2,1} & \cdots & a_{2,n} \\ \vdots & \ddots & \vdots \\ a_{n,1} & \cdots & a_{n,n} \\ \end{vmatrix} \]

对任意一行都有类似的展开方式。

拉普拉斯展开：对于第 \(i\) 行，先按可加性拆开拆成该行只有一个元素有值的 \(n\) 个行列式之和。将这个元素 \(a_{i,j}\) 通过行/列交换性挪到左上角，此时符号变了 \((-1)^{i+j}\)。那么由于该行其它元素都是 \(0\)，所以行列是定义中 \(p_1\) 只能取 \(1\)，剩下的就是一个 \(n-1\) 阶矩阵的行列式，即：

\[|A|=\sum_{j=1}^n a_{i,j} (-1)^{i+j} A_{i,j} \]

\(A_{i,j}\) 被称为 \(i,j\) 处的余子式，方阵被去掉了第 \(i\) 行第 \(j\) 列的行列式。

\(\text{LGV}\) 引理

给定有向图 \(G\)，每条边有权值 \(e_{u,v}\)，定义一条路径 \(P:u\to v\) 的权值 \(\omega(P)\) 为其经过的所有边的权值之积，定义两个点间的权值 \(\omega(u,v)=\sum_{P:u\to v} \omega(P)\)。

大多数情况下边的权值都可以理解成边的重数，\(\omega\) 可以直接理解为路径的方案数。然而 \(\text{LGV}\) 引理和下面的矩阵树定理在交换环上成立，所以我们可以把边权换成诸如多项式之类的奇怪东西。（省选联考考过这个套路）

定义大小为 \(n\) 起点集合和终点集合间的路径组 \(P'=(P_1,P_2,\cdots,P_n)\) 为存在一个排列 \(\sigma\) 满足 \(P_i:S_i\to T_{\sigma(i)}\)，由这个路径组确定的 \(\sigma\) 我们记为 \(\sigma(P')\)。路径组的权值 \(\omega(P')=\prod_{i=1}^n \omega(P_i)\)。若 \(P'\) 中有两条路径有公共点那么称 \(P'\) 为相交路径组。

\(\text{LGV}\) 引理讲的是：

\[\sum_{P' \text{是不相交路径组}} (-1)^{\text{inv}(\sigma(P'))} \omega(P')= \begin{vmatrix} \omega(S_1,T_1) & \omega(S_1,T_2) & \cdots & \omega(S_1,T_n) \\ \omega(S_2,T_1) & \omega(S_2,T_2) & \cdots & \omega(S_2,T_n) \\ \vdots & \vdots & \ddots & \vdots \\ \omega(S_n,T_1) & \omega(S_n,T_2) & \cdots & \omega(S_n,T_n) \end{vmatrix} \]

简要证明：

\[\begin{vmatrix} \omega(S_1,T_1) & \omega(S_1,T_2) & \cdots & \omega(S_1,T_n) \\ \omega(S_2,T_1) & \omega(S_2,T_2) & \cdots & \omega(S_2,T_n) \\ \vdots & \vdots & \ddots & \vdots \\ \omega(S_n,T_1) & \omega(S_n,T_2) & \cdots & \omega(S_n,T_n) \end{vmatrix} =\sum_p (-1)^{\text{inv}(p)} \prod_{i=1}^n \omega_{S_i,T_{p_i}}=\sum_{P' \text{是不相交路径组}} (-1)^{\text{inv}(\sigma(P'))} \omega(P')+\sum_{P' \text{是相交路径组}} (-1)^{\text{inv}(\sigma(P'))} \omega(P') \]

对于相交路径组，我们考虑构造变换 \(f(x)\)，我们取出 \(P'\) 中字典序最小的两条相交路径有序路径对 \((P_i,P_j)\)，找到字典序最小的点对 \((x,y)\) 满足 \(P_i\) 的第 \(x\) 个顶点与 \(P_j\) 第 \(y\) 个顶点相同。

我们交换 \(P_i\) 在 \(x\) 后面和 \(P_j\) 在 \(y\) 后面的路径，此时两个终点互换，\(\text{inv}(\sigma(P'))\) 取反。而由于字典序最小元的唯一性，我们发现 \(f(f(P'))=P'\)。那么相交排列成对出现，一个奇排列一个偶排列正好抵消。引理得证。

\(\text{Binet-Cauchy}\) 定理

更有趣的东西来了！由于行列式代表体积/缩放率，复合两个线性映射那么缩放率相乘，有对于同阶方阵 \(|AB|=|A||B|\)，我们考虑扩展这个结论。

对于一个 \(n\times m\) 的矩阵 \(A\) 和一个 \(m\times n\) 的矩阵 \(B\)，有：

\[|AB|= \begin{cases} 0 & n>m \\ |A||B| & n=m\\ \sum_{S\subset \{1,2,\cdots,m\}} |A_{\{1,2,\cdots,n\},S}| |B_{S,\{1,2,\cdots,n\}}| & n<m \end{cases} \]

其中 \(A_{S,T}\) 是 \(A\) 矩阵选出 \(S\) 中的行与 \(T\) 中的列构成的矩阵。

第一个 case 是映射 \(A\) 将一个 \(n\) 维向量压缩到 \(m\) 维，一定会丢失 \(n\) 维中的信息，于是再用 \(B\) 映射回 \(n\) 维时伸缩率为 \(0\)。

第二个 case 是一个特殊情况，我们考虑直接验证 \(m\geq n\) 的情况。

方法一

常规证法。

我们构造两个分块矩阵的行列式 \(M=\begin{vmatrix} A&O\\ -I&B \end{vmatrix}\) 和 \(N=\begin{vmatrix} O&AB\\ -I&B \end{vmatrix}\)。\(O\) 是零矩阵，\(I\) 是单位矩阵。

有 \(M=N\)，因为对于 \(a_{i,j}\) 我们拎出 \(-I\) 的第 \(j\) 行将它乘上 \(a_{i,j}\) 倍加到 \(A\) 的第 \(i\) 行，此时第 \(i\) 行的第 \(k\) 列就被加了 \(a_{i,j}b_{j,k}\) 次，正好是矩阵乘法的定义。

接下来多次使用行列式的定义。由于 \(AB\) 有 \(n\) 行 \(n\) 列，而 \(N_{i,p_i}\) 不能取到 \(0\)，所以 \(p_{m+1}\cdots p_{m+n}\) 只能取 \([m+1,m+n]\)，也就是 \(|AB|\)。由于 \(p\) 是排列，\(p_1\cdots p_m\) 只能取 \([1,m]\)，也就是 \((-1)^m\)。考虑两个分块阵间新形成的逆序对数，由于 \(AB\) 严格位于 \(-I\) 右边所以每一个新产生的对都是逆序对，方案数为 \((-1)^{nm}\)。所以 \(N=(-1)^{mn+m}|AB|\)。

之后“算两次”。对于 \(M\) 显然 \(-I\) 只能取主对角线上的值否则贡献为 \(0\)。我们假设左下角矩阵选取了集合 \(T\)，需要留出 \(n\) 个空位给 \(A,B\) 选所以 \(|T|=m-n\)，贡献为 \((-1)^{|T|}=(-1)^{m-n}\)，对于 \(S=\{1,2,\cdots,m\}/T\)，再由于 \(p_i\) 为排列，那么上方的 \(A\) 选取了 \(S\) 中的列，右边的 \(B\) 选取了 \(S\) 中的行。所以此处贡献为 \(|A_{\{1,2,\cdots,n\},S}| |B_{S,\{1,2,\cdots,n\}}|\)。考虑新形成的逆序对，\(A,B\) 间显然都是顺序对，\(-I\) 中每选一个元素会对 \(A\) 产生 \(x\) 个逆序对，对 \(B\) 产生 \(n-x\) 个逆序对（画画图就知道了）。所以 \(M=\sum_{S\subset \{1,2,\cdots,m\}}(-1)^{(m-n)(n+1)}|A_{\{1,2,\cdots,n\},S}| |B_{S,\{1,2,\cdots,n\}}|\)。

对比两边，由于 \((-1)^{-n^2-n}\) 显然为 \(1\) 所以定理成立。

方法二

潘家奇论文中的证法，与本文图论的主题有关，更加简洁有趣！

构造一张三部图 \(G=(V_L\cup V_M\cup V_R,E_L\cup E_R)\)，其中 \(|V_L|=|V_R|=n,|V_M|=m\)。\(E_L=\{(u,v)|u\in V_L,v \in V_M\},E_R=\{(u,v)|u\in V_M,v \in V_R\}\)，\(E_L\) 边权为 \(A_{i,j}\)，\(E_R\) 边权 \(B_{i,j}\)。

根据 \(\text{LGV}\) 引理我们知道 \(AB\) 的行列式值就是路径上不相交路径组数交错和。

路径只可能在中部点相交，我们继续“算两次”，我们可以考虑枚举经过的中部点集，这样就能保证不交。

然后我们发现把这些中部点拎出来对左右两边算行列式乘起来就是答案了！比对一下算两次的结果，原定理得证！

矩阵树定理

对于一张带权无向图 \(G=(V,E)\)，设 \(|V|=n,|E|=m\)，权值 \(\omega(u,v)\) 的定义与 \(\text{LGV}\) 引理相同，定义拉普拉斯矩阵或者叫基尔霍夫矩阵为 \(n\) 阶方阵：

\[L_{i,j}= \begin{cases} -\omega(i,j) & i\neq j \\ \sum_{x=1}^n \omega(i,x) & i=j \end{cases} \]

定义这张无向图生成树的权值为边权之积，那么所有生成树的权值和就是 \(L\) 的某一个余子式 \(L_{t,t}\) 的值

我们考虑给每一条无向边随意定向成有向边，定义 \(n\) 行 \(m\) 列关联矩阵为：

\[B_{i,j}= \begin{cases} \sqrt {\omega(E_i)} & i\text{是}E_i\text{的起点}\\ -\sqrt {\omega(E_i)} & i\text{是}E_i\text{的终点}\\ 0 & \text{otherwise} \end{cases} \]

分类讨论一下，我们容易发现：\(L=BB^T\)。

定义 \(n-1\) 行 \(m\) 列的减关联矩阵为 \(B\) 去掉第 \(t\) 行的结果 \(B'\)。依然可以看到 \(L_{t,t}=|B'B'^T|\)。

我们选取一个大小为 \(n-1\) 的边集 \(S\)，称 \(B'_{[S]}\) 是 \(B'\) 选择 \(S\) 中的列的结果是 \(B'_S\)，\(B'^T_{[S]}\) 是 \(B'^T\) 选择 \(S\) 中的行的结果。

以下我们考虑计算 \(|B'_{[S]}|\) 的值：

对于边集 \(S\)，我们可以看到首先如果这个边集不是生成树那么至少会有一个简单环（即使不联通）。把环上边对应列我们拎到一起，我们考虑对这个简单环消元。沿着环的顺序将每个点用倍加性消去，最后会得到零向量。也就是说这些向量线性相关，\(B'_{[S]}\) 行列式自然为 \(0\)。注意这个过程如果遇到了 \(B\) 中被去掉的第 \(t\) 行我们就当这一行存在，不影响正确性。

接下来若这个边集是生成树我们同样考虑消元。我们从叶子开始消。叶子点 \(v\) 对应的行只有一个元 \(\pm \sqrt{\omega(S_i:u\to v)}\)，我们把它的父亲节点 \(u\) 也消成只有一个元。一直做知道每一行都只有一个元 \(\pm\sqrt{\omega(S_x)}\)，于是 \(|B'_{[S]}|=\pm \prod_{x\in S} \sqrt{\omega(S_x)}\)。

以上对于 \(B'^T_{[S]}\) 同理，将行列式转置即可，正负号是相同的！

接下来根据 \(\text{Binet-Cauchy}\) 定理，有 \(L_{t,t}=\sum_{S\subset \{1,2,\cdots m\},|S|=n-1} |B'_{[S]}||B'^T_{[S]}|\)。

于是只有当 \(S\) 构成生成树时有值，且 \(\pm\) 号被消去，值正好为边权乘积。矩阵树定理的无向图形式得证！