Random permutations using GEPP
Abstract
Gaussian elimination with partial pivoting (GEPP) remains the most widely used solver for dense linear systems A x = b for A ∈ ℂn× n. We study the permutation π= π(A) that arises in the GEPP factorization PA = LU, encoded by the permutation matrix factor P = Pπ. When the input matrix is random, so is π. For random scalar butterfly matrices of size 2n (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 S2n 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 ≥ 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 β-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 ℓ1 rather than ℓ2 norm, changing the GUE(2) pivot probability from 1/√3 to 2/3. Together these results establish a new connection between random matrix theory and permutation combinatorics through numerical linear algebra.
Related
- Quadratic-size Random Permutations are Universal
- Permutations from ranking independent random variables
- Dimer model and random lattice permutations with general weights
- Superadditivity of classical communication over quantum channels via random and deterministic permutations
- A Short Proof of Zhang's Conjecture on Stack-Sortable Permutations
BibTeX
@misc{gunawan2026random,
title = {{Random permutations using GEPP}},
author = {Kenji Gunawan and John Peca-Medlin and Chenyang Zhong},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10481},
eprint = {2610.10481},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10481},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Random permutations using GEPP
AU - Kenji Gunawan
AU - John Peca-Medlin
AU - Chenyang Zhong
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10481
UR - https://arxiv.org/abs/2610.10481
AB - Gaussian elimination with partial pivoting (GEPP) remains the most widely used solver for dense linear systems A x = b for A ∈ ℂ^n× n. We study the permutation π= π(A) that arises in the GEPP factorization PA = LU, encoded by the permutation matrix factor P = P_π. When the input matrix is random, so is π. 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 ≥ 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 β-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 ℓ^1 rather than ℓ^2 norm, changing the GUE(2) pivot probability from 1/√3 to 2/3. Together these results establish a new connection between random matrix theory and permutation combinatorics through numerical linear algebra.
ER -