Bipartite Graphs and the Extremal Perron Eigenvalue

Why Bipartite Graphs Have Symmetric Spectra

The adjacency matrix records which pairs of vertices are joined by edges. In a bipartite graph, every edge runs between the two parts, so changing the sign of the coordinates in one part reverses the sign of the adjacency action. This simple operation has a strong consequence: each eigenvalue is paired with its negative. For a connected graph, the Perron–Frobenius theorem identifies the largest eigenvalue as the spectral radius; the pairing then forces its negative to be an eigenvalue as well.

Throughout, graphs are finite and simple. For \(G=(V,E)\), the adjacency matrix \(\mathbf A(G)\) has rows and columns indexed by \(V\), with entry \(1\) when the corresponding vertices are adjacent and \(0\) otherwise. It is a real symmetric matrix, so the real symmetric spectral theorem implies that its eigenvalues are real and that algebraic and geometric multiplicities agree. The spectral radius is the largest absolute value of an eigenvalue.

Order the vertices with those in \(X\) first and those in \(Y\) second. Since there are no edges within either part, the adjacency matrix has block form

where \(\mathbf B\) records the edges from \(X\) to \(Y\), and \(\mathbf B^T\) is its transpose. The zero blocks express the absence of edges within \(X\) or within \(Y\). The argument below works whether or not the graph is connected, and it allows isolated vertices.

The Sign-Change Argument

Let \(S\) be the diagonal matrix with diagonal entry \(1\) for a vertex in \(X\) and \(-1\) for a vertex in \(Y\). Then \(S^2=I\). For an adjacency-matrix entry \(A_{uv}\), the corresponding entry of \(S\mathbf A S\) is \(s_u A_{uv}s_v\). If \(uv\) is an edge, its endpoints lie in opposite parts, so \(s_us_v=-1\); if \(uv\) is not an edge, \(A_{uv}=0\). Thus every entry gives the identity

This identity has two useful interpretations. First, if \(\mathbf A x=\lambda x\), then \(\mathbf A(Sx)=-\lambda(Sx)\): multiplying the matrix identity by \(S\) gives \(\mathbf A S=-S\mathbf A\), and hence \(\mathbf A(Sx)=-S(\mathbf A x)=-\lambda Sx\). Since \(S\) is invertible, \(Sx\) is nonzero whenever \(x\) is nonzero. Second, the transformation \(x\mapsto Sx\) is its own inverse, so it gives a bijection between the eigenspaces for \(\lambda\) and \(-\lambda\).

Proof. Let \(n=|V|\), let \(p(t)=\det(tI-\mathbf A)\), and use the matrix \(S\) defined from a bipartition. The identity \(S\mathbf A S=-\mathbf A\) shows that \(\mathbf A\) and \(-\mathbf A\) are similar, because \(S^{-1}=S\). Similar matrices have the same characteristic polynomial. The characteristic polynomial of \(-\mathbf A\) is \(\det(tI+\mathbf A)=(-1)^n p(-t)\), so \(p(t)=(-1)^n p(-t)\). Therefore a root \(\lambda\) of \(p\) has the same multiplicity as the root \(-\lambda\): replacing \(t\) by \(-t\) preserves the order of a root, and the factor \((-1)^n\) is nonzero. The eigenspace bijection \(x\mapsto Sx\) gives the same conclusion for geometric multiplicities; in particular, the result is consistent with the real symmetric spectral theorem. \(\square\)

The Extreme Eigenvalues in a Connected Graph

For a connected graph with at least two vertices, its adjacency matrix is a nonnegative irreducible matrix: connectivity means no nonempty proper set of vertices is isolated from its complement, which is the irreducibility condition for this matrix. The Perron–Frobenius theorem for connected graphs, established in the earlier material on that theorem, says that the spectral radius \(\rho\) is a positive eigenvalue of algebraic multiplicity one. Bipartite spectral symmetry now gives the negative extreme eigenvalue.

Proof. The Perron–Frobenius theorem gives \(\rho>0\) as an eigenvalue of multiplicity one. Applying the bipartite spectral symmetry theorem with \(\lambda=\rho\) shows that \(-\rho\) is an eigenvalue with the same algebraic multiplicity, namely one. Since \(\rho\) is the largest absolute value of any eigenvalue, \(-\rho\) is the negative extreme eigenvalue. If \(G\) has just one vertex, then \(\mathbf A=[0]\), so \(\rho=0=-\rho\) and this one eigenvalue has multiplicity one. \(\square\)

The sign change also describes the eigenvectors directly. If \(x\) is a Perron eigenvector for a connected bipartite graph, then \(Sx\) is an eigenvector for \(-\rho\): its coordinates on one part retain their signs, while those on the other part change sign. This does not mean that the negative eigenvector is a second Perron eigenvector; it belongs to a different eigenvalue.

Why the Sign Matrix Must Match the Parts

The spectral pairing is a consequence of the edge pattern, not merely of having a matrix with many zero entries. The sign matrix must assign opposite signs to the endpoints of every edge. If a graph is disconnected, each component can still be assigned bipartition signs, and the same proof applies to the whole graph. Isolated vertices cause no difficulty: their adjacency-matrix rows and columns are zero, so they impose no sign constraint.

Common mistake: For the path with edges \(12\) and \(23\), assigning signs \(s_1=1,s_2=1,s_3=-1\) does not encode its bipartition. The transformed entry on edge \(12\) is \(s_1A_{12}s_2=1\cdot1\cdot1=1\), not \(-1\). Thus this choice cannot prove \(S\mathbf A S=-\mathbf A\). The correct parts are \(\{1,3\}\) and \(\{2\}\), giving \(S=\operatorname{diag}(1,-1,1)\); now both edge entries change sign, as required. Always check the signs at the two ends of each edge before using the similarity argument.

Another distinction is between the general pairing theorem and the connected-graph corollary. Bipartiteness alone guarantees that eigenvalues occur in opposite pairs, including equality of their multiplicities. Connectedness is used when Perron–Frobenius identifies a simple positive eigenvalue at the spectral radius. Without that hypothesis, a graph may have several components contributing the same extreme eigenvalue, so simplicity is not guaranteed, even though the positive and negative extreme multiplicities still agree for a bipartite graph.