矩阵树定理及其无向图形式证明

Achtoria

2021-03-06 10:06:48

题解

网上貌似证明比较少，而且不全，于是来 水一篇博客。

首先介绍行列式及其基本性质：

行列式之前

定义奇排列为逆序对数量为奇数的排列，对于偶排列类似。

  1. 交换排列两个元素，排列奇偶性改变。

一个简单的证明方法：考虑交换相邻两个元素，逆序对数量必 +1/-1，奇偶性必改变。

那么假设交换排列中两个元素 p_i, p_j 相当于先将 p_i 向右交换 j - i 次，再将 p_j 向左交换 j - i - 1 次，共 2 \times (j - i) - 1 次必改变奇偶性。

不妨将问题转化一下：考虑序列 f 表示每个位置前面比其大的数的个数，那么 \sum f_i 为逆序对数量。

不难发现对于任意的序列 f，若满足 \forall i, f_i \in [0, i - 1]，f 可唯一对应一个排列且不重不漏。证明考虑局限前 k 个数为一个排列，插入一个数将之前不小于其的数 +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_{p} \mathrm{sgn}(p) \prod\limits_{i = 1} ^ n a_{i, p_i} 其中 p 为一个排列。

性质

  1. 交换行列（方阵转置），行列式值不变。（即将原来的 a_{i, j} \rightarrow a_{j, i}）

只需证 \sum\limits_{p} \mathrm{sgn}(p) \prod\limits_{i = 1} ^ n a_{i, p_i} = \sum\limits_{p} \mathrm{sgn}(p) \prod\limits_{i = 1} ^ n a_{p_i, i} \Longleftrightarrow \mathrm{sgn}(p) = \mathrm{sgn}(p')(p'_{p_i} = i)

对于后者，其等价于按照排列权值大小排序后下标的逆序对数量，这与原逆序对定义的数量是一致的。

  1. 行列式某一行的倍数可以直接提取到行列式的值的外面

即对于方阵 A：

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

其行列式 \det(A) = k\sum\limits_{p} \mathrm{sgn}(p) \prod\limits_{i = 1} ^ n a_{i, p_i}，证明是容易的。

  1. 可以将行列式某行的值拆成两个部分其余行不变，然后拆开求和原行列式值相等

即：

\begin{vmatrix} a_{1, 1} & a_{1, 2} & \cdots & a_{1, n} \\ \vdots & \vdots & \ddots & \vdots \\ b_{i, 1} + c_{i, 1} & b_{i, 2} + c_{i, 2} & \cdots & b_{i, n} + c_{i, n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n, 1} & a_{n, 2} & \cdots & a_{n, n} \end{vmatrix} = \begin{vmatrix} a_{1, 1} & a_{1, 2} & \cdots & a_{1, n} \\ \vdots & \vdots & \ddots & \vdots \\ b_{i, 1} & b_{i, 2} & \cdots & b_{i, n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n, 1} & a_{n, 2} & \cdots & a_{n, n} \end{vmatrix} + \begin{vmatrix} a_{1, 1} & a_{1, 2} & \cdots & a_{1, n} \\ \vdots & \vdots & \ddots & \vdots \\ c_{i, 1} & c_{i, 2} & \cdots & c_{i, n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n, 1} & a_{n, 2} & \cdots & a_{n, n} \end{vmatrix}

证明是简单的。

  1. 交换行列式两行，行列式值反号。

根据排列性质 1，相当于交换原排列的两个位置，奇偶性改变 \rm sgn 值也必改变。

  1. 若行列式两行成比例，则行列式值为 0。

首先将比例提出，那么此时行列式存在两行相等，交换两行行列式不变但值反号，可知行列式值为 0。

  1. 将行列式某一行的 k 倍加到另一行上，行列式值不变。

将加后行列式的被加行改写成 kx + b 的形式，利用 3 线性拆开，其中 kx 的行列式根据 5 值为 0。

  1. 上述所有对行满足的性质，对于列而言也满足。

首先将矩阵转置，于是原来列操作等价于转置后的行操作，最后再转回来即可。

行列式值求法

1. 模数为质数

对于上三角方阵 A：

\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}

其行列式值显然为 \det(A) = \prod\limits_{i = 1} ^ n a_{i, i}，因此我们只需要将原行列式变成一个于其值相同的上三角方阵即可。

不难发现可以利用 6 的性质配合高斯消元即可求得行列式的值。

复杂度 \mathcal{O(n ^ 3)}。

2. 一般情况

若模式不为质数，我们在消元时就不能直接算出 \dfrac{a_{j, i}}{a_{i, i}}，因为不存在逆元。

故我们不能使用分数的方式一次性消掉另一行，但注意到我们只需要消除这一行，故可以寻找一些别的方式。

考虑辗转相除的过程，我们每次将第 j 行消去至 a_{j, i} \rightarrow a_{j, i} \% a_{i, i} 然后交换两行，直至 a_{j, i} = 0。

因为辗转相除过程中只会变小，因此取模不会影响复杂度，故可以取模。

注意到辗转相除的复杂度为 a_{i, i} 的减小次数，为 \mathcal{O(\log P)}，此部分总复杂度为 \mathcal{O(n ^ 2\log P)} 不为瓶颈。

因此复杂度为 \mathcal{O(n ^ 3)}。

定义

  1. 对于无向图，定义 D(G) 为图 G 的度数矩阵，其中：
D(G)(i, j) = \begin{cases} \deg_i & (i = j) \\ 0 & (i \ne j) \end{cases}
  1. 对于有向图，定义 D ^ {in}(G) 为图 G 的入度矩阵，D ^ {out}(G) 为图 G 的出度矩阵，其中：
D(G) ^ {in}(i, j) = \begin{cases} \mathrm{in}_i & (i = j) \\ 0 & (i \ne j) \end{cases}, D(G) ^ {out}(i, j) = \begin{cases} \mathrm{out}_i & (i = j) \\ 0 & (i \ne j) \end{cases}
  1. 定义 A(G) 为图 G 的邻接矩阵，其中：
A(G)(i, j) = \text{the number of the path from i to j}

  1. 定义图 G 的 \rm kirchhoff 矩阵 K(G) = D(G) - A(G)。

  2. 定义无向图 G 的生成树数量为 t(G)，有向图根向树生成树（根为 u，下同）数量为 t ^ {root}(G, u)，有向图叶向树数量为 t ^ {leaf}(G, u)。

  3. 定义图 G 的关联矩阵 M(G) 为一个大小为 n \times m 的矩阵，其中（一下的方向对于无向图随意）：

M(G)(i, j) = \begin{cases} -1 & (\text{i is the end of the } edge_j) \\ 1 & (\text{i is the start of the } edge_j) \\ 0 & (\text{Otherwise}) \\ \end{cases}

  1. 定义图 G 的减关联矩阵 M_0(G) 为关联矩阵 M(G) 去掉最后一行后的大小为 (n - 1) \times m 的矩阵。

  2. 定义图 G 的子减关联矩阵 M_0(G)[S] 为选出 M_0(G) 中的列构成子集 S，满足 |S| = n - 1, S \subseteq \{1, 2, \cdots m\}。

定理

以下默认所有数均为正整数，图不存在自环但可存在重边。

  1. 无向图矩阵树定理：
\forall i \in [1, n], t(G) = \det K(G) \begin{pmatrix}1, 2, \cdots i - 1, i + 1, \cdots n \\ 1, 2, \cdots i - 1, i + 1, \cdots n\end{pmatrix}
  1. 有向图矩阵树定理：
\forall i \in [1, n], t ^ {root}(G, i) = \det K ^ {out}(G) \begin{pmatrix}1, 2, \cdots i - 1, i + 1, \cdots n \\ 1, 2, \cdots i - 1, i + 1, \cdots n\end{pmatrix} \forall i \in [1, n], t ^ {leaf}(G, i) = \det K ^ {in}(G) \begin{pmatrix}1, 2, \cdots i - 1, i + 1, \cdots n \\ 1, 2, \cdots i - 1, i + 1, \cdots n\end{pmatrix}
\forall i \in [1, n], ec(G) = t ^ {root}(G, i) \prod\limits_{u \in V} (\deg_u - 1)!

其中对于欧拉图 \mathrm{in}, \mathrm{out} 均相同，因此 \deg 可任选其一。

若要求欧拉回路起点 k，则以 k 为起点的欧拉回路数量 ec(G, k) 为：

ec(G, k) = t ^ {root}(G, k) \deg_k \prod\limits_{u \in V} (\deg_u - 1)!

此定理下面暂不证明，先咕着。

以上所有定理，若带权求生成树 / 欧拉回路权值之和，可看 将权值看作重边 于是就可以划归到没有权值的情况。

证明

以下只证明无向图无根树生成树矩阵树定理。

1. 引理 1：

M \times M ^ {T} = K \begin{aligned} M \times M ^ {T}(i, j) &= \sum\limits_{k = 1} ^ m M(i, k) \times M ^ {T}(k, j) \\ &= \sum\limits_{k = 1} ^ m M(i, k) \times M(j, k) \\ \end{aligned}

可以发现当且仅当 i, j 都为边 k 的一个端点时，贡献不为 0。

若 i = j 则 M(i, k) = M(j, k) 贡献相等，那么两者乘积贡献 1。因此总贡献为 \deg_i。

若 i \ne j 则 M(i, k) \ne M(j, k) 贡献相反，那么两者乘积贡献 -1。因此总贡献为 -A(i, j)。

于是有引理 1 成立。

2. 引理 2：

若 S 构成的边集在原图上构成生成树，那么 \det M_0[S] = 1 / -1 否则 \det M_0[S] = 0。

先证后者：

若原图没有构成树，那么至少存在一个简单环 C(e_{i_1}, e_{i_2}, \cdots e_{i_k})，记 e_{{i_j}_u}, e_{{i_j}_v} 分别为边 e_{i_j} 的两个端点。

同时，对于 M_0[S] 有如下两点观察：

下面证明 M_0[S] 对应原简单环中的 i_1, i_2, \cdots i_k 列线性相关，考虑依次合并所有列：

我们首先拿第 i_1 列消 i_2 列，因为简单环上两边共点，因此至少存在一行使得两列上均非 0，我们消掉这一行后根据观察 2 必恰好仅有 e_{{i_1}_u}, e_{{i_2}_v} 这两行一行为 1 一行为 -1。

假设合并到第 i_j 列，若 j \ne k 那么使用 i_{j - 1} 列合并的结果同第一列消第二列的方式消掉第 i_j 列，于是第 i_j 列消完后必恰好在 e_{{i_1}_u}, e_{{i_j}_v} 这两行一行为 1 一行为 -1。

最后合并到第 i_{k - 1} 列时，此时非 0 两行与原 i_k 列未消时一致，故此时可以将第 i_k 列消为全 0。

因此这 i_1, i_2, \cdots i_k 列线性相关，\det M_0[S] = 0。

再证前者：

考虑将原行列式消成好算的形式，类似于高斯消元的方式，我们钦定一行的主元拿此行去消所有行。

具体地，若 S 构成的边集为一棵树，那么必定能找到叶子节点 u，此时选出 u 所在的行，必定恰好只存在一列非 0，拿此列去消所有行（事实上只能消掉边的另一个节点所对应的行）。

可以发现这等价于每次在 M_0[S] 中删去树上叶子节点所对应的一条边，故此过程一定可以不断递归直至消去所有边。

最后我们发现，每一行都只剩下恰好一列为其做为叶子时所对应列为 1 / -1，故此时行列式值仅在每行选这些列时非 0，不论逆序对数量，所得行列式值均为 1 / -1。

3. 引理 3（\rm Binet - Cauchy 定理）：

定义大小分别为 n \times m, m \times n(n \le m) 的矩阵 A, B 则有：

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

其中 A[S], B[S] 分别表示 A 取 S 集合内的列，B 取 S 集合内的行所构成的矩阵。

证明引理 3 之前再给出两条引理：

定义 \lambda(P) 为排列 P 的逆序对数量。

\lambda(P) = \lambda(P') $\quad$ 那么 $\lambda(P')$ 等价于将将序列 $A$ 按照第一关键字排序后以第二关键字为权值的逆序对数量。 $\quad$ 在这里等价于按照权值排序后求下标的逆序对，这与直接求原排列的逆序对是等价的。 * 2. 引理 $2$： * 定义 $P_{Q}$ 为排列 $Q$ 与排列 $P$ 的复合，则 $\lambda(P_{Q})$ 与 $\lambda(P) + \lambda(Q)$ 的奇偶性相同。 $\quad$ 仿照引理 $1$ 的证明方法，那么左式等价去求给定序列 $A$，每个元素存在两个关键字 $x, y$ 其中 $A_{i_x} = Q'_i, A_{i_y} = P_i$， $\quad$ 那么 $\lambda(P_Q)$ 等价于按照第一关键字排序后以第二关键字为权值的逆序对数量。 $\quad$ 考虑调整证明，可知一开始的逆序对数量为 $\lambda(P)$，排序利用冒泡排序的过程，可知有效的交换仅有 $Q'$ 的逆序对个。 $\quad$ 而我们知道每交换排列里两个元素排列逆序对数奇偶性改变，故总共改变 $\lambda(P)$ 次，所以 $\lambda(P_Q)$ 与 $\lambda(P) + \lambda(Q)$ 奇偶性相同。 --- 首先我们展开等式右侧： $$ \begin{aligned} & \sum\limits_{S \subseteq \{1, 2, \cdots m\}, |S| = n} \det(A[S]) \times \det(B[S]) \\ &= \sum\limits_{S \subseteq \{1, 2, \cdots m\}, |S| = n} \left(\sum\limits_{P} (-1) ^ {\lambda(P)} \prod\limits_{i = 1} ^ n A_{i, S_{P_i}}\right) \times \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}} \times B_{S_i, Q_i} \\ \end{aligned} $$ 再展开等式左侧： $$ \begin{aligned} & \det(AB) \\ &= \sum\limits_{P} (-1) ^ {\lambda(P)} \prod\limits_{i = 1} ^ n \left(\sum\limits_{j = 1} ^ m A_{i, j} \times B_{j, P_i}\right) \\ &= \sum\limits_{P} (-1) ^ {\lambda(P)} \sum\limits_{R} \left(\prod\limits_{i = 1} ^ n A_{i, R_i} \times B_{R_i, P_i}\right) (|R| = n, \forall i, R_i \in \{1, 2, \cdots m\}) \\ &= \sum\limits_{R} \sum\limits_{P} (-1) ^ {\lambda(P)} \left(\prod\limits_{i = 1} ^ n A_{i, R_i}\right) \times \left(\prod\limits_{i = 1} ^ n B_{R_i, P_i}\right) \end{aligned} $$ 仔细观察可知，对于可重排列 $R$，若存在 $i < j, R_i = R_j$ 那么交换 $P_i, P_j$ 后后面的积式不变，但逆序对奇偶性改变，因此两者贡献互为相反数可抵消。 因此我们只需钦定每个存在 $i < j, R_i = R_j$ 的可重排列 $R$，让其和交换满足条件的最小 $P_i, P_j$ 交换后的排列 $P$ 的贡献相抵即可。 因为交换最小的 $i, j$ 后依然满足 $i, j$ 为最小的满足条件的点对，因此可以两两唯一配对。 故我们只需枚举不重的序列即可，为此我们首先枚举 $\{1, 2, \cdots m\}$ 的子集，然后枚举一个长度为 $n$ 的排列 $Q$： $$ \begin{aligned} & \det(AB) \\ &= \sum\limits_{S} \sum\limits_{Q} \sum\limits_{P} (-1) ^ {\lambda(P)} \prod\limits_{i = 1} ^ n A_{i, S_{Q_i}} \times B_{S_{Q_i}, P_i} \\ &= \sum\limits_{S} \sum\limits_{Q} \sum\limits_{P_{Q'}} (-1) ^ {\lambda(P_{Q'})} \left(\prod\limits_{i = 1} ^ n A_{i, S_{Q_i}}\right) \times \left(\prod\limits_{i = 1} ^ n B_{S_i, P_{Q'_i}}\right) \\ &= \sum\limits_{S} \sum\limits_{Q} \sum\limits_{P_{Q'}} (-1) ^ {\lambda(P) + \lambda(Q)} \left(\prod\limits_{i = 1} ^ n A_{i, S_{Q_i}}\right) \times \left(\prod\limits_{i = 1} ^ n B_{S_i, P_{Q'_i}}\right) \end{aligned} $$ 整理即可得到从右侧推导得到的式子。 --- 下面我们只证明矩阵树定理删去最后一行最后一列是正确的（对于删去其余的情况，只需将 $M_0$ 的定义修改成删去改行即可）。 类似于引理 $1$，我们知道 $K_0 = M_0 \times M_0 ^ T$ 其中 $K_0$ 为 $K$ 去掉最后一行和最后一列得到的方阵。 再根据引理 $3$，可知： $$ \begin{aligned} \det K_0 &= \sum\limits_S \det(M_0[S]) \det(M_0 ^ T[S]) \\ &= \sum\limits_S \det{^ 2}(M_0[S]) \end{aligned} $$ 由定理 $2$，若边集 $S$ 不构成生成树，则 $\det(M_0[S]) = 0$，在该式中贡献为 $0$。 若边集 $S$ 构成生成树，则 $\det(M_0[S]) = 1 / -1$，在该式中贡献为 $1$。 故可得到 $\det K_0$ 即为原图的生成树数量。 --- 参考资料： [OI-Wiki](https://oi-wiki.org/graph/matrix-tree/) [行列式学习笔记 - suxxsfe](https://www.cnblogs.com/suxxsfe/p/12446673.html) [矩阵树定理（Matrix-tree Theorem）笔记 - silverxz](https://zhuanlan.zhihu.com/p/108209378) [Binet-Cauchy定理的证明 - lyyi2003](https://www.cnblogs.com/lishuyu2003/p/12093947.html)