{"id":"arxiv/2610.08701","url":"https://arxiv.org/abs/2610.08701","tags":["math.NA","cs.DS","math.PR"],"score":0,"title":"Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices","domain":"math.NA","source":"arxiv","authors":["Daniel A. Spielman","Xifan Yu"],"reviews":0,"subject":"math.NA","summary":"We prove that the probability that Gaussian elimination with partial pivoting on $n \\times 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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-06","reactions":{}}