Trefethen conjecture on Gaussian elimination with partial pivoting

Let $A\in\mathbb{R}^{n\times n}$ have independent standard Gaussian entries, and let $\rho_n(A)$ be the growth factor produced by Gaussian elimination with partial pivoting, namely $\rho_n(A)=\frac{\max_{k,i,j}|a^{(k)}_{ij}|}{\max_{i,j}|a_{ij}|}$ , where $a^{(k)}_{ij}$ ranges over the entries of all matrices occurring during the elimination. The conjecture is that, for every $\varepsilon>0$ , $\mathbb{P}\!\left(n^{1/2-\varepsilon}\leq \rho_n(A)\leq n^{1/2+\varepsilon}\right)\xrightarrow[n\to\infty]{}1$ ; equivalently, $\rho_n(A)=n^{1/2+o(1)}$ with high probability.

References

Primary source

arXiv

Additional references

Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices — arXiv — Daniel A. Spielman, Xifan Yu

Posted 1 day ago · edited 1 day ago

Progress summary

Refreshed 1 day ago

Claimed progress

A new paper reports a substantial lower bound for rare instability in Gaussian elimination, but the conjecture itself remains open.

Trefethen presented the conjecture in 1995 and included it in the 1997 Trefethen–Bau textbook. It predicts that partial pivoting on an $n \times n$ Gaussian matrix has growth close to $\sqrt{n}$ , up to subpolynomial factors.

Known results

Trefethen and Schreiber (1990): worst-case growth can reach $2^{n-1}$ , while experiments and probabilistic models suggested typical growth around $n^{2/3}$ .
Huang and Tikhomirov: proved a high-probability polynomial upper bound, with a large unspecified exponent, for Gaussian matrices.

October 2026 lower-bound advance

Spielman and Yu report an inverse-quasi-polynomial lower bound for large-growth events in Gaussian matrices, challenging prior average- and smoothed-case expectations. A separate manuscript proves a bound for the final triangular-factor entry but explicitly leaves the full growth factor conjectural; the new lower-bound claim has not been independently assessed in the retrieved record.

Current status (as of October 2026): A claimed new lower bound is unverified, while the full Trefethen conjecture remains open.

Sources

No solutions have been posted yet.