行列式与矩阵树定理
行列式与矩阵树定理
行列式的定义
行列式(\(\mathrm{Determinant}\)) 是一个函数定义， 取值是一个标量。
对于一个 \(n \times n\) 的矩阵 \(A\)， 它的行列式写作 \(\mathrm{det}(A)\) 或 \(|A|\)， 定义为 ：
\(\sum\limits_{p}(-1)^{\tau(p)}\prod\limits_{i=1}^{n}a_{i,p_i}\)
\(p\) 表示一个 \(1 \dots n\) 的排列， \(\tau(p)\) 表示 \(p\) 的逆序对个数。
行列式的性质
-
互换矩阵的两行或两列， 行列式的值取反。
-
互换矩阵的一行和一列， 行列式的值不变。
-
矩阵某一行（一列）的值 \(\times k\)， 行列式的值 \(\times k\)。
-
如果矩阵 \(A\) 的某一行（列）是另外两个矩阵 \(B\) , \(C\) 的此行（列）的和， \(B, C\) 其他元素与 \(A\) 相同， 则 \(\mathrm{det}(A) = \mathrm{det}(B) + \mathrm{det}(C)\)。
-
如果矩阵两行(列)互为比例关系， 则 \(\mathrm{det}(A) = 0\)。
-
把矩阵的一行全部乘上一个数再加在另一行， \(\mathrm{det}(A)\) 不变。
代数余子式
在一个 \(n\) 阶行列式 \(D\) 中选出 \(k\) 行 \(k\) 列组成一个 \(k\) 阶子行列式。
删除在 \(k\) 行 \(k\) 列后剩下的行列式记作 \(n - k\) 阶余子式。
设 \(A\) 在 \(D\) 中原来的元素行下标有集合\(\mathbb{I=\{i_1,i_2 ,\dots ,i_k\}}\) 列下标有集合\(\mathbb{ J=\{j_1,j_2 ,\dots ,j_k\}}\)，则有 \(\displaystyle(-1)^{\displaystyle(i_1+i_2+\dots+i_k)(j_1+j_2+\dots+j_k)}\times \det(M)\) 为 \(n\) 阶行列式 \(D\) 的 \(k\) 阶子式 \(A\) 的代数余子式。
对于单一元素 \(a_{i, j}\)， 我们令其代数余子式为 \(A_{i, j}\)， 余子式为 \(M_{i, j}\)。
行列式求值
由于性质 6, 直接用高斯消元把矩阵消成只剩主对角线， 此时 \(\mathrm{det}(A)\) 等于所有元素的乘积。但由于在消元中交换了行， 由于性质 1， 还要再记录交换的次数。
矩阵树定理
给定一个无向无权图 \(G\)， 设 \(D\) 为度数矩阵， 当 \(i = j\) 时， $D_{i, j} $ 等于点 \(i\) 的度数， \(i \neq j\) 时， \(D_{i, j} = 0\)。
设邻接矩阵 \(A\)， \(A_{i, j}\) 表示 \(i, j\) 之间的边的条数。
定义图 \(G\) 的 基尔霍夫 \(\mathrm{Kirchhoff}\) 矩阵 \(C = D - A\)。
矩阵树定理 ： \(G\) 的所有不同的生成树的个数等于 \(C\) 中任何一个 \(n - 1\) 阶主子式的行列式的绝对值。
例题 ：
[省选联考 2020 A 卷] 作业题
题意 ： 给定图 \(G\)， 求所有生成树的价值， 其中价值定义为 ：
\(val(T) = \sum\limits_{i=1}^{n - 1}w_i \times \gcd(\sum\limits_{i=1}^{n - 1}w_i)\)
设 \(\gcd(\sum\limits_{i=1}^{n-1}w_i) = S\)。
首先一坨 \(\gcd\) 可以欧拉反演或莫比乌斯反演掉。
\(S=\sum\limits_{d|S}\varphi(d)\)， 相当于所有 \(S\) 的倍数的边权做一次矩阵树。
但是本题要求生成树的权值之和， 而普通的是计算乘积。
我们把一条边看成一个一次多项式 \(F(x) = 1 + kx\)， 其中 \(k\) 是这条边的权值。
不难发现多项式乘起来之后的一次项 \(G(x)[1] = \sum\limits_{e}w_e\)。
多项式怎么求逆 ？ 设原多项式为 \(a +bx\)， 则我们要求一个 \(c+dx\) 使得 \((a+bx)(c+dx) = 1 (\mod(x^2))\)
简单拆一下可得 \(ac = 1, bc +ad = bd = 0\)， 显然 $c = a^{-1}, d = -b \cdot a^{-1} \cdot a^{-1} = -b \cdot a^{-2} $。
所以逆等于 \((a^{-1}, -ba^{-2})\)。
LGV引理
引理介绍 ：