In a bipartite graph the absolute value of any eigenvalue is less than the square root of number of edges. 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.
 A: 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}$.
