矩阵树定理

前置技能:行列式

定义

    \[\det(A)=\sum_{\sigma \in S_n}\operatorname{sgn}(\sigma)\prod_{i=1}^na_{i,\sigma(i)}\]

其中S_n表示集合(1,2,...,n)上置换的全体;\operatorname{sgn}(\sigma)表示\sigma \in S_{n}的符号差。具体地说,如果\sigma的逆序共有偶数个,则\operatorname{sgn}(\sigma)=1,如果共有奇数个,则\operatorname{sgn}(\sigma)=-1

性质

一个n维正方矩阵可以看成nn向量放在一起。行列式则表示该平行体的带符号体积;或者两个平行体之间该线性变化体积的变化率。这样我们就能形象地理解它的一个性质:交替多线性
具体来说,这个函数D满足以下两个性质:
  1. n重线性:{\displaystyle D(a_{1},\ldots ,ca_{i}+a_{i}',\ldots ,a_{n})=cD(a_{1},\ldots ,a_{i},\ldots ,a_{n})+D(a_{1},\ldots ,a_{i}',\ldots ,a_{n})}
  2. 交替性:{\displaystyle D(a_{1},a_{2},\ldots ,a_{n})=-D(a_{2},a_{1},\ldots ,a_{n})}
   且当a_{i}=a_{j}的时候,D(a_{1},\ldots ,a_{i},\ldots ,a_{j},\ldots ,a_{n})=0
之后的一些性质可由多线性和交替性得出:

  • 在行列式中,一行(列)元素全为0,则此行列式的值为0。

  • 在行列式中,某一行(列)有公因子k,则可以提出k

  • 在行列式中,某一行(列)的每个元素是两数之和,则此行列式可拆分为两个相加的行列式。

  • 行列式中的两行(列)互换,改变行列式正负符号。

  • 在行列式中,有两行(列)对应成比例或相同,则此行列式的值为0。

  • 将一行(列)的k倍加进另一行(列)里,行列式的值不变。

因此,我们可以通过高斯消元来快速地求一个n阶矩阵的行列式。

高斯消元

    \[\det(A)=(-1)^s\det(A')=(-1)^s\prod_{i=1}^nA_{i,i}\]

其中,A'表示高斯消元后的上三角矩阵,s表示在高斯消元列的交换次数。通过上述性质,证明显然。由于求行列式只能拿一行加到另一行上去,所以我们要用辗转相除法。

int solve(){
    int ans=1;
    for(int i=1;i<n;i++){
        for(int j=i+1;j<n;j++){
            while(a[j][i]){
                int t=a[i][i]/a[j][i];
                for(int k=i;k<n;k++)
                    a[i][k]=(a[i][k]-1ll*a[j][k]*t%mod+mod)%mod;
                swap(a[i],a[j]);
                ans=-ans;
            }
        }
        ans=1ll*ans*a[i][i]%mod;
    }
    return (ans+mod)%mod;
}

先来看一个小问题

生成计数问题:给一副n个节点的无向图G,求一个包含n-1条边的边集使得边集的边构成一颗树(图的生成树),问这样的边集的数量。矩阵树定理就是用来解决这样的问题的。

基尔霍夫矩阵

首先介绍两个矩阵:
  1.度数矩阵D是一个n阶矩阵,当i\neq j时,D_{i,j}=0;否则,D_{i,i}等于点i的度数。
  2.邻接矩阵A
构造基尔霍夫矩阵C:C=D-A.

性质

  1. 基尔霍夫矩阵的每一行每一列之和都为0.
  2. 拉普拉斯矩阵的任意一个代数余子式值都相同
    只需考虑证明\det(M_{i,k})=\det(M_{j,k})即可。把M_{i,k}i行取相反数,行列式变为原来的相反数。之后对于i外的每一行,都乘上-1加到i行上,由于性质1,操作后这一行就变成了原来的第j行,但相对位置还不是和M_{j,k}一样的。将i行一步步互换到j的位置,行列式需要乘上(-1)^{j-i-1},加上i行取反的-1,根据代数余子式定义还要乘上(-1)^{j-i},所以命题得证。
  3. \det(c)=0
    显然基尔霍夫矩阵的每一行每一列之和都为0,高斯消元后必然有一行元素为0.

矩阵树定理

对于一个无向简单图G,构造其基尔霍夫矩阵C,则该矩阵的任意代数余子式M的行列式值等于图G的生成树个数。

证明

证明过程可以参见这个博客
1. 当图G不连通时,\det(M)=0.
考虑重标号,使同一连通块在标号上连续。则C可拆分为至少两个相离的基尔霍夫矩阵。其余子式的行列式则可表示为每个相离矩阵行列式之积,而其中至少有一个完整的基尔霍夫矩阵。
2. 当图G是一棵树时,\det(M)=1
接着考虑重标号,使标号对应点的dfs序,这样就可以用归纳证明。显然在n=2\det(M)=1,对于一个n-1阶基尔霍夫矩阵C',加入一个点n产生的影响是C_{i,n},C_{n,i},C_{n,n}都加或减去1,如果我们用点i的余子式求行列式,那么最后一行只有M_{n-1,n-1}的值为1其余都是0.所以\det(M)=det(M').

推广

首先自环对答案没有贡献;
对于重边,邻接矩阵维护重边数量,度数正常维护即可;
对于有向图:
+ 对于i\neq j,C_{i,j}ij的有向边条数的相反数。
+ 对于任意i,C_{i,i}表示点i除去自环之后的入度。

然后\det(M_{i,i})表示以点i为根的生成树个数。

例题

bzoj4596: [Shoi2016]黑暗前的幻想乡


"Alone is what I have. Alone protects me." -Sherlock Holmes