Perron-Frobenius Theorem for Connected Graphs

The Perron Eigenvalue of a Connected Graph

The adjacency matrix of a graph records which pairs of vertices are joined by edges. When the graph is connected, that pattern of nonzero entries links the whole matrix together. The Perron–Frobenius theorem predicts a strong consequence: the spectral radius is an eigenvalue with a strictly positive eigenvector, and that eigenvalue is simple. For an undirected graph, these conclusions can be proved directly using the spectral theorem, a Rayleigh-quotient argument, and connectedness.

Throughout, \(G=(V,E)\) is a finite, simple, undirected, nonempty graph. Its adjacency matrix \(\mathbf A=\mathbf A(G)\) has entry \(A_{uv}=1\) when \(uv\in E\) and \(A_{uv}=0\) otherwise. A vector is strictly positive if every coordinate is greater than zero; it is nonnegative if every coordinate is at least zero. The spectral radius \(\rho(\mathbf A)\) is the maximum of the absolute values of the eigenvalues of \(\mathbf A\). An eigenvalue is simple if its algebraic multiplicity is one.

For this tutorial we need no result about general, possibly nonsymmetric, irreducible matrices. The nonnegative-matrix fact used in the proof is the entrywise inequality that, for a symmetric matrix \(A\) with nonnegative entries and any real vector \(z\), the quadratic form of the coordinatewise absolute-value vector satisfies \( |z|^{T}A|z|\geq |z^{T}Az| \). The spectral theorem then supplies the eigenvalue and maximizing properties needed below.

The Variational Fact Behind the Proof

Because \(\mathbf A\) is real and symmetric, the spectral theorem gives an orthonormal basis of real eigenvectors and real eigenvalues. Write \(\lambda_{\max}\) for its largest eigenvalue. For every nonzero real vector \(z\), its Rayleigh quotient satisfies \(\frac{z^T\mathbf A z}{z^Tz}\leq\lambda_{\max}\), with equality exactly when \(z\) is an eigenvector for \(\lambda_{\max}\). To see this, expand \(z\) in an orthonormal eigenbasis: the quotient is a weighted average of the eigenvalues, with nonnegative weights summing to one. It reaches the largest eigenvalue exactly when all nonzero weights belong to eigenvectors for that eigenvalue.

For a graph adjacency matrix, the quadratic form has the useful explicit expression \(\displaystyle z^T\mathbf A z=2\sum_{uv\in E}z_uz_v\). Consequently, \(\displaystyle |z^T\mathbf A z|\leq 2\sum_{uv\in E}|z_u||z_v|=|z|^T\mathbf A|z|\). The sum is over the unordered edges, so each edge contributes twice to the matrix quadratic form.

Proof. First suppose \(G\) has at least two vertices. Since it is connected, it has an edge \(uv\). The vector that is \(1\) at \(u,v\) and \(0\) elsewhere has Rayleigh quotient \(1\), because its squared norm is \(2\) and its quadratic form is \(2\). Hence \(\lambda_{\max}\geq 1\). Choose a unit eigenvector \(z\) for \(\lambda_{\max}\). The inequality above gives \(|z|^T\mathbf A|z|\geq |z^T\mathbf A z|=\lambda_{\max}\). The vector \(|z|\) has unit norm, so its Rayleigh quotient cannot exceed \(\lambda_{\max}\). Equality follows, and the variational fact shows that \(|z|\) is an eigenvector for \(\lambda_{\max}\). Set \(x=|z|\), so \(x\) is nonnegative, nonzero, and satisfies \(\mathbf A x=\lambda_{\max}x\).

We show that \(x\) is strictly positive. If \(x_v=0\) at some vertex \(v\), the eigenvector equation at \(v\) gives \(\lambda_{\max}x_v=\sum_{w\in N(v)}x_w\), hence \(\sum_{w\in N(v)}x_w=0\). Each term is nonnegative, so every neighbor of \(v\) also has coordinate zero. Repeating this along paths forces every coordinate to be zero, since \(G\) is connected. That contradicts \(x\neq 0\); therefore \(x_v>0\) for every vertex.

Next we identify \(\lambda_{\max}\) as the spectral radius. Let \(\mu\) be any eigenvalue and let \(y\) be a corresponding unit eigenvector. Then \(|\mu|=|y^T\mathbf A y|\leq |y|^T\mathbf A|y|\leq\lambda_{\max}\), where the last inequality is the maximum-Rayleigh-quotient property. Thus every eigenvalue has absolute value at most \(\lambda_{\max}\). Since \(\lambda_{\max}\geq1\) is itself an eigenvalue, \(\rho(\mathbf A)=\lambda_{\max}\).

Finally, suppose the eigenspace for \(\lambda_{\max}\) had dimension greater than one. Then it would contain a nonzero vector \(y\) orthogonal to \(x\). Because every coordinate of \(x\) is positive, \(x^Ty=0\) implies that \(y\) has both a positive and a negative coordinate. Also \(y^T\mathbf A y=\lambda_{\max}y^Ty\), so the same inequalities as above show that \(|y|\) attains the maximum Rayleigh quotient. It is therefore a nonnegative eigenvector for \(\lambda_{\max}\), and the positivity argument already given shows that \(|y|\) has no zero coordinate.

Equality must hold in \(|y|^T\mathbf A|y|\geq y^T\mathbf A y\). The difference is \(2\sum_{uv\in E}(|y_u||y_v|-y_uy_v)\). Each summand is nonnegative, so equality means no edge joins coordinates of opposite signs. Since \(G\) is connected and \(y\) has no zero coordinates, all coordinates of \(y\) must have the same sign. This contradicts \(x^Ty=0\), which required both signs. The eigenspace is therefore one-dimensional. A real symmetric matrix is diagonalizable, so the algebraic multiplicity equals the eigenspace dimension; hence \(\lambda_{\max}=\rho(\mathbf A)\) is simple.

If \(G\) has one vertex, its adjacency matrix is \([0]\), its spectral radius is \(0\), and the vector \([1]\) is a strictly positive eigenvector. The sole eigenvalue has multiplicity one. This proves the theorem in all cases. \(\square\)

Worked Examples

Why the Hypotheses Matter

Nonnegativity and symmetry play distinct roles in the proof. Nonnegative entries make replacing a vector by its coordinatewise absolute value increase the quadratic form; symmetry gives a real eigenbasis and the maximum-Rayleigh-quotient characterization. Connectedness then propagates a zero coordinate to all vertices and prevents a top eigenvector from splitting into sign-separated parts.

Common pitfall: dropping connectedness. Let \(V=\{1,2,3\}\) and \(E=\{12\}\). This graph is disconnected, and its adjacency matrix is \(\begin{pmatrix}0&1&0\\1&0&0\\0&0&0\end{pmatrix}\). Its eigenvalues are \(1,-1,0\), so its spectral radius is \(1\). The vector \((1,1,0)^T\) is an eigenvector for \(1\), but it is not strictly positive. In fact, every eigenvector for \(1\) has third coordinate zero. The nonnegative-matrix conclusion about a strictly positive eigenvector requires irreducibility, which fails here.

The result is useful because it singles out a canonical eigenvalue and eigenvector for every connected undirected graph. The positive eigenvector has no sign ambiguity except for scaling: its positive multiples are positive, while its negative multiples are negative. The simplicity conclusion means the eigenspace is one-dimensional, so there is no second independent eigenvector for the spectral radius.