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.
Best Answer
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.