# rank for the matrix of concatenating all $N \times N$ permutation matrics

Consider all $N\times N$ permutation matrix $\{M_1,M_2,\ldots,M_{N!}\}$

Define $S_N$ as concatenating each $\operatorname{vec}(M_i)$ as $S_N$'s $i$th column

Is there any convenient way to calculate $\operatorname{rank}(S_N)$ ?

Take $N=3$ for example.

$$M_1=\left[\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}\right]$$ $$M_2=\left[\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}\right]$$ $$M_3=\left[\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}\right]$$ ...

then $$S_3=\left[\begin{matrix} 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \end{matrix}\right]$$

and $\operatorname{rank}(S_3)=5$

Thanks for any suggestions!

-

In general this should be 1 plus the dimension $(n-1)^2$ of the Birkhoff polytope. The extra $1$ just comes from it lying in an affine, rather than linear, subspace.
Thanks, I found a similar problem, which might be more general(in some aspects) here. mt_ even gives the $(1+(n-1)^2)$ basis for this space. – Benson Jun 13 '12 at 11:13