= Graph Laplacian quadratic form
{title2=$x^TLx=\sum_{\{i,j\}\in E}(x_i-x_j)^2$}
Assign a real value $x_i$ to each <vertex>. The <Graph Laplacian quadratic form> measures disagreement across <edges>:
$$
x^TLx=\sum_{\{i,j\}\in E}(x_i-x_j)^2\geq0.
$$
This makes the <Graph Laplacian> a <positive semidefinite matrix>. The <energy> is small when neighbours have similar values, even if distant <vertices> have very different values; it depends on connections rather than where the <graph> is drawn. In the three-<vertex> <path graph>, take $x=(2,0,-1)^T$. Then
$$
Lx=(2,-1,-1)^T,\qquad
x^TLx=2\cdot2+0\cdot(-1)+(-1)\cdot(-1)=5,
$$
and the two <edges> contribute $(2-0)^2=4$ and $(0-(-1))^2=1$.
\Image[/graph-laplacian-edge-energy.png]
{title=Edge disagreement and eigenvectors of the three-vertex path Laplacian}
For a short proof, expand $x^T(D-A)x$. Each <edge> contributes $x_i^2+x_j^2$ through the <degree matrix> and $-2x_ix_j$ through the <adjacency matrix>, yielding $(x_i-x_j)^2$. The sum over unordered <edges> has no factor $1/2$; a sum over all ordered pairs does:
$$
x^TLx=\frac12\sum_{i,j}A_{ij}(x_i-x_j)^2.
$$
Equivalently, let $B$ be an <oriented incidence matrix>, with one row per <edge>. Then $Bx$ records endpoint differences and $L=B^TB$, independently of the chosen orientations. This translates a local comparison into a global <quadratic form> and makes its nonnegativity visible.
Back to article page
