Spectra of adjacency matrices of bipartite graphs

2.1k Views Asked by At

Let $G$ be a simple graph and $A$ its adjacency matrix. I found this statement on Wikipedia, without a citation:

It can be shown that for each eigenvalue $\lambda_{i}$, its opposite ${\displaystyle -\lambda _{i}=\lambda _{n+1-i}}$ is also an eigenvalue of $A$ if $G$ is a bipartite graph.

Source: https://en.wikipedia.org/wiki/Adjacency_matrix.

Is this statement true? Where can I find a proof?

2

There are 2 best solutions below

5
On BEST ANSWER

A proper indexing gives the adjacency matrix of a bipartite graph, with $n$ elements on one "side" and $p$ elements on the other, the following block form :

$$A=\begin{pmatrix}0&X\\X^T&0\end{pmatrix} \ \text{where} \ X \ \text{is} \ n \times p.$$

Let :

$$B:=A-\lambda I_{n+p}=\begin{pmatrix}-\lambda I_n&X\\X^T&-\lambda I_p\end{pmatrix}.$$

Using Schur's determinant formula (formula (5) in this document):

$$\det(B)=\det(-\lambda I_n)\det(-\lambda I_p-X^T(-\lambda I_n)^{-1}X)$$

$$\det(B)=\det(-\lambda I_n)\det\left(-\lambda I_p-X^T\left(\dfrac{1}{-\lambda}I_n\right)X\right)$$

$$=(-\lambda)^n\det\left[\dfrac{1}{-\lambda} (\lambda^2 I_p-X^TX)\right]$$

$$=(-\lambda)^n \dfrac{1}{(-\lambda)^p}\det[\lambda^2 I_p-X^TX]$$

$$=(-\lambda)^{(n-p)}\det[\lambda^2 I_p-X^TX]\tag{1}$$

which proves that, except the special case $\lambda = 0$, the eigenvalues come by pairs $\lambda$ and $-\lambda$ (your formulation of the result include both cases).

Moreover, the second category of eigenvalues are such that $|\lambda|$ is what is called a singular value of $X$.

Remark : in (1), the first factor brings $n-p$ eigenvalues, the second factor brings $2p$ eigenvalues. Summing : $(n-p)+2p=n+p$... perfect.

Connected : Proof that Laplacian spectrum is symmetric for bipartite graphs

2
On

Let $D$ be the diagonal matrix with $D_{i,i}=1$ if $i$ is in the first colour class and $D_{i,i}=-1$ if it is in the second. Then $DAD=-A$, so $A$ and $-A$ are similar and the spectrum of $A$ must be symmetric about the $y$-axis.