矩阵树定理

  学习笔记15 分钟读完 (大约2301个字)0次访问

矩阵树定理讲解

矩阵树定理

前置知识-行列式

定义

对于一个n×nn \times n的矩阵，其行列式为，

det⁡(A)=∑P(−1)μ(P)∏i=1nA(i,pi)\det(A) = \sum_{P}(-1)^{\mu(P)}\prod_{i = 1} ^ n A(i, p_i)

其中PP为1−n1 - n的一个排列， μ(P)\mu(P)为排列PP的逆序对个数。

性质

  1. 单位矩阵II的行列式为11， 上三角矩阵和下三角矩阵的行列式都是对角线乘积。

  2. 交换矩阵的两行，行列式变号（改变了奇数个逆序对）。

  3. 若某一行乘以kk，行列式乘以kk。

  4. 行的线性性。

    ∣a+a′b+b′cd∣=∣abcd∣+∣a′b′cd∣\begin{vmatrix} a + a'& b+ b' \\ c & d\end{vmatrix} = \begin{vmatrix} a & b \\ c & d\end{vmatrix} + \begin{vmatrix} a'& b' \\ c & d\end{vmatrix}

  5. 有某两行一样的矩阵，行列式为00。

    粗略的证明：根据1，假设我们交换相同的两行，会使行列式变号， 但是交换后，行列式并没有发生改变，也就是行列式只能等于00

  6. 用矩阵的上一行加上另一行的倍数， 行列式不变。

    证明：

    ∵∣abc⋯abc∣=0=∣abc⋯kakbkc∣=0∴∣abc⋯d+kae+kbf+kc∣=∣abc⋯kakbkc∣+∣abc⋯def∣=∣abc⋯def∣\because \begin{vmatrix} a & b & c \\ & \cdots \\ a & b & c\end{vmatrix} = 0 =\begin{vmatrix} a & b & c \\ & \cdots \\ ka & kb & kc\end{vmatrix} = 0 \\ \therefore \begin{vmatrix} a & b & c \\ & \cdots \\ d + ka & e + kb &f + kc\end{vmatrix} = \begin{vmatrix} a & b & c \\ & \cdots \\ ka & kb & kc\end{vmatrix} + \begin{vmatrix} a & b & c \\ & \cdots \\ d & e & f\end{vmatrix} = \begin{vmatrix} a & b & c \\ & \cdots \\ d & e & f\end{vmatrix}

消元法求行列式

首先高斯消元的过程中我们用到的是交换两行，行列式的值变号， 某一行乘上一个数，行列式乘上对应值，一行加上另一行的倍数，行列式不变，最后得到上三角矩阵后，把影响逆回去即可。

P7112 行列式求值 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 610;

int a[N][N];

int n, p;

signed main()
{
    scanf("%lld%lld", &n, &p);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%lld", &a[i][j]);
    int ans =  1, f = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            while(a[i][i])
            {
                int div = a[j][i] / a[i][i];
                for(int k = i; k <= n; k++)
                    a[j][k] = (a[j][k] - div * a[i][k] % p + p) % p;
                swap(a[i], a[j]);
                f = - f;
            }
            swap(a[i], a[j]); f = -f;
        }
    }
    for(int i = 1; i <= n; i++)
        ans = (ans * a[i][i]) % p;
    ans = f * ans;
    printf("%lld", (ans + p) % p);
    return 0;
}

概念

矩阵树定理(Matrix-tree Theorem) 是把图的生成树个数和矩阵行列式联系起来的定理。（有很大的用处！）

定义

首先设有无向图G=(V,E)G = (V, E)， 有pp个顶， qq条边。

然后我们把GG的每条边任意指定一个方向， 这样就可以定义GG的关联矩阵(Incidence Matrix)M(G)M(G), 为一个p×qp \times q的矩阵，

Mi,j={−1vi is the start of ej1vi is the end of ej0ortherwiseM_{i,j} = \left\{ \begin{aligned} & -1 & v_i \ is \ the \ start\ of \ e_j \\ & 1 & v_i \ is \ the \ end \ of \ e_j \\ & 0 & ortherwise \end{aligned} \right.

接着定义GG的拉普拉斯矩阵(Laplacian Matrix)L(G)L(G)， 为一个p×pp \times p的矩阵，

Li,j={−mi,ji≠j ,mi,j edge between vi,vjdeg(vi)i=jL_{i, j} = \left\{ \begin{aligned} & -m_{i, j} &i \not = j \ ,m_{i,j} \ edge \ between \ v_i, v_j \\ & deg(v_i) &i = j \end{aligned} \right.

注意到MM与GG指定的方向有关， 对LL没有影响，举一个例子：

graph 2.png

对应的关联矩阵MM为

∣100−1−1−1−1−1000011001001∣\begin{vmatrix}1&0&0&-1&-1\\-1&-1&-1&0&0\\0&0&1&1&0\\0&1&0&0&1\end{vmatrix}

对应的拉普拉斯矩阵LL为

∣3−1−1−1−13−1−1−1−120−1−102∣\begin{vmatrix} 3 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1\\ -1 & -1 & 2 & 0\\ -1 & -1 & 0 & 2 \end{vmatrix}

另外LL的非主对角线上的元素不一定是−1-1 ， GG中允许重边存在。

引理

Lemma 1

MMT=LM M ^T = L,其中MTM^T表示MM的转置

证明：由定义易得：(MMT)i,j=∑ek∈EMi,kMk,jT=∑ek∈EMi,kMj,k(MM^T)_{i,j} = \sum_{e_k \in E} M_{i,k} M ^T_{k,j} = \sum_{e_k \in E} M_{i,k}M_{j,k}，i=ji = j时就相当于连了几条边也就是入度，i≠ji \not = j时两点之间有连边的话其中必定是一个终点和一个起点，也就是对应的−mi,j-m_{i,j}，得证。

接下来引入一些MM的子矩阵，称为Reduce Incidence Matrix，M0M_0是去掉MM最后一行得到的(p−1)×q(p - 1) \times q矩阵。

定义一个(p−1)×(p−1)(p - 1) \times (p - 1)的矩阵M0[S]M_0[S],其中集合S={i1,i2,⋯ ,ip−1}∈{1,2,⋯ ,q}S = \{i _ 1, i_2, \cdots ,i_{p-1}\} \in \{1, 2, \cdots , q\}q其实就是抽出M0M_0中p−1p - 1列，得到的一个新的矩阵。

Lemma 2

令SS是边集EE的一个大小为p−1p - 1的子集，若G′=(V,S)G' = (V,S)不构成生成树，则det⁡M0[S]=0\det M_0[S] = 0，若G′G'构成生成树，则det⁡M0[S]=±1\det M_0[S] = \pm 1，其中det⁡\det表示矩阵的行列式

Lemma 3

Binet-Cauchy Theorem 设A=(ai,j)A = (a_{i,j})是一个m×nm \times n矩阵， B=(bi,j)B = (b_{i,j})是一个n×mn \times m矩阵，则有det⁡(AB)=∑S(det⁡A[s])(det⁡B[s])\det (AB) = \sum_{S} (\det A[s])(\det B[s])， 其中SS大小为mm，且是{1,2,⋯ ,n}\{ 1, 2, \cdots , n\}的子集。

Lemma 4

Matrix-tree Theorem 设图G=(V,E)G = (V, E), 拉普拉斯矩阵LL, 则GG的生成树的个数等于det⁡L0\det L_0， 其中L0L_0是去掉LL第ii列第ii行得到的子矩阵

拓展

无向图

设GG是一个有nn个顶点的无向图，定义其度数矩阵为

Di,i(G)=deg(i), Di,j(G)=0, i!=jD_{i,i}(G) = deg(i), \ D_{i, j}(G) = 0, \ i != j

其邻接矩阵为

Ai,j(G)=Aj,i(G)=e(i,j),i≠jA_{i, j}(G) = A_{j , i}(G) = e(i, j), i \not= j

其拉普拉斯矩阵为

L(G)=D(G)−A(G)L(G) = D(G) - A(G)

有向图

设GG是一个有nn个顶点的有向图， 定义其出度矩阵为

Diiout(G)=degout(i),Dijout=0,i≠jD^{out}_{ii}(G) = \mathrm{deg^{out}}(i), D^{out}_{ij} = 0, i\neq j

类似的入度矩阵也这样定义

定义其邻接矩阵为

Ai,j=e(i,j), i≠jA_{i,j} = e(i, j), \ i \not = j

其拉普拉斯矩阵LoutL^{out}为

Lout(G)=Dout(G)−A(G)L^{out}(G) = D^{out}(G) - A(G)

LinL^{in}为

Lin(G)=Din(G)−A(G)L^{in}(G) = D^{in}(G) - A(G)

带权-乘积之和

对于带权无向图，若存在边u→vu\rightarrow v，边权为cc， 则Dx,x+c,Dy,y+c,Ax,y+c,Ay,x+cD_{x, x} + c, D_{y,y} + c, A_{x, y} + c, A_{y, x} + c。删去任意一行和任意一列，求剩下的矩阵行列式即可。

对于带权有向图，若存在边u→vu \rightarrow v，边权为cc，外向树中Dy,y+cD_{y, y} + c， 内向树中Dx,x+cD_{x, x} + c， 内向树和外向树中Ax,y+cA_{x, y} + c。删去指定的根所在的行和列，求剩下的矩阵行列式即可。

P6178Matrix-Tree 定理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 310;
const int mod = 1e9 + 7;


ll D[N][N], A[N][N], L[N][N];

int n, m, t;

void add(int u, int v, int c, int type)
{
    if(t == 0)
    {
        (D[u][u] += c) %= mod;
        (D[v][v] += c) %= mod;
        (A[u][v] += c) %= mod;
        (A[v][u] += c) %= mod;
    }
    else
    {
        (D[v][v] += c) %= mod;
        (A[u][v] += c) %= mod;
    }
}

ll ans;

void gauss()
{
    ll f = 1;
    for(int i = 2; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            while(L[i][i])
            {
                ll div = L[j][i] / L[i][i];
                for(int k = i; k <= n; k++)
                    L[j][k] = ((L[j][k] -  L[i][k] * div % mod) % mod + mod) % mod;
                swap(L[i], L[j]);
                f = -f;
            }
            f = -f;
            swap(L[i], L[j]);
        }
    }
    ans = f;
    for(int i = 2; i <= n; i++)
        ans = (ans % mod * (L[i][i] + mod) % mod + mod) % mod;
}

int main()
{
    scanf("%d%d%d", &n, &m, &t);
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z, t);
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            L[i][j] = (D[i][j] - A[i][j] + mod) % mod;
    gauss();
    printf("%lld", ans);
    return 0;
}

带权-权值之和

上面的构造方式只是求了每个生成树边权乘积的和， 接下来需要解决，每个生成树边权之和的和，对于一条边权为ww的边，只需要将边权设为关于xx的多项式wx+1wx + 1，消元后最后的行列式的值的一次项系数就是答案， 对应的乘法改为(a+bx)(c+dx)=ac+(ad+bc)x(a + bx) (c + dx) = ac + (ad + bc)x，除法为a+bxc+dx=ac+bc−adc2x\frac{a + bx} {c + dx} = \frac{a}{c} + \frac{bc - ad}{c ^ 2}x，接下来证明一下构造方式的正确性，我们需要求的答案其实可以表示为每个边权×\times含有这条边权的生成树的个数，就可以构造一个多项式来求解，（老套路了），首先乘法的定义很好理解，说一下除法的，首先我们需要求的是C+Dx=1c+dxC + Dx = \frac{1}{c + dx}，即(C+Dx)(c+dx)=1 mod x2(C + Dx)(c + dx) = 1 \bmod x^2，展开即可得到C=1c,D=−dc2C = \frac{1}{c}, D = -\frac{d}{c^2}，然后再乘上a+bxa + bx，就可以得到新的式子为ac+bc−adc2x\frac{a}{c} + \frac{bc - ad}{c^2}x。

P6624 作业题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 310;
const int mod = 1e9 + 7;


ll D[N][N], A[N][N], L[N][N];

int n, m, t;

void add(int u, int v, int c, int type)
{
    if(t == 0)
    {
        (D[u][u] += c) %= mod;
        (D[v][v] += c) %= mod;
        (A[u][v] += c) %= mod;
        (A[v][u] += c) %= mod;
    }
    else
    {
        (D[v][v] += c) %= mod;
        (A[u][v] += c) %= mod;
    }
}

ll ans;

void gauss()
{
    ll f = 1;
    for(int i = 2; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            while(L[i][i])
            {
                ll div = L[j][i] / L[i][i];
                for(int k = i; k <= n; k++)
                {
                    L[j][k] = ((L[j][k] -  L[i][k] * div % mod) % mod + mod) % mod;
                }
                swap(L[i], L[j]);
                f = -f;
            }
            f = -f;
            swap(L[i], L[j]);
        }
    }
    ans = f;
    for(int i = 2; i <= n; i++)
        ans = (ans % mod * (L[i][i] + mod) % mod + mod) % mod;
}

int main()
{
    scanf("%d%d%d", &n, &m, &t);
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z, t);
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            L[i][j] = (D[i][j] - A[i][j] + mod) % mod;
    gauss();
    printf("%lld", ans);
    return 0;
}

后记

证明以后再补吧（逃

矩阵树定理

https://jekyll-y.github.io/2022/09/18/矩阵树定理/

作者

Jekyll_Y

发布于

2022-09-18

更新于

2023-03-02

许可协议

#

评论

Follow
×