矩阵树定理证明
_sys
·
·
个人记录
矩阵树定理（Matrix-Tree）
给定一个图 G, 定义其基尔霍夫矩阵 L=D−A，D 为该图的度数矩阵，A 为该图的邻接矩阵, 那么这张图的生成树个数即为 L 的任一代数余子式的值。
定义一个图 G 的关联矩阵 B 为一个 n \times m 的矩阵，对于边 (u_i, v_i)，B_{u_i, i}=1, B_{v_i, i}=-1，其余均为 0。
则有 L=BB^T。
引理（Binet-Cauchy）
设 C_{n \times n}=A_{n \times m}B_{m \times n}，则有：
\det C=\sum_{S \subset\{1, 2, \ldots, m\},|S|=n} \det A_S\det B_S
其中 A_S 表示选出 A 的所有在 S 中的列构成的方阵，B_S 表示选出 B 的所有在 S 中的行构成的方阵。
证明：
\det C=&\sum_p\text{sgn}(p)\prod_{i=1}^n C_{i, p_i} \\
=&\sum_p\text{sgn}(p)\prod_{i=1}^n \sum_{k=1}^n A_{i, k}B_{k, p_i} \\
=&\sum_p\text{sgn}(p)\sum_{T \in \{1, 2, \ldots, m\}^n}\prod_{i=1}^n A_{i, T_i}B_{T_i, p_i}
\end{aligned}
\hphantom{{}={}}&\sum_{S \subseteq\{1, 2, \ldots, m\} , |S|=n} \det A_S\det B_S \\
=&\sum_S\left(\sum_t \text{sgn}(t)\prod_{i=1}^n A_{i, S_{t_i}}\right)\left(\sum_q\text{sgn}(q)\prod_{i=1}^n B_{S_i, q_i}\right) \\
=&\sum_S\left(\sum_t \text{sgn}(t)\prod_{i=1}^n A_{i, S_i}\right)\left(\sum_q\text{sgn}(q)\prod_{i=1}^n B_{S_i, q_i}\right) \\
=&\sum_q \text{sgn}(q)\sum_{S \subseteq\{1, 2, \ldots, m\}, |S|=n}\prod_{i=1}^nA_{i, S_i}B_{S_i, q_i}
\end{aligned}
也就是说，我们只需要证明有标号可重集和不可重集的结果是一样的。即
\sum_p\text{sgn}(p)\sum_{T \in \{1, 2, \ldots, m\}^n}\prod_{i=1}^n A_{i, T_i}B_{T_i, p_i} = \sum_q \text{sgn}(q)\sum_{S \subseteq\{1, 2, \ldots, m\}, |S|=n}\prod_{i=1}^nA_{i, S_i}B_{S_i, q_i}
考虑 T_i=T_j，那我们令 T' 为 i, j 交换后的有标号可重集。
则 (-1)^{\sigma(T)}=-(-1)^{\sigma(T')}，后面相同。故消去。
那么考虑 (-1)^{\sigma(T)}=1 的与 =-1 的存在一一映射关系。
故所有可重的全部消去。 等式左右相等。
那么 \det M_i=\det B_i\det B_i^T=\sum_{|S|=n-1}\det B_{i,S}\det B_{i,S}^T
其中 M_i 表示 L 去掉第 i 行第 i 列的子矩阵，B_i 表示 B 去掉第 i 行的子矩阵。
而 \det B_{i, S} 表示选出的这 n-1 条边，是否连出环，是则 \det = 0，否则 |\det|=1，平方一下就是 1。
故 \det M_i 为生成树个数。