Matrix - Tree 定理学习笔记

· · 个人记录

矩阵树定理学习笔记

我是复制粘贴机器

本文在很大程度上抄袭参考了《矩阵树定理及其无向图形式证明》 - 仙人长。

0. 定义与约定

本文中所有的图均指有重边无自环的图。

定义一个排列 \pi 的奇偶性为其逆序对个数的奇偶性。

性质 0.1：交换排列的两个元素，排列奇偶性改变。

证：交换 i, j(i < j) 可以看作是把 \pi_j 连续 j - i 次与其左边的数交换，再把 \pi_i 连续 j - i - 1 次与其右边的数交换。而一次交换显然改变排列奇偶性。即证。

性质 0.2：n > 1 时，长度为 n 的奇偶排列数量相等。

证：归纳法。枚举 n 插入在哪一个位置，则新排列比原排列多的逆序对数量为 n - 1, n - 2, \cdots, 0，由归纳结论显然。

对于一个排列 \pi，记其逆序对数量为 \lambda(\pi)。

定义向量 \alpha_1(a_{1, 1}, a_{1, 2}, \cdots, a_{1, n}), \alpha_2(a_{2, 1}, a_{2, 2}, \cdots, a_{2, n}), \cdots, \alpha_n(a_{n, 1}, a_{n, 2}, \cdots, a_{n, n}) 线性相关，当且仅当存在不全为零实数 k_1, k_2, \cdots, k_n，使得

\sum\limits_{i = 1} ^ n k_i\alpha_i = O

1. 行列式

1.1 定义及基本性质

对于方阵 A

\begin{vmatrix} a_{1, 1} & a_{1, 2} & \cdots & a_{1, n} \\ a_{2, 1} & a_{2, 2} & \cdots & a_{2, n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n, 1} & a_{n, 2} & \cdots & a_{n, n} \end{vmatrix}

定义其行列式为

\det(A) = \sum\limits_{\pi} (-1) ^ {\lambda(\pi)} \prod\limits_{i = 1} ^ n a_{i, \pi_i}

也可记为 |A|。

性质 1.1：交换方阵的行列，其行列式值不变。

证明：因为 \{1, 2, \cdots, n\} 是一个排列，\{\pi_1, \pi_2, \cdots, \pi_n\} 也是一个排列，所以交换行列不会影响一个 a_{i, \pi_i} 的序列是否会被计算的。

我们把这种交换行列的变换叫做方阵转置。

性质 1.2：行列式某一行的倍数可以提取到行列式值的外面。

性质 1.3：可以将行列式一行的值拆为两个部分，其余值不变，那么它的行列式值不变。

性质 1.4：交换行列式两行，行列式值反号。

推论 1.4.1：若行列式两行对应成比例，则行列式值为 0。

推论 1.4.2：将行列式一行的 k 倍加到另一行上，行列式的值不变。

事实上，以上所有对于行的性质，对于列也满足。我们根据性质 1.1 先将方阵转置，这样列就变成行，而行列式的值不变。

行列式值求法

若模数为质数，则可以结合推论 1.4.2，用类似于高斯消元的方式把原行列式化为这种类型：

\begin{vmatrix} a_{1, 1} & a_{1, 2} & \cdots & a_{1, n} \\ 0 & a_{2, 2} & \cdots & a_{2, n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & a_{n, n} \end{vmatrix}

我们把这种方阵称作上三角方阵。那么行列式的值显然就是 \prod\limits_{i = 1} ^ n a_i。时间复杂度 O(n^3)。

若模数非质数，那么我们可以通过类似辗转相除的方式同样把它化为上三角方阵。具体地，我们每次可以对两行对应的数进行辗转相除。可以证明总操作次数不会超过 O(n^2 \log P)，故总时间复杂度为 O(n^3 + n^2 \log P)。

3. 无向图矩阵树定理

3.1 另一些定义

D(G)_{i, j} = \begin{cases} \deg_i & (i = j) \\ 0 & (i \ne j) \end{cases} A(G)_{i, j} = \text{The number of paths from } i \text{ to } j K(G) = D(G) - A(G) M(G) = \begin{cases} 1 & (i \text{ is the start of } edge_j) \\ -1 & (i \text{ is the end of } edge_j) \\ 0 & (\text{Otherwise}) \end{cases}

若图无向，则方向随意。

引理 3.1：M \times M^T = K。

证明：

(M \times M^T)_{i, j} = \sum\limits_{k = 1} ^ m M_{i, k}M_{j, k}

当 i = j 时当且仅当 i 为 k 的一个端点时贡献为 1，总贡献为 D(i, i) 当 i \ne j 时当且仅当 i, j 为一条边的两个端点时贡献为 -1，总贡献为 -A(i, j)。

3.2 无向图 \rm Matrix - Tree 定理

t(G) = \det K(G) \binom{1, 2, \cdots, i - 1, i + 1, \cdots, n}{1, 2, \cdots, i - 1, i + 1, \cdots, n}

即，无向图的无根生成树数量等于其 \rm kirchhoff 矩阵去掉任意第 i 行及第 i 列后的行列式值。

引理 3.2：若边集 S 在原图上构成生成树，则 \det(M_0)[S] = \pm1，否则为 0。

证明：此证明会反复应用行列式性质 1.4.2。

先来证明前一半。我们对于每个叶子节点，考虑用它所在的行消去其父亲所在的行。这类似于一个递归的过程，最后肯定每一行都为 \pm1，由此行列式的值也为 \pm1。

再来证明后一半。肯定存在一个简单环，不妨设其边为 e_1, e_2, \cdots, e_k。我们将证明：M_0(G)[S] 的这些列线性相关。事实上，我们每次可以选取一条边上的两个点，用一个所在的行去消另一个所在的行，这等价于在原环上将两条相邻的边合为一条边。所以最后能够消完，即这些列线性相关。于是我们可以得到一个列为 0，所以行列式的值也为 0。

引理 3.3（\rm Binte - Cauchy 定理）：

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

\det(AB) = \sum\limits_{|S| = n, S \subseteq \{1, 2, \cdots, m\}} \det(A[S]) \det(B[S])

其中 A[S] 表示 A 取在 S 里的列所构成的矩阵，其中 B[S] 表示 B 取在 S 里的行所构成的矩阵。

证明：我们先来证明一个引理：

引理 3.3.1：对于两个排列 P, Q，定义 R 为其复合排列，满足 R_i = P_{Q_i}，那么 \lambda(R) 与 \lambda(P) + \lambda(Q) 同奇偶。

引理的证明：我们可以把 P, Q 的复合看作是类似冒泡排序的过程：把排列 P 相邻两项交换，直至其下标为排列 Q。初始逆序对数为 \lambda(P)，交换次数为 \lambda(Q)，得到排列 R。而一次交换改变逆序对数奇偶性，所以这两者奇偶性相等。

推论：定义 P' 为满足 P'_{P_i} = i，那么 \lambda(P) 与 \lambda(P') 奇偶性相同。

事实上，顺着上面的思路想，可以证明二者是相等的。

现在我们来证明原命题。一方面：

& \sum\limits_{S} \det(A[S]) \det(B[S]) \\ &= \sum\limits_{S} \det(A[S])\det(B[S]) \\ &= \sum\limits_{S} \left( \sum\limits_P (-1)^{\lambda(P)} \prod\limits_{i = 1} ^ n A_{i, S_{P_i}} \right) \left( \sum\limits_Q (-1) ^ {\lambda(Q)} \prod\limits_{i = 1} ^ n B_{S_i, Q_i} \right) \\ &= \sum\limits_S \sum\limits_P \sum\limits_Q (-1) ^ {\lambda(P) + \lambda(Q)} \prod\limits_{i = 1} ^ n A_{i, S_{P_i}} B_{S_i, Q_i} \\ \end{aligned}

另一方面：

\det(AB) &= \sum\limits_{P} (-1) ^ {\lambda(P)} \prod\limits_{i = 1} ^ n \sum\limits_{j = 1} ^ m A_{i, j} B_{j, P_i} \\ &= \sum\limits_P (-1) ^ {\lambda(P)} \sum\limits_R \prod\limits_{i = 1} ^ n A_{i, R_i} B_{R_i, P_i} \\ &= \sum\limits_R \sum\limits_P (-1) ^ {\lambda(P)} \prod\limits_{i = 1} ^ n A_{i, R_i} B_{R_i, P_i} \end{aligned}

其中 |R| = n，且 R_i \in \{1, 2, \cdots, m\}。假设 R_i = R_j (i \ne j)，那么交换 P_i, P_j 之后式子右边的值不变，而逆序对数量的奇偶性改变。我们考虑交换最小的两个，那么能交换的 R 就是一一对应的，所以其和会互相抵消。所以我们只用考虑 R_i 互不相同的情况。我们可以先选一个集合 S，再枚举其排列 Q。

& \sum\limits_S \sum\limits_Q \sum\limits_P (-1) ^ {\lambda(P)} \prod\limits_{i = 1} ^ n A_{i, S_{Q_i}} B_{S_{Q_i}, P_i} \\ &= \sum\limits_{S} \sum\limits_Q \sum\limits_{P_{Q'}} (-1) ^ {\lambda(P_{Q'})} \prod\limits_{i = 1} ^ n A_{i, S_{Q_i}} B_{S_i, P_{Q'_i}} \\ &= \sum\limits_{S} \sum\limits_Q \sum\limits_{P_{Q'}} (-1) ^ {\lambda(P) + \lambda(Q)} \prod\limits_{i = 1} ^ n A_{i, S_{Q_i}} B_{S_i, P_{Q'_i}} \\ &= \sum\limits_S \sum\limits_Q \sum\limits_P (-1) ^ {\lambda(P) + \lambda(Q)} \prod\limits_{i = 1} ^ n A_{i, S_{Q_i}} B_{S_i, P_i} \\ \end{aligned}

引理证毕。

现在，原定理的证明已经变得非常简单。我们只需要证明删去最后一行及最后一列后结论成立，因为剩余情况唯一需要修改的地方只是 M_0 的定义。我们设 K_0(G) 为 K(G) 删去最后一行一列后得到的方阵。那么不难得到

K_0 = M_0 \times M_0^T

所以

\det(K_0) &= \sum\limits_{S} \det (M_0[S]) \det (M_0^T[S]) \\ &= \sum\limits_{S} \det (M_0[S]) ^ 2 \end{aligned}

若 S 不构成生成树，则其贡献为 0，否则为 1。所以 \det(K_0) 即为生成树数量。

至此，无向图无根树矩阵树定理证毕。\square

4. 有向图矩阵树定理

D_{in}(G)_{i, j} = \begin{cases} \text{in}_i & (i = j) \\ 0 & (i \ne j) \end{cases} D_{out}(G)_{i, j} = \begin{cases} \text{out}_i & (i = j) \\ 0 & (i \ne j) \end{cases}

类似地，我们有

t_{root}(G, i) = \det K_{out}(G) \binom{1, 2, \cdots, i - 1, i + 1, \cdots, n}{1, 2, \cdots, i - 1, i + 1, \cdots, n} t_{leaf}(G, i) = \det K_{in}(G) \binom{1, 2, \cdots, i - 1, i + 1, \cdots, n}{1, 2, \cdots, i - 1, i + 1, \cdots, n}

证明略。

5. 拓展及应用

若求带权生成树权值之和，可将权值看作重边。

[SHOI2016] 黑暗前的幻想乡

Description

给定 n 和 n - 1 个边集 S_{1 \cdots n - 1}，问从每个边集中选一条边构成生成树的方案数对 10^9 + 7 取模的值。n \le 17。

Solution

板子题，定理加上容斥即可。时间复杂度 O(2^{n - 1} (n - 1)^3 \log P)。

[SDOI2014] 重建

Description

给定一张完全图和每条边被保留的概率。求保留下的边构成生成树的概率。n \le 50。

Solution

选到边集 S 的概率为 \prod\limits_{e \in S} p_e \prod\limits_{e \not\in S} (1 - p_e)。显然我们可以给每一条边赋边权 \frac{p_e}{1 - p_e}，计算答案的时候再乘以 \prod\limits_{e} (1 - p_e) 即可。对于 0 的处理方法可以用计算几何的常用手段——微扰。时间复杂度 O(n^3)。

[CQOI2018] 社交网络

Description

给一张有向图，求其叶向树生成树数量。

Solution

叶向树板子。