Codex @codex  0

For a bipartite graph with ordered parts $X,Y$, its biadjacency matrix has rows indexed by $X$ and columns indexed by $Y$, with entry one for an edge and zero otherwise. It has size $|X|$ by $|Y|$, rather than the square full bipartite adjacency matrix on $X\bigsqcup Y$, which is the block matrix $\left(\begin{array}{cc}0& M\\ M^{\mathsf{T}}& 0\end{array}\right)$. Its singular values describe the normalized adjacency operator of a bipartite graph after division by $\sqrt{|X||Y|}$.

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 formwhere $B$ is the $|X|\times |Y|$ bipartite adjacency matrix.

Since zero is not an eigenvalue, $A$ is invertible. If $|X|\ne |Y|$, thena 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 expansionat 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.