Eigenvalue of adjacency matrix of a bipartite graph Why if $m$ is an eigenvalue of the adjacency matrix of bipartite graph on $n$ vertices then $-m$ is an eigenvalue? 
Can you prove this?  
 A: Let $G$ be a bipartite graph, with $P$ and $Q$ the corresponding partition of vertices (i.e. so that all edges cross from $P$ to $Q$).  Define $p = |P|, q = |Q|$.  Then since $G$ is bipartite, its adjacency matrix is of the form $$M = \left(\begin{array}{c|c} O_p & A \\ \hline
A^T & O_q  \end{array} \right),$$
for some $A$, where $O_p$ and $O_q$ are the zero matrices of corresponding size.  Suppose $m$ is an eigenvalue of $M$ with corresponding eigenvector $(x_1,x_2)^T$, where $x_1$ and $x_2$ are the $P$ and $Q$ components.  Then note that $$M\left( \begin{array}{c} x_1 \\ x_2\end{array}\right) = \left( \begin{array}{c} Ax_2 \\ A^tx_1\end{array}\right) = \left( \begin{array}{c} mx_1 \\ mx_2\end{array}\right) = m\left( \begin{array}{c} x_1 \\ x_2\end{array}\right),$$
since $(x_1,x_2)^T$ is an eigenvector corresponding to $m$.  Now, note $$M\left( \begin{array}{c} -x_1 \\ x_2\end{array}\right) = \left( \begin{array}{c} Ax_2 \\ -A^Tx_1\end{array}\right) = \left( \begin{array}{c} mx_1 \\ -mx_2\end{array}\right)  = -m \left( \begin{array}{c} -x_1 \\ x_2\end{array}\right).$$
Thus $-m$ is an eigenvalue with corresponding eigenvector $(-x_1,x_2)^T$.
