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:
