$\{0,1\}$-matrix and permutation matrices

Question

A permutation matrix is a square matrix with exactly one $\textbf{1}$ in each row and column, and zeros in all other positions of the matrix. Let $M$ be an $n \times n$ $\{0,1\}$-matrix with exactly $m$ ones in each row and column. Prove that $M$ can be written as the sum of $m$ permutation matrices.

---

I saw my lecturer about this problem and the hint he gave me was to think about decompositions of bipartite graphs into perfect matchings.

For the life of me I don't really understand what he means by that nor do I even know how to get started on the question. Any help would be greatly appreciated.

Answer 1

Here's a proof that a regular bipartite graph has a perfect matching: Show that a finite regular bipartite graph has a perfect matching.

Your matrix corresponds to an $m$-regular bipartite graph in which the rows and the columns form the two vertex classes and the ones determine the edges. A perfect matching is a matching in which every vertex is incident to exactly one edge of the matching. This corresponds to a permutation matrix, and subtracting out this matrix leaves $m-1$ ones in each row and column.

Answer 2

Let $M$ be an $n \times n$ matrix with each row sum and each column sum equal to $m$. We need to show that $M$ is a sum of $m$ permutation matrices. Construct a bipartite graph $G$ on vertex set $X \cup Y$, where $X = \{x_1,\ldots,x_n\}, Y = \{y_1,\ldots,y_n\}$, and with vertex $x_i$ joined to $y_j$ whenever the $ij$th entry of the matrix $M$ is equal to 1. Since each row sum is $m$, each vertex in $X$ has degree $m$, and since each column sum is $m$, each vertex in $Y$ has degree $m$. Thus, the graph $G$ constructed is an $m$-regular bipartite graph. A perfect matching in this graph is defined to be any set of $n$ independent edges. Thus, the 1's in $M$ corresponding to a perfect matching form a permutation matrix. Thus, the problem of expressing $M$ as a sum of $m$ permutation matrices is equivalent to the problem of expressing the edge set of $G$ as the disjoint union of $m$ perfect matchings.

You can show that the graph $G$ satisfies the sufficient condition in Hall's matching/marriage theorem. This proves that $G$ has a perfect matching. Removing this perfect matching from $G$ gives an $(m-1)$-regular bipartite graph, which again satisfies Hall's condition. So you can remove another perfect matching (and hence subtract off another permutation matrix from $M$). You can repeat this process $m$ times.