グラフのラプラシアン固有値0の重複度と連結成分の関係

ラプラシアン固有値$0$の重複度を$m_0$，グラフの連結成分を$C_l$（$1\le l\le c$）とする．
$C_l$（$1\le l\le c$）に対応した値が全て$1$，その他の値が全て$0$という$n$次ベクトル$x_l^{\prime }={}^t[0,\dots ,0,\underset{C_l\text{に対応した部分}}{\underbrace{1,\dots ,1}},0,\dots ,0]\text{（}1\le l\le c\text{）}$が線形独立な固有値$0$の固有ベクトルとして構成できるので，$m_0\ge c$である．$x={}^t[x_1,x_2,\dots ,x_n]$をラプラシアン固有値$0$の固有ベクトルとすると，${}^t{x}^{\prime }L{x}^{\prime }=0$ であるから，

$0={}^t{x}^{\prime }L{x}^{\prime }$
$=\sum _{l=1}^c\sum _{j\in C_l}{x}_j(Lx{)}_j$
$=\sum _{l=1}^c(\sum _{j\in C_l}{D}_{j,j}{x}_j^2-\sum _{j,k\in C_l}{A}_{j,k}{x}_j{x}_k)$ （$L=D-A$より）
$=\sum _{l=1}^c(\sum _{j\in C_l}\sum _{k\in C_l}{A}_{j,k}{x}_j^2-\sum _{j,k\in C_l}{A}_{j,k}{x}_j{x}_k)$
$=\sum _{l=1}^c\sum _{j\in C_l}{x}_j\sum _{k\in C_l}{A}_{j,k}(x_j-x_k)$
$=\frac{1}{2}\sum _{l=1}^c\sum _{j,k\in C_l}(x_j{A}_{j,k}(x_j-x_k)+x_k{A}_{k,j}(x_k-x_j))$
$=\frac{1}{2}\sum _{l=1}^c\sum _{j,k\in C_l}(x_j{A}_{j,k}-x_k{A}_{k,j})(x_j-x_k)$

ここで，$A_{j,k}=A_{k,j}$（$1\le j,k\le n$）より，

$=\frac{1}{2}\sum _{l=1}^c\sum _{j,k\in C_l}{A}_{j,k}(x_j-x_k{)}^2$

である．

連結成分$C_l$（$1\le l\le c$）上の任意の$2$頂点$j,k\in C_l$（$1\le l\le c$）は経路$j\to p_1\to p_2\to \cdots \to p_s\to k$（$p_1,\dots ,p_s\in C_l$（$1\le l\le c$））が存在して，$A_{j,p_1}=A_{p_1,p_2}=\cdots =A_{p_s,k}=1\text{（}1\le l\le c\text{）}$である．
したがって，$x_j=x_{p_1}=x_{p_2}=\cdots =x_{p_s}=x_k\text{（}j,p_1,\dots ,p_s,k\in C_l\text{（}1\le l\le c\text{））}$であるから，$x$がラプラシアン固有値$0$の固有ベクトルとなるとき，$x={}^t[\underset{C_1\text{に対応した部分}}{\underbrace{a_1,\dots ,a_1}},\underset{C_2\text{に対応した部分}}{\underbrace{a_2,\dots ,a_2}},\dots ,\underset{C_c\text{に対応した部分}}{\underbrace{a_c,\dots ,a_c}}]\text{（}{a}_l\in \mathbb{C}\text{，}1\le l\le c\text{）}$である．

よって，ラプラシアン固有値$0$の固有ベクトル$x$は$x_l^{\prime }$（$1\le l\le c$）を用いて$x=\sum _{l=1}^c{a}_l{x}_l^{\prime }\text{（}{a}_l\in \mathbb{C}\text{，}1\le l\le c\text{）}$である．
$x_l^{\prime }$（$1\le l\le c$）の線形結合として表せるから，$c\ge m_0$である．

よって，$m_0=c$であるから，グラフ$G$のラプラシアン固有値$0$の重複度は，連結成分の個数に等しい．