矩阵树定理

· · 个人记录

行列式默认大家都会。不会的可以买本线性代数看看，反正早晚都要学。对吗

首先介绍 Prufer序列（可跳过，和矩阵树定理没有什么关联）

Prufer序列 身份证：

形态：一个序列

对象：一棵树

作用：用一个序列去唯一表示一棵树。

具体是怎么做到的呢？我们来采访一下 Prufer先生

Prufer:见笑，见笑。其实我也没干什么。只是在无根树的情况，依次把度数为1，编号最小节点取了出来，并把它唯一连接的那个点的编号加到了序列里。在有根树的情况下。依次把编号最小的叶子结点取了出来，并把它的父亲放在了序列里。

我们可以发现，对于有根树的Prufer序列，最后一个数字一定是根节点的编号。

对于任意一个Prufer序列，我们也有简单的 n\log n 的模拟算法（有 O(n) 算法，此处略去不表）将其还原成树。我们首先维护一个备选"堆"，把Prufer序列里没出现的数字放到堆里面，一边扫Prufer序列，一边把堆里最小的挑出来，认Prufer序列扫到的那个数为爹。如果Prufer序列的这个数是它最后在序列里出现的话，那么把它也放在堆里面，这样就做完了。

这样我们就引出一个结论：n 个节点能构成 n^{n-2} 个有根树， n^{n-1} 个无根树。

矩阵树，它求的其实是

\sum\limits_{T为G(V,E)的生成树}\prod\limits_{E∈T}w(E)

看到和和乘，要注意其组合意义。看到 w(E)，要想到可以给它赋各种各样的权值来满足我们的目的。

可以先令 w(E)=1，这样就把问题变成了生成树计数。然后再扩展到 w(E) ∈ N 的情况，对于 w(E)=C，可以看作是 (u,v) 间连了 C 条边，你暗自想着。

就在这时，你的数学老师进来了，分发着一张试卷：同学们，我们开一个小灶！

试卷上的第一题写着：矩阵 A 是一个 n*m 的矩阵，B 是一个 m*n 的矩阵，证明

\det(AB)=\sum\limits_{S为1\cdots m选n个数}det(A里所有S列)det(B里所有S行)

你突然想到，当初证明 \det(A)\det(B)=\det(AB) (其中 A,B 都是方程)，是使用了\begin{bmatrix}A&O\\-E&B\end{bmatrix}作变换。

作为一个线性代数会举一反三的同学，你构造出了如下方阵。

\begin{bmatrix}A&O\\-E_{m}&B\end{bmatrix}

由于已经有了方阵行列式的性质，所以你和当初证明 \det(A)\det(B)=\det(AB) 有了不同，直接用矩阵乘法代表你的矩阵变换。

\begin{bmatrix}E_n&A\\O_{mn}&E_m\end{bmatrix}\begin{bmatrix}A&O\\-E_{m}&B\end{bmatrix}=\begin{bmatrix}O&AB\\-E_{m}&B\end{bmatrix}

第一个矩阵行列式是 1

因此我们有 \begin{vmatrix}A&O\\-E_{m}&B\end{vmatrix}=\begin{vmatrix}O&AB\\-E_{m}&B\end{vmatrix}

LHS: 上 n 行和右 n 列都要选，剩下的 m-n 是在 E_m 里选，也就是说对于 E_m 一共最多只能有 n 个 -1 被消掉了。也就是说 A 和 B 选取的是同样的行，同样的列！

RHS:直观感觉等于 ±\det(AB)

不要纠结正负了，其实关系不大。最后正负是对的。

这是 Binet-Cauchy 定理。

小灶结束，你继续在OI的海洋里自在探索。

首先我们讨论无向图的情况。

\det(AB)=\sum\limits_{S为1\cdots m选n个数}det(A里所有S列)det(B里所有S行)

构造 A_{n*m} ，对于第 i 条无向边 (u,v)，令 A_{u,i}=1,A_{v,i}=-1 (这里顺序不要紧)，然后对于 B_{n*m}，令 B_{i,u}=1,B_{i,v}=-1

令 C=AB，我们发现

C=\begin{bmatrix}\sum w_{(1,*)}&-w_{(1,2)}&-w_{(1,3)}&\cdots&-w_{(1,n)}\\-w_{(2,1)}&\sum w_{(2,*)}&-w_{(2,3)}&\cdots&-w_{(2,n)}\\-w_{(3,1)}&-w_{(3,2)}&\sum w_{(3,*)}&\cdots&-w_{(3,n)}\\\vdots&\vdots&\vdots&\vdots&\vdots\\-w_{(n,1)}&-w_{(n,2)}&-w_{(n,3)}&\cdots&\sum w_{(n,*)}&\end{bmatrix}

最后，我们删除 C 中一行一列（必须行号 =1 列号，这里假设删掉第一行），它的行列式就是最终的答案。

较为容易发现，这时的 C 相当于把 A 中的第 rt 行， B 中的第 rt 列去除，然后再乘起来的结果。

至于证明，我们先讨论 w(E)=1 的情况，从 A 和 B 入手。分为两个方面，一方面是生成树能够对答案产生 +1 的贡献，一方面是如果这里面有环贡献一定是 0。

两方面都蛮好证的，第一方面，我们搞出了一棵树，然后给这棵树建立 dfs 序，如果节点 i 的 dfs 序是 x，代表它和它的父亲对应的那条边，在 A 上将会被转到第 x 行。这样很容易看出来是一个上三角/下三角矩阵，\det 只能是 ±1

又 B=A^T，所以 det(B')=det(A')，最后出来就是 1

如果有环，此时注意一号节点需要特判。结果表明，无论有没有一号节点，只要有环。这个方阵的 n 个列向量就一定线性相关，从而行列式就是 0

这样子，我们再推到 w(E)∈N 的情况，把 E(u,v) 拆成 W(E) 条边，对应在两个矩阵上乱搞，最后出来的方阵 C 仍然和 w(E)=1 的形态一致！

恭喜你！无向图的情况被你解决了，现在我们来解决有向图的情况。

有向图，有根树，且要确定方向！

这里以外向图为例子！（外向，指从 root 开始就外向，从父亲指向儿子！）

这里，我们对 A 和 B 动一些手脚， A 负责没有环， B 负责外向。

我们发现，没有环且联通的情况下，外向当且仅当每个节点只被指向一次（除了根节点！）

所以我们要让存在节点被指向多次的选取方案，其行列式为 0 （线性相关），每个节点(除rt)被指向一次的选取方案，其行列式为 ±1，并和 A 中对应选取方案的行列式保持一致

这样看来就很明显了，对于第 i 条边 u -> v，我们只记 B_{i,y}=1，然后 A 中不得胡闹！必须得是 A_{x,i}=-w_i,A_{y,i}=w_i，以此和 B 的行列式保持一致（具体是为什么我没去想）

然后最后出来的 C=AB 就满足

C=\begin{bmatrix}\sum\limits_{j} w_{j→1}&-w_{1→2}&-w_{1→3}&\cdots&-w_{1→n}\\-w_{2→1}&\sum\limits_{j} w_{j→2}&-w_{2→3}&\cdots&-w_{2→n}\\-w_{3→1}&-w_{3→2}&\sum\limits_{j} w_{j→3}&\cdots&-w_{3→n}\\\vdots&\vdots&\vdots&\vdots&\vdots\\-w_{n→1}&-w_{n→2}&-w_{n→3}&\cdots&\sum\limits_{j} w_{j→n}&\end{bmatrix}

注意最后要把第rt行第rt列给去掉！原因在B矩阵中已经很明显了。