Rayleigh Quotients and Least Eigenvalues

From Eigenvalues to Quadratic Forms

The adjacency matrix records which vertex pairs are joined, while its eigenvalues summarize how that pattern acts on vectors. A basic way to connect the two is to evaluate a quadratic form \(x^{T}\mathbf{A}x\) and compare it with the squared length \(x^{T}x\). The resulting ratio cannot fall below the least adjacency eigenvalue. This simple inequality is a starting point for spectral arguments about independent sets and colorings.

Throughout, graphs are finite, simple and undirected. For a graph \(G=(V,E)\) with \(n\) vertices, \(\mathbf{A}=\mathbf{A}(G)\) is its \(n\times n\) adjacency matrix: its \(uv\) entry is \(1\) when \(uv\in E\) and \(0\) otherwise. Because the graph is undirected, \(\mathbf{A}\) is a real symmetric matrix. Write its eigenvalues in nonincreasing order as \(\lambda_1\ge\cdots\ge\lambda_n\), and let \(\lambda_{\min}=\lambda_n\).

The numerator has a useful graph interpretation. If \(x=(x_v)_{v\in V}\), then each edge contributes once from each of the two symmetric entries of \(\mathbf{A}\), so \(x^{T}\mathbf{A}x=2\sum_{uv\in E}x_ux_v\). The denominator is \(\sum_{v\in V}x_v^2\). Thus the quotient compares a sum over edges with a sum over vertices. The signs of the coordinates matter: an edge whose endpoints have opposite signs contributes negatively.

The Least-Eigenvalue Inequality

Proof. Since \(\mathbf{A}\) is real symmetric, the spectral theorem gives an orthonormal basis of real eigenvectors \(u_1,\ldots,u_n\), with corresponding eigenvalues \(\lambda_1,\ldots,\lambda_n\). Expand \(x=\sum_{i=1}^{n}c_i u_i\). Orthonormality gives \(x^{T}x=\sum_i c_i^2\), and the eigenvector equations give \(x^{T}\mathbf{A}x=\sum_i\lambda_i c_i^2\). Since every \(\lambda_i\ge\lambda_{\min}\), \(x^{T}\mathbf{A}x-\lambda_{\min}x^{T}x=\sum_i(\lambda_i-\lambda_{\min})c_i^2\ge0\). Dividing by \(x^{T}x>0\) proves the quotient inequality. Equality holds precisely when every term with \(\lambda_i>\lambda_{\min}\) has \(c_i=0\), which says that \(x\) is a linear combination of eigenvectors with eigenvalue \(\lambda_{\min}\). Since \(x\ne0\), this is exactly the condition that \(x\) is an eigenvector for \(\lambda_{\min}\). \(\square\)

This result is also called the minimum characterization of the least eigenvalue: among all nonzero real vectors, the smallest Rayleigh quotient is \(\lambda_{\min}\). The proof shows both why the inequality holds and when it is sharp. In applications, the chosen vector need not be an eigenvector; the inequality still gives a constraint.

Indicator Vectors and Independent Sets

For a vertex set \(S\subseteq V\), its indicator vector \(\mathbf{1}_S\) has coordinate \(1\) on \(S\) and \(0\) outside \(S\). Its squared length is \(|S|\). If \(S\) is independent, meaning that no two vertices of \(S\) are adjacent, then \(\mathbf{1}_S^{T}\mathbf{A}\mathbf{1}_S=0\): every edge has at least one endpoint outside \(S\). But inserting this vector directly into the least-eigenvalue inequality is usually not the most informative step. For a regular graph, centering the vector removes its component in the all-ones direction.

Proof. Regularity gives \(\mathbf{A}\mathbf{1}=d\mathbf{1}\), and hence \(\mathbf{1}^{T}\mathbf{A}\mathbf{1}=dn\). Independence gives \(\mathbf{1}_S^{T}\mathbf{A}\mathbf{1}_S=0\). Also, \(\mathbf{1}_S^{T}\mathbf{A}\mathbf{1}=ds\), because each of the \(s\) vertices in \(S\) has degree \(d\). Expanding the quadratic form, \(y^{T}\mathbf{A}y=\mathbf{1}_S^{T}\mathbf{A}\mathbf{1}_S-2(s/n)\mathbf{1}_S^{T}\mathbf{A}\mathbf{1}+(s^2/n^2)\mathbf{1}^{T}\mathbf{A}\mathbf{1}=0-2ds^2/n+ds^2/n=-ds^2/n\). For the squared length, \(\mathbf{1}_S^{T}\mathbf{1}_S=s\) and \(\mathbf{1}_S^{T}\mathbf{1}=s\), so \(y^{T}y=s-2s^2/n+(s^2/n^2)n=s-s^2/n\). The least-eigenvalue inequality applied to \(y\) gives the final assertion when \(y\ne0\); if \(y=0\), both sides of that inequality are \(0\), so it holds as well. \(\square\)

The centered vector has coordinate \(1-s/n\) on \(S\) and \(-s/n\) off \(S\). Its coordinates sum to zero, which is why it is useful when separating the uniform direction from variation across vertices. The proposition provides the quadratic-form relation used in spectral bounds; further algebraic steps turn such relations into bounds on the size of \(S\).

Color Classes and a Shared Quadratic Form

A proper coloring partitions the vertices into color classes, each of which is an independent set. The same centering calculation can therefore be applied to every class. The resulting summed inequality is a useful way to organize a spectral argument about the number of colors, without needing to know the individual locations of the classes.

Proof. Each color class is independent, so the preceding expansion applies to each \(C_i\), giving \(y_i^{T}\mathbf{A}y_i=-ds_i^2/n\) and \(y_i^{T}y_i=s_i-s_i^2/n\). Summing the first identities gives \(\sum_i y_i^{T}\mathbf{A}y_i=-(d/n)\sum_i s_i^2=-dQ/n\). Since the classes partition \(V\), \(\sum_i s_i=n\). Thus summing the squared lengths gives \(\sum_i(s_i-s_i^2/n)=n-Q/n\). For each \(i\), the Rayleigh inequality gives \(y_i^{T}\mathbf{A}y_i\ge\lambda_{\min}y_i^{T}y_i\), including the case \(y_i=0\), when both sides are zero. Adding these \(k\) inequalities proves \(-dQ/n\ge\lambda_{\min}(n-Q/n)\). \(\square\)

A Common Mistake and Why the Inequality Matters

Common mistake: reversing the inequality. The least eigenvalue is the minimum Rayleigh quotient, not the maximum. For the triangle in the example, take \(x=(1,0,0)^T\). Then \(x^{T}\mathbf{A}x=0\), \(x^{T}x=1\), and \(R(x)=0\), while \(\lambda_{\min}=-1\). The correct comparison is \(0\ge-1\). Claiming instead that \(R(x)\le\lambda_{\min}\) would give \(0\le-1\), which is false.

The vector used in a spectral argument should match the graph structure being studied. An indicator vector records membership in a set; centering it changes the coordinates without losing the set information, while making the regular-graph quadratic form computable. For a coloring, doing this once per class allows the inequalities to be added. In each case, the Rayleigh quotient supplies the same rigorous constraint, and equality occurs only when the relevant nonzero vector lies in the least-eigenvalue eigenspace.

Keep the assumptions visible when using these calculations. The inequality \(x^{T}\mathbf{A}x\ge\lambda_{\min}x^{T}x\) needs only a real symmetric adjacency matrix and a real vector; it does not require regularity or connectedness. The centered-vector identities above use \(d\)-regularity. They also remain valid when a centered vector is zero, as can happen when a class is all of \(V\); the zero vector satisfies the quadratic-form inequality with equality. For a graph with no edges, \(d=0\) and \(\lambda_{\min}=0\), so the formulas still hold, though they need not provide a useful numerical constraint.