6.1 圖拉普拉斯矩陣與譜座標

一組觀測未必附有每項特徵的有意義座標。我們可能只知道哪些對象互相作用，以及作用有多強。圖記錄的就是這類資料。要從圖建立座標，先要說清楚座標應達成甚麼：相鄰頂點的座標差應小，但整個配置又不能全部塌縮至同一點。

本原創補充筆記為有限、無向、非負加權圖推導這種構造。數學準備包括有限和、實內積、正交投影及基本微分。我們也會使用有限維緊緻性：實歐氏空間中的閉有界集是緊緻的，而非空緊緻集上的連續實函數取得最大值及最小值。PCA 筆記已發展 SVD 與投影優化；我們沿用其中的投影權重方法，並在此證明所需的有限維實譜定理。MDS 筆記處理另一問題：重建給定的距離表。這裏的路徑是由互不相同頂點組成的有限序列，相鄰頂點之間有正權邊；零長路徑把一個頂點連至自身。兩點之間存在路徑便稱為連通，所得等價類稱為連通分量。為證傳遞性，把兩條路徑串接成可重複頂點的遊走，再刪去同一頂點兩次出現之間的部分。每次刪除都保留端點並縮短遊走，有限次之後便得到路徑。

以下會明確區分三件事。對稱親和矩陣未必是半正定核矩陣；平穩的隨機遊走分佈未必是極限分佈；連續譜鬆弛未必精確解決其離散割問題。

1. 加權邊與頂點函數的能量

設頂點集為 $V=\{1,\ldots,n\}$，先假設 $n\ge1$。權重矩陣 $W=(w_{ij})\in\mathbb R^{n\times n}$ 滿足

$$w_{ij}=w_{ji}\ge0,\qquad w_{ii}=0.$$

權重可以是任何非負實數，不必是概率、整數或不大於一。支撐圖恰在 $w_{ij}>0$ 時有無向邊 $\{i,j\}$。所有連通分量均指此圖的分量。即使圖畫上畫了某對頂點之間的線，零權重也不提供連接。

加權度數、度數矩陣與未歸一化拉普拉斯矩陣分別為

$$d_i=\sum_{j=1}^n w_{ij},\qquad D=\operatorname{diag}(d_1,\ldots,d_n), \qquad L=D-W.$$

由非負性，$d_i=0$ 當且僅當第 $i$ 行的權重全部為零；這樣的頂點是孤立點。頂點函數是一個實列向量 $f=(f_1,\ldots,f_n)^T$，可表示候選座標、溫度或其他純量訊號。矩陣乘法給出

$$(Lf)_i=\sum_jw_{ij}(f_i-f_j).$$

因此 $L\mathbf1=0$，其中 $\mathbf1$ 是全一列向量。把常數加到訊號上不會改變邊兩端的差。

能量恆等式。 對每個 $f\in\mathbb R^n$，

$$f^TLf =\frac12\sum_{i,j}w_{ij}(f_i-f_j)^2 =\sum_{i<j}w_{ij}(f_i-f_j)^2.$$

證明。 展開雙和，兩個平方項給出 $\frac12\sum\limits_i d_i f_i^2+\frac12\sum\limits_j d_j f_j^2=\sum\limits_i d_i f_i^2$；第二個度數和的辨認使用了對稱性。交叉項是 $-\sum\limits_{i,j}w_{ij}f_if_j$，相減便是 $f^T(D-W)f$。每個無序頂點對在雙和出現兩次，對角項則為零，故亦得到最後的等式。所有和均為有限和。∎

所以 $L$ 對稱且半正定。強邊的座標差受到較重懲罰；這裏沒有使用協方差解釋，也沒有假設 $W$ 本身半正定。例如

$$W=\begin{pmatrix}0&a\\a&0\end{pmatrix},\qquad a>0,$$

的特徵值為 $a,-a$，其拉普拉斯矩陣的特徵值卻是 $0,2a$。這個圖親和矩陣不是半正定 Gram 矩陣。反過來，兩個實向量 $1,-1$ 的 Gram 矩陣為 $\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$；其二次型是 $(x_1-x_2)^2$，所以半正定，但非對角元素有負數，並不符合這裏的圖假設。

核與連通分量。 函數屬於 $\ker L$，當且僅當它在每個支撐分量上為常數。因此，若分量數為 $c$，則

$$\dim\ker L=c,\qquad \operatorname{rank}L=n-c.$$

證明。 若 $Lf=0$，則 $f^TLf=0$。能量的每項均非負，所以每條正權邊的端點函數值必相同。沿路徑傳遞此等式，便知每個分量上的值相同。反之，若函數在各分量為常數，則 $(Lf)_i=\sum\limits_jw_{ij}(f_i-f_j)$ 的每項均為零：正權邊留在同一分量，零權邊不作貢獻。分量的指示列向量支撐互不相交，而且每個分量非空，所以它們線性獨立，亦張成所有這類函數。每個孤立點同樣貢獻自己的指示向量。由秩—零度定理得到秩公式。∎

符號假設不能省略。若二點圖的唯一邊權為 $-1$，能量便是 $-(f_1-f_2)^2$，對非常數函數為負。有向圖與帶符號圖需要不同陳述，不在本筆記範圍內。

2. 有限維實譜橋樑與第二特徵值

PCA 的構造使用實對稱矩陣的正交歸一特徵基。以下給出有限維證明，讓圖的論證不依賴隱藏的譜定理。

實對稱譜定理。 每個實對稱矩陣 $S$ 都有由實特徵向量組成的正交歸一基。

證明。 零維時空基已足夠。維數 $m\ge1$ 時，連續函數 $x\mapsto x^TSx$ 在緊緻單位球面上取得最大值。選一個達到最大值的單位列向量 $v$。對任意滿足 $h^Tv=0$ 的實列向量 $h$，曲線

$$x(t)=\frac{v+th}{\sqrt{1+t^2\|h\|^2}}$$

對每個實 $t$ 都有單位長度。可以在零點微分，其二次型導數為

$$\left.\frac{d}{dt}\bigl(x(t)^TSx(t)\bigr)\right|_{t=0} =2h^TSv=0.$$

所以 $Sv$ 垂直於 $v^\perp$ 的每個向量。由 $\operatorname{span}\{v\}$ 與 $v^\perp$ 的正交分解，存在實數 $\lambda$ 使 $Sv=\lambda v$。若 $h\in v^\perp$，對稱性給出 $v^TSh=(Sv)^Th=\lambda v^Th=0$，故 $v^\perp$ 是不變子空間，限制在其上的算子仍實對稱。對維數 $m-1$ 使用歸納假設，再加上 $v$，便得到所需正交歸一特徵基。∎

半正定矩陣的每個特徵值均非負，因為 $Sq=\lambda q$ 且 $\|q\|=1$ 時有 $\lambda=q^TSq\ge0$。

將此用於 $L$。已知的零特徵值方向使我們可以先選第一個特徵向量：

$$q_1=\frac{\mathbf1}{\sqrt n}.$$

由 $\mathbf1^TLf=(L\mathbf1)^Tf=0$，空間 $\mathbf1^\perp$ 不變。對其限制使用定理，把特徵值遞增排列，得到

$$Lq_j=\lambda_jq_j,\qquad 0=\lambda_1\le\lambda_2\le\cdots\le\lambda_n.$$

此排序容許多個零特徵值。把 $q_1$ 選成常數並不表示圖連通。

當 $n\ge2$，第二特徵值具有精確優化公式

$$\lambda_2 =\min_{\substack{f^T\mathbf1=0\\\|f\|=1}} f^TLf.$$

證明。 把中心化單位函數寫為 $f=\sum\limits_{j=2}^n a_jq_j$，則 $\sum\limits_{j=2}^n a_j^2=1$，且 $f^TLf=\sum\limits_{j=2}^n\lambda_ja_j^2\ge\lambda_2$。取 $f=q_2$ 達到此界。等號成立當且僅當所有對應大於 $\lambda_2$ 特徵值的係數為零。因此所有極小函數是 $\mathbf1^\perp$ 中 $\lambda_2$ 特徵空間的單位向量，不是一個具有唯一方向的列向量。∎

特別地，$\lambda_2>0$ 當且僅當支撐圖連通。若連通，核只有 $\operatorname{span}\{\mathbf1\}$，其正交補上的每個特徵值均正。若不連通，便存在非零、中心化而分量常值的函數，故極小值為零。這是代數譜與組合結構之間的精確聯繫。

只有一個頂點時 $L=0$，既沒有第二特徵值，也沒有中心化單位函數。兩個或以上頂點的零矩陣有多個分量，且 $\lambda_2=0$。也可以另行容許空頂點集：矩陣為空，核的維數為零，但同樣沒有第二特徵值。這些情況都不表示在不存在的單位向量上取極小值。

3. 不除以孤立度數的歸一化

加權度數可能相差很大。歸一化以端點度數調整邊差，但必須先處理零度數。

設

$$S=\{i:d_i>0\},\qquad Z=V\setminus S.$$

沒有邊與 $Z$ 相接。把 $W,D,L$ 限於 $S$，所得矩陣記作 $W_S,D_S,L_S$。若 $S$ 非空，$D_S$ 正定，可以定義

$$N_S=D_S^{-1/2}L_SD_S^{-1/2} =I_S-D_S^{-1/2}W_SD_S^{-1/2}.$$

全空間的歸一化拉普拉斯矩陣 $N$ 在 $S$ 上等於 $N_S$，在每個孤立座標上則等於零。等價地，令對角矩陣 $R$ 在 $S$ 上的元素為 $d_i^{-1/2}$，在 $Z$ 上為零，則

$$N=RLR.$$

有孤立點時，此矩陣不等於 $I_n-RWR$；後者把孤立對角元素設成一。解釋零模前必須交代使用哪種約定。本筆記始終使用零延拓。若 $S$ 為空，$N=0$，不會形成任何度數逆矩陣。

對活躍座標上的列向量 $x$，令 $g=D_S^{-1/2}x$。能量恆等式給出

$$x^TN_Sx=\sum_{\substack{i<j\\i,j\in S}}w_{ij} \left(\frac{x_i}{\sqrt{d_i}}-\frac{x_j}{\sqrt{d_j}}\right)^2.$$

所以 $N_S$ 半正定。其核中的向量，在每個活躍支撐分量上都等於同一常數乘以 $\sqrt{d_i}$。逆向可由座標公式看出，或注意分量常值的 $g$ 滿足 $N_Sx=D_S^{-1/2}L_Sg=0$。因此每個活躍分量貢獻限制於該分量的 $\sqrt d$ 列向量；零延拓下每個孤立列向量 $e_i$ 再貢獻一個核向量。全歸一化矩陣與未歸一化矩陣的核維數相同，但在活躍分量上的向量縮放不同。

$N$ 的譜包含於 $[0,2]$。事實上，在活躍座標上，由 $(a-b)^2\le2a^2+2b^2$ 得

$$0\le x^TN_Sx \le 2\sum_i d_i\left(\frac{x_i}{\sqrt{d_i}}\right)^2 =2\|x\|^2.$$

每條邊分別貢獻至兩端的度數和，故沒有額外的二倍因子。把此界用於單位特徵向量，便知每個活躍特徵值介乎零與二；孤立零特徵值也符合此界。兩個頂點由一條正權邊相連時，歸一化矩陣是 $\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$，特徵值 $0,2$ 同時達到兩端。

歸一化是度量的改變，不是把零度數取逆的許可。加權形式 $f^TDg$ 在活躍座標上是內積，在全空間卻會於孤立列向量上消失，僅為半正定形式。

4. 可逆遊走未必收斂

只在活躍集上定義

$$P=D_S^{-1}W_S,\qquad P_{ij}=\frac{w_{ij}}{d_i}.$$

矩陣元素非負，每行和為一。因此它是行隨機轉移矩陣：$P_{ij}$ 表示一步由 $i$ 到 $j$ 的概率。對頂點函數 $f$，$(Pf)_i$ 是從 $i$ 出發走一步後的函數期望值。相反，概率列向量 $r_t$ 的更新是

$$r_{t+1}=P^Tr_t.$$

這個轉置不可忽略。把概率列向量乘以 $P$ 使用了另一約定，未必保留其總質量。

本節餘下所有矩陣與列向量均限於 $S$。由 $W$ 對稱，

$$DP=W=P^TD.$$

因此 $P$ 對內積 $\langle f,g\rangle_D=f^TDg$ 自伴： $f^TDPg=f^TWg=(Pf)^TDg$。它未必在普通歐氏內積下對稱。直接計算相似變換得

$$D^{1/2}PD^{-1/2}=D^{-1/2}WD^{-1/2}=I-N_S.$$

所以若 $N_Su=\mu u$，則 $f=D^{-1/2}u$ 滿足 $Pf=(1-\mu)f$。$N_S$ 的正交歸一特徵基轉成 $P$ 的 $D$-正交歸一特徵基。特別地，$P$ 的特徵值均為實數且位於 $[-1,1]$，不需要另引隨機矩陣譜定理。

若 $S$ 非空，總度數 $\operatorname{vol}(S)=\sum\limits_{i\in S}d_i$ 為正。定義概率列向量

$$\pi_i=\frac{d_i}{\operatorname{vol}(S)}.$$

對每個活躍 $j$，有限求和給出

$$(\pi^TP)_j =\sum_i\frac{d_i}{\operatorname{vol}(S)}\frac{w_{ij}}{d_i} =\frac{d_j}{\operatorname{vol}(S)}=\pi_j.$$

因此 $\pi$ 平穩。又有 $\pi_iP_{ij}=w_{ij}/\operatorname{vol}(S)=\pi_jP_{ji}$，即細緻平衡恆等式。活躍圖若不連通，在任一分量內單獨歸一化度數，便得到支撐於該分量的平穩分佈；這些分佈的凸組合也平穩。未經進一步論證，我們不宣稱唯一性。

平穩不等於收斂。兩個頂點之間只有一條正權邊時，

$$P=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad \pi=\begin{pmatrix}1/2\\1/2\end{pmatrix}.$$

分佈 $\pi$ 保持不變，但從頂點一出發的遊走，每個偶數時刻都在頂點一，奇數時刻都在頂點二，其分佈不收斂。代數上，特徵值 $-1$ 保留了一個交替分量；對應的歸一化特徵值是 $2$。所以存在平穩向量不能推出混合結論。本筆記不作一般收斂速率聲明。

若所有度數為零，活躍集為空，沒有活躍遊走或由度數歸一化得到的概率分佈。可以另行把孤立狀態設為吸收態，但那是額外模型資料，不是零除以零所得的值。

5. 譜座標實際極小化甚麼

常數座標的能量為零；把所有座標設成零，更會令所有頂點重合。為避免這些塌縮，要求座標列中心化且正交歸一。

對整數 $0\le k\le n-1$，選 $U\in\mathbb R^{n\times k}$ 滿足

$$U^TU=I_k,\qquad U^T\mathbf1=0.$$

頂點 $i$ 的座標是第 $i$ 行 $U_{i:}\in\mathbb R^k$。把純量能量公式用於每列並求和，便證得

$$\operatorname{tr}(U^TLU) =\sum_{i<j}w_{ij}\|U_{i:}-U_{j:}\|^2.$$

此目標是加權邊上的總平方變化，不是與給定成對距離表的誤差。

最小跡原理。 沿用第2節的特徵值排序，

$$\min_{\substack{U^TU=I_k\\U^T\mathbf1=0}} \operatorname{tr}(U^TLU) =\sum_{j=2}^{k+1}\lambda_j.$$

$k=0$ 時矩陣沒有列，兩邊均為零。$k\ge1$ 時可取 $U=[q_2\ \cdots\ q_{k+1}]$ 達到此值。

證明。 在 $\mathbf1^\perp$ 內工作，其正交歸一特徵基為 $q_2,\ldots,q_n$。令

$$a_j=\|U^Tq_j\|^2,\qquad 2\le j\le n.$$

因 $UU^T$ 是到 $U$ 列空間的正交投影，$0\le a_j\le1$。把 $U$ 每個單位列向量在此基底展開，再加總其平方係數，得 $\sum\limits_{j=2}^na_j=k$。譜展開亦給出 $\operatorname{tr}(U^TLU)=\sum\limits_{j=2}^n\lambda_ja_j$。

設 $c=\lambda_{k+1}$。剛證得的總和恆等式給出精確差值

$$\begin{aligned} \sum_{j=2}^n\lambda_ja_j-\sum_{j=2}^{k+1}\lambda_j &=\sum_{j=2}^{k+1}(c-\lambda_j)(1-a_j)\\ &\quad+\sum_{j=k+2}^n(\lambda_j-c)a_j\ge0. \end{aligned}$$

每個顯示的係數均非負。取中心空間內首 $k$ 個特徵向量便達到等號，證明了極小值。這正是 PCA 使用的投影權重方法，只因現在極小化變化而非極大化方差，所以特徵值排序方向相反。∎

對 $k\ge1$，差值公式亦給出精確等號條件。在 $\mathbf1^\perp$ 內，保留列空間必須包含特徵值小於 $c$ 的全部特徵空間，並垂直於特徵值大於 $c$ 的全部特徵空間；在特徵值等於 $c$ 的空間內，則可任選補足至 $k$ 維所需的維數。理由是：$a_j=1$ 表示投影保留 $q_j$ 的全部範數，故 $q_j$ 在該列空間；$a_j=0$ 表示它垂直於該空間。截斷值處的零係數恰好留下上述自由。即使 $c>0$，也不會要求把已排除的常數方向重新納入。

若 $k<n-1$ 且 $\lambda_{k+1}<\lambda_{k+2}$，保留子空間確定。若 $k=n-1$，保留的就是整個中心空間，也確定。但兩者都沒有固定一個帶方向的基底。若兩個可行矩陣 $U,V$ 張成同一子空間，定義 $Q=U^TV$。因到該空間的投影同時等於 $UU^T$ 與 $VV^T$，

$$UQ=UU^TV=V,\qquad Q^TQ=V^TUU^TV=V^TV=I_k.$$

方陣 $Q$ 正交，所以 $V=UQ$ 不改變行座標間的距離，亦有 $VV^T=UU^T$。但是跨越截斷邊界的重特徵值可以容許真正不同的保留子空間；它們的行距離未必相同，第2題會明算此現象。

若圖不連通，某些中心化分量指示組合具有零能量。定理仍成立，可以把不同分量分開而不為不存在的連接付出能量，但不會辨認出唯一聚類。一個頂點只允許 $k=0$。空圖也可另行容許空的零列配置，不涉及任何非零維嵌入聲明。

比較其目標：PCA 從特徵觀測保留最大方差方向；經典 MDS 從距離尋找中心化 Gram 實現；此處則由給定邊權定義平滑程度，保留最低非常數圖能量方向。使用特徵向量不代表解的是同一問題。因此以上正交歸一圖座標並未聲稱具有 PCA 解釋方差比例、MDS 距離保留定理，或逆平方根特徵值縮放。

6. 歸一化割的精確指示商與鬆弛

現在假設支撐圖連通且 $n\ge2$，故每個度數均正。對非空真子集 $A\subset V$，令 $B=V\setminus A$，定義

$$\operatorname{vol}(A)=\sum_{i\in A}d_i,\qquad \operatorname{cut}(A,B)=\sum_{\substack{i\in A\\j\in B}}w_{ij}.$$

體積把內部邊計兩次、跨界邊計一次：

$$\operatorname{vol}(A) =2\sum_{\substack{i<j\\i,j\in A}}w_{ij}+\operatorname{cut}(A,B).$$

把每個度數和按鄰點在 $A$ 內外分開，便得到此式。它不是僅數與 $A$ 相接的邊。寫 $a=\operatorname{vol}(A)>0$、$b=\operatorname{vol}(B)>0$，歸一化割值定義為

$$\operatorname{Ncut}(A,B) =\operatorname{cut}(A,B)\left(\frac1a+\frac1b\right).$$

這個指標有精確二次型表示。定義兩級函數

$$f_i=\begin{cases}1/a,&i\in A,\\-1/b,&i\in B.\end{cases}$$

其度數加權平均和平方範數為

$$f^TD\mathbf1=1-1=0,\qquad f^TDf=\frac1a+\frac1b.$$

只有跨界邊對能量有貢獻，所以

$$f^TLf=\operatorname{cut}(A,B)\left(\frac1a+\frac1b\right)^2.$$

以能量除以正的平方範數，證得

$$\frac{f^TLf}{f^TDf}=\operatorname{Ncut}(A,B).$$

要放鬆 $f$ 只能取這兩個值的限制，令 $x=D^{1/2}f$，則

$$x^TNx=f^TLf,\qquad x^Tx=f^TDf,\qquad x^T\sqrt d=f^TD\mathbf1=0,$$

其中 $\sqrt d=(\sqrt{d_1},\ldots,\sqrt{d_n})^T$。連通圖的 $N$ 恰有由 $\sqrt d$ 張成的一維核。先取其歸一化核向量，再如第2節般把正交補對角化。若特徵值依序為 $0=\mu_1<\mu_2\le\cdots\le\mu_n$，在該正交歸一特徵基展開便證得

$$\mu_2=\min_{\substack{x\ne0\\x^T\sqrt d=0}} \frac{x^TNx}{x^Tx} \le\min_{\varnothing\ne A\subsetneq V}\operatorname{Ncut}(A,V\setminus A).$$

非空真子集只有有限個，所以割的最小值存在。不等式成立是因為每個由指示函數所得的向量，都是連續問題的可行競爭者。鬆弛可行集還有很多其他向量，因此不必取等號。第4題給出嚴格差距。符號或排序閾值程序是額外的離散化選擇；這裏沒有證明它的一般精確割或近似保證。

圖若有孤立點，某一側可能體積為零，使此商沒有定義。第3節的活躍歸一化矩陣仍存在，卻不會因此替零分母指派值。歸一化割定理特意使用連通且正度數的支撐。

7. 常見解讀錯誤

零特徵值記錄分量常值訊號，不代表唯一且有資訊的座標；支撐不連通便有多個零模。孤立點不能按度數取逆，而把其零區塊暗改為一，會改變歸一化算子。

$P$ 的歐氏對稱性強於加權恆等式 $DP=P^TD$。同樣，細緻平衡與平穩向量不保證從每個起點收斂。二點例子把這些區別都保持為有限而精確的計算。

最後，座標符號任意，重特徵值則要求留意保留子空間。即使子空間已確定，基底仍可旋轉；重值若跨越截斷邊界，子空間本身也可改變。若不檢查這些選擇便比較繪圖軸，可能把代數不唯一性誤當成資料改變。

8. 題目與完整解答

Question 1

四個頂點的權重為 $w_{12}=1$、$w_{23}=2$，其他非對角權重均零。求度數、拉普拉斯矩陣、分量、核與完整未歸一化譜。求可處理孤立點的歸一化譜及一組正交歸一特徵基，再求活躍轉移矩陣與度數平穩分佈。解釋為何活躍均勻分佈及全矩陣 $I_4-RWR$ 都不符合所述結論或約定。

Solution. 對稱性給出反向邊權。矩陣為

$$W=\begin{pmatrix}0&1&0&0\\1&0&2&0\\0&2&0&0\\0&0&0&0\end{pmatrix},\qquad D=\operatorname{diag}(1,3,2,0),\qquad L=\begin{pmatrix}1&-1&0&0\\-1&3&-2&0\\0&-2&2&0\\0&0&0&0\end{pmatrix}.$$

兩個分量為 $\{1,2,3\}$ 與 $\{4\}$，故核由 $(1,1,1,0)^T$ 及 $e_4$ 張成。為計算其餘特徵值而非憑圖猜測，令 $L_3$ 為左上三階區塊。展開三對角行列式得

$$\begin{aligned} \det(tI-L_3) &=(t-1)\bigl((t-3)(t-2)-4\bigr)-(t-2)\\ &=t(t^2-6t+6). \end{aligned}$$

孤立零區塊再給一個因子 $t$，故完整譜（包括重數）為 $0,0,3-\sqrt3,3+\sqrt3$。

活躍集上的歸一化矩陣是

$$N_3=\begin{pmatrix} 1&-1/\sqrt3&0\\ -1/\sqrt3&1&-\sqrt{2/3}\\ 0&-\sqrt{2/3}&1 \end{pmatrix}.$$

直接相乘得到正交歸一特徵基

$$u_0=\frac{(1,\sqrt3,\sqrt2)^T}{\sqrt6},\qquad u_1=\frac{(\sqrt2,0,-1)^T}{\sqrt3},\qquad u_2=\frac{(1,-\sqrt3,\sqrt2)^T}{\sqrt6},$$

對應特徵值依次為 $0,1,2$。分子的平方範數依次為 $6,3,6$，彼此點積為零，核實了歸一化與獨立性。給這三列加上第四個零元素，再加 $e_4$，便成為全矩陣 $N$ 的正交歸一特徵基，其譜為 $0,0,1,2$。

因 $R_{44}=0$，矩陣 $I_4-RWR$ 把 $e_4$ 送到 $e_4$，會把孤立特徵值由零換成一；其活躍區塊相同，孤立點約定卻不同。

頂點 $1,2,3$ 上的轉移矩陣與平穩概率列向量為

$$P=\begin{pmatrix}0&1&0\\1/3&0&2/3\\0&1&0\end{pmatrix},\qquad \pi=\frac16\begin{pmatrix}1\\3\\2\end{pmatrix}.$$

直接相乘或使用度數恆等式，均得 $\pi^TP=(1,3,2)/6$。相反，均勻行向量 $(1/3,1/3,1/3)$ 變成 $(1/9,2/3,2/9)$，並不平穩。又 $P_{12}=1$ 而 $P_{21}=1/3$，所以 $P$ 不歐氏對稱；正確的對稱性是 $D_3P=P^TD_3$。此活躍構造沒有定義第四個孤立轉移行，故既不使用四頂點度數逆矩陣，也不由這種逆矩陣指派概率質量。

Question 2

對三頂點無權完全圖，解一維與二維座標的最小跡問題。比較兩個一維選擇

$$u=\frac{(1,-1,0)^T}{\sqrt2},\qquad v=\frac{(1,1,-2)^T}{\sqrt6}.$$

計算各自三對座標的平方距離，判斷是否所有極小座標都有相同距離。保留整個二維中心空間時，證明任意兩個正交歸一座標矩陣以正交變換相連，並計算其成對行座標平方距離。

Solution. 每個頂點度數為二，鄰接矩陣是 $J-I$，其中 $J=\mathbf1\mathbf1^T$，所以 $L=3I-J$。常數列向量有特徵值零；每個中心化列向量 $f$ 都滿足 $Jf=0$ 及 $Lf=3f$，故譜為 $0,3,3$。兩個給定列向量均中心化且為單位長，因此每個一維可行目標均為三，它們都是極小解。

對 $u$，按 $12,13,23$ 排列的平方距離為

$$(\sqrt2)^2=2,\qquad (1/\sqrt2)^2=1/2,\qquad(-1/\sqrt2)^2=1/2.$$

對 $v$ 則為

$$0,\qquad (3/\sqrt6)^2=3/2,\qquad (3/\sqrt6)^2=3/2.$$

兩組距離不同。一維正交變換只能把所有座標同乘 $1$ 或 $-1$，不會改變距離，因此這兩個極小解不是如此相連。重特徵值容許在二維中心特徵空間內選不同的一維子空間。

$k=2$ 時每個可行列空間都是整個 $\mathbf1^\perp$，最小值為 $3+3=6$，正交投影是 $H=I-J/3$。若 $U,V$ 為任意兩個可行矩陣，令 $Q=U^TV$，則 $UQ=UU^TV=HV=V$，且 $Q^TQ=V^THV=I_2$，確實得到把兩組座標相連的正交矩陣。兩者的 Gram 矩陣為 $UU^T=VV^T=H$。對不同 $i,j$，行座標平方距離是

$$H_{ii}+H_{jj}-2H_{ij}=\frac23+\frac23-2\left(-\frac13\right)=2.$$

保留整個重特徵空間固定了子空間與全部距離；在它之中截斷則不然。這些結論關於明確的圖能量約束，並未指定另一張 MDS 距離表。

Question 3

兩個頂點由一條權為 $a>0$ 的邊相連。推導活躍轉移矩陣、平穩分佈與歸一化特徵值。從點質量出發，計算每個時刻的分佈並判斷是否收斂。另解釋第1題的加權路徑轉移矩陣不對稱，為何不違反可逆性。對全零圖，度數公式究竟定義了甚麼？

Solution. 此處 $D=aI_2$，$W=a\begin{pmatrix}0&1\\1&0\end{pmatrix}$，所以

$$P=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad \pi=\begin{pmatrix}1/2\\1/2\end{pmatrix},\qquad N=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}.$$

列向量 $(1,1)^T/\sqrt2$ 與 $(1,-1)^T/\sqrt2$ 的歸一化特徵值為 $0,2$，對應轉移特徵值 $1,-1$。因 $P^2=I_2$，歸納得對每個整數 $m\ge0$，$P^{2m}=I_2$、$P^{2m+1}=P$。從概率列向量 $r_0=e_1$ 出發，注意此特例 $P^T=P$，得到 $r_{2m}=e_1$、$r_{2m+1}=e_2$。第一座標有值恆為一與恆為零的兩個子序列，所以沒有極限。然而平穩列向量仍滿足 $P^T\pi=\pi$；以相同權重平均兩個起始狀態便消去交替分量。

第1題的路徑有 $D_3=\operatorname{diag}(1,3,2)$，直接相乘得

$$D_3P=\begin{pmatrix}0&1&0\\1&0&2\\0&2&0\end{pmatrix}=P^TD_3.$$

這是在另一個正內積下自伴，而非普通矩陣對稱。細緻平衡使用 $\pi_iP_{ij}=\pi_jP_{ji}$，所以不相等的一步概率由不相等的平穩質量平衡。概率列向量按 $P^T$ 更新；$Pf$ 則取函數的條件期望。兩者在二點特例中碰巧是同一矩陣，在加權路徑則不是。

若所有權重為零，所有度數及總體積均為零，活躍集為空。零延拓歸一化拉普拉斯矩陣是零矩陣，但 $D^{-1}W$ 與 $d/\sum\limits_i d_i$ 都不是有定義的全空間公式。零列向量的元素和為零，也不是概率分佈。把孤立狀態設為吸收態會是額外轉移約定，並非此構造的結論。

Question 4

對無權路徑 $1-2-3-4$，計算歸一化譜，並核實

$$f=(1,1/2,-1/2,-1)^T$$

是滿足 $Lf=(1/2)Df$ 的廣義特徵函數。計算互換兩側視為相同後的全部歸一化割值，比較精確最優值與譜鬆弛，並求中央割的兩級指示商。

Solution. 度數矩陣與拉普拉斯矩陣為

$$D=\operatorname{diag}(1,2,2,1),\qquad L=\begin{pmatrix}1&-1&0&0\\-1&2&-1&0\\0&-1&2&-1\\0&0&-1&1\end{pmatrix}.$$

四個列向量

$$f_0=(1,1,1,1)^T,\quad f_{1/2}=(1,1/2,-1/2,-1)^T,\quad f_{3/2}=(1,-1/2,-1/2,1)^T,\quad f_2=(1,-1,1,-1)^T$$

滿足 $Lf_\mu=\mu Df_\mu$，可逐項相乘核實。例如 $Lf_{1/2}=(1/2,1/2,-1/2,-1/2)^T=(1/2)Df_{1/2}$。其度數加權平方範數依次為 $6,3,3,6$。乘以 $D^{1/2}$ 再除以相應正範數平方根，便得到 $N$ 的單位特徵向量。不同特徵值使它們正交：對稱 $N$ 給 $x^TNy$ 的兩個表示，故 $(\mu_y-\mu_x)x^Ty=0$。因此四個向量獨立，窮盡四維，歸一化譜恰為 $0,1/2,3/2,2$。

給定的 $f$ 是 $f_{1/2}$，加權平均為 $1+1-1-1=0$，加權平方範數為三。其 Rayleigh 商為 $1/2$，故達到鬆弛最小值。

無序的非平凡割有七個，因為兩側恰有一側包含頂點一，選它作 $A$ 即可；總體積為六。每條跨界路徑邊權為一，直接列舉得

最小離散值為 $2/3$，由 $\{1,2\}\mid\{3,4\}$ 達到。這個割的兩級函數為 $g=(1/3,1/3,-1/3,-1/3)^T$。只有中央邊貢獻能量，故 $g^TLg=(2/3)^2=4/9$；而 $g^TDg=6/9=2/3$，兩者比值為 $2/3$，直接驗證了指示公式。

我們得到嚴格不等式

$$\mu_2=\frac12<\frac23=\min_A\operatorname{Ncut}(A,V\setminus A).$$

鬆弛極小解取四個不同值，割函數則只取兩個值。符號閾值在此例恰好找出最優中央割，但這既不消除嚴格目標差距，也不證明閾值離散化的一般保證。