Spectral Radius of a Graph

From a Graph to a Matrix

A graph's adjacency matrix translates its connections into a symmetric matrix. The eigenvalues of this matrix summarize structural information in a way that is often useful for comparing graphs. This tutorial develops one such quantity, the spectral radius, and shows how the Rayleigh quotient helps compute it.

Throughout, graphs are finite and simple: they have no loops or multiple edges. For a graph \(G\) with vertices ordered as \(v_1,\dots,v_n\), its adjacency matrix has one row and column for each vertex. The entry in row \(i\), column \(j\) records whether those two vertices are adjacent.

An eigenvalue of a square matrix \(\mathbf A\) is a number \(\lambda\) for which \(\mathbf A x=\lambda x\) for some nonzero vector \(x\). The eigenvalues of a real symmetric matrix are real. We use the standard real spectral theorem from linear algebra: every real symmetric matrix has an orthonormal basis of eigenvectors. The theorem's proof is a linear-algebra result and is not reproduced here.

For a graph with at least one vertex, the adjacency matrix is symmetric, so all of its eigenvalues are real. The spectral radius is therefore the maximum of their absolute values. It is not, in general, the maximum degree: eigenvalues depend on how the edges are arranged throughout the graph, not just on the largest number of neighbors at one vertex.

The Rayleigh Quotient

The denominator is the squared length of \(x\), so it is positive whenever \(x\ne0\). The quotient is unchanged if \(x\) is multiplied by a nonzero scalar. It measures the value of the matrix quadratic form relative to the size of the vector.

Proof. By the real spectral theorem, choose an orthonormal eigenbasis \(u_1,\dots,u_n\) for \(\mathbf A\), with corresponding eigenvalues \(\lambda_1,\dots,\lambda_n\). Write any nonzero \(x\) as \(x=\sum_{i=1}^n c_i u_i\). Orthonormality gives \(x^{\mathsf T}x=\sum_{i=1}^n c_i^2\), while \(\mathbf A u_i=\lambda_i u_i\) gives \(x^{\mathsf T}\mathbf A x=\sum_{i=1}^n\lambda_i c_i^2\). Thus \(R_{\mathbf A}(x)=\dfrac{\sum_i\lambda_i c_i^2}{\sum_i c_i^2}\), a weighted average of the eigenvalues, with nonnegative weights \(c_i^2\). It lies between the smallest and largest eigenvalues. Taking \(x\) to be an eigenvector for the largest eigenvalue attains the upper endpoint; an eigenvector for the smallest attains the lower endpoint. This also covers the zero matrix and one-dimensional matrices, since they have eigenvectors and the same argument applies. \(\square\)

For adjacency matrices there is a useful extra fact: the largest eigenvalue is already the spectral radius, so no separate search for a large negative eigenvalue is needed.

Proof. Let \(\lambda_{\max}\) be the largest eigenvalue of \(\mathbf A(G)\). The Rayleigh quotient theorem gives \(\lambda_{\max}=\max_{x\ne0}R_{\mathbf A(G)}(x)\). Since each diagonal entry of \(\mathbf A(G)\) is zero, a vector that is \(1\) at one coordinate and \(0\) elsewhere has quotient \(0\). Therefore \(\lambda_{\max}\ge0\). For any real vector \(x\), let \(|x|\) be the vector whose coordinates are the absolute values of those of \(x\). The adjacency matrix has nonnegative entries, so \[ |x^{\mathsf T}\mathbf A(G)x| \le |x|^{\mathsf T}\mathbf A(G)|x| \le \lambda_{\max}|x|^{\mathsf T}|x| =\lambda_{\max}x^{\mathsf T}x. \] The second inequality follows from the maximum property of the Rayleigh quotient; if \(x\ne0\), then \(|x|\ne0\). Now take \(x\) to be any nonzero eigenvector with eigenvalue \(\lambda\). Dividing the inequality by \(x^{\mathsf T}x>0\) gives \(|\lambda|\le\lambda_{\max}\). Since \(\lambda_{\max}\) is itself an eigenvalue and is nonnegative, it follows that the largest absolute eigenvalue is \(\lambda_{\max}\). Hence \(\rho(G)=\lambda_{\max}\). \(\square\)

This proposition makes the Rayleigh quotient especially convenient for graphs: maximizing \(x^{\mathsf T}\mathbf A(G)x/(x^{\mathsf T}x)\) gives the spectral radius itself.

Complete Graphs

In a complete graph \(K_n\), every pair of distinct vertices is adjacent. Its adjacency matrix is the \(n\times n\) matrix with zeros on the diagonal and ones everywhere else. The vector with all coordinates equal to \(1\) is an eigenvector: each row sums to \(n-1\), so its eigenvalue is \(n-1\). The other eigenvalues can be found from vectors whose coordinates sum to zero. This gives a compact formula for the spectral radius.

Proof. When \(n=1\), the adjacency matrix is \([0]\), so its only eigenvalue is \(0=n-1\). Now let \(n\ge2\), and let \(\mathbf 1\) be the vector of \(n\) ones. Every coordinate of \(\mathbf A(K_n)\mathbf 1\) is \(n-1\), so \(\mathbf 1\) is an eigenvector with eigenvalue \(n-1\). If \(x\) has coordinate sum zero, then in row \(i\) the product \((\mathbf A(K_n)x)_i\) is the sum of all coordinates of \(x\) except \(x_i\). That sum is \(-x_i\), so \(\mathbf A(K_n)x=-x\). The subspace of vectors with coordinate sum zero has dimension \(n-1\), and together with \(\mathbf 1\) it accounts for all \(n\) dimensions. Thus the eigenvalues are \(n-1\) once and \(-1\) with multiplicity \(n-1\). For \(n\ge2\), \(n-1\ge1\), so the largest absolute value is \(n-1\). The \(n=1\) case was already checked. \(\square\)

Small Paths

For a path, the adjacency matrix has a \(1\) just above and below the main diagonal wherever consecutive vertices are adjacent, and zeroes elsewhere. Small characteristic polynomials can be computed directly. The roots of \(\det(\lambda I-\mathbf A)\) are the eigenvalues; taking the largest absolute value gives the spectral radius.

Common Pitfall: Maximum Degree Is Not the Spectral Radius

A tempting shortcut is to identify the spectral radius with the maximum degree. The \(P_3\) calculation shows why this is wrong. Its degrees are \(1,2,1\), so its maximum degree is \(2\), but its spectral radius is \(\sqrt2\), not \(2\). Indeed, \(2\ne\sqrt2\) because their squares are \(4\) and \(2\), respectively.

The Rayleigh quotient does provide a systematic way to find the largest eigenvalue, but an arbitrary test vector need not attain the maximum. For example, for the same path, \(x=(1,0,0)^{\mathsf T}\) has quotient \(0/1=0\), not \(\rho(P_3)\). The theorem guarantees that the maximum over all nonzero vectors is the largest eigenvalue; it does not say every quotient equals that maximum. For adjacency matrices, the proposition above then identifies this largest eigenvalue with the spectral radius.

Finally, an edgeless graph with at least one vertex has the zero adjacency matrix, so every eigenvalue and its spectral radius are zero. The empty graph also has spectral radius zero by the convention stated earlier. These cases are useful reminders that a spectral radius need not be positive.