變號邊 | LA Tea

根據離散峰谷定理，特徵向量的峰谷數與對應特徵值的序位有關。當考慮的圖為樹圖、且當向量為逐向非零時，若有 \(k\) 個強峰谷，則恰有 \(k - 1\) 條變號邊。實際上，這也是樹圖的特徵向量定理 2 的敘述，費德勒證明了在樹圖上，第 \(k\) 小的特徵值對應到的特徵向量，當其逐項非零時，恰有 \(k\) 個強峰谷、同時也恰有 \(k - 1\) 條變號邊。換句話說，變號邊的數量也可以用來描述向量在圖上的振盪程度，並用來估算特徵值序位。

伯科萊科（Gregory Berkolaiko）將費德勒的定理推廣到一般圖，並用圖的邊數來控制變號邊的數量。我們知道 \(n\) 個點的樹圖恰有 \(n - 1\) 條邊；當 \(G\) 為 \(n\) 個點 \(m\) 條邊的連通圖時，\(G\) 的 圈維度（cyclotomic number） 定為 \(\beta(G) = m - n + 1\)，可視為圖 \(G\) 超過樹圖的複雜程度。當連通圖 \(G\) 有 \(\beta(G) = 0\) 時，則 \(G\) 為樹圖；當 \(\beta(G)\) 愈高，則該圖就愈複雜。

定理 1（伯科萊科 2008）

令 \(G\) 為一連通圖、\(A\in\ddot{\mathcal{S}}(G)\)、\(\lambda\) 為 \(A\) 第 \(k\) 小的特徵值、且 \(\by\) 為一對應之特徵向量。若 \(\lambda\) 為單根且 \(\by\) 逐項非零，則 \(\by\) 在圖上的變號邊數有符合

\[ k - 1 \leq \vert{}\{\{i,j\}\in E(G): (\by)_i(\by)_j < 0\}\vert{} \leq k - 1 + \beta(G). \]

證明

令 \(n\) 為 \(G\) 的點數。令 \(p\) 為變號邊的數量、\(q\) 為同號邊的數量，我們有 \(p + q = m\) 為 \(G\) 的邊數。

定義 \(D\) 為對角矩陣，其對角線項為 \(\by\)。如此一來，\(B = D(A - \lambda I)D\) 符合 \(B\bone = D(A - \lambda I)D\bone = D(A - \lambda I)\by = \bzero\)。我們可以觀察到 \(B\in\mathcal{S}(G)\)：當 \(\{i,j\}\) 是 \(G\) 的一條邊時，有 \((B)_{i,j} = (\by)_i(A)_{i,j}(\by)_j\)；而當 \(\{i,j\}\) 不是邊且 \(i \neq j\) 時，\((B)_{i,j} = 0\)；\(B\) 的對角線項可由非對角線項及 \(B\bone = \bzero\) 這個關係計算得出。如果我們允許權重為負，\(B\) 可以看成是 \(G\) 的廣義賦權拉普拉斯矩陣，因此 \(B\) 可以寫成 \(p\) 個半負定秩一矩陣相加的和、再加上 \(q\) 個半正定秩一矩陣相加的和。由於 \(\lambda\) 為單根，\(n_-(A - \lambda I) = k - 1\) 且 \(n_+(A - \lambda I) = n - k\)。根據西爾維斯特慣性定律，我們有 \(k - 1 \leq p\) 且 \(n - k \leq q\)。由於 \(q = m - p = n - 1 + \beta(G) - p\)，前述的兩個不等式可總結為 \(k - 1 \leq p \leq k - 1 + \beta(G)\)，即為我們希望得到的不等式。\(\blacksquare\)

由於這個不等式，變號邊數扣掉 \(k - 1\) 的數量，被稱為 變號超出數（nodal surplus），用來描述該特徵向量的變號邊數超過基本值 \(k - 1\) 多少。而伯科萊科在幾年後發表了另一篇文章，說明變號超出數可以利用赫塞矩陣（Hessian matrix）來計算。回顧一下，如果 \(f: \mathbb{R}^d \rightarrow \mathbb{R}\) 為一函數，其變數為 \(x_1, \ldots, x_d\)，則 \(f\) 的赫塞矩陣 \(\operatorname{Hess}(f)\) 為一 \(d\times d\) 矩陣，其 \(i,j\)-項定義為 \(\frac{\partial f}{\partial x_i\partial x_j}\)。另一方面，給定一圖 \(G\) 及 \(A\in\mathcal{S}(G)\)，定義 \(A\) 的 磁擾動（magnetic perturbation） 如下：

將 \(G\) 的邊編號為 \(e_1, \ldots, e_m\)，並定義變數 \(\theta_1, \ldots, \theta_m\in\mathbb{R}\)。
若 \(e_r = \{i,j\}\) 且 \(i < j\)，更新 \(A\) 的 \(i,j\)-項為 \((A)_{i,j}e^{\theta_r\sqrt{-1}}\)、更新其 \(j,i\)-項為 \((A)_{i,j}e^{-\theta_r\sqrt{-1}}\)。對每條邊都做如此更新。
定義 \(\theta = (\theta_1, \ldots, \theta_m)\)，其對應更新後的矩陣稱為 \(A_\theta\)。

當 \(\theta = \bzero\) 時，我們有 \(A_\theta = A\)。同時注意到 \(A_\theta\) 是一個埃爾米特矩陣（Hermitian matrix），所以其特徵值均為實數。因此，當 \(\theta\) 在 \(\bzero\) 附近時，磁擾動 \(A_\theta\) 的特徵值會在 \(A\) 的特徵值附近移動。結合赫塞矩陣及磁擾動，伯科萊科證明的 變號磁定理（nodal magnetic theorem） 敘述如下。

變號磁定理（伯科萊科 2013）

令 \(G\) 為一連通圖、\(A\in\ddot{\mathcal{S}}(G)\)、\(\lambda\) 為 \(A\) 第 \(k\) 小的特徵值、且 \(\by\) 為一對應之特徵向量。若 \(\lambda\) 為單根且 \(\by\) 逐項非零，則 \(\by\) 在圖上的變號邊超出數有符合

\[ \vert{}\{\{i,j\}\in E(G): (\by)_i(\by)_j < 0\}\vert{} - (k - 1) = n_-(\operatorname{Hess}(\lambda_k(A_\theta))). \]

這裡的赫塞矩陣裡的微分取值在 \(\theta = \bzero\)，而 \(\lambda_k(A_\theta)\) 為 \(A_\theta\) 第 \(k\) 小的特徵值。

這個定理的證明需要的技術面向較多，所以我們這邊不提，但定理的敘述有一些細節值得注意。首先，\(A_{\bzero} = A\)，且 \(\lambda_k(A_{\bzero})\) 為單根，所以 \(\lambda_k(A_\theta)\) 是 \(\theta\) 的連續函數，讓微分是可能的。另一方面，\(A_\theta\) 的變數數即為 \(G\) 的邊數 \(m\)，所以這個赫塞矩陣是一個 \(m\times m\) 矩陣，但伯科萊科在同一篇文章中證明了 \(\lambda_k(A_\theta)\) 往 \(n - 1\) 個獨立的方向微分為零，因此該赫塞矩陣至多有 \(m - (n - 1) = \beta(G)\) 個負的特徵值，再次看出變號邊超出數的個數不大於 \(\beta(G)\)。

變號邊的個數是近期熱門的研究方向之一，結合了物理、偏微分方程、以及圖論，也還有許多待解的問題。變號邊個數和峰谷數的關係為何？離散峰谷定理給出峰谷數的上界，但定理 1 給出變號邊數的上下界，峰谷數是否也能用 \(\beta(G)\) 給出下界？這些界的等號都有可能發生嗎、或是可以再改進？

如果一個矩陣 \(A\in\ddot{\mathcal{S}}(G)\) 的每個特徵向量都是單根、且有一組特徵基底中的每個特徵向量都逐項非零，則我們可以考慮每個特徵值對應的變號超出數的總合。當 \(G\) 是樹圖時，這個總合是零；對一般 \(G\) 來說，近期也被證明介於 \(\beta(G)\) 到 \((n - 1)\beta(G)\) 之間。對於變號超出數的總合，我們也可以問同樣的問題：給定任一個圖，等號有可能發生嗎、或是可以再改進？

想想以下問題：

基於樹圖的特徵向量文末的程式碼，調整成一般圖，並觀察其特徵向量是否符合定理 1。
將 \(B\) 矩陣寫成 \(3\) 個半負定秩一矩陣的和、加上 \(1\) 個半正定秩一矩陣，其中
\[ B = \begin{bmatrix} 0 & 1 & 0 & -1 \\ 1 & -2 & 1 & 0 \\ 0 & 1 & -2 & 1 \\ -1 & 0 & 1 & 0 \end{bmatrix}. \]
西爾維斯特慣性定律有不同的版本，說明本篇文章中提到的是哪一個版本，並說明怎麼用它來證明定理 1。
令 \(L\) 為 \(P_3\) 的拉普拉斯矩陣，而 \(L_\theta\) 為 \(L\) 的磁擾動。說明對任何 \(\theta\) 都有 \(\spec(L_\theta) = \spec(L)\)。若 \(L\) 為一樹圖 \(T\) 的拉普拉斯矩陣，是否有同樣的性質？