Characterizing sums of permutation matrices Given an $n$ by $n$ matrix $A$ whose rows and columns sum to $m \in \mathbb N$ and entries are nonnegative integers, does there exist a permutation matrix $P$ such that $A - P$ has only nonnegative entries?
If this is true, then we can write $A$ as the sum of $m$ permutation matrices, and I'll have a good Thanksgiving.
 A: If we can find a permutation $\sigma$ such that $A_{i,\sigma(i)} \neq 0$, for every $1 \leq i \leq n$, then we are done, because the associated permutation matrix will satisfy what you want.
So we consider the following bipartite graph $G$ on $X \sqcup Y$, $X = Y = \{1,\ldots,n\}$, and we set $i \sim j$ if and only if $A_{i,j} \neq 0$. Any perfect matching on $G$ will give us the desired permutation, so lets check that we can satisfy Hall's condition in this graph.
Let $I \subseteq X$, and we have that $N(I) = \{j : \exists i \in I, i \sim j \}$. First notice that for any $i$ by definition of $A$ and construction of $G$ we have that $$\sum_{i \sim j}A_{i,j} = m$$ So we have the following
$$\begin{align}
|I| &= \frac{1}{m} \sum_{i \in I} \sum_{j \in N(I)} A_{i,j}\\
&= \frac{1}{m} \sum_{j \in N(I)} \sum_{i \in I} A_{i,j} \quad \text{(We switched sumation order)} \\
&\leq \frac{1}{m} \sum_{j \in N(I)} \sum_{i \in X} A_{i,j} \quad \text{(We sum over all $X$, which is $m$)}\\
&= \frac{1}{m}m|N(I)| = |N(I)|
\end{align}$$
Which is exactly Hall's condition, so $G$ has a perfect matching which gives us the permutation as we wanted.
A: By Birkhoff–von Neumann theorem, every doubly stochastic matrix is a convex combination of permutation matrices. Therefore $\frac1mA=\sum_{k=1}^r c_kP_k$ for some permutation matrices $P_1,P_2,\ldots,P_r$ and some $c_1,c_2,\ldots,c_n>0$. Hence $A\ge mc_1P_1$ entrywise. As $A$ is an integer matrix, it follows that $A\ge P_1$ entrywise, i.e. $A-P_1$ is entrywise nonnegative.
