Matrix-Tree定理和模意义下的矩阵行列式

最近读了《生成树的计数及其应用》一文，学到了Matrix-Tree定理大法，应用于无向图生成树计数问题，屡试不爽。然而原文中证明稍有不足，有些地方思维莫名跳跃，令我等难以跟上作者思路。还有一些线性代数的预备知识的写法确实不妥（比如奇偶排列的定义）。以下我把原论文结合自己的想法记录下来，以备将来查验。

重要提示：本文禁止任何形式的转载。若你觉得本文对你有帮助，你可以与别人分享，但不允许上传到各文库平台。

提示：阅读本文可能（不）需要基本的线性代数知识和基本的图论知识。

---

定义1（矩阵）：略。

定义2（行列式）：略。

定理1（行列式的基本性质）：

1. 交换任意两行（列），行列式变号。
2. 把某一行（列）乘上一个常数，行列式也乘上该常数。
3. 把一行（列）乘上一个常数加到另一行（列）上，行列式不变。
4. $det(A)=det(A^T)$

推论1：若矩阵中某一行（列）全为$0$，则行列式为$0$。

定理2：若一个方阵各行（或各列）的元素之和都为$0$，则该方阵行列式为$0$。（选定任意一列（行），把其余各列（各行）依次加到该列（行）上，然后这一列（行）就全变成了$0$，根据上面的推论就得出了结果）

定理3（拉普拉斯展开定理的推论）：

$$det begin{pmatrix} A & C \ 0 & B \ end{pmatrix} =det(A) det(B)$$
定义3（分块对角矩阵）：除主对角线上的矩阵之外，其余元素皆为零矩阵的分块矩阵。

定理4：分块对角矩阵的行列式等于主对角线上的矩阵行列的乘积。（可用定理3立即推出，或者运用初等变换把各个子矩阵消成上三角矩阵也可以看出来）

定理5：Cauchy–Binet formula（柯西–比内公式）
（记法有很多种，意思都是一样的，我选择了一种比较简洁规范的写法）

首先，设$mle n$。令$A$是$mtimes n$的矩阵，$B$是$n times m$的矩阵，$psi$是从${1dots m}$到${1dots n}$的函数，满足$psi(1) <psi(2)<dots<psi(m)$，令$A_psi$表示从$A$中选择$psi(1)dotspsi(m)$这$m$列得到的新矩阵，$B_psi$表示从$B$中选择$psi(1)dotspsi(m)$这$m$行得到的新矩阵，则有

$$det(A B) = sum_{psi} {det(A_{psi}) det(B_{psi})}$$
特别地，若 $A$是方阵，有 $det(A B) = det(A)det(B)$，令 $B=A^T$就得到 $det(A A^T)=det(A)det(A^T)=det^2(A)$
顺便说一句，若 $m>n$， $det(A B)=0$

定义5（子式和主子式）：在矩阵中选取相等数量的行和列之后所产生的方阵的行列式；若行和列的编号一致，就称为主子式。

---

定义一个图$G$的Kirchhoff矩阵$C$为

$$C_{ij} = begin{cases} text {the degree of $i$}, & text {if $i$ = $j$} \ -1, & text {if $i$ $ne$ $j$ and (i, j)$in$G(E)} \ 0, & text {if $i$ $ne$ $j$ and (i, j)$notin$G(E)} end{cases}$$
我们要证明的结论是：

$G$的所有不同的生成树的个数等于$C$中任何一个$n-1$阶主子式（原文中的说法是“主子式的行列式”

最后

以上就是土豪猎豹为你收集整理的Matrix-Tree定理和模意义下的矩阵行列式的全部内容，希望文章能够帮你解决Matrix-Tree定理和模意义下的矩阵行列式所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。