Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices

Abstract

We prove that the probability that Gaussian elimination with partial pivoting on $n\times n$ random matrices has growth $\rho$ is at least inverse quasi-polynomial: $\Omega (\exp (-c{\log }^2(\rho )\log (n)))$ for some constant $c>0$. This lower bound breaks standard conjectures in the smoothed and average-case analysis of Gaussian elimination. To the best of our knowledge, it is the first non-trivial lower bound on the probability of large growth for Gaussian random matrices.