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!