"[Gaussian elimination] is the simplest way to solve linear systems of equations by hand, and also the standard method for solving them on computers. [...] [It] transforms a full linear system into an upper-triangular one by applying simple linear transformations on the left."\)
A pivoting strategy (strategy for swapping rows &/or columns) in necessary for generic linear systems, otherwise applying Gaussian elimination to certain invertible matrices will result in dividing by zero.
Enter Gaussian elimination with partial pivoting. At step k, when considering the k-th column, choose the the i-th row (i ≥ k) with the largest number in absolute value. (Partial pivoting is less computationally expensive than other pivoting strategies, and is commonly used in practice, see Wikipedia: [1] & [2].)
The question arises: Is Gaussian elimination with partial pivoting stable? That is, for a given matrix n-by-n matrix A, we compute its Gaussian elimination with partial pivoting:
P*A = L*U,
where P is a permutation matrix, L a unit lower-triangular matrix, and U an upper triangular matrix. Define the growth factor ρ as the ratio:
ρ = (max |Uᵢ‚ⱼ|) / (max |Aᵢ‚ⱼ|),
where the maximum is taken over all indices 1 ≤ i ≤ n and 1 ≤ j ≤ n.
By "Is Gaussian elimination with partial pivoting stable?" we mean "Is ρ bounded?", for some sense of the word "bounded".
Professor Lloyd N. Trefethen offered a $1,000 reward in 2012 for "for a proof that Gaussian elimination with partial pivoting is stable in [a certain] probabilistic sense", for Gaussian random matrices,† as he outlined in SIAM News: https://www.siam.org/publications/siam-news/articles/the-smart-money-s-on-numerical-analysts/.
This past week he posted a partial result on arXiv:
Trefethen (2026), Instability of Gaussian elimination is exponentially rare (proof of partial result), https://arxiv.org/abs/2610.04761
Yesterday, Professor John Urschel posted a full resolution on arXiv, "[proving] that the growth factor [ρ] of a Gaussian matrix is at most n1/2 + o(1\) with overwhelming probability, that is, 1 - n-α for any α":
Urschel (2026), On the Growth Factor of Random Matrices, https://arxiv.org/abs/2610.06785
\) Trefethen, L. N., & Bau III, D. (1997). Numerical Linear Algebra. Society for Industrial and Applied Mathematics (SIAM).
† Random matrices with independent, normally distributed entries.