Laplacian matrix
= Laplacian matrix
{c}
{title2=$L$}
{wiki}
= Graph Laplacian
{c}
{synonym}
The <Graph Laplacian> converts local differences along <edges> into a <linear map>. Throughout this section, $G=(V,E)$ is a finite <undirected graph> with no <self-loops> or repeated <edges>, and each <edge> has weight one. In a fixed order of <vertices>, let $A$ be the <adjacency matrix> and $D$ the <degree matrix>. The combinatorial <Graph Laplacian> is
$$
L=D-A,\qquad (Lx)_i=\sum_{j:\{i,j\}\in E}(x_i-x_j).
$$
Thus the value at a <vertex> is compared with its neighbours. Every row sums to zero, so $L\mathbf1=0$: a constant <vector> produces no differences. This definition and the associated <Graph Laplacian quadratic form> are developed in Spielman's authored survey.https://www.cs.yale.edu/homes/spielman/PAPERS/SGTChapter.pdf[Spielman, Spectral Graph Theory, Sections 16.3.1–16.3.2]{ref}
For the three-<vertex> <path graph> $A-B-C$, the <vertex degrees> are $1,2,1$, and in that order
$$
A=\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix},\qquad
D=\begin{pmatrix}1&0&0\\0&2&0\\0&0&1\end{pmatrix},\qquad
L=\begin{pmatrix}1&-1&0\\-1&2&-1\\0&-1&1\end{pmatrix}.
$$
Direct multiplication gives three <eigenvectors> and their <eigenvalues>:
$$
L\begin{pmatrix}1\\1\\1\end{pmatrix}=0,\qquad
L\begin{pmatrix}1\\0\\-1\end{pmatrix}=\begin{pmatrix}1\\0\\-1\end{pmatrix},\qquad
L\begin{pmatrix}1\\-2\\1\end{pmatrix}=3\begin{pmatrix}1\\-2\\1\end{pmatrix}.
$$
The constant <eigenvector> has <eigenvalue> zero; the other two describe progressively stronger neighbour disagreement. Dividing these <eigenvectors> by $\sqrt3,\sqrt2,\sqrt6$, respectively, gives an <orthonormal basis>. The four-<vertex> <cycle graph> is already worked out under <circulant matrix>, where <Fourier diagonalization of a circulant matrix> gives its <eigenvalues>.
Every formula here uses $L=D-A$ without degree normalization. For comparison, Chung's treatment uses the degree-scaled <matrix> $D^{-1/2}LD^{-1/2}$, with a convention for isolated <vertices>; its <eigenvalues> must not be substituted into the examples here.https://www.math.ucsd.edu/~fan/cbms.pdf[Chung, Lectures on Spectral Graph Theory, Section 1.2]{ref}