OP-00218 Solution claimed

The square-root upper bound for Gaussian partial-pivoting growth

For a nonsingular $A \in \mathbb{R}^{n \times n}$ let $\rho_{\mathrm{PP}}(A)$ be the growth factor of Gaussian elimination with partial pivoting in exact arithmetic: the largest entry modulus of the successive active Schur complements $S_1 = A, S_2, \dots, S_n$, divided by the largest entry modulus of $A$. Let $G_n \in \mathbb{R}^{n \times n}$ have independent standard normal entries; it is almost surely nonsingular, with no ties in the choice of pivots. Huang and Tikhomirov showed that $\rho_{\mathrm{PP}}(G_n) \le n^{C}$ with probability tending to one, for a universal constant $C$. For the last pivot $u_{nn}$ alone, Trefethen gave a proof that for all $\eta, M > 0$, $\Pr\{|u_{nn}| > n^{1/2+\eta}\} < n^{-M}$ for all sufficiently large $n$.

Problem. Is $$\lim_{n \to \infty} \Pr\{\rho_{\mathrm{PP}}(G_n) > n^{1/2+\eta}\} = 0$$ for every $\eta > 0$?

Source: Trefethen, in Trefethen and Bau (1997), p. 169, as OpenProblemsInNLA cites it; stated precisely by Trefethen (2026, written in 2015), Section 5, with probability below n^(−M) for every M > 0. In this weaker form, with the probability only tending to zero, OpenProblemsInNLA.

Imported from github.com/ajt60gaibb/OpenProblemsInNLA.

Classification

Primary: NA — Numerical Analysis
Secondary: PR
Keywords: Gaussian elimination, growth factors, OpenProblemsInNLA, random matrices
Literature checked: Oct. 8, 2026 by clemens-admin

References

@book{trefethen1997,
  author    = {Trefethen, Lloyd N. and Bau, III, David},
  title     = {Numerical Linear Algebra},
  publisher = {SIAM},
  address   = {Philadelphia},
  year      = {1997},
  doi       = {10.1137/1.9780898719574},
  note      = {p. 169},
}
@misc{trefethen2026,
  author        = {Trefethen, Lloyd N.},
  title         = {Instability of {G}aussian elimination is exponentially rare (proof of partial result)},
  year          = {2026},
  eprint        = {2610.04761},
  archivePrefix = {arXiv},
}
@article{huang2024,
  author        = {Huang, Han and Tikhomirov, Konstantin},
  title         = {Average-case analysis of the {G}aussian elimination with partial pivoting},
  journal       = {Probab. Theory Related Fields},
  volume        = {189},
  number        = {1-2},
  year          = {2024},
  pages         = {501--567},
  doi           = {10.1007/s00440-024-01276-2},
  eprint        = {2206.01726},
  archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ie06,
  author       = {Townsend, Alex},
  title        = {{IE-06}: The square-root upper bound for Gaussian partial-pivoting growth},
  howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
  year         = {2026},
  url          = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/linear-systems-and-elimination/IE-06/README.md},
  note         = {Read at commit eb7c9d6, 2026-10-07},
}

Resolution claims

On the Growth Factor of Random Matrices v1 arXiv ↗

John Urschel

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 …

Full resolution · not verified · fidelity not established · posted on arXiv 5 Oct 2026

Status history

When	Change	By	Reason
2026-10-08	Needs verification → Solution claimed	clemens-admin	Listed with the record of its solution, unreviewed.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00218, "The square-root upper bound for Gaussian partial-pivoting growth", clopen.solutions.