详细揭秘：低秩矩阵分解与矩阵树定理极简证明

cyffff · 2025-11-13 07:53:14 · 算法·理论

低秩矩阵分解可用于解决特殊矩阵行列式求值，其中包括特殊图生成树计数问题。

回顾行列式的定义式：

\det(A)=\sum_{p_{1\sim n}}(-1)^{\text{inv}(p)}\prod_{i=1}^nA_{i,p_i}

对于求解 \det(A+B) 的问题，根据行列式的定义式，拆开贡献有：

选取一个集合 S\sube\{1,2,\dots,n\}；

如果其中 \text{rank}(A) 为常数，则可以进行低秩矩阵分解：根据行列式基本性质，只有 S 内行线性无关时才有可能做出贡献，此时明显有 |S|\le \text{rank}(A)。

例：矩阵树定理的证明

证明：给定一张图，令 D,A 分别为图的度数矩阵、邻接矩阵，则任意选定 x 并删除 D,A 中的第 x 行、第 x 列后，\det(D-A) 等于该图生成树个数。

对于一条边 (u,v)，其贡献为一个只有四个点有值的矩阵 M_i，其 (u,u),(v,v) 上的值为 1，(u,v),(v,u) 上的值为 -1。显然 M_i 的秩为 1，而 D-A 就是 \sum M_i，这适用低秩矩阵分解。

相当于对每个不等于 x 的点选择了一条边，且这些边互不相同。考虑每种方案的贡献：

如果选出了环，那么这些行加起来就是全零行，故对应贡献为 0。
如果没有任何环，那么考虑与 x 相连的任意点 p，其只能选择 (p,p) 上的 1，因为 (p,x) 被删去了，依此递推可以得到贡献为 1。

可以非常轻松地拓展至带权、有向版本推论。

例：Determinant

给定整数 n,c，求解 n\times n 的矩阵 A_{i,j} 的行列式：
A_{i,j}=\begin{cases}1,&i=j\\0,&i\ne j\land j\bmod i=0\\c,&\text{otherwise}\end{cases}
对 998244353 取模。

注意到 A_{i,j} 里面不等于 c 的位置很少，不妨令 A=B+C，其中 C 表示一个 n\times n 的全 c 矩阵，

B_{i,j}=\begin{cases}1-c,&i=j\\-c,&i\ne j\land j\bmod i=0\\0,&\text{otherwise}\end{cases}

容易发现，B 是一个上三角矩阵，C 的秩为一。

由于 \text{rank}(C)=1，于是考虑计算将 B_{i,j} 中至多一行替换为全 C 的行列式。

由于 B_{i,j} 是上三角矩阵，在没有替换时必有 p_i=i。如果替换了第 k 行，那么在排列上就会形成一个环，其中环上除了 k 的每个结点的编号都是下一个结点的因数，可以发现，其带来的逆序对数量为环上点数减一。

考虑计算贡献，令 f(i) 表示替换第 i 行的贡献，则有：

f(n)=\dfrac{c}{1-c}(1+\sum_{d|n,d\ne n}f(d))

后续优化可以移步完整题解查看。

例：能量场

给你一个长为 n 的序列 a_{1\dots n}，定义一条边 (u,v) 的权值为 a_u+a_v。对于一张图，定义其权值为包含的所有边的权值乘积。求所有 n 个点的有标号基环树的权值之和。对 998244353 取模。

考虑基环树把环缩起来就是一颗树，而树的权值乘积很自然就能想到矩阵树定理，我们不妨枚举哪些点在环上，我们可以 DP 求出这些点构成的环的权值和，然后将这些点缩起来（边权、度数相加）做一次矩阵树定理，为了方便我们可以将代表这个环的点删去。

我们需要求 \det(D-A)，其中 D 只有对角线位置有值且 D_{i,i}=na_i+\sum_{j=1}^na_j，A_{i,j}=a_i+a_j，不妨设 d_i=D_{i,i}。

可以观察到 A 中任意三行线性相关。于是我们只需要考虑大小不超过 2 的 S。

根据行列式的定义式，我们可以简单地将行列式求出：

后续优化可以移步完整题解查看。

思考：简单的生成树

给定两棵点数分别为 n,m 的树 T_1,T_2 ，再构造一个无向图 G，G 包含 T_1,T_2 的所有点、树边，且还包含所有跨越 T_1,T_2 的点对所组成的边。

求无向图 G 的生成树个数，对 10^9+7 取模。

本题虽有其它解法，不过请尝试使用低秩矩阵分解解决。

:::info[解答]

在两棵树上分别断开若干条边，设形成的连通块点数分别为 a_{1\sim p},b_{1\sim q}。

问题转化为二分图生成树个数，左部点 i 与右部点 j 之间的边权为 a_i\cdot b_j。

依旧对 \det(D-A) 做低秩矩阵分解，其中 \text{rank}(A)=2。

经过简单的推导，可得到答案为：

m^{p-1}n^{q-1}\prod_{i}a_i\prod_j b_j

树形 DP 即可求解，时间复杂度 O(n+m)。 :::

思考：Odd Namori

给定一个长为 n-1 的序列 p_{2\sim n}，求满足下列条件的有向图的权值和：

每个顶点的出度都为 1。

图中不存在偶环。

对于所有 i\in[2,n]，图中不包含边 i \to p_i。

一张图的权值定义为 2^c，其中 c 表示该图中的环数。答案对 998244353 取模。

:::info[提示：如何计算一张图的合法生成子图权值和] 令 D,A 分别为图的度数矩阵、邻接矩阵，则答案为 \det(D+A)。

:::success[证明] 仿照对矩阵树定理的证明。对于一条边 u\to v，其贡献为一个只有两个点有值的矩阵 M_i，其 (u,u),(u,v) 上的值为 1，同样适用低秩矩阵分解。

相当于对每个点选择了一条出边。考虑每种方案的贡献：

如果选出了偶环，那么这些行在环上编号为奇数的减去在环上编号为偶数的即可得到全零行，故对应贡献为 0。
如果没有任何偶环，那么每个环都有两种方向可选择，故贡献为 2^c，符合题意。

:::

:::info[解答] 有了上面的结论，我们能轻松求解给定内向树的补图的答案。

记从 0 开始的深度序列为 d_{1\sim n}。

完全图对应的矩阵为 \textbf{1}+nI，其中 \textbf{1} 为全 1 矩阵，I 为单位矩阵。而所求为 \det(\textbf{1}+nI-I'-A)，其中 I' 除了 (1,1) 为 0，其余位置均与单位矩阵相同，A 为给定内向树的邻接矩阵。

求行列式的矩阵为三个部分的和：\textbf{1}，nI-I'，-A，其中 \textbf{1} 的秩为 1。如果没有用 \textbf1 替换任意一行，则每个点均只能选第二部分，贡献为 n\cdot (n-1)^{n-1}。

否则若替换第 i 行，且第 i 行选择列 j，那么第 j 行只能选择第三部分，即选择第 p_j 列。以此类推可以知道 j 在 i 的子树中，且不在 j\to i 路径上的结点依旧只能选第二部分。由于 p_i<i，所以每跳一次同时会有来自 -A 的 -1 贡献和来自逆序对的 -1 贡献，即贡献抵消为 1。

如果 i\ne 1，则贡献为 n\cdot(n-1)^{n-(d_j-d_i+1)-1}；否则贡献为 (n-1)^{n-d_j-1}。

可以轻易线性计算，时间复杂度 O(n)。 :::