Laplacian matrix
This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.
$\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}}$
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
Let $\bx = (x_1,\ldots, x_n)\trans$.
Then the quadratic form of $L = L(G)$ is
Let $G$ be a graph and $L = L(G)$ its Laplacian matrix.
Thanks to the quadratic form, we can see the following properties:
執行以下程式碼。
Run the code below.### 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())
寫出圖 $G$ 的拉普拉斯矩陣 $L$。
Find the Laplacian matrix $L$ of $G$.寫出 $L$ 的二次型。
Find the quadratic form of $L$.已知 $\bx\trans L\bx = 0$ 和 $L\bx = \bzero$ 等價。
利用二次型求出 $\ker(L)$ 並判斷 $G$ 的連通區塊個數。
令
$$ \begin{aligned} V &= \{1,2,3,4\} \\ E &= \{\{1,2\}, \{1,3\}, \{1,4\}\} \end{aligned} $$且 $G = (V,E)$。
Let $$ \begin{aligned} V &= \{1,2,3,4\} \\ E &= \{\{1,2\}, \{1,3\}, \{1,4\}\} \end{aligned} $$ and $G = (V,E)$.畫出圖 $G$。
Draw the graph $G$.寫出圖 $L = L(G)$ 以及其二次型。
Find $L = L(G)$ and its quadratic form.說明 $L$ 是一個半正定矩陣,且 $L\bone = \bzero$。
Show that $L$ is a positive semidefinite matrix and $L\bone = \bzero$.令
$$ \begin{aligned} V &= \{1,2,3,4\} \\ E &= \{\{1,2\}, \{3,4\}\} \end{aligned} $$且 $G = (V,E)$。
Let $$ \begin{aligned} V &= \{1,2,3,4\} \\ E &= \{\{1,2\}, \{3,4\}\} \end{aligned} $$ and $G = (V,E)$.畫出圖 $G$。
Draw the graph $G$.寫出圖 $L = L(G)$ 以及其二次型。
Find $L = L(G)$ and its quadratic form.求 $\bx\trans L\bx = 0$ 的所有解。
Find all solutions to $\bx\trans L\bx = 0$.已知 $\bx\trans L\bx = 0$ 和 $L\bx = \bzero$ 等價。
利用二次型求出 $\ker(L)$ 並判斷 $G$ 的連通區塊個數。
令 $G$ 為一圖、且 $L = L(G)$。
以下練習探討 $\ker(L)$ 的結構。
令 $P$ 為任一半正定矩陣,證明 $\bx\trans P\bx = 0$ 和 $P\bx = \bzero$ 等價。
提示:可利用瑞利商定理、或是利用格拉姆矩陣的特性。
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.求 $\bx\trans L\bx = 0$ 的所有解。
Find all solutions to $\bx\trans L\bx = 0$.用上一題的結果說明 $\ker(L) = \{\phi_{X_1}, \ldots, \phi_{X_k}\}$。
這裡 $X_1, \ldots, X_k$ 為 $G$ 的各連通區塊所在的點集合、
而 $\phi_{X_1}, \ldots, \phi_{X_k}$ 為其指標向量(characteristic vector)。
令 $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$ 種。)
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.)令
$$ \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)$。
令 $N$ 為 $G$ 的一個相連矩陣、
而 $L$ 為 $G$ 的拉普拉斯矩陣。
證明對任意 $G$ 都有 $NN\trans = L$。
Let $N$ be an incidence matrix of $G$ and $L$ the Laplacian matrix of $G$. Show that $NN\trans = L$ for any $G$.利用 $NN\trans = L$ 來再次證明
$$ \bx\trans L\bx = \sum_{\{i,j\}\in E(G)}(x_i - x_j)^2. $$ Give an alternative proof of $$ \bx\trans L\bx = \sum_{\{i,j\}\in E(G)}(x_i - x_j)^2. $$ by $NN\trans = L$.令 $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)$。
證明以下敘述等價:
圖 $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)$。
令
$$ \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)$。