专栏文章

矩阵树定理

aaSunnyDay
个人记录参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqcn1yi
此快照首次捕获于
2025/12/04 02:37
3 个月前
此快照最后确认于
2025/12/04 02:37
3 个月前
查看原文
行列式默认大家都会。不会的可以买本线性代数看看，反正早晚都要学。对吗
首先介绍 Prufer序列（可跳过，和矩阵树定理没有什么关联）
Prufer序列 身份证：
形态：一个序列
对象：一棵树
作用：用一个序列去唯一表示一棵树。
具体是怎么做到的呢？我们来采访一下 Prufer先生
Prufer:见笑，见笑。其实我也没干什么。只是在无根树的情况，依次把度数为1，编号最小节点取了出来，并把它唯一连接的那个点的编号加到了序列里。在有根树的情况下。依次把编号最小的叶子结点取了出来，并把它的父亲放在了序列里。
我们可以发现，对于有根树的Prufer序列，最后一个数字一定是根节点的编号。
对于任意一个Prufer序列，我们也有简单的 nlog⁡nn\log n 的模拟算法（有 O(n)O(n) 算法，此处略去不表）将其还原成树。我们首先维护一个备选"堆"，把Prufer序列里没出现的数字放到堆里面，一边扫Prufer序列，一边把堆里最小的挑出来，认Prufer序列扫到的那个数为爹。如果Prufer序列的这个数是它最后在序列里出现的话，那么把它也放在堆里面，这样就做完了。
这样我们就引出一个结论：nn 个节点能构成 nn−2n^{n-2} 个有根树， nn−1n^{n-1} 个无根树。
矩阵树，它求的其实是
∑T为G(V,E)的生成树∏E∈Tw(E)\sum\limits_{T为G(V,E)的生成树}\prod\limits_{E∈T}w(E)
看到和和乘，要注意其组合意义。看到 w(E)w(E)，要想到可以给它赋各种各样的权值来满足我们的目的。
可以先令 w(E)=1w(E)=1，这样就把问题变成了生成树计数。然后再扩展到 w(E)∈Nw(E) ∈ N 的情况，对于 w(E)=Cw(E)=C，可以看作是 (u,v)(u,v) 间连了 CC 条边，你暗自想着。
就在这时，你的数学老师进来了，分发着一张试卷：同学们，我们开一个小灶！
试卷上的第一题写着：矩阵 AA 是一个 n∗mn*m 的矩阵，BB 是一个 m∗nm*n 的矩阵，证明
det⁡(AB)=∑S为1⋯m选n个数det(A里所有S列)det(B里所有S行)\det(AB)=\sum\limits_{S为1\cdots m选n个数}det(A里所有S列)det(B里所有S行)
你突然想到，当初证明 det⁡(A)det⁡(B)=det⁡(AB)\det(A)\det(B)=\det(AB) (其中 A,BA,B 都是方程)，是使用了[AO−EB]\begin{bmatrix}A&O\\-E&B\end{bmatrix}作变换。
作为一个线性代数会举一反三的同学，你构造出了如下方阵。
[AO−EmB]\begin{bmatrix}A&O\\-E_{m}&B\end{bmatrix}
由于已经有了方阵行列式的性质，所以你和当初证明 det⁡(A)det⁡(B)=det⁡(AB)\det(A)\det(B)=\det(AB) 有了不同，直接用矩阵乘法代表你的矩阵变换。
[EnAOmnEm][AO−EmB]=[OAB−EmB]\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}
第一个矩阵行列式是 11
因此我们有 ∣AO−EmB∣=∣OAB−EmB∣\begin{vmatrix}A&O\\-E_{m}&B\end{vmatrix}=\begin{vmatrix}O&AB\\-E_{m}&B\end{vmatrix}
LHS: 上 nn 行和右 nn 列都要选，剩下的 m−nm-n 是在 EmE_m 里选，也就是说对于 EmE_m 一共最多只能有 nn 个 −1-1 被消掉了。也就是说 AA 和 BB 选取的是同样的行，同样的列！
RHS:直观感觉等于 ±det⁡(AB)±\det(AB)
不要纠结正负了，其实关系不大。最后正负是对的。
这是 Binet−CauchyBinet-Cauchy 定理。
小灶结束，你继续在OI的海洋里自在探索。
首先我们讨论无向图的情况。
det⁡(AB)=∑S为1⋯m选n个数det(A里所有S列)det(B里所有S行)\det(AB)=\sum\limits_{S为1\cdots m选n个数}det(A里所有S列)det(B里所有S行)
构造 An∗mA_{n*m} ，对于第 ii 条无向边 (u,v)(u,v)，令 Au,i=1,Av,i=−1A_{u,i}=1,A_{v,i}=-1 (这里顺序不要紧)，然后对于 Bn∗mB_{n*m}，令 Bi,u=1,Bi,v=−1B_{i,u}=1,B_{i,v}=-1
令 C=ABC=AB，我们发现
C=[∑w(1,∗)−w(1,2)−w(1,3)⋯−w(1,n)−w(2,1)∑w(2,∗)−w(2,3)⋯−w(2,n)−w(3,1)−w(3,2)∑w(3,∗)⋯−w(3,n)⋮⋮⋮⋮⋮−w(n,1)−w(n,2)−w(n,3)⋯∑w(n,∗)]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}
最后，我们删除 CC 中一行一列（必须行号 =1=1 列号，这里假设删掉第一行），它的行列式就是最终的答案。
较为容易发现，这时的 CC 相当于把 AA 中的第 rtrt 行， BB 中的第 rtrt 列去除，然后再乘起来的结果。
至于证明，我们先讨论 w(E)=1w(E)=1 的情况，从 AA 和 BB 入手。分为两个方面，一方面是生成树能够对答案产生 +1+1 的贡献，一方面是如果这里面有环贡献一定是 00。
两方面都蛮好证的，第一方面，我们搞出了一棵树，然后给这棵树建立 dfsdfs 序，如果节点 ii 的 dfsdfs 序是 xx，代表它和它的父亲对应的那条边，在 AA 上将会被转到第 xx 行。这样很容易看出来是一个上三角/下三角矩阵，det⁡\det 只能是 ±1±1
又 B=ATB=A^T，所以 det(B′)=det(A′)det(B')=det(A')，最后出来就是 11
如果有环，此时注意一号节点需要特判。结果表明，无论有没有一号节点，只要有环。这个方阵的 nn 个列向量就一定线性相关，从而行列式就是 00
这样子，我们再推到 w(E)∈Nw(E)∈N 的情况，把 E(u,v)E(u,v) 拆成 W(E)W(E) 条边，对应在两个矩阵上乱搞，最后出来的方阵 CC 仍然和 w(E)=1w(E)=1 的形态一致！
恭喜你！无向图的情况被你解决了，现在我们来解决有向图的情况。
有向图，有根树，且要确定方向！
这里以外向图为例子！（外向，指从 root 开始就外向，从父亲指向儿子！）
这里，我们对 AA 和 BB 动一些手脚， AA 负责没有环， BB 负责外向。
我们发现，没有环且联通的情况下，外向当且仅当每个节点只被指向一次（除了根节点！）
所以我们要让存在节点被指向多次的选取方案，其行列式为 00 （线性相关），每个节点(除rt)被指向一次的选取方案，其行列式为 ±1±1，并和 AA 中对应选取方案的行列式保持一致
这样看来就很明显了，对于第 ii 条边 uu -> vv，我们只记 Bi,y=1B_{i,y}=1，然后 AA 中不得胡闹！必须得是 Ax,i=−wi,Ay,i=wiA_{x,i}=-w_i,A_{y,i}=w_i，以此和 BB 的行列式保持一致（具体是为什么我没去想）
然后最后出来的 C=ABC=AB 就满足
C=[∑jwj→1−w1→2−w1→3⋯−w1→n−w2→1∑jwj→2−w2→3⋯−w2→n−w3→1−w3→2∑jwj→3⋯−w3→n⋮⋮⋮⋮⋮−wn→1−wn→2−wn→3⋯∑jwj→n]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矩阵中已经很明显了。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...