Ordering and Multiplicity of Adjacency Eigenvalues

Ordering the Adjacency Spectrum

An adjacency matrix records which pairs of vertices are adjacent. Its eigenvalues give numerical summaries of the graph, but interpreting them requires care: eigenvalues can repeat, and their order is part of the notation. This tutorial develops the ordering and multiplicity conventions for a graph's adjacency eigenvalues, and explains how the Rayleigh quotient connects those values to vectors.

Let \(G=(V,E)\) be a finite simple graph with \(n=|V|\ge 1\). After choosing an ordering of \(V\), its adjacency matrix \(\mathbf{A}(G)\) is the \(n\) by \(n\) matrix whose \(ij\)-entry is \(1\) if the \(i\)th and \(j\)th vertices are adjacent, and \(0\) otherwise. Because the graph is undirected, \(\mathbf{A}(G)\) is real and symmetric. An eigenvalue of a matrix \(A\) is a number \(\lambda\) for which \(Ax=\lambda x\) for some nonzero vector \(x\); such an \(x\) is an eigenvector.

Ordering with repetition is essential. If an eigenvalue occurs twice, it occupies two positions in the ordered list. For a real symmetric matrix, all eigenvalues are real, and algebraic and geometric multiplicities agree. The result below proves these facts rather than assuming them.

Why Symmetry Gives Real Eigenvalues and Matching Multiplicities

Proof. We prove the orthonormal eigenbasis assertion by induction on \(n\). For \(n=1\), the sole coordinate vector is an eigenvector, so the assertion holds. Suppose \(n>1\), and assume the assertion holds for symmetric matrices of size \(n-1\). On the unit sphere in \(\mathbb{R}^n\), the continuous function \(x\mapsto x^{T}Ax\) attains a maximum, since that sphere is compact. Let \(x\) be a unit vector where the maximum occurs.

Take any vector \(y\) with \(x^{T}y=0\), and consider the unit vector \((x+ty)/\|x+ty\|\) for real \(t\). Its quadratic form is \[ \frac{x^{T}Ax+2t\,y^{T}Ax+t^2y^{T}Ay}{1+t^2\|y\|^2}, \] where symmetry of \(A\) gives \(x^{T}Ay=y^{T}Ax\). This expression has a maximum at \(t=0\), so its derivative there is \(2y^{T}Ax=0\). Thus \(Ax\) is orthogonal to every vector perpendicular to \(x\), and hence \(Ax=\lambda x\) for some real \(\lambda\).

The subspace \(x^\perp=\{z:x^{T}z=0\}\) is invariant under \(A\): if \(z\in x^\perp\), then \(x^{T}Az=(Ax)^{T}z=\lambda x^{T}z=0\). The restriction of \(A\) to \(x^\perp\) is symmetric. By induction it has an orthonormal eigenbasis, and adjoining \(x\) gives an orthonormal eigenbasis for the whole space. In this basis, \(A\) is diagonal, with its real eigenvalues on the diagonal. Its characteristic polynomial is the product of the corresponding linear factors, so the algebraic multiplicity of each eigenvalue is the number of times it appears on the diagonal. That number is also the dimension of its eigenspace, proving equality of the two multiplicities. \(\square\)

Adjacency matrices of simple undirected graphs meet the theorem's symmetry hypothesis. Thus their eigenvalues can be ordered on the real line. In particular, repeated values are not a sign that a matrix has too few eigenvectors: for a symmetric matrix, the eigenspace dimension supplies exactly the multiplicity required by the characteristic polynomial.

The Rayleigh Quotient

Proof. By the theorem just proved, choose an orthonormal eigenbasis \(u_1,\dots,u_n\), with \(Au_i=\lambda_i u_i\). Write \(x=\sum_{i=1}^{n}c_i u_i\). Orthonormality gives \(x^{T}x=\sum_i c_i^2\) and \(x^{T}Ax=\sum_i\lambda_i c_i^2\). Therefore \[ R_A(x)=\frac{\sum_i\lambda_i c_i^2}{\sum_i c_i^2}. \] The coefficients \(c_i^2/\sum_j c_j^2\) are nonnegative and sum to \(1\), so this quotient is a weighted average of the eigenvalues. It lies between their minimum and maximum. The difference from the upper bound is \[ \lambda_1-R_A(x)=\frac{\sum_i(\lambda_1-\lambda_i)c_i^2}{\sum_i c_i^2}. \] Every term in the numerator is nonnegative. The difference is zero exactly when \(c_i=0\) for every \(i\) with \(\lambda_i<\lambda_1\), which says precisely that \(x\) lies in the \(\lambda_1\)-eigenspace. The lower-bound equality follows in the same way from \[ R_A(x)-\lambda_n=\frac{\sum_i(\lambda_i-\lambda_n)c_i^2}{\sum_i c_i^2}. \] Thus both bounds and both equality conditions hold. \(\square\)

The quotient is not generally an eigenvalue: it is a value formed from a chosen vector. The theorem says it cannot exceed the largest eigenvalue or fall below the smallest. It also says that the extreme values are attained exactly on the corresponding eigenspaces.

Worked Spectral Calculations

Common Mistake: Confusing an Eigenvalue with a Quotient

A frequent error is to calculate a Rayleigh quotient for one vector and report it as an eigenvalue. For example, in the star calculation, \(x=(2,1,0,0)^T\) gives \(R_{\mathbf{A}(G)}(x)=4/5\). The incorrect conclusion would be “\(4/5\) is an eigenvalue.” The computation only shows the quotient for this particular vector. In fact the eigenvalues are \(\sqrt{3},0,0,-\sqrt{3}\), so \(4/5\) is not among them. The corrected interpretation is that \(4/5\) lies between the least and greatest eigenvalues; equality with an extreme would require \(x\) itself to belong to that extreme eigenspace.

Multiplicity also must not be discarded when ordering. Writing the star spectrum as just \(\sqrt{3},0,-\sqrt{3}\) records the distinct values but omits one eigenvalue occurrence. The full ordered list has four entries because the matrix is \(4\) by \(4\). For symmetric adjacency matrices, either the characteristic polynomial or the dimensions of the eigenspaces can be used to verify how many times each value occurs.

Why These Ideas Matter

The ordered spectrum lets us refer unambiguously to the largest value \(\lambda_1\) and least value \(\lambda_n\), while multiplicity records how many independent directions share an eigenvalue. This distinction matters whenever a later calculation uses an extremal eigenvalue or an eigenspace rather than merely a list of distinct numbers. The Rayleigh quotient supplies a practical bridge: a chosen vector gives a numerical bound on the extremes, and an eigenvector gives equality. For graph adjacency matrices, the symmetry that makes this reasoning possible follows directly from undirected adjacency.