數學-Matrix Tree定理證明

2020 年 3 月 17 日
筆記

老久沒更了，冬令營也延期了（延期後豈不是志願者得上學了？）

最近把之前欠了好久的債，諸如FFT和Matrix-Tree等的搞清楚了（啊我承認之前只會用，沒有理解證明……），FFT老多人寫，而MatrixTree沒人證我就寫一下吧……

Matrix Tree結論

Matrix Tree的結論網上可多，大概一條主要的就是，圖中生成樹的數量等於 (V-E) 的任一餘子式，其中：

(V) 為對角陣，第 (i) 個元素為點 (i) 的度數
(E) 為對稱陣，對角線為零且 (E_{i,j}) 為點 (i) 與點 (j) 之間邊的數量的相反數

這個結論眾人皆知，但我好像沒怎麼搜到證明？

圖的關聯矩陣

為了求無向圖中有多少組 (n-1) 條邊可以形成樹，一般需要枚舉所有的可能，無法在多項式內解決，但我們利用數學工具將其轉換——引入關聯矩陣

為了後面討論我們給每條邊隨意分配一個方向。

圖的鄰接矩陣是一個 (ntimes n) 的用於存儲圖的矩陣。而關聯矩陣 (A) 則為 (ntimes m) 的矩陣，其中行對應點，列對應邊，如果 (A_{i,j}) 非零，則說明第 (j) 條邊的起點或終點為點 (i)（如 (i) 為起點則為 (+1)，終點則為 (-1)，否則為 (0)）。如下圖即為一張 (4) 點 (5) 邊的圖的關聯矩陣：
[ begin{bmatrix} +1 & -1 & +1 & 0 & 0\ -1 & 0 & 0 & +1 & -1\ 0 & +1 & 0 & -1 & 0\ 0 & 0 & -1 & 0 & +1 end{bmatrix} ]

可以看到，如果只考慮這張圖的結構的話，關聯矩陣的行之間或列之間隨意交換都是無所謂的（行交換代表點重新編號……）

我們可以證明一個結論，任意連通圖的關聯矩陣秩為 (n-1)。

有兩種理解方式：

按行來看：
- 首先去掉任意一行都是可以復原的：因為每一列都是一個 (+1) 一個 (-1)，可以輕鬆由其他 (n-1) 行得到這一行。故去掉任意一行不會丟失資訊，秩 (le n-1)；
- 其次去掉任意兩行都是無法復原的：因為任意去掉兩行 (x,y)，在這張連通圖上找到一條 (x) 到 (y) 的路徑，取其中 (xto y) 方向第一條邊 (a)、(yto x) 方向第一條邊 (b)，則在還原關聯矩陣時無法確定非零位置是 ((x,a)&(y,b)) 還是 ((x,b)&(y,a))。故去掉任意兩行都會丟失資訊，秩 (ge n-1)
再按列來看更為顯然：
- 由於列對應邊，故選取若干列，若這些列對應的邊在圖上組成了環，則一定線性相關（因為將環按一個方向捋一遍然後加起來一定為零）
- 故要求「最多的線性無關的列」，也即求「在不出現環的前提下最多能找出多少邊」，答案顯然為 (n-1)

這下從行列兩個方向證明了這個結論，但有何用處呢？

我們剛在從列的方向證明結論時用到了「生成樹」的概念，仔細考慮一下，求「圖中有多少種 (n-1) 條邊的組合沒有環」，等價於求「關聯矩陣中有多少種 (n-1) 列的組合線性無關」

同時我們證明了 (n) 個行中總有一個是多餘的，故考慮刪去其中一行對答案無影響。

這下將圖中的問題轉化為了矩陣中的問題，但是否將過程複雜化了呢？

Binet-Cauchy公式

為了解決這個問題，我們需要引入 Binet-Cauchy公式：

若存在 (ntimes m) 的矩陣 (A) 與 (mtimes n) 的矩陣 (B)，則矩陣 (AB) 的行列式等於：從 (m) 中任意選取 (n-1) 個指標，並取出 (A) 的這 (n) 列得到 (A')，和 (B) 的這 (n) 行的得到 (B')，將它們行列式乘起來得到 (det A'times det B')，對所有共 (C_m^n) 種選取情況求和。

數學表達：
[ det (AB)=sum_{Ssube U,|S|=n}det(A_S)det(B_S) ]
（其中 (U) 表示集合 ({1,2,dots,m})，(A_S) 表示取出 (S) 中下標的列組成的矩陣，(B_S) 表示取出 (S) 中下標的行組成的矩陣）

可以發現其中幾種特殊情況：

(n=1)：此時公式等價於計算兩個 (m) 維向量的點積
(n=m)：此時公式等價於表示 (det(AB)=det(A)det(B)) 的行列式可乘性質
(n>m)：此時公式中由於無法選出任何一組，故右邊恆等於 (0)，其表達的其實是矩陣 (AB) 不滿秩

這個公式的證明過於繁瑣，不予展開，但可以感性理解：(AB) 是 (A) 的以 (B) 為係數的線性組合，將 (AB) 的行列式展開後分離貢獻，(det (A_S)) 的係數是 (det(B_S))

利用公式

為了解決這個問題引入這個公式，很明顯是和其中的共同擁有的「任意選取」、「線性無關」兩個因素有關。

很容易想到是想要將圖的關聯矩陣 (D)（去掉一行後）放入 (A) 或 (B) 的位置，但具體怎麼放，另一個矩陣又是什麼？

引理：連通圖的關聯矩陣中，任意一個子矩陣的行列式都為 (pm 1) 或 (0)

證明：

若子矩陣不可逆，則行列式自然為零

若子矩陣可逆，則不可能每一列都同時存在兩個非零項（否則每一列都是一個 (+1) 一個 (-1)，將所有行加起來一定是 (0)），故按只有一個非零項的列進行行列式展開，則可以歸納至低一階的情況

有了這個引理，可以非常自然的考慮將 (A) 設為 (D)，(B) 設為 (D^T)，則 (A_S) 和 (B_S) 都是取 (D) 的不同列向量組成的矩陣。

由於我們證明了，列線性無關的子矩陣行列式一定為 (pm 1)，則平方後一定為 (1)。再利用上述公式，故原問題的的答案即為 (det (AB))

至於 (AB) 是啥？(AB=DD^T)

考慮下關聯矩陣 (D) 的定義，即可發現 ((AB)_{i,j})：

當 (i=j) 時：((AB)_{i,i}) 為 (D) 第 (i) 行與自己的點積，由於非零項都為 (pm 1)，則 ((AB)_{i,i}) 即為第 (i) 行的非零項個數——即點 (i) 的度數
當 (ine j) 時：((AB)_{i,j}) 為 (D) 第 (i) 行與 (j) 的點積，由於每一列都只有兩個元素（一個 (+1) 一個 (-1)），故每個位置如果有值，則一定為 (-1)，((AB)_{i,j}) 即為它們求和——點 (i) 與點 (j) 之間邊的數量的相反數

總結

回顧整個過程：

問題一開始是「有多少種選取 (n-1) 條邊的方式，使選出的邊構成樹」
然後引入圖的關聯矩陣，證明了其秩為 (n-1)，同時也發現問題等價於「有多少種在關聯矩陣中選取 (n-1) 列的方式，使選出的列線性無關」（同時發現刪去關聯矩陣任意一行對答案無影響）
針對「任意選取」和「線性無關」兩個特點，引入了同樣擁有這兩個特點的 Binet-Cauchy公式
- 利用 Binet-Cauchy任意選取的特點，和「線性無關(iff) 行列式非零」的性質，希望將關聯矩陣放入公式
為了將關聯矩陣放入公式，證明了關聯矩陣中任意一個子矩陣行列式為 (pm 1) 或 (0)
巧妙地將 (A) 設為 (D)，(B) 設為 (D^T)，則得到的結果 (det(AB))
- 等價於：任取 (D) 的 (n-1) 列求出行列式，平方後求和。
- 等價於：任取 (D) 的 (n-1) 列，行列式非零的方案數
考慮 (AB=DD^T) 的現實意義，得到開頭提到的Matrix Tree定理

有向生成樹的擴展

剛才討論的都是無向生成樹，可以考慮到有向生成樹的情況：

由於點可以重新標號，我們只考慮以 (1) 號點為根的情況
由於內向生成樹可以將邊取反後求外向生成樹，故只考慮外向生成樹的情況

考慮外向生成樹關聯矩陣的特點：除了根以外每一行都只有一個 (-1)（樹上只有一個父親）

而若生成樹不是外向生成樹，則一定存在一個點 (x)，關聯矩陣中 (x) 對應的那一行沒有 (-1)

所以可以考慮將原來每條邊「一個 (+1) 一個 (-1)」中的 (+1) 置為零，則在計算時：

如果這棵生成樹不是外向生成樹，則一定存在一行全為零，其行列式也為零
如果這棵樹是外向生成樹，由於每一行有一個 (-1)，故其行列式為 ((-1)^{n-1}) 也只可能為 (pm 1)