Random Permutation Matrices Form a Basis with High Probability

Yijun Jiang

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