Source-linked AI summary
Instability of Gaussian elimination is exponentially rare (proof of partial result)
Lloyd N. Trefethen
TL;DR
Although Gaussian elimination with partial pivoting can have a very large growth factor, experiments suggest extreme growth is rare, while a proof for the full growth factor remains open. This paper proves that large values of the corner entry u_nn are exponentially rare for random matrices, taking a step toward confirming those observations.
Problem
Experiments suggest large growth factors are exponentially rare, but the paper notes that evidence for the full growth factor remains unproved; large growth can make the algorithm unstable.
Source: §1 · pp. 1–2Method
The proof shows that triangular factors computed by GE on random matrices are exponentially unlikely to be ill-conditioned.
Source: §1 · p. 2Results
Takeaways & Limitations
The work is at least part-way to a theorem that justifies the empirical curves associated with GE’s success over the years.
Source: §6 · p. 7
Abstract
from arXiv · showhide
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/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}^{}$.
Preliminary note.
The paper was essentially written in 2015, with a few updates added in October 2026, when the author made it available alongside John Urschel’s manuscript apparently proving the section 5 conjecture affirmatively by different arguments.
Preliminary note.
- John Urschel’s concurrently posted manuscript apparently settles the section 5 conjecture affirmatively using different arguments.The paper was essentially written in 2015, with only a few updates added in October 2026.Source: Preliminary note · p. 1
1. Introduction.
The paper proves a partial probabilistic explanation for Gaussian elimination’s practical reliability: for Gaussian random matrices, unusually large corner entries of the computed triangular factor are exponentially rare. Its argument turns on the claim that triangular factors produced by elimination are unlikely to be ill-conditioned, despite random triangular matrices being exponentially ill-conditioned.
1. Introduction.
- Gaussian elimination is almost perfectly reliable in practice, yet its growth factor can reach 2^(n−1), with instability observed in worst-case examples.Wilkinson’s analysis showed that Gaussian elimination can be unstable only when the growth factor is large.Source: §1 · p. 1
- Earlier experiments suggested that large growth factors are extremely rare among random matrices, but no theorem had established this behavior.Source: Figure 1.1 · p. 2, §1 · p. 2
- For matrices with independent standard normal entries, corner entries |u_nn| much larger than n^1/2 are exponentially rare, a partial result toward the conjecture for all entries u_ij.The paper leaves the corresponding claim for every entry of U unproved.Source: §1 · p. 2
- The argument shows that triangular factors computed by Gaussian elimination are exponentially unlikely to be ill-conditioned, unlike random triangular matrices, which are exponentially ill-conditioned.Source: §1 · p. 2
2. Problem setting and the definition of “exponentially unlikely”.
The analysis uses Gaussian random matrices and defines “exponentially unlikely” to describe rare events as the dimension grows. It establishes bounds for the final entry u_nn of U, while the corresponding bound for the full growth factor remains a conjecture in the supplied passages.
2. Problem setting and the definition of “exponentially unlikely”.
- A random n × n matrix has independent standard-normal entries, and partial pivoting produces PA = LU by selecting a largest-magnitude pivot in each column.The factorization has unit diagonal entries in L and subdiagonal entries with absolute value at most 1.Source: §2 · p. 3
- “Exponentially unlikely” means the event bound holds for every α > 0 and M > 0 for all sufficiently large n.The supplied definition introduces this terminology for quantities associated with random n × n matrices.Source: §2 · p. 3
3. First theorem: n3/2 for the final entry of U
- n^3/2: It is exponentially unlikely that u_nn is much greater than n^3/2 when GE is applied to a random n × n matrix.The proof relates u_nn to the last row of L−1 and bounds its entries using the pivoting constraints and Gaussian randomness.Source: §2 · p. 4
4. Second theorem: n1/2 for the final entry of U
- For a random n × n matrix to which GE is applied, it is exponentially unlikely that the final entry u_nn of U is much greater than n^1/2.This improves the earlier n^3/2 bound for the final entry of U to n^1/2.Source: §2 · p. 5
- For ε ≪ 1, it is exponentially unlikely that W contains a µ×µ submatrix Wµ such that qᵀWµ has all entries smaller than ε¹ᐟ², for random unit-norm µ-vector q.Source: §2 · p. 6
5. Conjecture: n1/2 for the growth factor ρ
- The paper conjectures that it is exponentially unlikely for the full growth factor ρ to be much greater than n^1/2, but the supplied passage says a proof had not yet been found.The conjecture concerns ρ, which incorporates earlier entries of U as well as u_nn.Source: §2 · p. 6
6. Discussion.
The discussion argues that the work is part-way to a theorem explaining Gaussian elimination’s observed success, while emphasizing that a statistical explanation does not settle the method’s mechanics.
- Across decades, Wilkinson, Dongarra, Bunch, Moler, and Stewart, Stoer and Bulirsch, Gill, Murray and Wright, and Demmel described large growth as rare or bounds as pessimistic.Source: §6 · p. 6
- Later accounts likewise characterize serious or exponential element growth with partial pivoting as extremely rare in practice.Source: §6 · pp. 6–7
- Stability for random matrices can explain GE’s observed practical stability, but cannot guarantee it, since unstable matrices might have arisen exceptionally often in practice.Source: §6 · p. 7
- A mechanistic account remains open: prior work links rank-1 elimination corrections and post-initial entry distributions approaching N(0, 1), but this paper makes no universality or stability claim.The cited discussion relates the entry-distribution behavior to possible central-limit effects and Deift et al..Source: §6 · p. 7
- The work is part-way to a theorem justifying the observed success curves; GEPP’s stability may be viewed as a statistical law, though its mechanics remain incompletely understood.The discussion compares this statistical justification to physical laws while noting that the analogy may overstate current mechanistic understanding.Source: §6 · p. 7
Appendix.
The appendix proves a lemma used in Theorem 2, related to restricted isometry constants in compressed sensing. It shows that certain submatrices with many small singular values are exponentially unlikely.
Appendix
- For μ ∼ C|log ε|, it is exponentially unlikely that a random μ × n matrix has a μ × μ submatrix with at least μ/2 singular values ≤ ε.Here ε ≪ 1, and “exponentially unlikely” follows the paper’s equation (2.2).Source: Appendix · p. 7
- The proof uses a union bound: it suffices to consider at most (3n/μ)^μ random μ × μ matrices, avoiding a finer analysis of dependencies among A’s columns.The bound covers the number of μ × μ submatrices formed by choosing distinct columns.Source: Appendix · p. 7
- Theorem 1.2 of supplies a probability bound with a universal constant, which the proof uses to imply (6.2).Source: Appendix · p. 8