Speaker
Description
Gaussian elimination with partial pivoting (GEPP) remains the most widely used dense linear solver. GEPP produces the factorization $PA = LU$, where $L$ and $U$ are lower and upper triangular matrices and $P$ is a permutation matrix; together, these encode the pivoting strategy, directly influencing stability through classical growth-factor bounds and matrix norm inequalities. When $A$ is random, the permutation arising from the $P$ factor is itself random. When is this permutation uniform? How many cycles appear in its disjoint cycle decomposition (equivalently, how many pivot movements occur during GEPP — providing a new link between random matrix theory and permutation statistics through numerical linear algebra)? What is the length of the longest increasing subsequence of this permutation? We provide statistical answers to these questions for selected random matrix ensembles and transformations. For structured cases involving butterfly permutations, we present full distributional descriptions of these statistics. Moreover, we introduce a random butterfly matrix ensemble whose GEPP-induced permutations are distributed according to Haar measure on a full 2-Sylow subgroup of the symmetric group on a set of size $2^n$.