Random Permutation Matrices Form a Basis with High Probability

Abstract

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 linearly independent with probability $1-O(n^{-1/2})$. Conditioning on distinctness gives the same conclusion for a uniformly random $d_n$-element subset, thereby confirming a conjecture of Kushwaha and Tripathi. The proof combines three ingredients: a mod-$2$ complexity parameter for assignment functionals, the characteristic-function estimate of Roos in the form recorded by Do--Nguyen--Phan--Tran--Vu, and a kernel decomposition argument of Ferber--Kwan--Sauermann. For the uniform-subset model, we also record the elementary lower bound $\exp (3/2+o(1))n^2{e}^{-n}$ coming from an unoccupied matrix position.

10 pages