How many $3 \times 3$ matrices are sum of $r$ permutation matrices?

Question

I'm trying to understand the solution of P.Stanley to the following:

Let $H(r)$ be the number of $3 \times 3$ matrices of natural numbers that are the sum of $r$ permutation matrices $3 \times 3$.

Prove that $H(r)= {r+5 \choose 5} - {r+2 \choose 5}$.

Let $A$ be such a matrix, we can write:

$A=\sum_{\omega \in S_3} \alpha_\omega P_\omega$, with $\alpha_\omega \in \mathbb{N}$ and $\sum \alpha_\omega = r$.

The number of ways to choose $\alpha_\omega \in \mathbb{N}$ is the number of weak compositions of $r$ in $6$ parts (since $S_3$ has six elements), and this number is $r+5 \choose 5$.

Now the problem is that we are counting too many objects, in facts the six permutation matrices are not linearly independent so matrices do not have a unique representation. Fortunately any five matrices from these six are linearly independent.

We than notice that any combination of the type $\sum_{\omega \in S_3} \alpha_\omega P_\omega =0$ implies $\alpha_{123}=\alpha_{231}=\alpha_{312}=-\alpha_{132}=-\alpha_{213}=-\alpha_{321}$.

Stanley justifies the $-{r+2\choose 5}$ term saying that it is the number of ways to choose $\alpha_{123},\alpha_{231},\alpha_{321}\in \mathbb{N}$ and $\alpha_{213},\alpha_{132},\alpha_{321}\in \mathbb{N}_{>0}$ such that $\sum \alpha_\omega=r$ is in fact ${r+2\choose 5}$, but I don't understand the meaning of it.

Why in this way we obtain the result?

Answer 1

Summarizing what OP has written, and recasting the problem, we want to find the number of solutions to

• Solutions in non-negative integers to $a+b+c+d+e+f = r $(sum of these permutation matrices)
  • There are ${ r + 5 \choose 5 } $ solutions if we ignore the following restrictions.
• $\min (a, b, c ) = 0 $ (else $a-1, b-1, c-1, d+1, e+1, f+1$ yields the same matrix)
• $\min (d, e, f) = 0 $ (for a similar reason)

OP is wondering how the restriction results in ${r + 2 \choose 5 } $ double counting.

To get a handle on what's happening (or you can skip ahead), let's consider an explicit scenario, namely the first time when the value is non-zero, which occurs when $ r = 3$. In this case, $ a=b=c=1, d=e=f=0$ and $a=b=c=0, d=e=f=1$ results in a double counting of the all-1's matrix, so we need to remove one count of this.

Now, let's see how we can make this count of values that violate the condition.

• First we take the bijection $$ a, b, , d, e, f \rightarrow a +\min(d, e, f), b + \min(d, e, f) , c + \min (d, e, f) , d - \min(d, e, f) , e - \min (d, e, f), g - \min (d, e, f).$$
  This results in the $a, b, c \geq 1, d, e, f \geq 0$, $a+b+c+d+e+f = r$ scenario that was described.
• Second we take the bijection $$a, b, c, d, e, f \rightarrow a-1, b-1, c-1, d, e, f .$$ This results in $a, b, c, d, e, f \geq 0$ with $a+b+c+d+e+f = r - 3$, of which we know there are ${ r + 2 \choose 5 } $solutions. Hence, that is how much we're double counting by.