Skip to content
DraconiticResearch
Search Sources API
197,788 studies31 sourcesUpdated 49 min ago
PreprintCC BY 4.0arXiv

On the Growth Factor of Random Matrices

  • John Urschel
Open at sourcePDFDOICite

Abstract

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 the growth factor of a matrix preconditioned by a Haar orthogonal matrix without pivoting and characterize the asymptotic distribution of the growth factor of Gaussian matrices without pivoting. Second, and most notably, we prove that the growth factor of an n × n Gaussian matrix under partial pivoting is rarely much larger than √n, resolving an old conjecture of Nick Trefethen. The same techniques used to prove this conjecture also provide an improved smoothed analysis of the growth factor under partial pivoting.

Related

  1. Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices
    Daniel A. Spielman, Xifan Yu
    arXivPreprintarXiv licenceFull textNumerical analysis & scientific computingProbabilityarXiv
  2. Random p-adic matrices with fixed zero entries and the Cohen–Lenstra distribution
    Dong Yeap Kang, Jungin Lee, Myungjun Yu
    Selecta MathematicaPeer-reviewedLicence not statedFull text11 citedAlgebra & number theoryOpenAlex
  3. Delocalization and Quantum Diffusion of Random Band Matrices in High Dimensions I: Self-energy Renormalization
    Fan Yang, Horng‐Tzer Yau, Jun O. S. Yin
    Communications in Mathematical PhysicsPeer-reviewedLicence not statedFull text33 citedMathematical physicsOpenAlex
  4. Universality for the global spectrum of random inner-product kernel matrices in the polynomial regime
    Sofiia Dubova, Yue M. Lu, Benjamin McKenna +1
    The Annals of Applied ProbabilityPeer-reviewedLicence not statedFull text19 citedStatisticsOpenAlex
  5. On non-monotonicity of logarithmic energy for random matrices
    Theodoros Assiotis
    arXivPreprintCC BY 4.0Full textMathematical physicsProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{urschel2026growth,
  title = {{On the Growth Factor of Random Matrices}},
  author = {John Urschel},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.06785},
  eprint = {2610.06785},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.06785},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - On the Growth Factor of Random Matrices
AU  - John Urschel
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2610.06785
UR  - https://arxiv.org/abs/2610.06785
AB  - 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 the growth factor of a matrix preconditioned by a Haar orthogonal matrix without pivoting and characterize the asymptotic distribution of the growth factor of Gaussian matrices without pivoting. Second, and most notably, we prove that the growth factor of an n × n Gaussian matrix under partial pivoting is rarely much larger than √n, resolving an old conjecture of Nick Trefethen. The same techniques used to prove this conjecture also provide an improved smoothed analysis of the growth factor under partial pivoting.
ER  -