線性代數在圖論的應用 (三)：拉普拉斯矩陣

本文的閱讀等級：中級

令 $G=(V,E)$ 為一個無向圖 (undirected graph)，其中 $V=\{v_1,\ldots,v_n\}$ 是頂點集合， $n=\vert V\vert$ 稱為圖 $G$ 的階 (order)， $E$ 是無向邊集合。若頂點 $v_i$ 和 $v_j$ 之間存在一邊，記為 $\{v_i,v_j\}$ ，我們稱 $v_i$ 和 $v_j$ 鄰接 (adjacent)，並稱該邊與二頂點有關聯 (incident)。無向邊不具方向性， $\{v_i,v_j\}$ 是兩頂點組成的集合，即每一邊可視為一無序頂點對。以下考慮簡單無向圖，意思是不存在自迴路 (self-loop)，即 $\{v_i,v_i\}$ ，且不存在重邊 (multiedge)，即任二相異頂點至多僅存在一關聯邊。對應 $n$ 階圖 $G=(V,E)$ ，鄰接矩陣 $A=[a_{ij}]$ 為一 $n\times n$ 階矩陣，定義如下： $a_{ij}=1$ 若 $\{v_i,v_j\}\in E$ ，否則 $a_{ij}=0$ (見“線性代數在圖論的應用 (一)：鄰接矩陣”)。顯然， $a_{ij}=a_{ji}$ ， $A$ 是一對稱矩陣。表面上，鄰接矩陣是一圖的最自然的表示方式，但它的實用價值卻不大，原因在於鄰接矩陣的特徵值和特徵向量未能揭露圖結構的重要訊息，此外，鄰接矩陣的二次型亦缺乏明確的涵義。本文介紹一種適於建立矩陣譜 (相異特徵值集合，spectrum) 理論的無向圖表示矩陣，稱為拉普拉斯矩陣 (Laplacian)。對於頂點 $v_i$ ，分支度 (度數，degree) $d_i$ 是所有與 $v_i$ 有關聯的邊數，即鄰接矩陣 $A$ 的第 $i$ 列 (或行) 和， $d_i=\sum_{j=1}^na_{ij}$ 。對應無向圖 $G$ ，拉普拉斯矩陣 (Laplacian) 定義為 $L=D-A$ ，其中 $D=\text{diag}(d_1,\ldots,d_n)$ 稱為分支度矩陣。因為 $D$ 和 $A$ 是對稱矩陣，拉普拉斯矩陣 $L$ 也是對稱矩陣。為簡化符號，頂點 $v_i$ 可用下標 $i$ 表示。下圖為一例： $G=(V,E)$ ，其中 $V=\{1,2,3,4\}$ ， $E=\{\{1,2\},\{1,3\},\{1,4\},\{3,4\}\}$ 。

對應此圖的鄰接矩陣 $A$ 、分支度矩陣 $D$ 和拉普拉斯矩陣 $L$ 分別是

$\displaystyle A=\begin{bmatrix} 0&1&1&1\\ 1&0&0&0\\ 1&0&0&1\\ 1&0&1&0 \end{bmatrix},~~D=\begin{bmatrix} 3&0&0&0\\ 0&1&0&0\\ 0&0&2&0\\ 0&0&0&2 \end{bmatrix},~~L=\left[\!\!\begin{array}{rrrr} 3&-1&-1&-1\\ -1&1&0&0\\ -1&0&2&-1\\ -1&0&-1&2 \end{array}\!\!\right]$ 。

給定一 $n$ 階簡單無向圖 $G=(V,E)$ ， $V=\{1,\ldots,n\}$ ，下面介紹三個重要的拉普拉斯矩陣性質。

性質一：對於任一 $\mathbf{x}=(x_1,\ldots,x_n)^T\in\mathbb{R}^n$ ，

$\displaystyle \mathbf{x}^TL\mathbf{x}=\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^na_{ij}(x_i-x_j)^2=\sum_{\{i,j\}\in E}(x_i-x_j)^2$ 。

使用定義，直接計算即可證明：

$\displaystyle \begin{aligned} \mathbf{x}^TL\mathbf{x}&=\mathbf{x}^TD\mathbf{x}-\mathbf{x}^TA\mathbf{x}\\ &=\sum_{i=1}^nd_ix_i^2-\sum_{i=1}^n\sum_{j=1}^na_{ij}x_ix_j\\ &=\frac{1}{2}\left(\sum_{i=1}^nd_ix_i^2-2\sum_{i=1}^n\sum_{j=1}^na_{ij}x_ix_j+\sum_{j=1}^nd_jx_j^2\right)\\ &=\frac{1}{2}\left(\sum_{i=1}^n\sum_{j=1}^na_{ij}x_i^2-2\sum_{i=1}^n\sum_{j=1}^na_{ij}x_ix_j+\sum_{j=1}^n\sum_{i=1}^na_{ji}x_j^2\right)\\ &=\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^na_{ij}(x_i-x_j)^2=\sum_{\{i,j\}\in E}(x_i-x_j)^2. \end{aligned}$

若 $n$ 維向量 $\mathbf{x}=(x_1,\ldots,x_n)^T$ 代表附著於頂點 $1,\ldots,n$ 的度量值，性質一說明二次型 $\mathbf{x}^TL\mathbf{x}$ 代表所有鄰接頂點的度量值總變異量，也就是度量值的分配平滑性 (smoothness)。明顯地，若 $\mathbf{x}$ 的所有元皆相同，則 $\mathbf{x}^TL\mathbf{x}=0$ 。

性質二：拉普拉斯矩陣 $L$ 是一實對稱半正定矩陣。

對於任一 $\mathbf{x}=(x_1,\ldots,x_n)^T\in\mathbb{R}^n$ ，性質一給出 $\mathbf{x}^TL\mathbf{x}=\sum_{\{i,j\}\in E}(x_i-x_j)^2\ge 0$ ，故 $L$ 是半正定矩陣。

性質三：拉普拉斯矩陣 $L$ 的最小特徵值是 $0$ ，對應的特徵向量為 $\mathbf{e}=(1,\ldots,1)^T$ 。

因為 $L$ 的每一列和皆為 $0$ ，立得 $L\mathbf{e}=\mathbf{0}$ ，即知 $L$ 有特徵值 $0$ ，對應特徵向量 $\mathbf{e}$ 。半正定矩陣的特徵值必定不為負 (見“半正定矩陣的判別方法”)，故 $0$ 是 $L$ 的最小特徵值。

若一無向圖的任意兩頂點之間存在一序列的邊，則稱之為連通圖 (connective graph)。所謂連通元件是指圖 $G=(V,E)$ 的頂點子集 $S\subseteq V$ 及相關聯的邊子集 $\{\{u,v\}\in E\vert u,v\in S\}$ 所構成連通圖，但任意 $u\in S$ 和 $v\in V\setminus S$ 之間不存在連通路徑。拉普拉斯矩陣是實對稱矩陣，故可正交對角化 (見“實對稱矩陣可正交對角化的證明”)，這意味 $L$ 的每一特徵值 $\lambda_i$ 的代數重數等於幾何重數，即 $L-\lambda_iI$ 的零空間維數 $\dim N(L-\lambda_iI)$ 。以下代數重數和幾何重數簡稱為相重數。

定理一：對應無向圖 $G$ 的拉普拉斯矩陣 $L$ 的特徵值 $0$ 的相重數等於 $G$ 的連通元件數。

證明於下：假設圖 $G=(V,E)$ ， $V=\{1,\ldots,n\}$ ，包含 $p$ 個連通元件 $G_k(V_k,E_k)$ ， $k=1,\ldots,p$ ，彼此互不連通。令 $n$ 維向量 $\mathbf{u}_k$ 的第 $l$ 元為 $1$ 若 $l\in V_k$ ，否則設為 $0$ ， $1\le k\le p$ ， $1\le l\le n$ 。不難驗證 $L\mathbf{u}_k=\mathbf{0}$ ， $1\le k\le p$ ，且 $\{\mathbf{u}_1,\ldots,\mathbf{u}_p\}$ 形成一正交集 (orthogonal set)。考慮 $L\mathbf{x}=\mathbf{0}$ ，則 $\mathbf{x}^TL\mathbf{x}=\sum_{\{i,j\}\in E}(x_i-x_j)^2=0$ ，由此推斷每一 $\{i,j\}\in E_k$ 滿足 $x_i=x_j$ 。換句話說， $\mathbf{x}$ 可表示為 $\mathbf{u}_1,\ldots,\mathbf{u}_p$ 的線性組合，故 $\dim N(L)=p$ ，證明 $L$ 的特徵值 $0$ 的相重數等於 $G$ 的連通元件數。

舉一例說明，見下圖， $G$ 包含連通元件 $G_1(V_1,E_1)$ 和 $G_2(V_2,E_2)$ ，其中 $V_1=\{1,3\}$ ， $V_2=\{2,4,5\}$ ， $E_1=\{\{1,3\}\}$ ， $E_2=\{\{2,4\},\{2,5\}\}$ 。

對應的拉普拉斯矩陣為

$\displaystyle L=\left[\!\!\begin{array}{rrrrr} 1&0&-1&0&0\\ 0&2&0&-1&-1\\ -1&0&1&0&0\\ 0&-1&0&1&0\\ 0&-1&0&0&1 \end{array}\!\!\right]$ 。

令 $\mathbf{u}_1=(1,0,1,0,0)^T$ 和 $\mathbf{u}_2=(0,1,0,1,1)^T$ 。明顯地， $L\mathbf{u}_1=\mathbf{0}$ ， $L\mathbf{u}_2=\mathbf{0}$ 且 $\mathbf{u}_1\perp\mathbf{u}_2$ 。為看清圖的連通結構，我們可將頂點排序 $\{1,2,3,4,5\}$ 變更為 $\{1,3,2,4,5\}$ 。具體的作法是執行下列排列相似變換 (見“矩陣視覺化”)：

$\displaystyle L\mapsto P^TLP$ ，

其中 $P$ 是置換第 $2$ 與 $3$ 行 (或列) 的基本排列矩陣，即置換單位矩陣 $I_5$ 第 $2$ 與 $3$ 行 (或列) 的結果。經過頂點排序後的拉普拉斯矩陣為分塊對角矩陣：

$\displaystyle P^TLP=\left[\!\!\begin{array}{rrcrrr} 1&-1&\vline&0&0&0\\ -1&1&\vline&0&0&0\\\hline 0&0&\vline&2&-1&-1\\ 0&0&\vline&-1&1&0\\ 0&0&\vline&-1&0&1 \end{array}\!\!\right]$ ，

其中每一對角分塊即所對應連通元件的拉普拉斯矩陣，有一個相重數為 $1$ 的零特徵值。

以下設拉普拉斯矩陣 $L$ 的特徵值按遞增順序排列， $0=\lambda_1\le\lambda_2\le\cdots\le\lambda_n$ 。定理一的必然結果： $G$ 是一連通圖若且惟若 $\lambda_2>0$ 。在圖論中， $\lambda_2$ 稱為 $G$ 的代數連通度 (algebraic connectivity)。若一連通圖的 $\lambda_2$ 數值小，只要刪除少許邊即可將將圖切割為兩個連通元件；反之，若 $\lambda_2$ 的數值大，則必須刪除很多邊方能將圖切割為二。代數連通度 $\lambda_2$ 涉及較為複雜的分析，下面僅列舉一些基本圖的拉普拉斯矩陣並計算矩陣譜，由此讀者可以略窺代數連通度與圖結構的關係。

例一：完全圖 (complete graph)

完全圖 $K(V,E)$ 是指任兩個相異頂點皆有一連接邊，即 $E=\{\{i,j\}\vert i,j\in V, i<j\}$ 。完全圖的拉普拉斯矩陣為

$\displaystyle L_K=\left[\!\!\begin{array}{cccc} n-1&-1&\cdots&-1\\ -1&n-1&\cdots&-1\\ \vdots&\vdots&\ddots&\vdots\\ -1&-1&\cdots&n-1 \end{array}\!\!\right]$ 。

完全圖是一個連通圖，定理一表明 $L_K$ 的特徵值 $0$ 的相重數為 $1$ ，特徵空間為 $\text{span}\{\mathbf{e}=(1,\ldots,1)^T\}$ ，即知 $L_K$ 有 $n-1$ 個非零特徵值，特徵空間為 $\text{span}\{\mathbf{e}\}$ 的正交補餘 $\text{span}\{\mathbf{e}\}^{\perp}$ (因為 $L_k$ 可正交對角化)。若 $\mathbf{x}=(x_1,\ldots,x_n)^T\in\text{span}\{\mathbf{e}\}^{\perp}$ ，則 $\mathbf{x}^T\mathbf{e}=x_1+\cdots+x_n=0$ 。使用此性質，可得

$\displaystyle\begin{aligned} L_K\mathbf{x}&=\left[\!\!\begin{array}{cccc} n-1&-1&\cdots&-1\\ -1&n-1&\cdots&-1\\ \vdots&\vdots&\ddots&\vdots\\ -1&-1&\cdots&n-1 \end{array}\!\!\right]\begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{bmatrix}\\ &=\begin{bmatrix} (n-1)x_1-\sum_{i\neq 1}x_i\\ (n-1)x_2-\sum_{i\neq 2}x_i\\ \vdots\\ (n-1)x_n-\sum_{i\neq n}x_i \end{bmatrix}=\begin{bmatrix} nx_1\\ nx_2\\ \vdots\\ nx_n \end{bmatrix}=n\mathbf{x}.\end{aligned}$

所以， $L_K$ 有特徵值 $0$ ，相重數是 $1$ ，以及特徵值 $n$ ，相重數是 $\dim N(L_K-nI)=\dim\text{span}\{\mathbf{e}\}^{\perp}=n-1$ 。我們將 $L_K$ 的矩陣譜記為 $\{0,n^{(n-1)}\}$ ，上標括弧內的數字表示相重數 (當相重數不等於 $1$ 時)，並知 $\lambda_2=n$ 。

例二：星狀圖 (star graph)

因為頂點標號可以隨意置換，設星狀圖 $S(V,E)$ 的中心點為 $v_1$ ，外圍點為 $v_2,\ldots,v_n$ ，則 $E=\{\{1,i\}\vert 2\le i\le n\}$ 。星狀圖的拉普拉斯矩陣是

$\displaystyle L_S=\left[\!\!\begin{array}{crrrr} n-1&-1&-1&\cdots&-1\\ -1&1&0&\cdots&0\\ -1&0&1&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ -1&0&0&\cdots&1 \end{array}\!\!\right]$ 。

定理一表明 $L_S$ 的特徵值 $0$ 的相重數為 $1$ 。令 $n$ 維向量 $\mathbf{x}_j$ 的第 $2$ 元為 $1$ ，第 $j$ 元為 $-1$ ，其餘元為 $0$ ，其中 $j>2$ 。很容易驗證 $L_S\mathbf{x}_j=\mathbf{x}_j$ ， $3\le j\le n$ ，且 $\{\mathbf{x}_3,\mathbf{x}_4,\ldots,\mathbf{x}_n\}$ 構成一線性獨立集，故 $L_S$ 有特徵值 $1$ ，相重數至少為 $n-2$ 。然而， $L_S$ 的特徵值和等於 $\text{trace}L_S=2n-2$ ，因此斷定 $L_S$ 尚有一特徵值 $n$ ，相重數是 $1$ 。所以， $L_S$ 的矩陣譜為 $\{0,1^{(n-2)},n\}$ ，得知 $\lambda_2=1$ 。

例三：環狀圖 (ring graph)

在不失一般性的前提下，設環狀圖 $R(V,E)$ 的邊集合為 $E=\{\{i,i+1\}\vert 1\le i<n\}\cup\{(1,n)\}$ ，則拉普拉斯矩陣為

$\displaystyle L_R=\left[\!\!\begin{array}{rrcrr} 2&-1&&&-1\\ -1&2&-1&&\\ &\ddots&\ddots&\ddots&\\ &&-1&2&-1\\ -1&&&-1&2 \end{array}\!\!\right]$ 。

觀察發現 $L_R$ 為一循環矩陣，具有下列形式：

$\displaystyle \begin{bmatrix} c_0&c_1&c_2&\cdots&c_{n-1}\\ c_{n-1}&c_0&c_1&\cdots&c_{n-2}\\ c_{n-2}&c_{n-1}&c_0&\cdots&c_{n-3}\\ \vdots&\vdots&\ddots&\ddots&\vdots\\ c_1&c_2&\cdots&c_{n-1}&c_0 \end{bmatrix}$ 。

比較可得 $c_0=2$ ， $c_1=c_{n-1}=-1$ ，且 $c_i=0$ ， $2\le i\le n-2$ 。令 $L_R$ 的特徵值為 $\mu_m$ ， $m=0,1,\ldots,n-1$ 。套用循環矩陣的特徵值公式 (見“特殊矩陣 (7)：循環矩陣”)，

$\displaystyle\begin{aligned} \mu_m&=\sum_{k=0}^{n-1}c_ke^{-2\pi imk/n}\\ &=2-e^{-2\pi im/n}-e^{-2\pi im(n-1)/n}\\ &=2-e^{-2\pi im/n}-e^{2\pi im/n}e^{-2\pi im}\\ &=2-2\cos\left(\frac{2\pi m}{n}\right),\end{aligned}$

其中 $i=\sqrt{-1}$ 。因為 $\cos\left(\frac{2\pi m}{n}\right)=\cos\left(\frac{2\pi (n-m)}{n}\right)$ ，若 $n$ 是奇數， $L_R$ 矩陣譜為 $\{0, 2-2\cos\left(\frac{2\pi m}{n}\right)^{(2)}, 1\le m\le \frac{n-1}{2}\}$ ，若 $n$ 是偶數，矩陣譜為 $\{0, 4, 2-2\cos\left(\frac{2\pi m}{n}\right)^{(2)}, 1\le m\le \frac{n}{2}-1\}$ 。所以， $\lambda_2=2-2\cos\left(\frac{2\pi}{n}\right)$ 。對應特徵值 $\mu_m$ ， $m=0,1,\ldots,n-1$ ，循環矩陣的特徵向量公式給出

$\displaystyle\begin{aligned} \displaystyle\mathbf{z}_m&= \begin{bmatrix} 1\\ e^{-2\pi im/n}\\ \vdots\\ e^{-2\pi im(n-1)/n} \end{bmatrix}=\begin{bmatrix} 1\\ \cos\left(\frac{2\pi m}{n}\right)-i\sin\left(\frac{2\pi m}{n}\right)\\ \vdots\\ \cos\left(\frac{2\pi m(n-1)}{n}\right)-i\sin\left(\frac{2\pi m(n-1)}{n}\right) \end{bmatrix}\\ &=\begin{bmatrix} 1\\ \cos\left(\frac{2\pi m}{n}\right)\\ \vdots\\ \cos\left(\frac{2\pi m(n-1)}{n}\right) \end{bmatrix}-i\begin{bmatrix} 0\\ \sin\left(\frac{2\pi m}{n}\right)\\ \vdots\\ \sin\left(\frac{2\pi m(n-1)}{n}\right) \end{bmatrix}=\mathbf{x}_m-i\mathbf{y}_m,\end{aligned}$

其中 $\mathbf{x}_m=\text{Re}[\mathbf{z}_m]$ ， $\mathbf{y}_m=\text{Im}[\mathbf{z}_m]$ 。實矩陣 $L_R$ 的特徵值 $\mu_m$ 為實數，將上式代入 $L_R\mathbf{z}_m=\mu\mathbf{z}_m$ ，可得 $L_R\mathbf{x}_m=\mu_m\mathbf{x}_m$ 和 $L_R\mathbf{y}_m=\mu_m\mathbf{y}_m$ 。我們只要考慮線性獨立的 $\mathbf{x}_m$ 和 $\mathbf{y}_m$ 作為特徵向量：若 $n$ 是奇數，對應特徵值 $2-2\cos\left(\frac{2\pi m}{n}\right)$ ， $1\le m\le\frac{n-1}{2}$ ，的兩個特徵向量為 $\mathbf{x}_m$ 和 $\mathbf{y}_m$ ；若 $n$ 是偶數，對應特徵值 $4$ 的特徵向量為 $\mathbf{x}_{n/2}=(1,-1,\ldots,1,-1)^T$ ( $\mathbf{y}_{n/2}=\mathbf{0}$ )，對應特徵值 $2-2\cos\left(\frac{2\pi m}{n}\right)$ ， $1\le m\le\frac{n}{2}-1$ ，的兩個特徵向量為 $\mathbf{x}_m$ 和 $\mathbf{y}_m$ 。

例四：道路圖 (path graph)

道路圖 $P(V,E)$ 是指 $n$ 個頂點排成一列，每一頂點和相近頂點鄰接，也就是說 $E=\{\{i,i+1\}\vert 1\le i<n\}$ 。道路圖的拉普拉斯矩陣具有三對角形式：

$\displaystyle L_P=\left[\!\!\begin{array}{rrcrr} 1&-1&&&\\ -1&2&-1&&\\ &\ddots&\ddots&\ddots&\\ &&-1&2&-1\\ &&&-1&1 \end{array}\!\!\right]$ 。

給定 $\mathbf{u}=(u_1,\ldots,u_n)^T$ ，將 $L_P$ 視為一線性變換，則

$\displaystyle L_P\mathbf{u}=\begin{bmatrix} u_1-u_2\\ -u_1+2u_2-u_3\\ \vdots\\ -u_{n-2}+2u_{n-1}-u_n\\ -u_{n-1}+u_{n} \end{bmatrix}$

的第 $1<i<n$ 元 $-u_{i-1}+2u_{i}-u_{i+1}$ 形如計算一維 Laplace 算子所採用的中央差分近似 (除了正負號相反，見“線性代數在數值分析的應用 (二)：Dirichlet 問題”)，此即拉普拉斯矩陣的命名由來。

利用環狀圖的結果可以導出 $L_P$ 的特徵值。為方便說明，考慮 $n=3$ 的情況，設包含 $2n=6$ 個頂點的環狀圖 $R(V,E)$ 的邊集合為 $E=\{\{1,2\}, \{2,3\}, \{3,6\}, \{6,5\}, \{5,4\}, \{4,1\}\}$ 。寫出 $6\times 6$ 階 $L_R$ 矩陣的特徵多項式

$\displaystyle p_{L_R}(\lambda)=\begin{vmatrix} 2-\lambda&-1&0&\vline&-1&0&0\\ -1&2-\lambda&-1&\vline&0&0&0\\ 0&-1&2-\lambda&\vline&0&0&-1\\\hline -1&0&0&\vline&2-\lambda&-1&0\\ 0&0&0&\vline&-1&2-\lambda&-1\\ 0&0&-1&\vline&0&-1&2-\lambda \end{vmatrix}$ 。

使用分塊矩陣的行列式公式 (見“分塊矩陣的行列式”)

$\displaystyle \begin{vmatrix} A&B\\ B&A \end{vmatrix}=\det (A+B)\det (A-B)$ ，

其中 $A$ 和 $B$ 是同階方陣，可得

$\displaystyle p_{L_R}(\lambda)=\begin{vmatrix} 1-\lambda&-1&0\\ -1&2-\lambda&-1\\ 0&-1&1-\lambda \end{vmatrix}\cdot\begin{vmatrix} 3-\lambda&-1&0\\ -1&2-\lambda&-1\\ 0&-1&3-\lambda \end{vmatrix}=p_{L_P}(\lambda)\cdot q(\lambda)$ ，

表明 $p_{L_P}(\lambda)$ 整除 $p_{L_R}(\lambda)$ 。換句話說， $L_R$ 的特徵值即為下面二矩陣的特徵值的聯集：

$\displaystyle L_P=\left[\!\!\begin{array}{rrr} 1&-1&0\\ -1&2&-1\\ 0&-1&1 \end{array}\!\!\right],~M=\left[\!\!\begin{array}{rrr} 3&-1&0\\ -1&2&-1\\ 0&-1&3 \end{array}\!\!\right]$ 。

計算可得 $L_P$ 的特徵值是 $0,1,3$ ， $M$ 的特徵值是 $1, 3, 4$ 。推廣至一般情況，道路圖 $L_P$ 的矩陣譜即是 $\{0,2-2\cos\left(\frac{\pi m}{n}\right),1\le m\le n-1\}$ ，故 $\lambda_2=2-2\cos\left(\frac{\pi}{n}\right)$ 。對應特徵值 $2-2\cos\left(\frac{\pi m}{n}\right)$ ， $m=0,1,\ldots,n-1$ ，請讀者自行驗證 $L_P$ 的特徵向量為

$\displaystyle \begin{bmatrix} \cos\left(\frac{m\pi}{n}-\frac{m\pi}{2n}\right)\\ \cos\left(\frac{2m\pi}{n}-\frac{m\pi}{2n}\right)\\ \vdots\\ \cos\left(\frac{nm\pi}{n}-\frac{m\pi}{2n}\right) \end{bmatrix}$ 。

拉普拉斯矩陣存在多種變化，譬如，我們可以考慮加權圖，其中每一邊附著一非負權重代表二鄰接頂點的相似性。拉普拉斯矩陣的特徵值和特徵向量理論統稱為圖譜分析，其中最具代表性的一項技術是目前廣泛應用於網絡分割 (分群) 的譜聚類分析 (spectral clustering)，日後我們將探討這個主題。

4 Responses to 線性代數在圖論的應用 (三)：拉普拉斯矩陣

Meiyue Shao says:

06/18/2015 at 9:39 am

我觉得定理一还可以再加一些解释（或者说是另一种相对麻烦的证明），这样会比较直观地揭示出本质。

首先，对于连通图而言Laplace矩阵只有一个零特征值（最快捷的证明或许是利用Cauchy交错定理）。然后对于一般的图，将顶点重新编号（或者对Laplace矩阵进行行列重排）可以得到分块对角阵，每个连通分支对应于一个零特征值重数为一的对角块。

然后对例一之前的小例子的2,3两行两列交换可以看清上述分块对角结构。

- ccjou says:
  
  06/18/2015 at 2:59 pm
  
  謝謝，眼前我先將上面的例子重排頂點以顯示分塊對角型態。
  
Andy says:

05/13/2021 at 11:47 pm

想請問一下，如何將實數矩陣轉為圖論的鄰接矩陣或Affinity matrix？

3142697773 says:

06/05/2021 at 5:26 pm

想知道这些知识的参考书籍是哪些？

	jianglong on Strassen 演算法──分治矩陣乘法
	jianglong on Strassen 演算法──分治矩陣乘法
	xmj on 內積的定義
	Ning ChingSan on 線性代數的第一堂課──矩陣乘法的定義
	momo on 兩岸線性代數用詞參照
	訪客 on 克拉瑪公式的簡易幾何證明