Perron Vectors in Explicit Graphs

Positive Eigenvectors and Spectral Radius

For a connected graph, the adjacency matrix records which vertices are joined, and its largest eigenvalue measures a form of overall adjacency. In several basic graph families, a positive eigenvector can be written down explicitly. For paths its entries vary with position; for cycles, complete graphs and hypercubes, a constant vector suffices. We will compute these vectors and use them to determine the spectral radius.

Throughout, graphs are finite and simple. The adjacency matrix \(\mathbf{A}(G)\) has entry \(1\) in positions \(u,v\) when \(uv\in E(G)\), and entry \(0\) otherwise. An eigenvector is positive if all its entries are strictly greater than zero. The spectral radius \(\rho(G)\) is the maximum of the absolute values of the eigenvalues of \(\mathbf{A}(G)\). Multiplying an eigenvector by any positive constant gives another positive eigenvector for the same eigenvalue.

Proof. Since \(A\) has nonnegative entries and \(x\) has positive entries, each coordinate of \(Ax\) is nonnegative. From \(Ax=\lambda x\), it follows that \(\lambda\ge 0\). Let \(\mu\) be any eigenvalue of \(A\), and let \(y\ne 0\) be a corresponding possibly complex eigenvector. Choose an index \(i\) for which \(|y_i|/x_i\) is largest, and write \(M=|y_i|/x_i\). Since \(y\ne0\), \(M>0\), so \(|y_i|>0\). Using \(Ay=\mu y\), nonnegativity of \(A\), and \(|y_j|\le Mx_j\) for every \(j\), we obtain \[ |\mu||y_i| =\left|\sum_j A_{ij}y_j\right| \le \sum_j A_{ij}|y_j| \le M\sum_j A_{ij}x_j =M\lambda x_i =\lambda|y_i|. \] Dividing by \(|y_i|>0\) gives \(|\mu|\le\lambda\). This holds for every eigenvalue \(\mu\), while \(\lambda\) itself is an eigenvalue. Thus \(\rho(A)=\lambda\). \(\square\)

Applied to an adjacency matrix, the lemma means that once we exhibit a positive vector \(x\) satisfying \(\mathbf{A}(G)x=\lambda x\), we have also identified the spectral radius. This gives a direct way to verify the spectral-radius claims below without needing to calculate every eigenvalue.

Paths: A Sine-Shaped Positive Eigenvector

Proof. The path has edges \(j(j+1)\) for \(1\le j<n\). Set \(x_0=0\) and \(x_{n+1}=0\); these values agree with the sine formula because \(\sin(0)=0\) and \(\sin((n+1)\theta)=\sin(\pi)=0\). For each vertex \(j\), the \(j\)th coordinate of \(\mathbf{A}(P_n)x\) is the sum of the entries at its neighbors, which is \(x_{j-1}+x_{j+1}\), including at the endpoints under these boundary conventions. The sine addition identity gives \[ x_{j-1}+x_{j+1} =\sin((j-1)\theta)+\sin((j+1)\theta) =2\cos(\theta)\sin(j\theta) =2\cos(\theta)x_j. \] For \(1\le j\le n\), we have \(0<j\theta<\pi\), so \(x_j>0\). The lemma now gives \(\rho(P_n)=2\cos(\theta)\). This also covers \(n=1\): then \(\theta=\pi/2\), the vector is \((1)\), and the eigenvalue and spectral radius are both \(0\). \(\square\)

Cycles, Complete Graphs and Hypercubes

For these families, every vertex has the same degree. If \(G\) is \(r\)-regular, then each row of \(\mathbf{A}(G)\) has exactly \(r\) entries equal to \(1\). Therefore the all-ones vector \(\mathbf{1}\) satisfies \(\mathbf{A}(G)\mathbf{1}=r\mathbf{1}\). It is positive, so the lemma proves \(\rho(G)=r\). This argument includes a graph with one vertex and no edges: its degree and spectral radius are both \(0\).

Each vertex of a cycle has two neighbors, giving the cycle result. In \(K_n\), each vertex is adjacent to the other \(n-1\) vertices, giving the complete-graph result. For \(K_1\), the vector has one positive entry and its image under the zero adjacency matrix is zero, so the stated formula remains valid.

The \(d\)-dimensional hypercube \(Q_d\), for \(d\ge0\), has as vertices all binary strings of length \(d\); two strings are adjacent exactly when they differ in one coordinate. For \(d=0\), there is one empty string and no edges. For any \(d\), each vertex has exactly \(d\) neighbors, one for each coordinate that can be changed. Hence \[ \mathbf{A}(Q_d)\mathbf{1}=d\mathbf{1}, \qquad \rho(Q_d)=d. \] The constant vector is positive even in the \(d=0\) case, where the eigenvalue is zero.

How to Use the Formulas

The formulas give a quick choice of positive eigenvector once the graph family is recognized. For \(P_n\), the coordinate at vertex \(j\) depends on its position and is \(\sin(j\pi/(n+1))\), up to positive scaling. For \(C_n\), \(K_n\), and \(Q_d\), every vertex has the same degree, so the all-ones vector works. The resulting spectral radii are summarized here.

These computations illustrate why a positive eigenvector is useful: it identifies the spectral radius, not merely some eigenvalue. A vector with entries of mixed sign may still be an eigenvector, but the lemma does not apply to it. Positivity is the key condition in this method.

Common Pitfall: Maximum Degree Is Not Always the Spectral Radius

For a regular graph, the degree equals the spectral radius because the all-ones vector is a positive eigenvector. It is not valid to assume the same equality for every graph. For example, in the explicitly listed \(P_3\) above, the maximum degree is \(2\), but the calculation gives \(\rho(P_3)=\sqrt2\). The mistaken calculation “\(\rho(P_3)=\Delta(P_3)=2\)” confuses a degree bound with an equality. The path vector verifies the correction directly: \(\mathbf{A}(P_3)(1,\sqrt2,1)^{\mathsf T}=(\sqrt2,2,\sqrt2)^{\mathsf T}=\sqrt2(1,\sqrt2,1)^{\mathsf T}\), and the positive-eigenvector lemma establishes that \(\sqrt2\), not \(2\), is the spectral radius.