矩阵树定理证明

· · 算法·理论

0 前言

矩阵树定理严谨彻底的证明常常对选手的 OI 学习造成困难。本文参考了 一篇有关矩阵树的题解 和 OI-wiki的证明，两种证明的思路和过程大相径庭。由于两篇文章都只描述了主要思路的证明，本文根据二者思路进行了严谨地证明并补全了相关引理的证明。其中本文的后一种证明方式更(?)适合 OI 选手食用。

1 约定

1.1 记号

1.2 图的矩阵

1.2.1

1.3 matrix-tree 定理

2. 常规证明

依照 OI-wiki 的证明思路，以更清晰和完整的过程证明。以下思路摘自 OI-wiki。

2.1 引理证明

2.1.1 Lemma 1

L^{out}(G)=(M^{out})^T(M^{out}-M^{in})

证明：

直接展开即可。

考虑每一条边，e_i=(u \to v)，有：

(M^{out})^T_{u,i}&=\sqrt{e} \\ (M^{out}-M^{in})_{i,u}&=\sqrt{e} \\ (M^{out}-M^{in})_{i,v}&=-\sqrt{e} \end{aligned}

将因式相乘，考虑验证 Laplace 中度数矩阵所在的对角线：

\begin{aligned} \sum_i(M^{out})^T_{u,i}(M^{out}-M^{in})_{i,u}&=\sum_{e_i=(u\to v)} w(e) \\ &=L^{out}_{u,u} \end{aligned}

同理，考虑验证邻接矩阵：

\begin{aligned} \sum_i(M^{out})^T_{u,i}(M^{out}-M^{in})_{i,v}&=\sum_{e_i=(u\to v)} -w(e) \\ &=L^{out}_{u,v} \end{aligned}

2.1.2 Lemma 2

对于图 G 我们选取一个边集 S 及其联结的点集 W,

  • 那么子图 (W,S) 不构成一棵根向树，当且仅当: \det (M^{out}[S,W]) \det(M^{out}[S,W]-M^{in}[S,W])=0
  • 如果构成一棵根向树，当且仅当： \det (M^{out}[S,W]) \det(M^{out}[S,W]-M^{in}[S,W])= \prod w(e)

证明：

转化
根据定义，M^{out}，M^{in} 每行有且仅有一个非零值 \sqrt{w(e)}，考虑行列式的计算方式，我们将每行提出一个 \sqrt{w(e)}。此时新矩阵的每行有且仅有一个非零值 1，我们接下来的所有讨论都将针对新矩阵，此时 Lemma2 的第二种情况转化为

\det (M^{out}[S,W]) \det(M^{out}[S,W]-M^{in}[S,W])= 1

出于方便，我们钦定左式的第一个因式为 \det M，第二个因式为 \det M'。

case 1
考虑证明 Lemma2 的第一个情况。考虑证明其否命题， \det M \det M' 不为 0 等价于 M 和 M' 均满秩，亦即矩阵的行向量线性不相关：

case 2
考虑证明第二个情况，即求出生成树情况下，\det M \det M'的值。考虑高斯消元进行行列式求值的过程，我们希望通过等价变换，使矩阵的左下三角形变为全零。此时矩阵的行列式即为 (-1)^{cnt}\prod A_{i,i}，其中 cnt 为交换行时引起的行列式取反。

考虑如何对 M 和 M' 分别构造出这样的变换：

综上 \det M \det M'=(\det M)^2=1，Lamma2 完结。

2.2 Cauchy-Binet 定理

\det(AB)=\sum_S{\det A[[n],S]} \det B[S,[n]]

接下来将从转化，建模，讨论右式，讨论左式四步证明 Cauchy-Binet 定理：

2.2.1 证明 step1

考虑 \det 可以转化为什么模型。

对于一个 n\times n 的矩阵 A，我们建一张二分图 G(L,R,E)，其中 |L|, |R| 是大小为 n 的点集。 对于两侧任意一个点对 (L_i,R_j)，在 E 中有边且边权为 A_{ij}。

因为

\det A= \sum\limits_{\sigma} (-1)^{\tau(\sigma)}\prod A_{i,\sigma_i}

约定 ： \sigma 表示一个排列（置换），\tau 描述该排列的奇偶性，即逆序对个数。

观察可以发现，每枚举一个 \sigma 就是枚举二分图上的一个完全匹配。又因为 A_{i,\sigma_i} 就是 (L_i,R_{\sigma_i}) 的边权，所以每个 \sigma 的贡献为边权的乘积乘以一个系数。考虑分析系数是什么。

容易发现 \tau 统计的是 i<j 且 \sigma_i> \sigma_j 的对数，如果将二分图按编号放在平面上，那么其等价于满足 (i,\sigma_i) 与 (j,\sigma_j) 相交的点对 (i,j) 的数量。

我们不妨称 \sigma 对应的匹配为一个路径组，称其奇偶性为路径组产生的交点的奇偶性。那么排列的奇偶性等于其对应的路径组的奇偶性。

我们希望把奇偶性拆分到每一条路径上，我们定义某一 \sigma 中的路径 (i,\sigma_i) 的奇偶性为其与路径组交点数量的奇偶性 sgn_i。
因为

(-1)^{\tau(\sigma)}=(-1)^{\sum sgn_i}=\prod(-1)^{sgn_i}

那么有

\det A=\sum_{\sigma}\prod_{i}(-1)^{sgn_i}A_{i,\sigma_i}

通过这种方式我们将贡献拆到了每一种路径组中的每一条边上。

2.2.2 证明 step2

考虑对定理建模，我们可以构建有三列点的图，仅在一二列之间和二三列之间存在边。 第一列和第三列有 n 个点， 第二列有 m 个点，我们将 A 对应的二分图复制到一二列构成的子图中，将 B 对应的二分图复制到二三列构成的子图中。

我们考虑将左边式子中的贡献拆到每一条路径，再将每条路径一分为 2，左侧由 A' 的路径贡献，右侧则有 B'，两条路径首尾相连。

2.2.3 证明 step3

将右式用分配律展开：

&=\sum_S\sum_{\sigma_{A'}}\sum_{\sigma_B'}(\prod^n)(\prod^n) \end{aligned}

为了方便,我们将 \sigma_{A'} 记作 \sigma，\sigma_{B'} 记作 \xi。
当我们确定 S，\sigma ，\xi 时，我们考察这 2n 条路径贡献的连乘。根据 2.1.2 的思路，我们考虑将 (i,\sigma_i) 和 (\sigma_i,\xi_{\sigma_i}) 用结合律进行组合。

(\prod^n(-1)^{sgn(i,\sigma)} A'_{i,\sigma_i})(\prod^n(-1)^{sgn(i,\xi)} B'_{i,\xi_i}) \\ =\prod^n((-1)^{sgn(i,\sigma)+sgn(\sigma_i,\xi)})(A'_{i,\sigma_i}B'_{\sigma_i,\xi_{\sigma_i}})

考察每一个组合的图论意义。我们将两条路径拼接为一条，我们将位于 A' 子图的路径称为 l, 位于 B' 子图的路径称为 r, 路径 i \to \xi_{\sigma_i} 称为 e。

我们先考虑系数是否正确。考察 \sigma 和 \xi 构成的路径组(即 \xi_\sigma )与 e 的交点数量:

我们将不同情况代入系数，容易证明：

sgn(i,\sigma)+sgn(\sigma_i,\xi)\equiv sgn(i,\xi_\sigma) \pmod 2

带回原式,注意到可以以 (i,\xi_{\sigma_i}) 重构计算顺序，并且 S 的取值不影响交点。

\mathrm{RHS}&=\sum_S\sum_{\sigma}\sum_{\xi}\prod^n((-1)^{sgn(i,\xi_\sigma)})(A'_{i,\sigma_i}B'_{\sigma_i,\xi_{\sigma_i}}) \\ &=\sum_{S}\sum_{\xi_\sigma}\sum_{\sigma}(\prod_i(-1)^{sgn(i,\xi_\sigma)})(\prod_iA'_{i,\sigma_i}B'_{\sigma_i,\xi_{\sigma_i}}) \\ &=\sum_{\xi_\sigma}(\prod_i(-1)^{sgn(i,\xi_\sigma)})(\sum_S\sum_{\sigma}\prod_iA'_{i,\sigma_i}B'_{\sigma_i,\xi_{\sigma_i}})\\ \end{aligned}

注意到 \sum_S\sum_{\sigma} 代表先选 n 个数再打乱。令 T 为 在 [m] 中选 n 个数组成的排列，同时我们用 \sigma 代表 \xi_\sigma (注意此后的 \sigma 均不代表 \sigma_{A'})。那么有：

\mathrm{RHS}&=\sum_{\xi_\sigma}(\prod_i(-1)^{sgn(i,\xi_\sigma)})(\sum_T\prod_i A_{i,T_i}B_{T_i,\xi_{\sigma_i}}) \\ &=\sum_T\sum_{\sigma}(-1)^{\tau(\sigma)}\prod_iA_{i,T_i}B_{T_i,\sigma_i} \end{aligned}

2.2.4 证明 step4

考虑化简左式子，并将其与右式形成同构，通过对应关系证明：

\mathrm{LHS}=\sum_{\sigma}(-1)^{\tau(\sigma)}\prod_{i}\sum_j^m A_{i,j}B_{j,\sigma_i}

注意到如果将 \sum_j^m 展开，相当于在每个因式中挑一个 j。令 P 为在 [m] 中取 n 个数（可以重复取）组成的序列，那么有

\mathrm{LHS}&=\sum_{\sigma}(-1)^{\tau(\sigma)}(\sum_P\prod_i^n A_{i,P_i}B_{P_i,\sigma_i}) \\ &=\sum_P\sum_{\sigma}(-1)^{\tau(\sigma)} \prod _i^nA_{i,P_i}B_{P_i,\sigma_i} \end{aligned}

令 H 为在 [m] 中取 n 个数（必须存在重复）组成的序列，左式子减右式子：

\mathrm{D}=\mathrm{LHS}-\mathrm{RHS}=\sum_H\sum_{\sigma}(-1)^{\tau(\sigma)}\prod_i A_{i,H_i}B_{H_i,\sigma_i}

考察 \mathrm{D} 式的几何含义，当我们确定一个 H 时，不妨令 H 中其中一对相等的位置为 x 和 y，不妨钦定 z=H_x=H_y。

对于每一个确定的 \sigma, 在 2.1.2 的三层图中，均存在这样的路径：

对于每一个 \sigma 我们均可以构造一个路径组 \sigma'，使 \sigma_x=\sigma'_y 且 \sigma_y=\sigma'_x ，同时满足其他位置相同。此时两个路径组仅存在两条路径不一样，对于 \sigma' :

注意到我们相当于交换了 \sigma 的两个位置，这会使其奇偶性恰好改变 1，同时 (\prod A_{i,H_i})(\prod B_{H_i,\sigma_i}) 不变

由此对于每一个 H 的每一个 \sigma 均存在位于同一个 H 下的 \sigma' 满足：

(-1)^{\tau(\sigma)}\prod_i A_{i,P_i}B_{P_i,\sigma_i}+(-1)^{\tau(\sigma’)}\prod_i A_{i,P_i}B_{P_i,\sigma'_i}=0

即 \sigma 和 \sigma' 的贡献互为相反数，所以 \mathrm{D} 为 0 。即:

\mathrm{LHS}=\mathrm{RHS}

2.3 matrix-tree

根据思路我们需要计算有向图根向树的数量，其数量等于：

\det L^\mathrm{out}(G)[[n] \setminus k,[n] \setminus k]

为了方便书写，我们令 [n] \setminus k=\setminus k
推式子：

\det L^{out}[\setminus k,\setminus k] &=\det(M^{out}[[m],\setminus k](M^{out}[[m],\setminus k]-M^{in}[[m]\setminus k])) \\ &=\sum_{S\subset[m],|S|=n-1}\det(M^{out}[S,\setminus k]) \det(M^{out}[S,\setminus k]-M^{in}[S,\setminus k]) \\ &=\sum_{S\subset[m],|S|=n-1} [S是否为生成树的边集] \end{aligned}

完结撒花

3 更简短清晰显然的证明

3.0 约定

3.2 Lemma

置换环有如下性质：

  1. 排列图中的联通块仅由孤立的单点和置换环构成；
  2. 排列，排列图，置换环三者任意两者一一对应；
  3. 置换环是简单多元环；

性质 1，2，3 显然，下面证明性质 4：

3.3 matrix-tree

注意边权的含义，即 (u,v) 之间的连边方案，亦即 (u,v) 之间的边数。

我们需要证明的是 生成树计数 与 \det式 相等。

考虑我们需要证明的用来计数的式子反应了什么
为了方便我们用 L 代指 L^{out}[\setminus k,\setminus k]：

\det L &= \sum_{\sigma}(-1)^{\tau(\sigma)}\prod^{n-1} L_{i,\sigma i} \\ &= \sum_{\sigma}((-1)^{\tau(\sigma)}(\prod_{i,i=\sigma_i}D_{i,i}\prod_{i,i \ne \sigma_i} -A_{i,\sigma_i}))\\ &=\sum_{\sigma}((-1)^{\tau(\sigma)+\sum_i^{n-1}[i \ne \sigma_i]} \prod_{i,i=\sigma_i} D_{i,i}\prod_{i,i \ne \sigma_i} A_{i,\sigma_i} \end{aligned}

3.3.1 \det 式的贡献式

考虑 \prod_{i=\sigma_i} D_{i,i}\prod_{i \ne \sigma_i} A_{i,\sigma_i} 的图论组合意义。

据此，对于每一个 \sigma，不考虑其 \pm1 的系数时，贡献为各个点的贡献乘积。具体地代表这样的意义：

描述1：给你一张图，求子图的方案数，满足所有点出度为 1 且子图中包含所有给定的特定环。（环内的连接顺序给定，子图不一定需要联通）。

容易发现，第二类点产生的就是排列图中的置换环，同时第一类点选边时可能会产生新的环。如果我们令集合函数 g(T) 表示：

描述2：给你一张图，求子图的方案数，满足所有点出度为 1 且子图中包含且仅包含所有给定的特定环。（环内的连接顺序给定，子图不一定需要联通）。

令集合 U 表示原图中所有环的集合，注意到：

以上几种情形的存在与否不影响贡献的计算，所以我们只讨论 T \subset U 且 p(\sigma) \subset U 的合法情形。分析描述 1 和描述 2 容易发现：

\prod_{i=\sigma_i} D_{i,i}\prod_{i \ne \sigma_i} A_{i,\sigma_i}=\sum_{p(\sigma)\subset T\subset U} g(T)

3.3.2 生成树计数

注意到 3.3.1 结尾的式子是超集容斥的形式，又因为 p 与 \sigma 一一对应，所以有：

g(T)=\sum_{\sigma，T\subset p(\sigma) \subset U} (-1)^{|p(\sigma)|-|T|}\prod_{i=\sigma_i} D_{i,i}\prod_{i \ne \sigma_i} A_{i,\sigma_i}

容易证明:

所以生成树计数等于所有点出度为 1 时无环的子图方案数，即为 g(\varnothing)。

将原证明的化简：

\iff& g(\varnothing) &=\det L \\ \iff& \sum_{\sigma} (-1)^{|p(\sigma)|}\prod_{i=\sigma_i} D_{i,i}\prod_{i \ne \sigma_i} A_{i,\sigma_i}&=\sum_{\sigma}((-1)^{\tau(\sigma)+\sum_i^{n-1}[i \ne \sigma_i]} \prod_{i,i=\sigma_i} D_{i,i}\prod_{i,i \ne \sigma_i} A_{i,\sigma_i} \\ \iff& |p(\sigma)|&\equiv \tau(\sigma)+\sum_i^{n-1}[i \ne \sigma_i] \pmod 2 \end{array}

3.3.3 \det 式的系数式

由 Lemma 对逆序对的分析，我们不妨令:

根据 Lemma 的结论：

发现，系数式第二项 \sum_i^{n-1}[i \ne \sigma_i] 就是统计处于环上的点数。将上述式子代入。

\tau(\sigma)+\sum_i^{n-1}[i \ne \sigma_i] &\equiv n'-k+(n'-(k-|p(\sigma)|)) \pmod 2 \\ &= (n'-k)\times 2 + |p(\sigma)| \\ &\equiv |p(\sigma)| \pmod 2 \end{aligned}

于是我们证明 3.3.2 结尾的式子，完结撒花。