2
$\begingroup$

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!

1 Answers 1

2

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.

  • 1
    Thanks, I found a similar problem, which might be more general(in some aspects) [here](http://math.stackexchange.com/questions/70569/span-of-permutation-matrices). mt_ even gives the $(1+(n-1)^2)$ basis for this space.2012-06-13