= Kernel of a graph Laplacian
{title2=$\dim\ker L=\text{number of connected components}$}
The <kernel> of the <Graph Laplacian> consists exactly of <vectors> constant on each <connected component of a graph>. Indeed, $Lx=0$ implies $x^TLx=0$, so the <Graph Laplacian quadratic form> forces equality at the endpoints of every <edge>; equality then propagates along <graph paths>. Conversely, these equalities make every entry of $Lx$ zero. Thus the <dimension> of the <kernel>, equivalently the multiplicity of the zero <eigenvalue>, counts the <connected components of a graph>.
For the disconnected <graph> with just two <edges>, $AB$ and $CD$, in order $A,B,C,D$,
$$
L=\begin{pmatrix}1&-1&0&0\\-1&1&0&0\\0&0&1&-1\\0&0&-1&1\end{pmatrix},\qquad
\ker L=\operatorname{span}\left\{\begin{pmatrix}1\\1\\0\\0\end{pmatrix},\begin{pmatrix}0\\0\\1\\1\end{pmatrix}\right\}.
$$
The two displayed <vectors> form a <basis> of the <kernel>. The other two <eigenvectors> $(1,-1,0,0)^T$ and $(0,0,1,-1)^T$ each have <eigenvalue> two, so the full list of <eigenvalues>, including multiplicities, is $0,0,2,2$. Separate <connected components of a graph> allow independent constant levels; a single global constant is only one of these possibilities.
\Image[/graph-laplacian-connected-components.png]
{title=Two disconnected edges give two independent zero eigenvectors}
Back to article page
