这篇博客主要是对矩阵树的一些简要总结。
一、矩阵树定理基本形式与证明思路
矩阵树定理基本形式：一个无向图的生成树个数等于其拉普拉斯矩阵(度数矩阵-邻接矩阵)的任一余子式的值。
证明思路：
1、定义$E(G)$为无向图$G$的关联矩阵，若图$G$有$n$个点，$m$条边，则$E(G)$有$n$行$m$列。其定义如下(用$E$代指$E(G)$)：
其中$u_j$，$v_j$分别表示第$j$条边的两个端点。注意到这是一个无向图，所以$u_j$,$v_j$的顺序可以调换。
定义$E’(G)$为$E(G)$去掉任意一行产生的矩阵。
定理：如果图$G$为一棵树(此时$m=n-1$，$E’(G)$有$n-1$行$n-1$列)，$det(E’(G))^2=1$，否则$det(E’(G))^2=0$(产生了线性组合)。
由上，有：
其中$G$为待计算的图，组合数代表图$G$中任意$n-1$条边组成的新图。
2、定理(Cauchy-Binet公式)：
$[n]$代表$1-n$所有整数组成的集合，组合数代表其大小为$m$的子集。
该公式中，矩阵$A$有$m$行$n$列，$B$有$n$行$m$列。矩阵下标代表该矩阵提出(行集合$*$列集合)组成的子矩阵。
结合该公式与答案式，有：
3、定理：
其中$mat(G)$为$G$的邻接矩阵($mat(G)_{ij}=i$与$j$之间边的数量)，$deg(G)$为$G$的度数矩阵($deg(G)_{ij}=[i=j]i$的度数)。$L=deg(G)-mat(G)$，即图$G$的拉普拉斯矩阵。
这个很好证，考察左式的定义即可。
由于$E’(G)$为$E(G)$去掉任意一行得到，所以有:
其中$det(L’)$为$L$去掉$i$行$i$列的余子式$M_{ii}$($i$为不大于$n$的任意正整数)。
二、变元矩阵树定理
若将邻接矩阵定义为($mat(G)_{ij}=i与j之间边权和$)，度数矩阵定义为($deg(G)_{ij}=[i=j]i$相连边的边权和)，则：
$T$为图$G$所有生成树，$e$为图$G$中的边，$w_e$为$e$的边权。注意这里的边权可以为实数。
这个定理可以将矩阵树基本定理推广到概率等加强形式。
三、有向图矩阵树定理
将邻接矩阵定义为($mat(G)_{ij}=i$到$j$的边数量)，将度数矩阵定义为($deg(G)_{ij}=[i=j]i$的入度)，则$L$去掉第$i$行$i$列得到的余子式$M_{ii}=$以点$i$为根的外向生成树个数。
若将度数矩阵定义为($deg(G)_{ij}=[i=j]i$的出度)，则$L$去掉第$i$行$i$列得到的余子式$M_{ii}=$以点$i$为根的内向生成树个数。
变元矩阵树定理同样适用于有向图。