Random Permutation Matrices Form a Basis with High Probability

Abstract

Let d=(n−1)²+1, the dimension of the real linear span of the n× n permutation matrices. We prove that d independent uniformly random permutation matrices fail to form a basis with probability (1+o(1))n²(1−1/n)^d=(e^3/2+o(1))n²e⁻ⁿ. 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 these results, we develop support estimates valid over arbitrary fields, derive Fourier bounds from permanental minors, and introduce a counting argument for concentrated assignment functionals over large prime fields. We also give a sparse lifting argument showing that real rank deficiency without an annihilating functional of small support has probability o(e^−Cn) for every fixed C>0.

Exact probability distributions of complex spacing ratios in non-Hermitian random matrices
Kohei Kawabata
arXiv28 Sep 2026PreprintCC BY 4.0Full textMathematical physics Condensed matterarXiv
New classes of trace-form permutation polynomials and their compositional inverses
Kirpa Garg
arXiv1 Sep 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
High-Girth QLDPC Codes from Circulant and Affine Permutation Matrices
Vahid Nourozi, Roxana Smarandache, David G. M. Mitchell†
arXiv14 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv
Permutation binomials of the form X^r(X^q−1+a) over finite fields
Junna Ni, Xuan Pang, Jianhua Yu +1
arXiv23 Sep 2026PreprintarXiv licenceFull textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
The occupation time of a random walk generated by the uniform random permutation--a GPT-6 Astra proof
Wenpin Tang
arXiv20 Sep 2026PreprintarXiv licenceFull textProbabilityarXiv

Cite

BibTeX RIS

BibTeX

@misc{jiang2026random,
  title = {{Random Permutation Matrices Form a Basis with High Probability}},
  author = {Yijun Jiang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.05581},
  eprint = {2609.05581},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.05581},
}

RIS

TY  - UNPB
TI  - Random Permutation Matrices Form a Basis with High Probability
AU  - Yijun Jiang
PY  - 2026
DA  - 2026/10/08
PB  - arXiv
DO  - 10.48550/arxiv.2609.05581
UR  - https://arxiv.org/abs/2609.05581
AB  - Let d=(n−1)^2+1, the dimension of the real linear span of the n× 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 these results, we develop support estimates valid over arbitrary fields, derive Fourier bounds from permanental minors, and introduce a counting argument for concentrated assignment functionals over large prime fields. We also give a sparse lifting argument showing that real rank deficiency without an annihilating functional of small support has probability o(e^−Cn) for every fixed C>0.
ER  -

Abstract

Related

Cite