拉普拉斯矩陣

考慮一張簡單圖 \(G\)，並令其上的點為 \(\{1, \ldots, n\}\)，則圖 \(G\) 的 拉普拉斯矩陣（Laplacian matrix） 是一個 \(n\times n\) 的對稱矩陣 \(L(G) = \begin{bmatrix} \ell_{i,j}\end{bmatrix}\)，其中

\[ \ell_{i,j} = \begin{cases} -1 & \text{ if } \{i,j\}\in E(G),\ i\neq j \\ 0 & \text{ if } \{i,j\}\notin E(G),\ i\neq j \\ \deg_G(i) & \text{ if } i = j. \end{cases} \]

比如說當 \(P_3\) 是一個三個點的路徑圖，則它所對應到的拉普拉斯矩陣為

\[ L(P_3) = \begin{bmatrix} 1 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 1 \end{bmatrix}. \]

如果我們把 \(n\) 維向量 \(\bx = (x_1, \ldots, x_n)\trans\) 看成點上的函數 \(\bx: V(G) \rightarrow \mathbb{R}\)，定義為 \(\bx(i) = x_i\)，則矩陣則是把函數轉換成另一個函數的線性算子。實際上，拉普拉斯矩陣就是在模擬幾何流型上的拉普拉斯算子（Laplace–Beltrami operator），只是幾何上習慣的拉普拉斯算子是半負定算子，而圖論所用的拉普拉斯矩陣是半正定矩陣，差一個負號。

一個對稱矩陣 \(A\) 的 二次型（quadratic form） 定為是 \(\bx\trans A\bx\)，其中 \(\bx\) 是要輸入的向量。二次型可以用來判斷矩陣是否為正定、也可以配合瑞利商（Rayleigh quotient）來計算 \(A\) 的特徵值。

接下來我們聊聊拉普拉斯矩陣的二次型 \(\bx\trans L\bx\)。以上述 \(P_3\) 的例子來說，直接計算可以得到

\[ \begin{aligned} \bx\trans L(P_3)\bx &= \begin{bmatrix} x_1 & x_2 & x_3 \end{bmatrix} \begin{bmatrix} 1 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} \\ &= x_1^2 + 2x_2^2 + x_3^2 - 2x_1x_2 - 2x_1x_3 \\ &= (x_1 - x_2)^2 + (x_2 - x_3)^2. \end{aligned} \]

另一種看法是先計算

\[ \begin{bmatrix} x_i & x_j \end{bmatrix} \begin{bmatrix} 1 & -1 \\ -1 & 1 \end{bmatrix} \begin{bmatrix} x_i \\ x_j \end{bmatrix} = (x_i - x_j)^2, \]

再進一步觀察到

\[ \begin{bmatrix} 1 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 1 \end{bmatrix} = \begin{bmatrix} 1 & -1 & 0 \\ -1 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix} + \begin{bmatrix} 0 & 0 & 0 \\ 0 & 1 & -1 \\ 0 & -1 & 1 \end{bmatrix}. \]

實際上，對任意的圖 \(G\) 來說，其拉普拉斯矩陣都可以由許多小塊的 \(2\times 2\) 矩陣疊加而成，而其二次型都有可以寫成

\[ \bx\trans L(G)\bx = \sum_{\{i,j\}\in E(G)} (x_i - x_j)^2. \]

拉普拉斯矩陣的大量性質，都可以單從其二次型來得出。

性質

令 \(L = L(G)\) 為簡單圖 \(G\) 的拉普拉斯矩陣，則

  1. \(L\) 是半正定矩陣，因此 \(\ker(L) = \{\bx : \bx\trans L\bx = 0\}\)。
  2. \(\bx\trans L\bx = 0\) 發生時，\(\bx\) 在 \(G\) 上同一個連通區塊的值都一樣。
  3. \(\nul(L)\) 等於 \(G\) 的連通區塊的個數。

舉例來說，考慮 \(G\) 是 \(5\) 個點的點，其中 \(\{1,2\}\) 互連、\(\{3,4,5\}\) 彼此互連。則

\[ L = L(G) = \begin{bmatrix} 1 & -1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 2 & -1 & -1 \\ 0 & 0 & -1 & 2 & -1 \\ 0 & 0 & -1 & -1 & 2 \\ \end{bmatrix} \]

且其二次型為

\[ \bx\trans L\bx = (x_1 - x_2)^2 + (x_3 - x_4)^2 + (x_4 - x_5)^2 + (x_3 - x_5)^2. \]

由於二次型恆正，得知 \(L\) 是半正定矩陣，而 \(\ker(L)\) 即為所有能讓二次型為 \(0\) 的 \(\bx\)。再次觀察二次型，其為 \(0\) 的條件為

\[ \begin{aligned} x_1 &= x_2, \\ x_3 &= x_4 = x_5, \end{aligned} \]

也就是 \(\bx\) 在同一連通區塊的值必需相同。滿足這樣的 \(\bx\) 可以寫為

\[ \ker(L) = \{(a,a,b,b,b)\trans: a,b\in\mathbb{R}\}, \]

是一個二維空間。因為每一個連通區塊都有一個自由度來決定 \(\bx\) 在其上的值，因此 \(\nul(L)\) 會等於連通區塊的個數。

想想以下問題：

  1. 說明為什麼 \(\bx\trans L(G)\bx = \sum_{\{i,j\}\in E(G)} (x_i - x_j)^2\)。
  2. 利用瑞利商定理來說明，如果 \(L\) 是一個半正定矩陣，則 \(\ker(L) = \{\bx : \bx\trans L\bx = 0\}\)。
  3. 如果把圖 \(G\) 的每一個點看成一個儲水槽，有連邊的兩個儲水槽底部有水管相接。另外把向量 \(\bx\) 的每一項看成是每一個儲水槽的高度。說明 \(L(G)\bx\) 的第 \(i\) 項
    \[ (L(G)\bx)_i = \sum_{j: j\sim i} (x_i - x_j) \]

    可以看成是第 \(i\) 個儲水槽高過周圍儲水槽的位能差的總合。

  4. 拉普拉斯矩陣的二次型 \(\bx\trans L\bx\) 常被描述為一個系統（水位、彈簧）的潛能（potential energy），而潛能愈大時則系統愈不穩定。說明這個比喻的合理性。