Laplacian matrix

Remarks

For every real vector $x$, $x^{T} L x = \sum (x_i - x_j)^2$, the sum running over the edges $v_i v_j$. Hence $L$ is symmetric and positive semidefinite, the all-ones vector lies in its kernel, and the multiplicity of the eigenvalue $0$ equals the number of connected components of $G$. Example: for the path $v_1 v_2 v_3$, $$L = \begin{pmatrix} 1 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 1 \end{pmatrix},$$ whose eigenvalues are $0$, $1$ and $3$, with eigenvectors $(1,1,1)$, $(1,0,-1)$ and $(1,-2,1)$. Non-example: the matrix $D + A$ has the right diagonal but the wrong sign off the diagonal. It is the signless Laplacian, and it has the same spectrum as $L$ when $G$ is bipartite, but not in general. The normalized Laplacian $D^{-1/2} L D^{-1/2}$, defined when no vertex is isolated, is also common. Mathlib defines the Laplacian matrix as SimpleGraph.lapMatrix.