Random Permutation Matrices Form a Basis with High Probability

Yijun Jiang

Let $d_n=(n-1{)}^2+1$, the dimension of the real linear span of the $n\times n$ permutation matrices. We prove that $d_n$ independent uniformly random permutation matrices are linear…