Let $n \ge 1$ be a positive integer. An $n \times n$ matrix is called good if each entry is a non-negative integer, the sum of entries in each row and each column is equal. A permutation matrix is an $n \times n$ matrix consisting of $n$ ones and $n(n-1)$ zeroes such that each row and each column has exactly one non-zero entry. Prove that any good matrix is a sum of finitely many permutation matrices.
Problem
Source: India TST 2017 D1 P3
Tags: linear algebra, matrix, combinatorics
utkarshgupta
09.12.2017 18:30
Characterizing Sums of Permutation Matrices
anantmudgal09
09.12.2017 22:35
Suppose $m \ge 1$ is the common sum. Induct on $m$; for $m=1$ we have precisely a permutation matrix. Consider a bipartite multigraph $\mathcal{G}$ with vertices as the rows and the columns. Each row and column are connected by as many edges as the number written at their junction. Claim. It is possible to select a perfect matching. (Proof) Suppose we pick $1 \le k \le m$ rows. Each vertex of $\mathcal{G}$ has degree $m$ hence we have a total of $km$ edges emanating through at least one of them. Now each vertex among the columns can consume at most $m$ of these edges. Hence the total number of columns which share an edge with one of these rows is at least $ \left \lfloor {\frac{km}{m}} \right \rfloor=k$. Hall's condition is met, hence we can pick a matching. $\blacksquare$ Remove each edge of this matching and apply induction hypothesis from the $(m-1)$ case. Thus, we obtain the desired representation.