# 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.

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.
By Birkhoff–von Neumann theorem, every doubly stoahastic 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.
• In this case, if a doubly stochastic matrix $A$ is not a scalar multiple of permutation matrix, one can show that there is a closed walk between some $m\le n$ nodes and hence $A\pm\epsilon B$ is doubly stochastic for some nonzero matrix $B$ and for all small $\epsilon$. Such an argument does not rely on the existence of a positive diagonal. – user1551 Nov 29 '13 at 1:36
• How do we know that $mc_j$ is an integer? Isn't it possible that $\{mc_1,\ldots, mc_r\} \cap \mathbb Z = \emptyset$? Does this matter? I think it does because if $0<|mc_j|<1$ then doesn't that mean that $A \geq P_j$ entrywise is false? – user28877 Nov 29 '13 at 19:36
• @user710587 No one says that $mc_1$ is an integer. It is merely positive. However, since $A\ge mc_1P_1$ entrywise, if the $(i,j)$-th entry of $P_1$ is $1$, the $(i,j)$-th entry of $A$ must be positive. Since $A$ is an integer matrix, this means the entry must be at leasst $1$. Therefore, for all $1$s in $P_1$, the counterpart entries in $A$ must be at least $1$, i.e. $A\ge P_1$ entrywise. – user1551 Nov 29 '13 at 23:31