【算法】Matrix Tree 定理证明 ——hzy

原博客链接

老久没更了，冬令营也延期了（延期后岂不是志愿者得上学了？）

最近把之前欠了好久的债，诸如 FFT 和 Matrix-Tree 等的搞清楚了（啊我承认之前只会用，没有理解证明……），FFT 老多人写，而 MatrixTree 没人证我就写一下吧……

Matrix Tree 结论

Matrix Tree 的结论网上可多，大概一条主要的就是，图中生成树的数量等于 $V-E$ 的任一余子式，其中：

• $V$ 为对角阵，第 $i$ 个元素为点 $i$ 的度数
• $E$ 为对称阵，对角线为零且 $E_{i,j}$ 为点 $i$ 与点 $j$ 之间边的数量的相反数

这个结论众人皆知，但我好像没怎么搜到证明？

图的关联矩阵

为了求无向图中有多少组 $n-1$ 条边可以形成树，一般需要枚举所有的可能，无法在多项式内解决，但我们利用数学工具将其转换——引入关联矩阵

为了后面讨论我们给每条边随意分配一个方向。

图的邻接矩阵是一个 $n\times n$ 的用于存储图的矩阵。而关联矩阵 $A$ 则为 $n\times m$ 的矩阵，其中行对应点，列对应边，如果 $A_{i,j}$ 非零，则说明第 $j$ 条边的起点或终点为点 $i$（如 $i$ 为起点则为 $+1$，终点则为 $-1$，否则为 $0$）。如下图即为一张 $4$ 点 $5$ 边的图的关联矩阵：

$$
\begin{bmatrix}
+1&-1&+1&0&0\\
-1&0&0&+1&-1\\
0&+1&0&-1&0\\
0&0&-1&0&+1
\end{bmatrix}
$$

可以看到，如果只考虑这张图的结构的话，关联矩阵的行之间或列之间随意交换都是无所谓的（行交换代表点重新编号……）

---

我们可以证明一个结论，任意连通图的关联矩阵秩为 $n-1$。

有两种理解方式：

• 按行来看：
  • 首先去掉任意一行都是可以复原的：因为每一列都是一个 $+1$ 一个 $-1$，可以轻松由其他 $n-1$ 行得到这一行。故去掉任意一行不会丢失信息，秩 $\le n-1$；
  • 其次去掉任意两行都是无法复原的：因为任意去掉两行 $x,y$，在这张连通图上找到一条 $x$ 到 $y$ 的路径，取其中 $x\to y$ 方向第一条边 $a$、$y\to x$ 方向第一条边 $b$，则在还原关联矩阵时无法确定非零位置是 $(x,a)\&(y,b)$ 还是 $(x,b)\&(y,a)$。故去掉任意两行都会丢失信息，秩 $\ge n-1$
• 再按列来看更为显然：
  • 由于列对应边，故选取若干列，若这些列对应的边在图上组成了环，则一定线性相关（因为将环按一个方向捋一遍然后加起来一定为零）
  • 故要求 “最多的线性无关的列”，也即求 “在不出现环的前提下最多能找出多少边”，答案显然为 $n-1$

这下从行列两个方向证明了这个结论，但有何用处呢？

我们刚在从列的方向证明结论时用到了 “生成树” 的概念，仔细考虑一下，求 “图中有多少种 $n-1$ 条边的组合没有环”，等价于求 “关联矩阵中有多少种 $n-1$ 列的组合线性无关”

同时我们证明了 $n$ 个行中总有一个是多余的，故考虑删去其中一行对答案无影响。

这下将图中的问题转化为了矩阵中的问题，但是否将过程复杂化了呢？

Binet-Cauchy 公式

为了解决这个问题，我们需要引入 Binet-Cauchy 公式：

若存在 $n\times m$ 的矩阵 $A$ 与 $m\times n$ 的矩阵 $B$，则矩阵 $AB$ 的行列式等于：从 $m$ 中任意选取 $n-1$ 个指标，并取出 $A$ 的这 $n$ 列得到 $A’$，和 $B$ 的这 $n$ 行的得到 $B’$，将它们行列式乘起来得到 $\det A’\times \det B’$，对所有共 $C_m^n$ 种选取情况求和。

数学表达：
$$
\det (AB)=\sum_{S\subseteq U,|S|=n}\det(A_S)\det(B_S)
$$
（其中 $U$ 表示集合 ${1,2,\dots,m}$，$A_S$ 表示取出 $S$ 中下标的列组成的矩阵，$B_S$ 表示取出 $S$ 中下标的行组成的矩阵）

可以发现其中几种特殊情况：

• $n=1$：此时公式等价于计算两个 $m$ 维向量的点积
• $n=m$：此时公式等价于表示 $\det(AB)=\det(A)\det(B)$ 的行列式可乘性质
• $n>m$：此时公式中由于无法选出任何一组，故右边恒等于 $0$，其表达的其实是矩阵 $AB$ 不满秩

---

这个公式的证明过于繁琐，不予展开，但可以感性理解：$AB$ 是 $A$ 的以 $B$ 为系数的线性组合，将 $AB$ 的行列式展开后分离贡献，$\det (A_S)$ 的系数是 $\det(B_S)$

利用公式

为了解决这个问题引入这个公式，很明显是和其中的共同拥有的 “任意选取”、“线性无关” 两个因素有关。

很容易想到是想要将图的关联矩阵 $D$（去掉一行后）放入 $A$ 或 $B$ 的位置，但具体怎么放，另一个矩阵又是什么？

引理：连通图的关联矩阵中，任意一个子矩阵的行列式都为 $\pm 1$ 或 $0$

证明：

• 若子矩阵不可逆，则行列式自然为零
• 若子矩阵可逆，则不可能每一列都同时存在两个非零项（否则每一列都是一个 $+1$ 一个 $-1$，将所有行加起来一定是 $0$），故按只有一个非零项的列进行行列式展开，则可以归纳至低一阶的情况

有了这个引理，可以非常自然的考虑将 $A$ 设为 $D$，$B$ 设为 $D^T$，则 $A_S$ 和 $B_S$ 都是取 $D$ 的不同列向量组成的矩阵。

由于我们证明了，列线性无关的子矩阵行列式一定为 $\pm 1$，则平方后一定为 $1$。再利用上述公式，故原问题的的答案即为 $\det (AB)$ 。

至于 $AB$ 是啥？$AB=DD^T$

考虑下关联矩阵 $D$ 的定义，即可发现 $(AB)_{i,j}$：

当 $i=j$ 时：$(AB){i,i}$ 为 $D$ 第 $i$ 行与自己的点积，由于非零项都为 $\pm 1$，则 $(AB){i,i}$ 即为第 $i$ 行的非零项个数——即点 $i$ 的度数

当 $i\neq j$ 时：$(AB){i,j}$ 为 $D$ 第 $i$ 行与 $j$ 的点积，由于每一列都只有两个元素 (一个 $+1$ 一个 $-1$ )，故每个位置如果有值，则一定为 $-1$，$(AB){i,j}$ 即为它们求和——点 $i$ 与点 $j$ 之间边的数量的相反数

总结

回顾整个过程：

• 问题一开始是 “有多少种选取 $n-1$ 条边的方式，使选出的边构成树”

• 然后引入图的关联矩阵，证明了其秩为 $n-1$，同时也发现问题等价于 “有多少种在关联矩阵中选取 $n-1$ 列的方式，使选出的列线性无关”（同时发现删去关联矩阵任意一行对答案无影响）

• 针对 “任意选取” 和 “线性无关” 两个特点，引入了同样拥有这两个特点的 Binet-Cauchy 公式
  • 利用 Binet-Cauchy 任意选取的特点，和 “线性无关 $\iff$ 行列式非零” 的性质，希望将关联矩阵放入公式
• 为了将关联矩阵放入公式，证明了关联矩阵中任意一个子矩阵行列式为 $\pm 1$ 或 $0$
• 巧妙地将 $A$ 设为 $D$，$B$ 设为 $D^T$，则得到的结果 $\det(AB)$
  • 等价于：任取 $D$ 的 $n-1$ 列求出行列式，平方后求和。
  • 等价于：任取 $D$ 的 $n-1$ 列，行列式非零的方案数
• 考虑 $AB=DD^T$ 的现实意义，得到开头提到的 Matrix Tree 定理

有向生成树的扩展

刚才讨论的都是无向生成树，可以考虑到有向生成树的情况：
– 由于点可以重新标号，我们只考虑以 $1$ 号点为根的情况
– 由于内向生成树可以将边取反后求外向生成树，故只考虑外向生成树的情况

考虑外向生成树关联矩阵的特点：除了根以外每一行都只有一个 $-1$（树上只有一个父亲）

而若生成树不是外向生成树，则一定存在一个点 $x$，关联矩阵中 $x$ 对应的那一行没有 $-1$

所以可以考虑将原来每条边 “一个 $+1$ 一个 $-1$” 中的 $+1$ 置为零，则在计算时：
– 如果这棵生成树不是外向生成树，则一定存在一行全为零，其行列式也为零
– 如果这棵树是外向生成树，由于每一行有一个 $-1$，故其行列式为 $(-1)^{n-1}$ 也只可能为 $\pm 1$