離散峰谷定理

拉普拉斯矩陣可視為 拉普拉斯算子（Laplacian operator） \(\Delta\) 的離散化¹。以一維函數 \(f: [0,1] \rightarrow \mathbb{R}\) 來說，\(\Delta f = f''\)。如考慮邊界問題

\[ f'' = \lambda f,\ f(0) = 0,\ f(1) = 0, \]

會發現 \(f = e^{\sqrt{\lambda}x}\)，若 \(f\neq 0\) 要能符合邊界條件，只能在 \(\lambda < 0\) 且 \(\sqrt{\lambda} = i\sqrt{-\lambda}\) 的時候，此時 \(f = C\sin(\sqrt{-\lambda}\,x)\)，推得 \(\lambda\) 只有離散解 \(\lambda_k = -k^2\pi^2\)。這個方程反應了絃振盪時的駐波，當 \(k = 1\) 時，有一個波峰、\(k = 2\) 時有一峰一谷、\(k = 3\) 時有兩峰一谷，推得第 \(k\) 個解峰谷數合計總是 \(k\) 個。這個現象被稱為 庫朗峰谷定理（Courant nodal domain theorem）：第 \(k\) 個特徵函數至多有 \(k\) 個峰谷。既然拉普拉斯矩陣是拉普拉斯算子的離散化，其特徵向量是否有類似的定理呢？

我們先明確定義峰和谷的意思，若 \(G\) 為一個圖、\(n\) 為其點數、而 \(\by\in\mathbb{R}^n\) 被視為是 \(V(G) \rightarrow\mathbb{R}\) 的函數。令 \(N_{>0}\) 和 \(N_{<0}\) 分別為 \(\by\) 上的正點集合和負點集合，則 \(\by\) 的一個 強峰（positive strong nodal domain） 為 \(G[N_{>0}]\) 上的一個連通區塊，而一個 強谷（negative strong nodal domain） 為 \(G[N_{<0}]\) 上的一個連通區塊。兩著合併計算，\(\by\) 上強峰和強谷的總數計作 \(\mathfrak{S}(\by)\)。

我們先觀察樹圖的費德勒向量，考慮一樹圖 \(T\) 及其拉普拉斯矩陣。若 \(T\) 為第二類，則費德勒向量有一強峰、一強谷，合計 \(2\) 個，而費德勒向量對應的特徵值是 \(\lambda_2\) 單根，所以 \(2 \leq 2\) 符合期待。若 \(T\) 為第一類，則似乎沒辦法確定總區塊數。以實際例子來說，若 \(T = K_{1,3}\) 時，其拉普拉斯特徵值為 \(\{0,1,1,4\}\)，而其費德勒向量均有 \((0,a,b,-a-b)\) 的形式；這裡 \(1\) 號點是中心點。這樣的費德勒向量，取決於 \(a,b\) 的選取，其強峰谷總數會改變；當 \(a,b > 0\) 時，有兩強峰一強谷，合計 \(3\) 個，似乎與特徵值為 \(\lambda_2\) 相抵觸，因為 \(3 \not\leq 2\)。然而，我們發現 \(1\) 這個特徵向量可以當成 \(\lambda_2\) 也可以當成 \(\lambda_3\)，所以 \(1\) 這個特徵值的序位不唯一，最大可以寫為 \(3\)，似乎 \(3 \leq 3\) 還是說得通。但這個例子告訴我們在特徵值重數大於 \(1\) 時，要有一些特別的處理。

另一方面，我們再以單邊弱峰谷定理的視角來看這個例子，它限制了 \(G[N_{\geq 0}]\) 及 \(G[N_{\leq 0}]\) 的區塊數。如果把零點加進來，則 \(\by\) 的一個 弱峰（positive weak nodal domain） 為 \(G[N_{\geq 0}]\) 上的一個連通區塊，而一個 弱谷（negative weak nodal domain） 為 \(G[N_{\leq 0}]\) 上的一個連通區塊。兩者合併計算，\(\by\) 上弱峰和弱谷的總數計作 \(\mathfrak{W}(\by)\)。依定義，我們有 \(\mathfrak{W}(\by) \leq \mathfrak{S}(\by)\) 的關係。依這樣的觀點，\(K_{1,3}\) 上不管選取哪一個費德勒向量，弱峰谷總數仍然會是 \(2\)，不論對應特徵值重數為何，總是有 \(2 \leq 2\) 的關係。

總結來說，初步觀察我們會發現，如果有離散型的峰谷定理，那我們至少要留意以下兩件事：

當特徵值重數大於 \(1\) 時，序位的選取不唯一。
峰谷有強和弱兩種定義，會造成不一樣的峰谷數。

接下來我們正式介紹離散峰谷定理，前述兩點也會在定理敘述中反映出來。注意到定理對任意離散薛丁格算子都正確，不一定要是拉普拉斯矩陣。

離散峰谷定理（布萊恩戴維斯等人 2001）

令 \(G\) 為一連通圖而 \(A\in\ddot{\mathcal{S}}(G)\)，將其特徵值由小到大排序為 \(\lambda_1 \leq \cdots \leq \lambda_n\)。令 \(\lambda\) 為一特徵值，其最小的序位為 \(a\)、最大的序位為 \(b\)，也就是 \(a \leq b\) 且

\[ \lambda_{a-1} < \lambda_a = \lambda = \lambda_b < \lambda_{b + 1}. \]

若 \(\by\) 為 \(A\) 上對應到 \(\lambda\) 的一個特徵向量，則有 \(\mathfrak{S}(\by) \leq b\) 及 \(\mathfrak{W}(\by) \leq a\)。

在進入到證明之前，我們先觀察以下幾個核心觀念。

若考慮 \(A - \lambda I\)，則 \(a = n_-(A - \lambda I) + 1\)、而 \(b = n_-(A - \lambda I) + n_0(A - \lambda I)\)，分別代表了負的特徵值個數（加 \(1\)）以及零或負的特徵值個數。
根據柯西交錯定理，若 \(B\) 為 \(A - \lambda I\) 的主子矩陣（principal submatrix），則 \(n_-(B) + 1 \leq a\) 且 \(n_-(B) + n_0(B) \leq b\)。

搭配西爾維斯特慣性定律，我們可以更強化這個性質。

引理 2

令 \(M\) 為一 \(n\times n\) 對稱矩陣，\(S\) 為一 \(n\times s\) 矩陣，其行向量線性獨立。令 \(B = S\trans MS\)，則 \(n_-(B) \leq n_-(M)\) 且 \(n_-(B) + n_0(B) \leq n_-(M) + n_0(M)\)。

證明

因為 \(S\) 的行向量獨立，它可以擴充為一個 \(n\times n\) 的可逆矩陣 \(Q\)，其前 \(s\) 行為 \(S\)。依照西爾維斯特慣性定律，\(M\) 和 \(Q\trans MQ\) 有相同的慣性。接下來觀察 \(B\) 是 \(Q\trans MQ\) 左上角的主子矩陣，因此柯西交錯定理告訴我們

\[ \begin{aligned} n_-(B) &\leq n_-(Q\trans MQ) = n_-(M), \\ n_-(B) + n_0(B) &\leq n_-(Q\trans MQ) + n_0(Q\trans MQ) = n_-(M) + n_-(M). \\ \end{aligned} \]

因此得證。\(\blacksquare\)

透過引理 2，我們已經看到一些證明的影子，如果我們可以找到適當 \(S\) 讓 \(B\) 跟總峰谷數有關聯，我們就能證明離散峰谷定理。

離散峰谷定理的證明

我們先證明 \(\mathfrak{S}(\by) \leq b\)。方便起見，我們令 \(A' = A - \lambda I\)，如此一來就有 \(n_-(A') + n_0(A') = b\)。而我們的目標是利用引理 2 找到一個矩陣 \(B\) 使得 \(n_-(B) + n_0(B) = \mathfrak{S}(\by)\)。

根據 \(\by\)，令 \(X_1, \ldots, X_p\) 為 \(G[N_{> 0}]\) 上的區塊點集、 \(X_{p+1}, \ldots, X_{p+q}\) 為 \(G[N_{< 0}]\) 上的區塊點集、而 \(s = p + q = \mathfrak{S}(\by)\)。對於所有 \(k = 1, \ldots, s\)，將 \(\by\) 上 \(X_i\) 以外的項都設定為 \(0\)，稱此向量為 \(\by_i\)。如此一來我們有 \(\sum_{i=1}^s\by_i = \by\)，同時我們有 \(\by_1,\ldots, \by_p \geq 0\) 以及 \(\by_{p+1}, \ldots, \by_{p+q} \leq 0\)。

令 \(S\) 為 \(n\times s\) 矩陣，其行向量為 \(\by_1, \ldots, \by_s\)。由於這些向量的非零項位置彼此沒有重疊，\(S\) 的行向量集合線性獨立。令 \(B = S\trans A'S\)，則 \(B\) 是一個 \(s\times s\) 矩陣，且根據引理 2 我們有 \(n_-(B) + n_0(B) \leq n_-(A') + n_0(A')\)。接著我們觀察 \(B\) 具有以下的形式

\[ B = \begin{bmatrix} D_1 & C \\ C\trans & D_2 \end{bmatrix}. \]

首先，\((B)_{i,j} = \by_i\trans A'\by_j\)。當 \(i\neq j\) 同屬 \(\{1,\ldots, p\}\) 時，因為 \(X_i\) 和 \(X_j\) 沒有相鄰的點，所以 \((B)_{i,j} = 0\)；同樣的，當 \(i\neq j\) 同屬 \(\{p+1, \ldots, p+q\}\) 時，一樣有 \((B)_{i,j} = 0\)。因此，\(D_1\) 和 \(D_2\) 為對角矩陣。另一方面，當 \(i\in\{1, \ldots, p\}\) 且 \(j\in\{p+1, \ldots, p+q\}\) 時，\(\by_i \geq 0\)、\(A'[X_i,X_j] \leq 0\)、以及 \(\by_j \leq 0\) 使得 \((B)_{i,j} \leq 0\)。最後，\(B\bone = S\trans A'S\bone = S\trans A'\by = \bzero\)，如此一來，\(D_1\) 和 \(D_2\) 的對角線元素會被 \(C\) 決定，且 \(D_1, D_2 \leq 0\)。所以 \(B\) 是一個賦權拉普拉斯矩陣的負號，因此 \(B\) 為半負定矩陣。如此一來我們就有

\[ \mathfrak{S}(\by) = s = n_-(B) + n_0(B) \leq n_-(A') + n_0(A') = b. \]

接下來我們證明 \(\mathfrak{W}(\by) \leq a\)，流程幾乎跟強峰谷的狀況一樣，但我們需要多加一個步驟。令 \(N_0\) 為對於 \(\by\) 來說 \(G\) 上零點的集合，並令 \(I_0\) 為 \(n\times n\) 對角矩陣，其 \(i,i\)-項當 \(i\in N_0\) 時是 \(1\)，否則為 \(0\)。由於 \(I_0\) 是一個半正定矩陣，對任意 \(t > 0\)，都有 \(n_-(A - \lambda I + tI_0) \leq n_-(A - \lambda I)\)。我們取 \(t > 0\) 夠大，使得 \((A - \lambda I + tI_0)[N_0]\) 是一個正定矩陣，並令 \(A' = A - \lambda I + tI_0\)。如此一來就有 \(n_-(A') + 1 \leq n_-(A - \lambda I) + 1 = b\)。我們的目標是利用引理 2 找到一個矩陣 \(B\) 使得 \(n_-(B) + 1 = \mathfrak{W}(\by)\)。

剩下的論述與強峰谷的部份類似。根據 \(\by\)，令 \(X_1, \ldots, X_p\) 為 \(G[N_{\geq 0}]\) 上的區塊點集、 \(X_{p+1}, \ldots, X_{p+q}\) 為 \(G[N_{\leq 0}]\) 上的區塊點集、而 \(s = p + q = \mathfrak{W}(\by)\)。對於所有 \(k = 1, \ldots, s\)，更新 \(X_i\) 為 \(X_i \setminus N_0\)，接著將 \(\by\) 上 \(X_i\) 以外的項都設定為 \(0\)，稱此向量為 \(\by_i\)。如此一來我們有 \(\sum_{i=1}^s\by_i = \by\)，同時我們有 \(\by_1,\ldots, \by_p \geq 0\) 以及 \(\by_{p+1}, \ldots, \by_{p+q} \leq 0\)。（依照這樣的設定，每個 \(X_i\) 都是一些強峰的聯集、或是一些強谷的聯集。）我們也令 \(Z_1, \ldots, Z_r\) 為 \(G[N_0]\) 上的區塊點集；對於 \(k = 1,\ldots, r\)，定義 \(\bz_k[N_0]\) 為 \(A'[Z_k]\) 的最小特徵值的特徵向量，而 \(\bz_k\) 上的其它項為零。根據佩弗定理，我們可以取 \(\bz_k[N_0] > 0\)。

令 \(S\) 為 \(n\times (r+s)\) 矩陣，其行向量為 \(\bz_1, \ldots, \bz_r, \by_1, \ldots, \by_s\)。由於這些向量的非零項位置彼此沒有重疊，\(S\) 的行向量集合線性獨立。令 \(B = S\trans A'S\)，且根據引理 2 我們有 \(n_-(B) \leq n_-(A')\)。接著我們觀察 \(B\) 具有以下的形式

\[ B = \begin{bmatrix} D_0 & E_1 & E_2 \\ E_1\trans & D_1 & C \\ E_2\trans & C\trans & D_2 \end{bmatrix}, \]

其中 \(D_0,D_1,D_2\) 的大小分別為 \(r,p,q\)。由於 \(A'[N_0]\) 正定，\(D_0\) 是一個正定對角矩陣；根據弱峰谷的定義，每塊 \(Z_k\) 都只會跟 \(\{X_1, \ldots, X_p\}\) 中其中一塊相鄰；若相鄰兩塊，這兩塊應該要屬於同一個弱峰。同理，每塊 \(Z_k\) 只會跟 \(\{X_{p+1}, \ldots, X_{p+q}\}\) 中其中一塊相鄰。這表示從 \(D_0\) 的任一列往右看，在 \(E_1\) 中只有一個非零項，而在 \(E_2\) 中也只有一個非零項。由於 \(\by = \sum_{k=1}^s \by_k\)，我們有

\[ \begin{bmatrix} D_0 & E_1 & E_2 \\ E_1\trans & D_1 & C \\ E_2\trans & C\trans & D_2 \end{bmatrix} \begin{bmatrix} \bzero \\ \bone \\ \bone \end{bmatrix} = \bzero. \]

因此前述 \(E_1\) 和 \(E_2\) 中同一列上的兩個非零項剛好一正一負，且相加為零。如此一來，我們可以對 \(B\) 和 \(D_0\) 計算舒爾補矩陣（Schur complement），並得到 \(B / D_0\) 是一個連通圖的賦權拉普拉斯矩陣的負號，因此 \(n_-(B) = n_-(B / D_0) = s - 1\)。統整所有資訊，得到

\[ \mathfrak{W}(\by) = s = n_-(B) + 1 \leq n_-(A') + 1 \leq n_-(A - \lambda I) + 1 = b. \]

如此完成定理證明。\(\blacksquare\)

令 \(G\) 為一個連通圖、\(A\in\ddot{\mathcal{S}}(G)\) 且 \(\by\) 為其一特徵向量。在只知道 \(\by\) 正負號但不知道 \(A\) 和 \(\by\) 的情況下，離散峰谷定理給出對應特徵值的序位 \(a\) 和 \(b\) 的下界。這個下界是最好的嗎？換句話說，如果只給定 \(G\) 和 \(\by\) 的正負號，有沒有可能找到 \(A\) 和 \(\by\) 使得 \(\mathfrak{W}(\by) = a\) 或 \(\mathfrak{S}(\by) = b\)？另一方面，費德勒對於樹圖特徵向量的刻畫非常精細，離散峰谷定理如果套用在樹圖上時，跟費德勒的結果相比又是如何呢？

想想以下問題：

基於樹圖的特徵向量文末的程式碼，調整成一般圖，並觀察其特徵向量是否符合離散峰谷定理。
比較離散峰谷定理的證明中，強峰谷及弱峰谷處理方式的不同。
描述舒爾補矩陣的定義，並說明對任意對稱矩陣 \(M\) 及其主子矩陣 \(A\) 來說，都有 \(\operatorname{in}(M) = \operatorname{in}(A) + \operatorname{in}(M/A)\)。
描述離散峰谷定理的弱峰谷證明中，\(B/D_0\) 的圖長什麼樣子。
觀察離散峰谷定理的強峰谷證明，並證明 \(\mathfrak{S}(\by) - c + 1 \leq a\)。[提示：觀察 \(n_-(B)\)。]
當 \(G\) 是樹圖時，比較樹圖的特徵向量定理 4 和離散峰谷定理的優劣。