In a bipartite graph the absolute value of any eigenvalue is less than the square root of number of edges.

Question

Let $G$ be a bipartite graph with $e$ edges. How do we show that the absolute value of any eigenvalue $\lambda$ of $G$ (i.e., the eigenvalue of the adjacency matrix of $G$) is less than or equal to $\sqrt e$.

Any suggestion is appreciated.

Answer 1

Well, note that if your graph has vertex set $V=V_{odd}\cup V_{even}$ and adjacency matrix $A$, then $\mathbb{R}^V=U_{odd}\oplus U_{even},$ where $V_{even}=\textrm{span}\{e_v|v\in V_{odd}\}$ and similarly for $U_{even}$.

Then, for a general vector $x=\sum_{v\in V_{odd}} \alpha_v e_v+\sum_{w\in V_{even}} \beta_we_w$, then we have

$$ Ax=\sum_{v\in V_{odd}}\sum_{w\in V_{even}} A_{v,w} \beta_w e_v+ \sum_{w\in V_{even}}\sum_{v\in V_{odd}} A_{w,v} \alpha_v e_w $$ Thus, we get $$ \|Ax\|^2=\sum_{v\in V_{odd}} \left(\sum_{w\in V_{even}} A_{v,w} \beta_w\right)^2+\sum_{w\in V_{even}} \left(\sum_{v\in V_{odd}} A_{w,v} \alpha_v \right)^2 $$ and for any sequence of numbers $(z_i)_{1\leq i\leq n}$, we see that $$ \left( \sum_{i=1}^n z_i\right)^2=\sum_{i=1}^n z_i^2+\sum_{n\geq j>i\geq 1} 2z_iz_j\leq \sum_{i=1}^n z_i^2+\sum_{n\geq j>i\geq 1} z_i^2+z_j^2\leq n\sum_{i=1}^n z_i^2 $$ Therefore, since every $A_{v,w}$ is either $0$ or $1$, we get that $$ \|A x\|^2\leq \sum_{v\in V_{odd}} |\{w|; A_{v,w}\neq 0\}| \sum_{w\in W_{odd}} \beta_w^2+\sum_{v\in V_{odd}}|\{w|; A_{v,w}\neq 0\}| \sum_{v\in W_{even}} \alpha_v^2 $$ and since, $\sum_{v\in V_{odd}}|\{w|; A_{v,w}\neq 0\}|\leq e$ (and vice versa), we get that $$ \|Ax\|^2\leq e\|x\|^2, $$ which, in particular, implies that the largest eigenvalue of $A$ is at most $\sqrt{e}$.