ラプラシアン行列
なぜなら定義 ∑ j L i j = 0 {\textstyle \sum _{j}L_{ij}=0} によれば、全てが1のベクトル v 1 {\textstyle \mathbf {v} ^{1}} は核内にある。また、グラフ中に k {\textstyle k} 個の互いに素な連結成分が存在するならば、この全てが1のベクトルは1と0からなる k {\textstyle k} 個の独立な λ = 0 {\textstyle \lambda =0} 固有ベクトルの和へと分割できる。それぞれの連結成分は連結成分中の要素では1を持つ固有ベクトルと、その他の場所では0を持つ固有ベクトルと対応している。
この結果は、 N {\textstyle N} 個の頂点を持つグラフについて任意の初期条件 c ( 0 ) {\textstyle c(0)} では、
lim t → ∞ φ ( t ) = ⟨ c ( 0 ) , v 1 ⟩ v 1 {\displaystyle \lim _{t\to \infty }\phi (t)=\left\langle c(0),\mathbf {v^{1}} \right\rangle \mathbf {v^{1}} }
となる。上式において、
(対称)正規化ラプラシアンは以下のように定義される。
L sym := D − 1 2 L D − 1 2 = I − D − 1 2 A D − 1 2 {\displaystyle L^{\text{sym}}:=D^{-{\frac {1}{2}}}LD^{-{\frac {1}{2}}}=I-D^{-{\frac {1}{2}}}AD^{-{\frac {1}{2}}}}
上式において、Lは(非正規化)ラプラシアン、Aは隣接行列、Dは次数行列である。次数行列Dは対角行列で正であるため、その逆数平方根 D − 1 2 {\textstyle D^{-{\frac {1}{2}}}} は単にその対角成分がDの対角成分の正の平方根の逆数である対角行列となる。対称正規化ラプラシアンは対称行列である。
L sym = S S ∗ {\textstyle L^{\text{sym}}=SS^{*}} が存在する。Sは、列が頂点によって添え字を付けられ、行がGの辺によって添え字が付けられた行列である。これらは、辺e = {u, v} に対応するそれぞれの行がuに対応する列において成分 1 d u {\textstyle {\frac {1}{\sqrt {d_{u}}}}} を、vに対応する列において成分 − 1 d v {\textstyle -{\frac {1}{\sqrt {d_{v}}}}} を、それ以外では0成分を持つことになるように索引付けされる(注: S ∗ {\textstyle S^{*}} はSの転置行列を示す)。
正規化ラプラシアンの全ての固有値は実数かつ非負である。