Prove that a matrix can be written as a sum of permutation matrices 
Given a square matrix $A$ of size $n$ whose entries are non-negative integers and where the sum of each column and row is equal to $k$, prove that $A$ can be written as a sum of $k$ permutation matrices.


First, it is obvious to see that a sum o $k$ permutation matrices will result in a matrix where the rows and columns sums to $k$. By Birkhoff's theorem, any doubly stochastic matrix can be written as a linear combination of permutation matrices,
$$\frac{1}{k}A = \sum_{i=1}^{r}{c_i P_i}$$
$$A = k \left(\sum_{i=1}^{r}{c_i P_i}\right)$$
where $c_i > 0$ is a real coefficient and $P_i$ is a permutation matrix. However, my solution can have more than $k$ permutation matrices (because the $c_i$ can be less than $1$) and each one with a real coefficient and question asks for just a sum of $k$ permutation matrices (so $c_i = 1$).

Some related questions that guided me:

*

*Characterizing sums of permutation matrices


*Is it possible to solve for values in a matrix such that all rows and columns have equal sum?


*Prove the existence of a permutation for a matrix

You can use induction on $k$. The base case $k=1$ is clear. If $k>1$, then by Birkhoff's theorem you cited (or by Hall's marriage lemma), there is some permutation matrix  $P$
so that $P_{ij}>0$ implies $A_{ij}>0$  (any $P$ that is part of the Birkhoff decomposition of $A/k$ will do.) For this $P$, the $n \times n$ matrix  $A-P$ has  non-negative integer entries, and the sum of each column and row of $A-P$ is equal to $k-1$.By the inductive hypothesis,
$A-P$ can be written as a sum of $k-1$ permutation matrices, whence $A$
can be written as a sum of $k$ permutation matrices.
