行列式 / 矩阵树定理 / BEST 定理 笔记

一、行列式

对于一个 $n\times n$ 的（即 $n$ 阶的）矩阵 $A$，定义它的行列式

$$det(A)=\sum _p((-1{)}^{\mu (p)+1}\prod _{i=1}^n{A}_{i,p_i})$$

其中 $p_{1\dots n}$ 是 $n$ 的一个排列，$\mu (p)$ 在这里表示 $p$ 的逆序对对数。

定理 1

对于一个右上三角矩阵 $A$（$\mathrm{\forall }i$，第 $i$ 行只有 $A_{i,[i,n]}\ne 0$ 矩阵），$det(A)=\prod _{i=1}^n{A}_{i,i}$。

证明：考虑构造使得乘积不为 $0$ 的排列 $p$，第 $n$ 行只能选择 $A_{n,n}$，即 $p_n=n$，第 $n-1$ 行只能选择 $n-1,n$，其中 $n$ 已被选择，故 $p_{n-1}=n-1$，可以得到 $p_i=i$，此时 $p$ 中没有逆序对。

定理 2

交换 $A_i,A_j(i<j)$ 两行得到 $A^{\prime }$，$det(A^{\prime })=-det(A)$。

证明：原操作相当于交换 $p_i,p_j$，考虑 $p$ 中逆序对个数的变化。分类讨论可以证明变化总是奇数，故 $-1$ 的指数奇偶改变，取反。

定理 3

将某行的每一个数乘上一个数 $k$，$det(A^{\prime })=kdet(A)$。

证明：因为每一行只取一个数，故在每次乘积上都乘了个 $k$。

定理 4

有两行相同的矩阵，$det=0$。

证明：由定理 2，交换这两行，$det$ 取反，但是交换前后矩阵一致，故 $det=0$。

定理 5

$$\left|\begin{array}{cc}a+c& b+d\\ e& f\end{array}\right|=\left|\begin{array}{cc}a& b\\ e& f\end{array}\right|+\left|\begin{array}{cc}c& d\\ e& f\end{array}\right|$$

证明：乘法分配律

定理 6

$$\left|\begin{array}{cc}a& b\\ c+ka& d+kb\end{array}\right|=\left|\begin{array}{cc}a& b\\ c& d\end{array}\right|$$

证明：$\left|\begin{array}{cc}a& b\\ ka& kb\end{array}\right|=\left|\begin{array}{cc}a& b\\ a& b\end{array}\right|=0$。

实现

根据定理 1 & 6，使用高斯消元 / 辗转相除法，即可求出行列式。

点击查看代码（高斯消元）

bool op = false;
for (int i = 1; i < n; i++) {
    for (int j = i; j < n; j++)
        if (a[j][i]) {
            if (j != i)
                op ^= 1;
            swap(a[i], a[j]);
            break;
        }
    if (!a[i][i]) {
        cout << 0;
        return 0;
    }
    ans = ans * a[i][i] % mod;
    for (int j = i + 1; j < n; j++) {
        int x = a[j][i] * inv(a[i][i]) % mod;
        for (int k = i; k < n; k++)
            a[j][k] = (a[j][k] - a[i][k] * x % mod + mod) % mod;
    }
}
cout << (op ? (mod - ans) % mod : ans);

点击查看代码（辗转相除法）

bool op = false;
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] % mod + mod) % mod;
            swap(a[i], a[j]);
            op ^= 1;
        }
        swap(a[i], a[j]);
        op ^= 1;
    }
    ans = ans * a[i][i] % mod;
}
cout << (op ? (mod - ans) % mod : ans);

二、余子式

注意本节符号与其它节的不同。

定义

假设 $n$ 阶矩阵 $A$ 的第 $i$ 行第 $j$ 列是 $a_{i,j}$，将第 $i$ 行第 $j$ 列去掉，剩下的 $n-1$ 阶矩阵的行列式记作 $M_{i,j}$，称为“余子式”。

令 $A_{i,j}=(-1{)}^{i+j}{M}_{i,j}$，称为“代数余子式”。

与主子式的关系

选定一个 $i$，则有

$$detA=\sum _{j=1}^n{a}_{i,j}{A}_{i,j}$$

选定一个 $j$，也有

$$detA=\sum _{i=1}^n{a}_{i,j}{A}_{i,j}$$

太菜了，不会证明啊。

三、矩阵树定理

1. 无向图无权情况

定义 $D_{i,i}={\mathrm{deg}}_i$，$A_{i,j}$ 表示是否有边 $i-j$。

定义 $L=D-A$，将 $L$ 的第 $i$ 行与第 $i$ 列（$i$ 可取任意数）删去后，$det(L)$ 即为图的生成树个数。

2. 有向图外向树

外向树，即从根指向四周。

定义 $D_{i,i}={\mathrm{indeg}}_i$，$A_{i,j}$ 表示是否有边 $i\to j$。

删去 $L$ 的第 $i$ 行与第 $i$ 列，则表示以 $i$ 为根。

3. 有向图内向树

内向树，即从四周指向根。

定义 $D_{i,i}={\mathrm{outdeg}}_i$，$A_{i,j}$ 表示是否有边 $i\leftarrow j$。

4. 重边情况

将“是否有边”改成“边的个数即可”。

5. 刷题总结

(1). P6178 【模板】Matrix-Tree 定理

生成树的权值是边权的乘积，其意义就是在一条边有边权种选择，本质就是重边。

(2). P4208 [JSOI2008] 最小生成树计数

将边权 $w$ 从小到大考虑，当考虑到 $w$ 时，小于 $w$ 的边权一定已经将树连成了若干个连通块，按照 Kruskal，每个连通块包含的点集一定是确定的，可以考虑反证法，如果包含的点集不确定，那么这多种点集必然可以合并进一个更大的点集。

将连通块缩点后，对 $w$ 的边做生成树计数即可，各个边权的答案独立，使用乘法原理解决。

(3). P2144 [FJOI2007] 轮状病毒

裸的矩阵树定理就能做，但是 $n=100$ 还要跑高精度还是太慢了，有没有更快的方法？

分析一下矩阵 $L$（注意有 $n+1$ 个点）。

$$\left|\begin{array}{ccccccc}n& -1& -1& -1& \dots & -1& -1\\ -1& 3& -1& 0& \dots & 0& -1\\ -1& -1& 3& -1& \dots & 0& 0\\ -1& 0& -1& 3& \dots & 0& 0\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ -1& 0& 0& 0& \dots & 3& -1\\ -1& -1& 0& 0& \dots & -1& 3\end{array}\right|$$

那矩阵树定理做 $n$ 阶矩阵肯定去掉神秘的第一行第一列，变成：

$$\left|\begin{array}{cccccc}3& -1& 0& \dots & 0& -1\\ -1& 3& -1& \dots & 0& 0\\ 0& -1& 3& \dots & 0& 0\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& \dots & 3& -1\\ -1& 0& 0& \dots & -1& 3\end{array}\right|$$

设 $n$ 阶这玩意的行列式是 $A_n$，要求的最终答案就是 $A_n$。

可是 $(1,n)$ 和 $(n,1)$ 的 $-1$ 还是破坏了矩阵的规律，考虑用余子式和主子式的关系。

选定第一行做行列式向代数余子式的转换。

删除 $(1,1)$

$$\left|\begin{array}{cccccc}3& -1& 0& \dots & 0& -1\\ -1& 3& -1& \dots & 0& 0\\ 0& -1& 3& \dots & 0& 0\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& \dots & 3& -1\\ -1& 0& 0& \dots & -1& 3\end{array}\right|$$

则得到

$$3\times (-1{)}^{1+1}\times \left|\begin{array}{ccccc}3& -1& \dots & 0& 0\\ -1& 3& \dots & 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \dots & 3& -1\\ 0& 0& \dots & -1& 3\end{array}\right|$$

这回右边的矩阵很有规律了，记 $n$ 阶这玩意的行列式是 $B_n$，则删除 $(1,1)$ 得到 $3B_{n-1}$

删除 $(1,2)$

$$\left|\begin{array}{cccccc}3& -1& 0& \dots & 0& -1\\ -1& 3& -1& \dots & 0& 0\\ 0& -1& 3& \dots & 0& 0\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& \dots & 3& -1\\ -1& 0& 0& \dots & -1& 3\end{array}\right|$$

则得到

$$-1\times (-1{)}^{1+2}\times \left|\begin{array}{ccccc}-1& -1& \dots & 0& 0\\ 0& 3& \dots & 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \dots & 3& -1\\ -1& 0& \dots & -1& 3\end{array}\right|$$

考虑再对这个矩阵的第一列做转化，当选中 $(1,1)$ 时为 $-1\times (-1{)}^{1+1}\times B_{n-2}=-B_{n-2}$；当选中 $(n-1,1)$ 时发现变成了一个左下三角矩阵，且对角线皆为 $-1$，则这一部分是 $-1\times (-1{)}^{n-1+1}\times (-1{)}^{n-2}=(-1{)}^{2n-1}=-1$。总的就是 $-1\times (-1{)}^{1+2}\times (-B_{n-2}-1)=-B_{n-2}-1$。

删除 $(1,n)$，得

$$-1\times (-1{)}^{1+n}\times \left|\begin{array}{ccccc}-1& 3& -1& \dots & 0\\ 0& -1& 3& \dots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \dots & 3\\ -1& 0& 0& \dots & -1\end{array}\right|$$

同上，选中第一列做转化，当选中 $(n-1,1)$ 时为 $-1\times (-1{)}^{n-1+1}\times B_{n-2}=(-1{)}^{n+1}\times B_{n-2}$；当选中 $(1,1)$ 时为右上三角矩阵，对角线皆为 $-1$，$-1\times (-1{)}^{1+1}\times (-1{)}^{n-2}=(-1{)}^{n+1}$。总的即为 $-1\times (-1{)}^{1+n}\times [(-1{)}^{n+1}\times B_{n-2}+(-1{)}^{n+1}]=-B_{n-2}-1$。

终于，我们得到了 $A_n=3B_{n-1}-2B_{n-2}-2$。

接着考虑求 $B$ 的递推式，用“删除 $(1,2)$”时相同的方法推两次即可以得到 $B_n=3B_{n-1}-B_{n-2}$。

用复杂的线性代数知识就可以得到 $A_n=3A_{n-1}-A_{n-2}+2$，我太菜了实在不会 QAQ。

四、BEST 定理

对于一个有向图的欧拉回路，将除了起点 $s$ 以外每个点的最后走的一条出边，构成一棵树，可以得到一棵以 $s$ 为根的内向树。

假如走出了环，回路最后一定要回到 $s$，而在点 $x$ 最后走的一条边走出了一个环，再次回到点 $x$ 后它将无边可走，不能回到 $s$。

起点有 ${\mathrm{deg}}_s!$（$\mathrm{deg}$ 是出度）种排列选择的可能，其它每个点还有 $({\mathrm{deg}}_i-1)!$ 种可能，所以总欧拉回路数是

$$T\times ({\mathrm{deg}}_s)!\times \prod _{i\ne s}({\mathrm{deg}}_i-1)!$$

其中 $T$ 是图的内向树个数。

若无规定起点，则要除去循环同构的部分。$s$ 在欧拉回路序列中一共出现了 ${\mathrm{deg}}_s$ 次，将这 ${\mathrm{deg}}_s$ 个位置分别移动到序列开头，并将选中位置的前面丢到序列末尾，这样产生了 ${\mathrm{deg}}_s$ 个循环同构的欧拉回路，除去他们。

$$T\times \prod ({\mathrm{deg}}_i-1)!$$