Metraipolis › archive › dc_c49f70f69ed2
Random permutations using GEPP — arXiv:2610.10481
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.10481
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T12:43:17.482Z
- SHA-256 of the archived text
451b8c0b3daf738580351535597ce1bc0ab231500289e2cd681d3cf923e58979- Stable URL of this page
https://metraipolis.com/documento/dc_c49f70f69ed2
How to cite
Random permutations using GEPP — arXiv:2610.10481 — arXiv (en), https://arxiv.org/abs/2610.10481 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c49f70f69ed2 (Metraipolis archive dc_c49f70f69ed2, sha256 451b8c0b3daf738580351535597ce1bc0ab231500289e2cd681d3cf923e58979)
BibTeX
@misc{dcc49f70f69ed2,
title = {Random permutations using GEPP — arXiv:2610.10481},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.10481},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c49f70f69ed2; sha256 451b8c0b3daf738580351535597ce1bc0ab231500289e2cd681d3cf923e58979},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.10481. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Gaussian elimination with partial pivoting (GEPP) remains the most widely used solver for dense linear systems $A \mathbf x = \mathbf b$ for $A \in \mathbb C^{n\times n}$. We study the permutation $\pi = \pi(A)$ that arises in the GEPP factorization $PA = LU$, encoded by the permutation matrix factor $P = P_\pi$. When the input matrix is random, so is $\pi$. For random scalar butterfly matrices of size $2^n$ (a recursively defined family originally introduced to eliminate the need for pivoting altogether), we give the exact GEPP factorization and fully classify the induced permutation as an element of a $2$-Sylow subgroup of $S_{2^n}$ contained in the separable permutations. Moreover, the uniform-angle model induces the uniform distribution on this subgroup. For the GOE, GUE, and iid Bernoulli models, the induced permutation is never exactly uniform for $n \ge 2$. We give the precise rate of departure from uniformity at the leading pivot for the GOE and GUE, and give evidence that this non-uniformity vanishes asymptotically in the permuton sense. In contrast, for banded random matrices of sublinear bandwidth, including the tridiagonal $\beta$-Hermite ensembles, the induced permutation converges to the diagonal permuton. We further show that the resulting pivot probabilities are sensitive to implementation choices: standard LAPACK routines compare complex pivot candidates using the $\ell^1$ rather than $\ell^2$ norm, changing the GUE(2) pivot probability from $1/\sqrt3$ to $2/3$. Together these results establish a new connection between random matrix theory and permutation combinatorics through numerical linear algebra.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.PR, nuovi lavori del giorno).
Categorie arXiv: Probability (math.PR) ; Combinatorics (math.CO); Numerical Analysis (math.NA).
Pagina del lavoro: https://arxiv.org/abs/2610.10481 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:16:30.210Z dalla pagina https://arxiv.org/list/math.PR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).