On the Growth Factor of Random Matrices

Abstract

Gaussian elimination is the oldest and most popular method for solving a linear system. Its numerical stability for a given matrix is controlled by the growth factor, a measure of how large entries can become during elimination. In this work, we prove a number of new results regarding the growth factor of random matrices. First, we provide tight estimates for the growth factor of a matrix preconditioned by a Haar orthogonal matrix without pivoting and characterize the asymptotic distribution of the growth factor of Gaussian matrices without pivoting. Second, and most notably, we prove that the growth factor of an $n \times n$ Gaussian matrix under partial pivoting is rarely much larger than $\sqrt{n}$, resolving an old conjecture of Nick Trefethen. The same techniques used to prove this conjecture also provide an improved smoothed analysis of the growth factor under partial pivoting.