Rayleigh Quotients and the Spectral Gap

From a Random Walk to a Rayleigh Quotient

For a random walk on a regular graph, the transition matrix is a rescaled adjacency matrix. Its eigenvalues describe how the walk acts on functions on the vertices. The spectral gap measures how far the second-largest eigenvalue lies below \(1\). This tutorial derives a variational formula for that gap and expresses its numerator as an energy built from differences across edges.

Throughout, \(G=(V,E)\) is a finite, simple, undirected, connected \(d\)-regular graph, where \(d\ge 1\). Write \(n=|V|\). For a function \(f:V\to\mathbb R\), define its uniform mean by \(\overline f=\frac1n\sum_{v\in V}f(v)\). We use the inner product and norm

The subscript \(\pi\) indicates the uniform probability distribution on the vertices. In a regular graph this distribution is stationary for the simple random walk: from each vertex the walk chooses each of its \(d\) neighbors with probability \(1/d\).

Connectedness ensures that the eigenvalue \(1\) occurs only on constant functions. The spectral theorem for real symmetric matrices gives an orthonormal basis of eigenvectors; applying it to \(P\), we can take the constant functions as the eigenspace for \(\lambda_1=1\). We justify the connectedness claim as part of the energy identity below. The definition here uses the second-largest eigenvalue, not the largest absolute value among the nonconstant eigenvalues. That distinction matters for graphs with eigenvalues near \(-1\).

The Dirichlet Energy

The matrix definition has a direct edge-by-edge form. Each edge is counted once in the sum below.

Proof. By the definition of \(P\),

In the double sum, every undirected edge \(uv\) contributes once as the ordered pair \((u,v)\) and once as \((v,u)\). Thus the double sum is \(2\sum_{uv\in E}f(u)f(v)\). Also, regularity gives \(\sum_{uv\in E}(f(u)^2+f(v)^2)=d\sum_{v\in V}f(v)^2\), since each vertex appears in exactly \(d\) edges. Expanding the squares on the right-hand side of the claimed identity therefore gives

This proves the identity. If the energy is zero, every squared difference across an edge is zero, so \(f\) takes equal values at the endpoints of every edge. Along any path its value remains constant; connectedness then makes \(f\) constant on all of \(V\). Conversely, a constant function has zero difference on every edge and hence zero energy. In particular, the only functions satisfying \(Pf=f\) are constants, so the eigenvalue \(1\) is simple. \(\square\)

The factor \(1/(nd)\) depends on using the normalized inner product \(\langle\cdot,\cdot\rangle_\pi\), and on summing over undirected edges just once. Keeping these conventions fixed makes the variational quotient easy to interpret and compute.

Variational Characterization of the Gap

Proof. Let \(q_1,\ldots,q_n\) be an orthonormal eigenbasis for \(P\) in the uniform inner product, with \(Pq_i=\lambda_iq_i\) and \(q_1\) constant. A function has mean zero exactly when it is orthogonal to \(q_1\): the inner product with a nonzero constant function is a nonzero constant multiple of its mean. Thus every nonzero mean-zero \(f\) has an expansion \(f=\sum_{i=2}^n c_iq_i\), with at least one \(c_i\ne0\). Orthonormality gives \(\|f\|_\pi^2=\sum_{i=2}^n c_i^2\). Using the eigenvector equations gives \(\mathcal E(f,f)=\sum_{i=2}^n(1-\lambda_i)c_i^2\). Since \(\lambda_i\le\lambda_2\) for every \(i\ge2\), each coefficient \(1-\lambda_i\) is at least \(1-\lambda_2\). Therefore

For equality, choose a nonzero eigenvector \(q_2\) for \(\lambda_2\). It is orthogonal to the constant eigenvector, so it has mean zero, and its quotient is \((1-\lambda_2)\|q_2\|_\pi^2/\|q_2\|_\pi^2=1-\lambda_2\). Hence the minimum is attained and equals the gap. Substituting the edge formula for \(\mathcal E(f,f)\) proves the final expression. \(\square\)

The minimization is restricted to mean-zero functions because constants have zero energy and would make an unrestricted minimum equal to zero. The quotient compares edge variation with squared size: functions that change little across edges relative to their norm give a small quotient.

Worked Examples

Interpretation and a Common Pitfall

By the theorem, a small spectral gap means there is a nonzero mean-zero function whose squared differences across edges are small compared with its squared norm. The mean-zero condition removes the constant functions, which have no variation at all. This gives a useful way to read the gap: it is the least edge-based variation available to a function of unit squared norm after constants have been excluded. It also gives a concrete optimization problem for finding the gap, rather than only an eigenvalue calculation.

Common mistake: omitting the normalization factor. In the four-cycle example, the sum of the squared edge differences for \(f=(1,0,-1,0)\) is \(4\). Dividing only by \(d=2\) would give \(4/2=2\) for the energy. That is incorrect for the normalized inner product used here: the edge formula divides by \(nd=4\cdot2=8\), so the energy is \(4/8=1/2\). The squared norm is also normalized by \(n\), giving \(2/4=1/2\); the quotient is therefore \(1\), not \(2/(1/2)=4\). Always check that the energy and norm use the same inner-product convention.

Another distinction is that the variational formula selects the second-largest eigenvalue, not the eigenvalue with second-largest absolute value. For a non-lazy walk, negative eigenvalues can have large absolute value, as the two-vertex example shows. Replacing \(\lambda_2\) by an absolute-value convention changes the parameter being studied and does not give the minimum quotient proved here.