Instability of Gaussian elimination is exponentially rare (proof of partial result)

Gaussian elimination with partial pivoting is the standard algorithm for solving a dense $n\times n$ system of linear equations $Ax=b$. The ``growth factor’’ $\rho$ for this process may be as large as $2^{n-1}$, and when $\rho$ is large, the algorithm is unstable. Nevertheless, long experience has shown that Gaussian elimination is resoundingly stable in practice. Experiments indicate that among random matrices with independent normally distributed entries, growth factors $\rho \gg n^{1\mathrm{/}2}$ are in a precise sense exponentially rare. Here we take a step toward confirming this observation by proving it not for the full growth factor, which depends on all the entries of the upper-triangular factor $U$, but for the corner entry $u_{nn}^{}$.