樹圖的特徵向量

$\newcommand{\mul}{\operatorname{mult}}$

費德勒於 1975 年在 Czechoslovak Mathematical Journal 上連發了兩篇經典著作，描述許多拉普拉斯矩陣特徵向量的性質，尤其是在樹圖上有精確的描述。我們來欣賞他這兩篇文章中各種優美的定理。

樹圖是結構最簡單的一類圖，而樹圖上的特徵向量具有許多獨特的好性質。這些好性質不僅限於拉普拉斯矩陣，它適用於更廣泛的矩陣族群。以下介紹常見的幾類。令 $T$ 為一樹圖，$n$ 為其點數，我們定義 $\mathcal{S}(T)$ 為所有滿足以下條件的 $n\times n$ 對稱矩陣 $A$：

當 $i \neq j$ 時，
- 若 $\{i,j\}\in E(T)$，則 $(A)_{i,j} \neq 0$；
- 若 $\{i,j\}\notin E(T)$，則 $(A)_{i,j} = 0$。
$A$ 的對角線項可以為任意實數。

集合 $\mathcal{S}(T)$ 中的矩陣，可以視為是 $T$ 的廣義相鄰矩陣，每條邊有非零的權重，可正可負，而對角線可以為任意值。另外 $\ddot{\mathcal{S}}(T)$ 收集所有 $\mathcal{S}(T)$ 中對角線外各項均為零為負的矩陣，這些矩陣稱為 $T$ 的離散薛丁格算子（discrete Schrödinger operator）。最後，$\mathcal{S}_L(T)$ 收集 $\ddot{\mathcal{S}}(T)$ 中符合 $A\bone = \bzero$ 的所有矩陣 $A$，這些矩陣稱為 $T$ 的賦權拉普拉斯矩陣。整體而言，三者有 $\mathcal{S}_L(T) \subseteq \ddot{\mathcal{S}}(T) \subseteq \mathcal{S}(T)$ 的關係。

如果我們在意的是矩陣的特徵值，那麼對樹圖來說 $\mathcal{S}(T)$ 和 $\ddot{\mathcal{S}}(T)$ 沒有太大的差別。我們觀察等式

\[ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 0 & 0 \\ 2 & 3 & -4 & 0 \\ 0 & -4 & 5 & 6 \\ 0 & 0 & 6 & 7 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & -2 & 0 & 0 \\ -2 & 3 & -4 & 0 \\ 0 & -4 & 5 & -6 \\ 0 & 0 & -6 & 7 \end{bmatrix}, \]

記成 $DAD = B$。這裡 $A\in\mathcal{S}(P_4)$、$B\in\ddot{\mathcal{S}}(P_4)$，且 $D = D^{-1}$ 是對角線矩陣，因而 $A$ 和 $B$ 相似且有相同的特徵值。

定理 1（費德勒 1975）

令 $T$ 為一樹圖。對任意 $A\in\mathcal{S}(T)$，都有對角矩陣 $D$ 使得 $DAD\in\ddot{\mathcal{S}}(T)$ 且 $D = D^{-1}$。

這個定理讓我們可以把焦點放在 $\ddot{\mathcal{S}}(T)$ 上。費德勒接著證明了樹圖特徵值的變號數，恰好是特徵值由小到大的排序的編號減 $1$。這邊我們會用到矩陣的 慣性（inertia），對一個實對稱矩陣 $A$ 來說，它的慣性定義為數對 $\operatorname{in}(A) = (n_+(A), n_-(A), n_0(A))$，這三個數字分別是 $A$ 的正、負、零特徵值的個數。舉例來說，如果 $A$ 的特徵值由小到大為 $\lambda_1, \ldots, \lambda_n$，且 $\lambda_k$ 為單根，則 $\operatorname{in}(A - \lambda_k I) = (n - k, k - 1, 1)$。由此也可以見到慣性可以幫助我們了解特徵值的序位。

我們一樣先觀察一個例子，令下方最左邊的矩陣為 $A$，這個矩陣滿足 $A\bone = \bzero$。由左至右我們不斷執行對稱的行列運算；比如說第一步我們把第一列加到第二列，也對行做對稱的動作。

\[ \begin{bmatrix} 1 & -1 & 0 & 0 \\ -1 & 3 & -2 & 0 \\ 0 & -2 & -1 & 3 \\ 0 & 0 & 3 & -3 \end{bmatrix} \rightsquigarrow \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 2 & -2 & 0 \\ 0 & -2 & -1 & 3 \\ 0 & 0 & 3 & -3 \end{bmatrix} \rightsquigarrow \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & -3 & 3 \\ 0 & 0 & 3 & -3 \end{bmatrix} \rightsquigarrow \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & -3 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \]

著名的 西爾維斯特慣性定律（Sylvester's law of inertia） 證明了對一個矩陣做對稱行列運算時，不會改變它的慣性。因此上述的四個矩陣慣性都一樣，而從最右邊的矩陣可以看出慣性是 $(2,1,1)$。基於這個例子，我們可以觀察到當 $B\in\mathcal{S}(T)$ 且 $B\bone = \bzero$ 時，則 $\operatorname{in}(B) = (p,q,1)$，這裡 $p$ 是 $B$ 中上嚴格三角區域（不含對角線）內負項的個數，而 $q$ 是同一區域正項的個數。

定理 2（費德勒 1975）

令 $T$ 為一樹圖且 $A\in\ddot{\mathcal{S}}(T)$。令 $A$ 的特徵值由小到大為 $\lambda_1, \ldots, \lambda_n$。若 $\by$ 為對應到 $\lambda_k$ 的特徵向量且 $\by$ 逐項非零，則 $\lambda_k$ 為單根，且 $\by$ 沿著 $T$ 的變號數，恰好等於 $k - 1$。也就是

\[ \vert{}\{\{i,j\}\in E(T): (\by)_i(\by)_j < 0\}\vert{} = k - 1. \]

證明

因為 $\by$ 是特徵向量，我們有 $(A - \lambda_k I) \by = \bzero$。令 $D$ 為一對角矩陣，其對角線各項等於 $\by$ 各項。由於 $\by$ 逐項非零，所以 $D$ 是可逆矩陣。考慮 $B = D(A - \lambda_k I)D$，則西爾維斯特慣性定律告訴我們 $A - \lambda_k I$ 和 $B$ 有相同的慣性。同時，$B\in\mathcal{S}(T)$ 且 $B\bone = \bzero$，因此 $\operatorname{in}(B) = (p,q,1)$。因為 $n_0(B) = 1$，我們知道 $\lambda_k$ 為單根，且 $n_-(A - \lambda_k I) = n_-(B) = k - 1$。另一方面，$q = k - 1$ 為 $B$ 中嚴格上三角區域的正項數，觀察 $B = D(A - \lambda_k I)D$ 可知這個量同時也是 $\by$ 沿著 $T$ 的變號數。$\blacksquare$

當特徵向量逐項非零時，這個定理精準地刻畫特徵值序位。另一方面，對於特徵向量有零項時，費德勒一樣給出了精確的描述。這邊我們先給一些名詞定義，令 $G$ 是一個圖且 $A\in\mathcal{S}(G)$，則 $A(i)$ 指的是把 $A$ 中第 $i$ 行和列去掉的子矩陣；同理，若 $\by$ 是一個可以和 $A$ 相乘的向量，則 $\by(i)$ 代表的是把 $\by$ 中第 $i$ 項去掉的子向量。當圖 $G$ 和 $\by$ 都很明確時，我們依照 $(\by)_i$ 是正、負、或零而稱 $i$ 是正點、負點、或是零點。當一個零點有相鄰一個非零點時，我們稱這個零點為 邊界點。

另外，這裡我們會討論同一個特徵值 $\lambda$ 在 $A$ 及 $A(i)$ 中的重數。根據柯西交錯定理，$\mul_{A(i)}(\lambda)$ 只有 $\mul_A(\lambda) - 1$、$\mul_A(\lambda)$、以及 $\mul_A(\lambda) + 1$ 三種可能。第三種狀況 $\mul_{A(i)}(\lambda) = \mul_A(\lambda) + 1$ 有點違反直覺，當矩陣變小時，特徵值的重數反而變大，這是較特殊的狀況，此時我們稱 $i$ 為 派特點（Parter vertex）。舉列來說，$K_{1,4}$ 的相鄰矩陣 $A$ 的特徵值是 $-2,0,0,0,2$，當 $i$ 是中心點時 $A(i)$ 的特徵值為 $0,0,0,0$，此時 $0$ 的重數從 $3$ 變成 $4$。當我們再次細看柯西交錯定理時，我們會發現派特點發生時，一定有 $\operatorname{in}(A(i)) = \operatorname{in}(A) + (-1,-1,1)$。

定理 3（費德勒 1975）

令 $T$ 為一樹圖且 $A\in\mathcal{S}(T)$、並令 $\lambda$ 為 $A$ 的一個特徵值且 $\by$ 為對應的特徵向量。對於 $T$、$A$、$\by$ 而言，任一個邊界點都是派克點。

證明

令 $i$ 為一邊界點、且 $j$ 為 $i$ 鄰居中的一個非零點。令 $X_1,\ldots,X_c$ 為 $G - i$ 的連通區塊的點集；不失一般性，假設 $j\in X_1$。依照 $\{i\},X_1, \ldots, X_c$ 的分割，我們可以把 $(A - \lambda I)\by = \bzero$ 寫成

\[ \begin{bmatrix} ? & \bb_1\trans & \cdots & \bb_c\trans \\ \bb_1 & A_1 & ~ & ~ \\ \vdots & ~ & \ddots & ~ \\ \bb_c & ~ & ~ & A_c \end{bmatrix} \begin{bmatrix} 0 \\ \by_1 \\ \vdots \\ \by_c \end{bmatrix} = \bzero. \]

這裡有一些觀察。第一、觀察上述等式可發現，每一個 $k = 1, \ldots, c$ 都有 $A_k\by_k = \bzero$。第二、根據圖的結構，$i$ 到每一個 $G - i$ 的區塊都只有連一條邊，翻譯到矩陣上的意思就是 $\bb_1, \ldots, \bb_c$ 中每個向量都恰只有一個非零項，不仿假設它們的非零項都是各向量上的第 $1$ 項。第三、延續第二的觀察，$\bb_1$ 上只有第 $j$ 項非零，而 $\by_1$ 上的第 $j$ 項非零，因此有 $\inp{\by_1}{\bb_1} \neq 0$。最後，綜合第一和第三個觀察，$\by_1\in\ker(A_1)$ 但 $\inp{\by_1}{\bb_1} \neq 0$，這表示 $\bb_1\notin\Col(L_1)$，因此得到 $\mul_{A(i)}(\lambda) = \mul_A(\lambda) + 1$。$\blacksquare$

在費德勒年代的前後，派特（Seymour Parter）於 1960 年、以及威納（Gerry Wiener）於 1984 年，分別討論過樹圖上的派特點。近代稱這個定理為 派威定理（Parter–Wiener theorem），這也是它被稱作派特點的原因。

最後，費德勒證明了以下對特徵向量的刻畫。

定理 4（費德勒 1975）

令 $T$ 為一樹圖且 $A\in\mathcal{S}(T)$、並令 $\lambda$ 為 $A$ 的一個特徵值且 $\by$ 為對應的特徵向量。對於 $T$ 和 $\by$ 而言，令 $a_-$ 為變號邊的個數、$a_+$ 為同號邊的個數、$b$ 為 $T$ 刪掉所有邊界點後區塊上 $\by$ 值非零向量的區塊數、$p$ 為邊界點的個數、$c$ 為非邊界點的零點個數。這些量依定義滿足 $a_- + a_+ + b + p + c = \vert{}V(T)\vert{}$。此時可計算 $A - \lambda I$ 的慣性，

\[ \begin{aligned} n_-(A - \lambda I) &= a_- + p + c_-, \\ n_+(A - \lambda I) &= a_+ + p + c_+, \\ n_0(A - \lambda I) &= c - p + c_0. \end{aligned} \]

這裡 $c_-,c_+,c_0$ 為符合 $c_- + c_+ + c_0 = c$ 的非負整數。而對於任何可能的 $c_-,c_+,c_0$ 都找得到 $A$ 讓等式成立。

證明

將邊界點拿掉後，留下來的區塊分兩類，一類是 $\by$ 在其上全為零，另一零是 $\by$ 在其上全非零。後者可以用定理 2 找到其慣性，前者由於 $\by$ 在其上全為零沒有給任何限制，所以任何慣性都有可能發生。綜合本篇所有定理，即可推得 $A$ 的慣性。$\blacksquare$

想想以下問題：

說明定理 1 中的 $D$ 要怎麼找，以及為什麼這個定理一定要 $T$ 是樹圖。
證明定理 2。融合定理 1 及定理 2，將定理 2 推廣到 $\mathcal{S}(T)$ 上。
考慮一個對稱矩陣 $M$，將其根據第 $1$ 行列分割為
\[ M = \begin{bmatrix} a & \bb\trans \\ \bb & C \end{bmatrix}. \]

證明以下三個敘述：
1. 若 $\bb\notin\Col(C)$，則 $\nul(C) = \nul(M) + 1$。此時任意 $\bv\in\ker(M)$ 都有 $(\bv)_i = 0$。
2. 若存在 $\bx$ 使得 $\bb = C\bx$ 且 $a \neq \bx\trans C\bx$，則 $\nul(C) = \nul(M)$。此時任意 $\bv\in\ker(M)$ 都有 $(\bv)_i = 0$。
3. 若存在 $\bx$ 使得 $\bb = C\bx$ 且 $a = \bx\trans C\bx$，則 $\nul(C) = \nul(M) - 1$。
證明定理 4。融合定理 1 及定理 4，將定理 4 推廣到 $\mathcal{S}(T)$ 上。
利用下方程式碼觀察定理 1、定理 2 及定理 4 的現象。