On the Growth Factor of Random Matrices

DOI10.48550/arXiv.2610.06785MaRDI QIDQ7367838arXivFDO

Authors John Urschel

Publication date 5 October 2026

Published in arXiv

Tldr We derive tight bounds on the growth factor for both unpreconditioned and preconditioned Gaussian matrices with Haar orthogonal preconditioning, as well as a new bound on the growth factor of partially pivoted Gaussian elimination, resolving Trefethen's conjecture that it is rarely larger than $\sqrt{n}$.

Full work available at URL https://doi.org/10.48550/arXiv.2610.06785

arXiv classification

math.NA

Cites work

• A new upper bound for the growth factor in Gaussian elimination with complete pivoting
• A tail inequality for quadratic forms of subgaussian random vectors
• Accuracy and Stability of Numerical Algorithms
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Average-case analysis of the Gaussian Elimination with Partial Pivoting
• Average-Case Stability of Gaussian Elimination
• Entry growth in Gaussian elimination
• Error Analysis of Direct Methods of Matrix Inversion
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Growth Factors of Random Butterfly Matrices and the Stability of Avoiding Pivoting
• LU Factorization of Discrete Random Matrices
• Numerical Linear Algebra
• Numerical stability in Gaussian elimination
• On the complete pivoting conjecture for a hadamard matrix of order 12
• Probabilistic Analysis of Gaussian Elimination Without Pivoting
• Random matrices: law of the determinant
• Random matrices: overcrowding estimates for the spectrum
• Searching for Rare Growth Factors Using Multicanonical Monte Carlo Methods
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• Some New Results on the Maximum Growth Factor in Gaussian Elimination

Cited in

(1)

• Instability of Gaussian elimination is exponentially rare (proof of partial result)

This page was built for publication: On the Growth Factor of Random Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7367838)