最近读了《生成树的计数及其应用》一文，学到了Matrix-Tree定理大法，应用于无向图生成树计数问题，屡试不爽。然而原文中证明稍有不足，有些地方思维莫名跳跃，令我等难以跟上作者思路。还有一些线性代数的预备知识的写法确实不妥（比如奇偶排列的定义）。以下我把原论文结合自己的想法记录下来，以备将来查验。 重要提示：本文禁止任何形式的转载。若你觉得本文对你有帮助，你可以与别人分享，但不允许上传到各文库平台。 提示：阅读本文可能（不）需要基本的线性代数知识和基本的图论知识。

---

定义1（矩阵）：略。 定义2（行列式）：略。 定理1（行列式的基本性质）：

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

推论1：若矩阵中某一行（列）全为0，则行列式为0。 定理2：若一个方阵各行（或各列）的元素之和都为0，则该方阵行列式为0。（选定任意一列（行），把其余各列（各行）依次加到该列（行）上，然后这一列（行）就全变成了0，根据上面的推论就得出了结果） 定理3（拉普拉斯展开定理的推论）：
det(A0CB)=det(A)det(B)
定义3（分块对角矩阵）：除主对角线上的矩阵之外，其余元素皆为零矩阵的分块矩阵。 定理4：分块对角矩阵的行列式等于主对角线上的矩阵行列的乘积。（可用定理3立即推出，或者运用初等变换把各个子矩阵消成上三角矩阵也可以看出来） 定理5：Cauchy–Binet formula（柯西–比内公式）
（记法有很多种，意思都是一样的，我选择了一种比较简洁规范的写法） 首先，设m≤n。令A是m×n的矩阵，B是n×m的矩阵，ψ是从{1…m}到{1…n}的函数，满足ψ(1)<ψ(2)<⋯<ψ(m)，令Aψ表示从A中选择ψ(1)…ψ(m)这m列得到的新矩阵，Bψ表示从B中选择ψ(1)…ψ(m)这m行得到的新矩阵，则有
det(AB)=∑ψdet(Aψ)det(Bψ)
特别地，若A是方阵，有det(AB)=det(A)det(B)，令B=AT就得到det(AAT)=det(A)det(AT)=det2(A)
顺便说一句，若m>n，det(AB)=0 定义5（子式和主子式）：在矩阵中选取相等数量的行和列之后所产生的方阵的行列式；若行和列的编号一致，就称为主子式。

---

定义一个图G的Kirchhoff矩阵C为Cij=⎧⎩⎨the degree of i,−1,0,if i = jif i ≠ j and (i, j)∈G(E)if i ≠ j and (i, j)∉G(E)
我们要证明的结论是： G的所有不同的生成树的个数等于C中任何一个n−1阶主子式（原文中的说法是“主子式的行列式”，我认为不妥，因为子式的定义就已经包含了行列式。而且原论文用了绝对值的说法，不过按照证明，并不需要取绝对值）。我们把这个主子式对应的矩阵记为Cr，表示从