Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper analyzes the permutation induced by Gaussian elimination with partial pivoting (GEPP) on random matrices, specifically scalar butterfly and GOE/GUE/Bernoulli ensembles. It precisely characterizes the permutation for scalar butterfly matrices as an element of a specific 2-Sylow subgroup and demonstrates non-uniformity for other random ensembles, with asymptotic convergence to uniformity in the permuton sense. The study reveals implementation-dependent pivot probabilities, highlighting a novel link between random matrix theory, permutation combinatorics, and numerical linear algebra.
GEPP's induced permutation on random matrices deviates from uniformity, with implementation details significantly altering pivot probabilities.
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 $π= π(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 \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 $β$-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.