The Sign Change Behind Spectral Symmetry
The adjacency matrix records which pairs of vertices are joined by edges. In a bipartite graph, every edge runs between the two parts. If we change the signs of coordinates belonging to one part, each adjacency contribution changes sign. This simple operation has a strong consequence: whenever \(\lambda\) is an adjacency eigenvalue, so is \(-\lambda\). The zero eigenvalue is the only one that need not have a distinct partner.
Throughout, graphs are finite and simple. For a graph \(G=(V,E)\), its adjacency matrix \(\mathbf A(G)\) has entry \(1\) in positions \(u,v\) and \(v,u\) when \(uv\in E\), and entry \(0\) otherwise. An eigenvalue \(\lambda\) of a square matrix \(\mathbf A\) is a scalar for which there is a nonzero vector \(x\) satisfying \(\mathbf A x=\lambda x\). An eigenvector is such a nonzero vector \(x\). We count eigenvalues with their algebraic multiplicities, that is, their multiplicities as roots of the characteristic polynomial.
Order the vertices with the \(p=|X|\) vertices of \(X\) first and the \(q=|Y|\) vertices of \(Y\) second. The adjacency matrix has the block form established for bipartite adjacency matrices:
where \(\mathbf B\) is a \(p\)-by-\(q\) matrix. The zero diagonal blocks express the fact that no edge has both endpoints in the same part. The same fact can be used without block multiplication: assign the number \(+1\) to each vertex in \(X\), and \(-1\) to each vertex in \(Y\). Multiplying a coordinate by its assigned sign is the key operation.
Proof. Let \(s_v=1\) for \(v\in X\) and \(s_v=-1\) for \(v\in Y\). Let \(\mathbf S\) be the diagonal matrix whose diagonal entry at \(v\) is \(s_v\). Since \(s_v^2=1\) for every vertex, \(\mathbf S^2=\mathbf I\), so \(\mathbf S^{-1}=\mathbf S\). For any vertices \(u,v\), the \(u,v\) entry of \(\mathbf S\mathbf A(G)\mathbf S\) is \(s_u\mathbf A(G)_{uv}s_v\). If \(uv\) is an edge, bipartiteness puts its endpoints in different parts, so \(s_us_v=-1\), and this entry is \(-\mathbf A(G)_{uv}\). If \(uv\) is not an edge, then \(\mathbf A(G)_{uv}=0\), and both entries are zero. Thus \(\mathbf S\mathbf A(G)\mathbf S=-\mathbf A(G)\). Because \(\mathbf S^{-1}=\mathbf S\), this is a similarity. Similar matrices have the same characteristic polynomial, hence the same eigenvalues with algebraic multiplicities. The eigenvalues of \(-\mathbf A(G)\) are the negatives of those of \(\mathbf A(G)\): indeed, \(\det(t\mathbf I+\mathbf A(G))=(-1)^n\det((-t)\mathbf I-\mathbf A(G))\), where \(n=|V|\). Therefore the eigenvalues of \(\mathbf A(G)\) and their negatives occur with equal multiplicities. For the graph with no vertices the matrices are empty and the claim is vacuous. \(\square\)
There is also a direct eigenvector explanation. From \(\mathbf S\mathbf A\mathbf S=-\mathbf A\) and \(\mathbf S^2=\mathbf I\), it follows that \(\mathbf A\mathbf S=-\mathbf S\mathbf A\). If \(\mathbf A x=\lambda x\), then \(\mathbf A(\mathbf Sx)=-\lambda(\mathbf Sx)\). Since \(\mathbf S\) is invertible, \(\mathbf Sx\) is nonzero. In fact, this map sends the \(\lambda\)-eigenspace bijectively to the \(-\lambda\)-eigenspace. The real symmetric spectral theorem, a standard result of linear algebra, ensures that the adjacency matrix has a full set of eigenvectors; the similarity argument above also establishes equality of algebraic multiplicities.
Worked Spectral Examples
Worked Example: The Star \(K_{1,3}\)
Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,13,14\}\). Take \(X=\{1\}\), \(Y=\{2,3,4\}\), and order vertices as \(1,2,3,4\). Its adjacency matrix is
For \(\lambda=\sqrt{3}\), the vector \(x=(\sqrt{3},1,1,1)^{\mathsf T}\) satisfies \(\mathbf A x=(3,\sqrt{3},\sqrt{3},\sqrt{3})^{\mathsf T}=\sqrt{3}x\). For \(\lambda=-\sqrt{3}\), take \(y=(\sqrt{3},-1,-1,-1)^{\mathsf T}\). Then \(\mathbf A y=(-3,\sqrt{3},\sqrt{3},\sqrt{3})^{\mathsf T}=-\sqrt{3}y\).
The vectors \(z_1=(0,1,-1,0)^{\mathsf T}\) and \(z_2=(0,1,0,-1)^{\mathsf T}\) each have coordinate sum zero on the leaves, so direct multiplication gives \(\mathbf A z_1=\mathbf A z_2=0\). The four vectors \(x,y,z_1,z_2\) are linearly independent: \(x,y\) are independent and span a space with equal leaf coordinates, while the independent vectors \(z_1,z_2\) have center coordinate zero and leaf coordinates summing to zero. Thus the spectrum, including multiplicities, is \(\sqrt{3},-\sqrt{3},0,0\).
Check: The diagonal entries of \(\mathbf A^2\) are the degrees \(3,1,1,1\), so their sum is \(3+1+1+1=6\). The squared eigenvalues sum to \((\sqrt{3})^2+(-\sqrt{3})^2+0^2+0^2=3+3=6\). The two totals agree; equivalently, \(\operatorname{tr}(\mathbf A^2)=6\).
Worked Example: The Path \(P_4\)
Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\). Its bipartition is \(X=\{1,3\}\), \(Y=\{2,4\}\). In the order \(1,2,3,4\),
To compute its characteristic polynomial, let \(p_k(t)\) be the determinant of \(t\mathbf I-\mathbf A(P_k)\), with \(p_0(t)=1\). Expanding the tridiagonal determinant at an end gives \(p_k(t)=t p_{k-1}(t)-p_{k-2}(t)\): the term using the first diagonal entry contributes \(t p_{k-1}\), and the other nonzero term contributes \(-p_{k-2}\). Therefore \(p_1=t\), \(p_2=t^2-1\), \(p_3=t^3-2t\), and \(p_4=t^4-3t^2+1\).
Setting \(u=t^2\), the equation \(p_4(t)=0\) becomes \(u^2-3u+1=0\). The quadratic formula gives \(u=(3+\sqrt{5})/2\) or \(u=(3-\sqrt{5})/2\), both positive. Hence the four eigenvalues are
Check: The two values of \(u\) sum to \(3\) and multiply to \(1\). Thus the polynomial factors as \((t^2-(3+\sqrt{5})/2)(t^2-(3-\sqrt{5})/2)=t^4-3t^2+1\), the determinant recurrence’s result. Each eigenvalue has its negative partner.
Worked Example: A Disconnected Graph with an Isolated Vertex
Let \(G\) have \(V=\{a,b,c,d\}\) and \(E=\{ab,bc\}\). The vertex \(d\) is isolated. Choose \(X=\{a,c\}\), \(Y=\{b,d\}\), and order the vertices \(a,b,c,d\). Then
For \(\lambda=\sqrt{2}\), \(x=(1,\sqrt{2},1,0)^{\mathsf T}\) gives \(\mathbf A x=(\sqrt{2},2,\sqrt{2},0)^{\mathsf T}=\sqrt{2}x\). For \(\lambda=-\sqrt{2}\), \(y=(1,-\sqrt{2},1,0)^{\mathsf T}\) gives \(\mathbf A y=(-\sqrt{2},2,-\sqrt{2},0)^{\mathsf T}=-\sqrt{2}y\). The vectors \(z_1=(1,0,-1,0)^{\mathsf T}\) and \(z_2=(0,0,0,1)^{\mathsf T}\) satisfy \(\mathbf A z_1=\mathbf A z_2=0\). These four nonzero eigenvectors are independent: the first two have distinct eigenvalues, and the last two are independent vectors in the zero eigenspace. Thus the eigenvalues are \(\sqrt{2},-\sqrt{2},0,0\).
Check: The degrees are \(1,2,1,0\), whose sum is \(4\). The squared eigenvalues sum to \(2+2+0+0=4\). The isolated vertex contributes a zero row and column, accounting for a zero eigenvalue; the other zero eigenvalue comes from the three-vertex path component.
What the Pairing Does—and Does Not—Say
The theorem says that the spectrum is symmetric about zero: positive eigenvalues are balanced by negative eigenvalues of equal multiplicity. It does not say that every eigenvalue is nonzero or that the zero eigenvalue has even multiplicity. In the star example, zero has multiplicity two; in a graph with an isolated vertex, zero is necessarily an eigenvalue because the corresponding column of the adjacency matrix is zero. More generally, the sign-change proof pairs the \(\lambda\)- and \(-\lambda\)-eigenspaces, while the zero eigenspace maps to itself.
The result applies to disconnected bipartite graphs as well. Each edge still crosses the chosen parts, and the sign matrix is defined on all vertices at once. Isolated vertices cause no problem: their rows and columns are zero, and the sign assigned to such a vertex does not affect the matrix identity. If one part is empty, there can be no edges, \(\mathbf A=\mathbf 0\), and the identity \(\mathbf S\mathbf A\mathbf S=-\mathbf A\) still holds.
Common Pitfall
Changing signs does not automatically negate every adjacency matrix. The crucial condition is that each edge joins vertices with opposite signs. For a concrete failure, take the triangle with \(V=\{1,2,3\}\), \(E=\{12,23,13\}\), and assign signs \(s_1=s_2=1\), \(s_3=-1\). The edge \(12\) has endpoints with the same sign, so the \(1,2\) entry of \(\mathbf S\mathbf A\mathbf S\) is \(1\), not \(-1\). Thus \(\mathbf S\mathbf A\mathbf S\ne-\mathbf A\). A sign choice proves spectral symmetry only when it assigns opposite signs across every edge, which is exactly what a bipartition provides.
A related computational mistake is to confuse the diagonal entries of \(\mathbf A^2\) with squared degrees. For a simple graph, \((\mathbf A^2)_{vv}=\deg(v)\): it counts the length-two walks from \(v\) back to itself, one for each neighbor. In the star calculation, these entries are \(3,1,1,1\), not \(3^2,1^2,1^2,1^2\). Checking traces or squared eigenvalues requires using the former values.
Check Your Understanding
Use the sign-matrix argument and the computations above to answer these questions.
- For a bipartition \(X,Y\), what diagonal entries should the matrix \(\mathbf S\) have, and why does \(\mathbf S^{-1}=\mathbf S\)?
- Starting from \(\mathbf A x=\lambda x\), derive directly that \(\mathbf Sx\) is an eigenvector for \(-\lambda\).
- Why does an isolated vertex not prevent the identity \(\mathbf S\mathbf A\mathbf S=-\mathbf A\) from holding?
- For the star \(K_{1,3}\), verify by multiplication that \((0,1,-1,0)^{\mathsf T}\) is a zero eigenvector.
- In the triangle example, identify the edge whose endpoints receive the same sign and explain why its adjacency entry does not change sign.