矩陣樹定理

令 \(G\) 為一連通圖，如果一個 \(G\) 的子圖 \(T\) 是一個點集為 \(V(G)\) 的樹圖，則 \(T\) 被稱為 \(G\) 的 生成樹（spanning tree）。生成樹可以被視為是圖的骨幹，它用最少的邊，把所有點連接在一起。

舉例來說，圈圖 \(C_n\) 上共有 \(n\) 個生成樹，可以由 \(C_n\) 拿掉任意一條邊形成。令 \(G = K_4 - e\)，其中 \(e = \{3,4\}\)，則 \(G\) 有 \(8\) 個生成樹，由以下方式形成：

去掉 \(\{1,2\}\) 先形成 \(C_4\)，之後任意去掉一條邊形成 \(4\) 個生成樹。
或是在 \(\{\{1,3\},\{2,3\}\}\) 中選一條邊去掉、再從 \(\{\{1,4\},\{2,4\}\}\) 中選一條邊去掉，如此得到另外 \(4\) 個生成樹。

大家也可以試試看，完全圖 \(K_3\) 有 \(3\) 個生成樹、\(K_4\) 有 \(16\) 個生成樹、\(K_5\) 有 \(125\) 個生成樹。凱力（Arthur Cayley）於 1889 年證明完全圖 \(K_n\) 的生成樹個數共有 \(n^{n-2}\)，這個式子也被稱為 凱力公式（Cayley's formula）。凱力使用的是代數方法來證明，他證明 \(K_n\) 的生成樹個數與

\[ x_1 \cdots x_n(x_1 + \cdots + x_n)^{n-2} \]

中的總項數一樣，也就是代入 \(x_1 = \cdots = x_n = 1\) 的值。普呂弗（Heinz Prüfer）在 1918 引入了 普呂弗碼（Prüfer code），提供了凱力公式的組合證明；每一個普呂弗碼都是一串長度 \(n - 2\) 的字串，每個位元可以從 \(1\) 到 \(n\) 中選取，普呂弗證明完全圖的生成樹和普呂弗碼有一一對應的關係。

凱力和普呂弗關注的都是完全圖中生成樹的個數，但有趣的是，在他們之前的克希荷夫（Gustav Kirchhoff）¹，於 1847 年的一篇電路學的論文中，證明了 矩陣樹定理（Matrix tree theorem），描述任一圖的生成樹個數，可以由其拉普拉斯矩陣的子矩陣行列式值算出²。由現在的觀點，克希荷夫的定理可以有效地算出完全圖生成數個數，以及許多圖類的生成樹個數的公式。由於當時資訊流通較慢，加上克希荷夫的論文著重的都是電路學的應用，才會導致這樣有趣的狀況。

這邊我們延用子矩陣的符號，\(L(i,j)\) 代表 \(L\) 刪掉第 \(i\) 行第 \(j\) 列的子矩陣，當 \(i = j\) 時，我們寫 \(L(i) = L(i,j)\)。

矩陣樹定理（克希荷夫 1847）

令 \(G\) 為一個圖，而 \(L\) 為其拉普拉斯矩陣。則對任意點 \(i\in V(G)\) 而言，\(\det(L(i))\) 恰為 \(G\) 上生成樹的個數。

這邊我們先處理 \(i\) 的選擇上的問題。依照定理敘述，\(\det(L(i))\) 對任意 \(i\) 來說都是定值，我們先來看看為什麼。我們將說明 \(\det(L(1)) = -\det(L(1,2)) = \det(L(2))\)，而類似的論述可以說明 \(\det(L(1)) = (-1)^{i+j}\det(L(i,j))\)。首先我們知道 \(L\bone = \bzero\)，這表示 \(L\) 的行向量有 \(\bc_1 + \cdots + \bc_n = \bzero\) 的關係。方便起見，我們令 \(\bc = \bc_3 + \cdots + \bc_n\)。如此一來我們有 \(\bc_1 + \bc_2 + \bc = \bzero\) 的關係，也就是 \(\bc_1 = -\bc_2 - \bc\)。觀察 \(L(1)\) 和 \(L(1,2)\) 只有差在它們的第一行，一個是 \(\bc_2\)，一個是 \(\bc_1\)，而前述的關係式告訴我們 \(L(1)\) 可以經由一系列的行運算來得到 \(L(1,2)\)，仔細記錄這些行運算對行列式值的影響，即可證明 \(\det(L(1)) = -\det(L(1,2))\)。由於 \(L\) 是對稱矩陣，前述的行運算可以改為列運算，得到 \(-\det(L(1,2)) = \det(L(2))\)。這樣的關係對於任何滿足 \(A\bone = \bzero\) 的對稱矩陣都是對的。

接下來我們介紹 柯比公式（Cauchy–Binet formula），它是重要的行列式值公式，也是證明矩陣樹定理的關鍵之一。我們熟知行列式值有可乘性，也就是 \(\det(AB) = \det(A)\det(B)\)，但這樣的性質僅限於 \(A\) 和 \(B\) 都是方陣的時候。如果 \(A\) 是 \(n\times m\) 矩陣而 \(B\) 是 \(m\times n\) 矩陣，則 \(AB\) 是 \(n\times n\) 矩陣，我們有沒有辦法利用 \(A\) 和 \(B\) 上的資訊來計算 \(\det(AB)\) 呢？先看幾個極端的例子，當 \(n > m\) 時，由於 \(\rank(AB) \leq \rank(A) \leq m\) 導致 \(AB\) 的秩不夠大，所以必有 \(\det(AB) = 0\)，因此我們可以著重在 \(n \leq m\) 的狀況；另一方面，當 \(n = 1\) 時，\(AB\) 基本上就是兩個向量內積，我們有

\[ \det(AB) = \sum_{j = 1}^m (A)_{1,j}(B)_{j,1}, \]

所以看似公式中某種程度的相加是無可避免的。柯比公式給出了計算 \(\det(AB)\) 的一種方法。這邊 \([m] = \{1, \ldots, m\}\)。

柯比公式（柯西–比內 1812）

令 \(A\) 為 \(n\times m\) 矩陣而 \(B\) 為 \(m\times n\)。則

\[ \det(AB) = \sum_{\substack{\alpha\subseteq [m]\\ \vert{}\alpha\vert{} = n}} \det(A[:,\alpha])\det(B[\alpha,:]). \]

舉例來說，考慮 \(A\) 及 \(B\) 矩陣如下：

\[ A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix} \qquad B = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{bmatrix} \]

我們可以直接計算得到

\[ AB = \begin{bmatrix} 4 & 5 \\ 10 & 11 \\ \end{bmatrix} \]

以及 \(\det(AB) = -6\)。但另一方面我們也可以透過柯比公式計算，這裡 \([m] = \{1,2,3\}\)，所以 \(\alpha\) 有三種可能 \(\{1,2\}\), \(\{1,3\}\), \(\{2,3\}\)，而代入公式可得

\[ \begin{aligned} \det(AB) &= \det\begin{bmatrix} 1 & 2 \\ 4 & 5 \end{bmatrix} \det\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} + \det\begin{bmatrix} 1 & 3 \\ 4 & 6 \end{bmatrix} \det\begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} + \det\begin{bmatrix} 2 & 3 \\ 5 & 6 \end{bmatrix} \det\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \\ &= (-3) + (-6) + (3) = -6, \end{aligned} \]

與直接計算的結果一致。

有了柯比公式，矩陣樹定理就唾手可得了。

矩陣樹定理的證明

令 \(G\) 為一個圖，而 \(L\) 為其拉普拉斯矩陣。我們已知 \(\det(L(i))\) 不受 \(i\in V(G)\) 的選取影響，所以可以固定 \(i = 1\)。令 \(N\) 為 \(G\) 的一個相連矩陣，我們知道 \(L = NN\trans\)，所以也有 \(L(i) = N(i,:]N\trans[:,i)\)。令 \(A = N(i,:]\) 及 \(B = N\trans[:,i)\)。

結總相連矩陣的子矩陣行列式值的引理 2 和引理 3，對於滿足 \(\vert{}\beta\vert{} = \vert{}V(G)\vert{} - 1\) 的 \(\beta\subseteq E(G)\) 來說，我們有：

若 \(\beta\) 包含圈，則 \(\det(A[:,\beta]) = \det(B[\beta,:]) = 0\)。因此 \(\det(A[:,\beta])\det(B[\beta,:]) = 0\)。
若 \(\beta\) 不包含圈，即 \(\beta\) 形成一個生成樹，則 \(\det(A[:,\beta]) = \det(B[\beta,:])\) 且其值為 \(\pm 1\)。因此 \(\det(A[:,\beta])\det(B[\beta,:]) = 1\)。

我們對 \(L(i) = AB\) 套用柯比公式，即可得到 \(\det(L(i))\) 恰為生成樹的個數。\(\blacksquare\)

矩陣樹定理後來被推廣為 全子矩陣樹定理（all minors matrix tree theorem）。矩陣樹定理計算的是刪掉一行一列的 \(L(i,j)\) 的行列式值，而全子矩陣樹定理進一步考慮刪掉 \(k\) 行 \(k\) 列的 \(L(\alpha,\beta)\) 的行列式值，並賦與它組合意義，其中 \(\vert{}\alpha\vert{} = \vert{}\beta\vert{} = k\)。如此一來，我們可以藉由全子矩陣樹定理計算 \(L\) 的任何子矩陣行列式值，進而可以計算特徵多項式的每一項係數。另一方面，不論是矩陣樹定理或是全子矩陣樹定理，都可以推廣到賦權圖或是有向圖的拉普拉斯矩陣之上，進而可以計算這些圖上的格林函數。

生成樹除了與拉普拉斯矩陣行列式值有關連以外，也和組合學裡的 停車函數（parking function） 有對應關係。全部 \(n\) 臺車可以停進 \(n\) 個車位的停車函數恰有 \((n+1)^{n-1}\) 個，將 \(n\) 取代為 \(n -1\) 以後，即為計算生成樹的凱力公式。兩者有一一對應關係。

全子矩陣樹定理以及停車函數，現今仍不斷看到新的理論發展以及應用，是活躍的研究方向之一。

想想以下問題：

任找一個圖，畫出它的所有生成樹。
證明柯比公式。
描述全子矩陣樹定理，並用其計算任一圖的拉普拉斯矩陣特徵多項式。
描述樹圖的 瓶頸矩陣（bottleneck matrix），並用全子矩陣樹定理來說明它與拉普拉斯矩陣的關係。
描述賦權拉普拉斯矩陣的矩陣樹定理。
任給一個正整數 \(k\)，能不能找到一個圖它的生成樹個數恰為 \(k\)？如果可以，這個圖最少有幾個點？