Laplacian Eigenvalues And The Rayleigh Quotient

From Edge Energy to Eigenvalues

The graph Laplacian records how a vector of vertex values changes across edges. Its quadratic form is an edge-energy: each edge contributes the square of the difference between the values at its endpoints. This simple identity has two important consequences. First, Laplacian eigenvalues cannot be negative. Second, the second-smallest eigenvalue can be found by minimizing a quotient of edge-energy by squared vector length, with one essential restriction: the vector must be perpendicular to the all-ones vector.

Let \(G=(V,E)\) be a finite simple undirected graph of order \(n\), with vertices ordered as \(v_1,\dots,v_n\). Its adjacency matrix is \(\mathbf A\), its diagonal degree matrix is \(\mathbf D\), and its Laplacian is \(\mathbf L=\mathbf D-\mathbf A\). Vectors in this tutorial are real column vectors in \(\mathbb R^n\). Write \(\mathbf 1=(1,\dots,1)^\top\), use \(x^\top y\) for the Euclidean inner product, and write \(\|x\|^2=x^\top x\).

For an undirected graph, \(\mathbf L\) is real and symmetric. The real symmetric spectral theorem from linear algebra says that such a matrix has an orthonormal basis of real eigenvectors, with real eigenvalues. We use this standard linear-algebra result without proving it here. List the Laplacian eigenvalues in nondecreasing order, including multiplicity, as \(\lambda_1\le\lambda_2\le\cdots\le\lambda_n\).

The Edge-Energy Identity

For each vertex \(v\), the diagonal contribution to \(x^\top\mathbf D x\) is \(\deg(v)x_v^2\). The adjacency-matrix contribution is \(x^\top\mathbf A x=2\sum_{uv\in E}x_ux_v\), because each undirected edge appears in both symmetric positions of \(\mathbf A\). Also, \(\sum_{v\in V}\deg(v)x_v^2=\sum_{uv\in E}(x_u^2+x_v^2)\): each edge contributes one square for each endpoint. Subtracting gives the identity below.

This identity is valid for every real vector \(x\), including \(x=0\). It also explains the word “energy”: an edge contributes zero when its endpoint values agree, and contributes a positive amount when they differ.

Proof. Let \(q\ne0\) be an eigenvector with eigenvalue \(\lambda\), so \(\mathbf Lq=\lambda q\). Multiplying on the left by \(q^\top\) and using the edge-energy identity gives \(\lambda\|q\|^2=q^\top\mathbf Lq=\sum_{uv\in E}(q_u-q_v)^2\ge0\). Since \(\|q\|^2>0\), division shows \(\lambda\ge0\). For the all-ones vector, every coordinate of \(\mathbf L\mathbf 1\) is \(\deg(v)-\deg(v)=0\), so \(\mathbf L\mathbf 1=0\). Thus zero is an eigenvalue, and the ordered list begins with \(\lambda_1=0\). \(\square\)

The energy identity also says exactly when the quadratic form vanishes: every summand is nonnegative, so the sum is zero if and only if \(x_u=x_v\) on every edge \(uv\). In particular, the all-ones vector has zero energy. To find the next eigenvalue, we must remove this constant direction from consideration; that is the role of the perpendicularity condition.

The Variational Characterization

Proof. Since \(\mathbf L\) is real and symmetric, choose an orthonormal eigenbasis \(q_1,\dots,q_n\), ordered so that \(\mathbf Lq_i=\lambda_iq_i\). We can take \(q_1=\mathbf 1/\sqrt n\), since \(\mathbf L\mathbf 1=0\). This choice remains possible if the zero eigenvalue has multiplicity greater than one: within its eigenspace, choose the normalized all-ones vector as the first basis vector and complete it to an orthonormal basis.

Take any \(x\ne0\) with \(x\perp\mathbf 1\). Expand it in the eigenbasis as \(x=\sum_{i=1}^n a_iq_i\). Orthogonality to \(\mathbf 1\) gives \(a_1=x^\top q_1=0\), so \(x=\sum_{i=2}^n a_iq_i\). The eigenvectors are orthonormal, hence \(x^\top x=\sum_{i=2}^n a_i^2\). Using \(\mathbf Lq_i=\lambda_iq_i\) and orthonormality also gives \(x^\top\mathbf Lx=\sum_{i=2}^n\lambda_i a_i^2\). Therefore \(\displaystyle R_{\mathbf L}(x)=\frac{\sum_{i=2}^n\lambda_i a_i^2}{\sum_{i=2}^n a_i^2}\ge\lambda_2\), because \(\lambda_i\ge\lambda_2\) for every \(i\ge2\).

To show that this lower bound is attained, take \(x=q_2\). It is nonzero, and \(q_2\perp q_1\), so \(q_2\perp\mathbf 1\). Its quotient is \(\displaystyle R_{\mathbf L}(q_2)=\frac{q_2^\top\mathbf Lq_2}{q_2^\top q_2}=\frac{\lambda_2 q_2^\top q_2}{q_2^\top q_2}=\lambda_2\). Thus the minimum exists and equals \(\lambda_2\), as claimed. \(\square\)

The restriction \(x\perp\mathbf 1\) is indispensable. Without it, the constant vector is an allowed nonzero vector and has quotient zero, so the minimum over all nonzero vectors is \(\lambda_1=0\), not \(\lambda_2\). The theorem is a minimization over a subspace of dimension \(n-1\); it does not require the graph to be connected.

How to Use the Formula and a Common Pitfall

The variational formula gives a way to estimate \(\lambda_2\) without finding every eigenvalue. Any nonzero vector \(x\perp\mathbf 1\) gives an upper bound: by the theorem, \(\lambda_2\le R_{\mathbf L}(x)\). To prove that a proposed value is exactly \(\lambda_2\), one also needs a lower bound for every admissible vector, or an exact spectral calculation such as the eigenbasis checks above.

A common mistake is to use the wrong denominator. In the \(P_3\) example, the vector \(x=(1,0,-1)^\top\) has energy \(2\) and squared length \(2\), so its Rayleigh quotient is \(2/2=1\). Dividing by the length \(\|x\|=\sqrt2\) instead would give \(2/\sqrt2=\sqrt2\), which is not the Rayleigh quotient. The denominator is \(x^\top x=\|x\|^2\), not \(\|x\|\).

A second mistake is to omit the perpendicularity condition. The nonzero vector \(\mathbf 1\) always has quotient \(0\), because \(\mathbf L\mathbf 1=0\). It is excluded from the minimization for \(\lambda_2\) precisely because \(\mathbf 1^\top\mathbf 1=n\ne0\). In a disconnected graph there may be other zero-energy vectors perpendicular to \(\mathbf 1\), as the two-edge example demonstrates; the formula still holds, and its minimum is then zero.

The edge-energy form is useful because it translates a matrix question into a statement about differences across edges. The perpendicular constraint removes the constant vector, while allowing every other direction in the space. Together, these ingredients explain both the nonnegative spectrum and the precise variational meaning of the second-smallest eigenvalue.