ラプラシアン行列
(無向)グラフGと固有値 λ 0 ≤ λ 1 ≤ ⋯ ≤ λ n − 1 {\textstyle \lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{n-1}} を持つそのラプラシアン行列Lについて:
Lは対称である。
Lは半正定値である(すなわち全ての i {\textstyle i} について λ i ≥ 0 {\textstyle \lambda _{i}\geq 0} )。これは接続行列の節で検証される。これは、ラプラシアンが対称であり、優対角(英語版)であるという事実からも見ることができる。
LはM-行列である(その非対角成分は非正であり、そのうえその固有値の実部は非負である)。
Lの全ての行の和と列の和はゼロである。実際、和の計算において、頂点の次数には隣接する頂点ごとに「−1」が足される。
その結果、 λ 0 = 0 {\textstyle \lambda _{0}=0} となる。これは、ベクトル v 0 = ( 1 , 1 , ... , 1 ) {\textstyle \mathbf {v} _{0}=(1,1,\dots ,1)} が L v 0 = 0 {\textstyle L\mathbf {v} _{0}=\mathbf {0} } を満たすためである。これは、ラプラシアン行列が特異行列であることも暗示する。
n個の頂点を持つ単純グラフを考えると、そのラプラシアン行列 L n × n {\textstyle L_{n\times n}} は以下の式で定義される。
L = D − A {\displaystyle L=D-A}
上式において、Dはグラフの次数行列、Aは隣接行列である。 G {\textstyle G} は単純グラフであるため、 A {\textstyle A} の成分は1または0のみであり、その対角要素は全て0である。
有向グラフの場合は、入次数または出次数のいずれかが、応用に依存して使われるだろう。
L {\textstyle L} の要素は式
L i , j := { deg  ( v i ) if i = j − 1 if i ≠ j and v i is adjacent to v j 0 otherwise {\displaystyle L_{i,j}:={\begin{cases}\deg(v_{i})&{\mbox{if}}\ i=j\\-1&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}\end{cases}}}
によって与えられる。上式において、 deg  ( v i ) {\displaystyle \operatorname {deg} (v_{i})} は頂点 i {\displaystyle i} の次数である。