Random Permutation Matrices Form a Basis with High Probability
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 basis with probability $(1+o(1))n^2(1-1/n)^d=(e^{3/2}+o(1))n^2e^{-n}$. The same asymptotic holds for a uniformly random $d$-element subset, confirming a conjecture of Kushwaha and Tripathi and identifying the leading obstruction: a matrix position avoided by every sample. More generally, for any fixed number of additional samples, we determine the first three exponential orders of the failure probability. To prove…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.05581
curl -X POST /api/v1/records/arxiv/2609.05581/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.05581/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'