# 拉普拉斯矩陣

Laplacian matrix

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

$\newcommand{\trans}{^\top}
\newcommand{\adj}{^{\rm adj}}
\newcommand{\cof}{^{\rm cof}}
\newcommand{\inp}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\dunion}{\mathbin{\dot\cup}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\nul}{\operatorname{null}}
\newcommand{\rank}{\operatorname{rank}}
%\newcommand{\ker}{\operatorname{ker}}
\newcommand{\range}{\operatorname{range}}
\newcommand{\Col}{\operatorname{Col}}
\newcommand{\Row}{\operatorname{Row}}
\newcommand{\spec}{\operatorname{spec}}
\newcommand{\vspan}{\operatorname{span}}
\newcommand{\Vol}{\operatorname{Vol}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\idmap}{\operatorname{id}}
\newcommand{\am}{\operatorname{am}}
\newcommand{\gm}{\operatorname{gm}}
\newcommand{\mult}{\operatorname{mult}}
\newcommand{\iner}{\operatorname{iner}}$

## Main idea

This section discusses the Laplacian matrix of a simple graph.
See 414 for more basic properties of a graph.

Let $G = (V,E)$ be a graph.
The **degree** of a vertex $v$ in $G$ is the number of edges incident to $v$, denoted by $\deg_G(v)$.
Two vertices are said to be **reachable** if there is a way to go from one vertex to the other vertex through a sequence of edges.
Being reachable is an equivalence relation on $V$, and the subgraph induced on each equivalence class is called a **(connected) component** of $G$.

Let $G = (V,E)$ be a graph with $V = [n]$.
The **Laplacian matrix** of $G$ is the $n\times n$ matrix $L(G)$ whose $i,j$-entry is

$$
\begin{cases}
\deg_G(i) & \text{if }i = j, \\
-1 & \text{if }\{i,j\}\in E(G), \\
0 & otherwise.
\end{cases}
$$

Let $\bx = (x_1,\ldots, x_n)\trans$.
Then the quadratic form of $L = L(G)$ is

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

Let $G$ be a graph and $L = L(G)$ its Laplacian matrix.
Thanks to the quadratic form, we can see the following properties:

- The matrix $L$ is positive semidefinite for any choice of $G$, and $L\bone = \bzero$.
- The number of components of $G$ is the same as $\nul(L)$.

## Side stories

- structure of $\ker(L(G))$
- incident matrix
- algebraic connectivity

## Experiments

##### Exercise 1

執行以下程式碼。

<!-- eng start -->
Run the code below.
<!-- eng end -->

### code
set_random_seed(0)
print_ans = False

n = 4
g = graphs.RandomGNP(n, 0.5)
g.relabel({i:i + 1 for i in range(n)})

g.show(figsize=(3,3), title="$G$")

if print_ans:
    L = g.laplacian_matrix()
    pretty_print(LatexExpr("L ="), L)
    xs = var(" ".join("x%s"%i for i in g.vertices()))
    qua = sum((xs[e[0] - 1] - xs[e[1] - 1])^2 for e in g.edges(labels=False))
    print("quadratic form:")
    show(qua)
    print("ker(L) is spanned by the rows of")
    show(L.kernel().basis_matrix())
    print("Number of connected components =", L.nullity())

##### Exercise 1(a)

寫出圖 $G$ 的拉普拉斯矩陣 $L$。

<!-- eng start -->
Find the Laplacian matrix $L$ of $G$.
<!-- eng end -->

##### Exercise 1(b)

寫出 $L$ 的二次型。

<!-- eng start -->
Find the quadratic form of $L$.
<!-- eng end -->

##### Exercise 1(c)

已知 $\bx\trans L\bx = 0$ 和 $L\bx = \bzero$ 等價。
利用二次型求出 $\ker(L)$ 並判斷 $G$ 的連通區塊個數。

<!-- eng start -->
It is known that $\bx\trans L\bx = 0$ and $L\bx = \bzero$ are equivalent. Find $\ker(L)$ by the quadratic form and determine the number of components of $G$.
<!-- eng end -->

:::info
What do the experiments try to tell you? (open answer)

...
:::

## Exercises

##### Exercise 2

令

$$
\begin{aligned}
V &= \{1,2,3,4\} \\
E &= \{\{1,2\}, \{1,3\}, \{1,4\}\}
\end{aligned}
$$

且 $G = (V,E)$。

<!-- eng start -->
Let

$$
\begin{aligned}
V &= \{1,2,3,4\} \\
E &= \{\{1,2\}, \{1,3\}, \{1,4\}\}
\end{aligned}
$$

and $G = (V,E)$.
<!-- eng end -->

##### Exercise 2(a)

畫出圖 $G$。

<!-- eng start -->
Draw the graph $G$.
<!-- eng end -->

##### Exercise 2(b)

寫出圖 $L = L(G)$ 以及其二次型。

<!-- eng start -->
Find $L = L(G)$ and its quadratic form.
<!-- eng end -->

##### Exercise 2(c)

說明 $L$ 是一個半正定矩陣，且 $L\bone = \bzero$。

<!-- eng start -->
Show that $L$ is a positive semidefinite matrix and $L\bone = \bzero$.
<!-- eng end -->

##### Exercise 3

令

$$
\begin{aligned}
V &= \{1,2,3,4\} \\
E &= \{\{1,2\}, \{3,4\}\}
\end{aligned}
$$

且 $G = (V,E)$。

<!-- eng start -->
Let

$$
\begin{aligned}
V &= \{1,2,3,4\} \\
E &= \{\{1,2\}, \{3,4\}\}
\end{aligned}
$$

and $G = (V,E)$.
<!-- eng end -->

##### Exercise 3(a)

畫出圖 $G$。

<!-- eng start -->
Draw the graph $G$.
<!-- eng end -->

##### Exercise 3(b)

寫出圖 $L = L(G)$ 以及其二次型。

<!-- eng start -->
Find $L = L(G)$ and its quadratic form.
<!-- eng end -->

##### Exercise 3(c)

求 $\bx\trans L\bx = 0$ 的所有解。

<!-- eng start -->
Find all solutions to $\bx\trans L\bx = 0$.
<!-- eng end -->

##### Exercise 3(d)

已知 $\bx\trans L\bx = 0$ 和 $L\bx = \bzero$ 等價。
利用二次型求出 $\ker(L)$ 並判斷 $G$ 的連通區塊個數。

<!-- eng start -->
It is known that $\bx\trans L\bx = 0$ and $L\bx = \bzero$ are equivalent. Find $\ker(L)$ by the quadratic form and determine the number of components of $G$.
<!-- eng end -->

##### Exercise 4

令 $G$ 為一圖、且 $L = L(G)$。
以下練習探討 $\ker(L)$ 的結構。

<!-- eng start -->
Let $G$ be a graph and $L = L(G)$. The following exercises studies the structure of $\ker(L)$.
<!-- eng end -->

##### Exercise 4(a)

令 $P$ 為任一半正定矩陣，證明 $\bx\trans P\bx = 0$ 和 $P\bx = \bzero$ 等價。

提示：可利用瑞利商定理、或是利用格拉姆矩陣的特性。

<!-- eng start -->
Let $P$ be a positive semidefinite matrix. Show that $\bx\trans P\bx = 0$ and $P\bx = \bzero$ are equivalent.

Hint: You may either use the Rayleigh quotient theorem or use the structure of a Gram matrix.
<!-- eng end -->

##### Exercise 4(b)

求 $\bx\trans L\bx = 0$ 的所有解。

<!-- eng start -->
Find all solutions to $\bx\trans L\bx = 0$.
<!-- eng end -->

##### Exercise 4(c)

用上一題的結果說明 $\ker(L) = \{\phi_{X_1}, \ldots, \phi_{X_k}\}$。
這裡 $X_1, \ldots, X_k$ 為 $G$ 的各連通區塊所在的點集合、
而 $\phi_{X_1}, \ldots, \phi_{X_k}$ 為其指標向量（characteristic vector）。

<!-- eng start -->
Use the result from the previous exercise to show that $\ker(L) = \{\phi_{X_1}, \ldots, \phi_{X_k}\}$. Here $X_1, \ldots, X_k$ are the vertex set of each connected components of $G$, and $\phi_{X_1}, \ldots, \phi_{X_k}$ are their characteristic vectors.
<!-- eng end -->

##### Exercise 5

令 $G = (V,E)$ 為一圖、其中 $V = \{v_1,\ldots,v_n\}$、$E = \{e_1,\ldots,e_m\}$。
定義 $\bu_j$ 為一 $\mathbb{R}^n$ 中的向量，
其上有一個 $1$ 和一個 $-1$，分別落在 $e_j$ 的兩個端點上（哪一個放 $-1$ 皆可），
而其它項皆是 $0$。

則 $G$ 的 **相連矩陣（incidence matrix）** 為一 $n\times m$ 矩陣 $N(G)$，
其第 $j$ 行為 $\bu_j$。

（相連矩陣並不唯一，取決於 $-1$ 放的位置，有 $2^m$ 種。）

<!-- eng start -->
Let $G = (V,E)$ be a graph such that $V = \{v_1,\ldots,v_n\}$ and $E = \{e_1,\ldots,e_m\}$. Define the vector $\bu_j$ in $\mathbb{R}^n$ such that it has a $1$ and a $-1$ on the two endpoints of $e_j$ (you may decide which one is $1$ and which one is $-1$) while other entries are zero.

The **incidence matrix** of $G$ is defined as the $n\times m$ matrix $N(G)$ whose $j$-th column is $\bu_j$.

(The incidence matrix is not unique. Depending on the locations of $-1$, there are $2^m$ choices.)
<!-- eng end -->

##### Exercise 5(a)

令

$$
\begin{aligned}
V &= \{1,2,3,4\} \\
E &= \{\{1,2\}, \{1,3\}, \{1,4\}\}
\end{aligned}
$$

且 $G = (V,E)$。
寫出 $G$ 的一個相連矩陣 $N$，並驗證 $NN\trans = L(G)$。

<!-- eng start -->
Let

$$
\begin{aligned}
V &= \{1,2,3,4\} \\
E &= \{\{1,2\}, \{1,3\}, \{1,4\}\}
\end{aligned}
$$

and $G = (V,E)$。
Find an incidence matrix $N$ of $G$ and verify that $NN\trans = L(G)$.
<!-- eng end -->

##### Exercise 5(b)

令 $N$ 為 $G$ 的一個相連矩陣、
而 $L$ 為 $G$ 的拉普拉斯矩陣。

證明對任意 $G$ 都有 $NN\trans = L$。

<!-- eng start -->
Let $N$ be an incidence matrix of $G$ and $L$ the Laplacian matrix of $G$. Show that $NN\trans = L$ for any $G$.
<!-- eng end -->

##### Exercise 5(c)

利用 $NN\trans = L$ 來再次證明

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

<!-- eng start -->
Give an alternative proof of

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

by $NN\trans = L$.
<!-- eng end -->

##### Exercise 6

令 $G$ 為一 $n$ 個點的圖而 $L = L(G)$。
令 $L$ 的特徵值為 $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$。
因為 $L\bone = \bzero$，所以 $\lambda_1 = 0$。
而 $\lambda_2$ 則稱為 $G$ 的 **代數連通度（algebraic connectivity）** ，記作 $\lambda_2(G)$。

<!-- eng start -->
Let $G$ be a graph on $n$ vertices and $L = L(G)$. Let $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$ be the eigenvalues of $L$. Since $L\bone = \bzero$, we have $\lambda_1 = 0$. On the other hand, $\lambda_2$ is known as the **algebraic connectivity** of $G$, denoted by $\lambda_2(G)$.
<!-- eng end -->

##### Exercise 6(a)

證明以下敘述等價：

- $\lambda_2(G) = 0$。
- $G$ 不連通。

<!-- eng start -->
Show that the following are equivalent:

- $\lambda_2(G) = 0$.
- $G$ is disconnected.
<!-- eng end -->

##### Exercise 6(b)

圖 $G$ 的連通度指的是最少須要拿掉幾個點才能讓 $G$ 變得不連通，這個連通度記作 $\kappa(G)$。
另一個 $\lambda_2(G)$ 被稱為代數連通度的原因是 $\lambda_2(G) \leq \kappa(G)$ 對任何圖 $G$ 都成立。

令

$$
\begin{aligned}
V &= \{1,2,3,4\} \\
E &= \{\{1,2\}, \{2,3\}, \{3,4\}, \{4,1\}\}
\end{aligned}
$$

且 $G = (V,E)$。
計算 $G$ 的 $\lambda_2(G)$ 和 $\kappa(G)$。

<!-- eng start -->
The connectivity of a graph $G$ is the minimum number vertices whose removal makes $G$ disconnected, denoted by $\kappa(G)$. The other reason why $\lambda_2(G)$ is called the algebraic connectivity is because the relation $\lambda_2(G) \leq \kappa(G)$.

Let

$$
\begin{aligned}
V &= \{1,2,3,4\} \\
E &= \{\{1,2\}, \{2,3\}, \{3,4\}, \{4,1\}\}
\end{aligned}
$$

and $G = (V,E)$。
Find $\lambda_2(G)$ and $\kappa(G)$ of $G$.
<!-- eng end -->

##### Exercise 6(c)

令

$$
\begin{aligned}
V &= \{1,2,3,4,5,6\} \\
E &= \{\{1,2\}, \{2,3\}, \{3,4\}, \{4,5\}, \{5,6\}, \{6,1\}\}
\end{aligned}
$$

且 $G = (V,E)$。
計算 $G$ 的 $\lambda_2(G)$ 和 $\kappa(G)$。

<!-- eng start -->
Let

$$
\begin{aligned}
V &= \{1,2,3,4,5,6\} \\
E &= \{\{1,2\}, \{2,3\}, \{3,4\}, \{4,5\}, \{5,6\}, \{6,1\}\}
\end{aligned}
$$

and $G = (V,E)$。
Find $\lambda_2(G)$ and $\kappa(G)$ of $G$.
<!-- eng end -->