= Solution
The eigenvalues of a graph are the eigenvalues of its adjacency matrix. Order the vertices with those of $X$ first and those of $Y$ second. The adjacency matrix then has block form
$$
A=\begin{pmatrix}0&B\\B^T&0\end{pmatrix},
$$
where $B$ is the $|X|\times|Y|$ <bipartite adjacency matrix>.
Since zero is not an eigenvalue, $A$ is invertible. If $|X|\ne|Y|$, then
$$
\operatorname{rank}A\leq2\min(|X|,|Y|)<|X|+|Y|,
$$
a contradiction. Thus $|X|=|Y|=r$. Moreover, if $B$ were singular, a nonzero $v$ with $Bv=0$ would give $A(0,v)^T=0$. Hence $B$ is invertible.
In the determinant expansion
$$
\det B=\sum_{\pi\in S_r}\operatorname{sgn}(\pi)
\prod_{i=1}^r B_{i,\pi(i)},
$$
at least one product is nonzero. For its permutation $\pi$, all entries $B_{i,\pi(i)}$ equal one, so the corresponding $r$ edges pair every vertex of $X$ with a distinct vertex of $Y$. They form the required matching.
Back to article page
