PreprintarXiv licencearXiv
Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices
Abstract
We prove that the probability that Gaussian elimination with partial pivoting on n × n random matrices has growth ρ is at least inverse quasi-polynomial: Ω(exp(−c log2 (ρ)log(n))) for some constant c > 0. This lower bound breaks standard conjectures in the smoothed and average-case analysis of Gaussian elimination. To the best of our knowledge, it is the first non-trivial lower bound on the probability of large growth for Gaussian random matrices.
Related
- Instability of Gaussian elimination is exponentially rare (proof of partial result)
- Entry growth in Gaussian elimination
- Chordal Codes: Code Construction and Efficient Gaussian-Elimination Decoding
- Freeness for the G-circulant Decomposition of the Partial Transpose of Random Matrices
- Large deviations for the largest eigenvalue of a polynomial in Gaussian matrices
BibTeX
@misc{spielman2026large,
title = {{Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices}},
author = {Daniel A. Spielman and Xifan Yu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08701},
eprint = {2610.08701},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08701},
}
RIS
TY - UNPB
TI - Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices
AU - Daniel A. Spielman
AU - Xifan Yu
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08701
UR - https://arxiv.org/abs/2610.08701
AB - We prove that the probability that Gaussian elimination with partial pivoting on n × n random matrices has growth ρ is at least inverse quasi-polynomial: Ω(exp(−c log^2 (ρ)log(n))) for some constant c > 0. This lower bound breaks standard conjectures in the smoothed and average-case analysis of Gaussian elimination. To the best of our knowledge, it is the first non-trivial lower bound on the probability of large growth for Gaussian random matrices.
ER -