数学-Matrix Tree定理证明

老久没更了，冬令营也延期了（延期后岂不是志愿者得上学了？） 最近把之前欠了好久的债，诸如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\sube 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\ne 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$