Let $G$ be a bipartite biregular graph. That is, $G$ is a bipartite graph with vertex sets $V_1$ and $V_2$ such that every vertex in $V_1$ has degree $d_1$ and every vertex in $V_2$ has degree $d_2$. The adjacency matrix of $G$ is a block matrix in the form $A = \begin{bmatrix} 0 & X \\ X^T & 0 \end{bmatrix}$ for some $m \times n$ matrix $X$ where $|V_1| = m$ and $|V_2| = n$. I have seen the claim that $\sqrt{d_1 d_2}$ is the largest eigenvalue of $A$. It's clear to me that $\sqrt{d_1 d_2}$ is an eigenvalue of $A$ since it is a singular value of $X$, but I have two questions about this.
- How do I show that $\sqrt{d_1 d_2}$ is the largest eigenvalue of $A$?
- What is an eigenvector with eigenvalue $\sqrt{d_1 d_2}$?
Best Answer
The simplest way to find an eigenvector in this case is to make some assumptions about what an eigenvector should look like, which will also allow us to find the eigenvalues.
Let $G$ be a bipartite, biregular graph with partition $V_1, V_2$, $c$ the degree of each vertex in $V_1$, and $d$ the degree of each vertex in $V_2$. The adjacency matrix of this graph has the block form $$ A = \begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix} $$ for some $m \times n$ matrix $B$. The equality $\mathbf d = A \mathbf 1$ for the degree vector implies $B \mathbf 1 = c \mathbf 1$ and $B^T \mathbf 1 = d \mathbf 1$. Now, we make our guess. Suppose that there exist real numbers $k, \ell$ such that $\mathbf x = (k \mathbf 1, \ell \mathbf 1)$ is an eigenvector of $A$. Multiplying by $A$, we have $$ \begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix} \begin{pmatrix} k \mathbf 1 \\ \ell \mathbf 1 \end{pmatrix} = \begin{pmatrix} \ell (B \mathbf 1) \\ k (B^T \mathbf 1) \end{pmatrix} = \begin{pmatrix} c \ell \mathbf 1 \\ dk \mathbf 1 \end{pmatrix} $$ and the above is an eigenvector for $\lambda$ satisfying the (nonlinear) system $$\begin{align*} k \lambda &= c \ell \\ \ell \lambda &= dk. \end{align*}$$ Rearranging, $k = c\ell/\lambda$ and $\lambda^2 = cd$, from which we derive $\lambda = \pm \sqrt{cd}$. Substituting back into the system allows us to solve for $k$ and $\ell$.
The fact that $\lambda = \sqrt{cd}$ is the largest eigenvalue of our adjacency matrix follows from the Perron-Frobenius theorem, which states that an eigenvalue of largest modulus for an irreducible matrix corresponds to the eigenvector with nonnegative entries. By the previous argument, the eigenvector of $\sqrt{cd}$ is strictly positive and as such $\rho(A) = \sqrt{cd}$.