On the Growth Factor of Random Matrices

1.1. Partial Pivoting.

• Although partial pivoting can have exponentially large worst-case growth, experiments suggested Gaussian matrices typically grow around n^1/2, motivating Trefethen’s conjecture.Earlier mathematical progress included a high-probability polynomial bound with a large unspecified exponent.Source: §1.1 · p. 2

1.2. Alternatives to Partial Pivoting.

• Partial pivoting remains preferred in practice despite quasipolynomial growth bounds for complete pivoting, owing to its lower computational cost and memory-access requirements.The paper also discusses approaches that avoid pivoting, including orthogonal and butterfly preconditioning.Source: §1.2 · p. 3
• The paper bounds growth for Haar-orthogonally preconditioned matrices without pivoting and shows the exponent is tight for non-adaptive orthogonal preconditioners.For Gaussian matrices without pivoting, scaled growth converges in distribution to an inverse exponential law.Source: §1.3 · p. 3, §1.4 · p. 4

1.3. Our Contributions.

• Gaussian matrices under partial pivoting have growth at most n^(1/2+o(1)) with overwhelming probability, proving Trefethen’s conjecture.The result concerns the growth factor of an n × n Gaussian matrix under the partial pivoting map.Source: §1.3 · p. 3
• For polynomially small Gaussian perturbations of bounded-norm matrices, the smoothed bound is n^O(log log n), improving the longstanding n^O(log n) bound.The setting assumes ∥A∥2 ≤ 1; the paper notes that the correct behavior is likely n^O(1).Source: §1.3 · p. 4
• For Gaussian elimination without pivoting, growth divided by n^3/2 converges to an inverse exponential distribution.The stated distribution has cumulative distribution function e^(−2/(3√πx)) for x > 0.Source: §1.3 · p. 3, §1.4 · p. 4

1.4. Remainder of Paper.

• The paper also proves six technical lemmas on Gaussian matrices and singular values, used in its analyses of partial pivoting and smoothed growth.The smoothed result generalizes the Gaussian partial-pivoting analysis.Source: §1.4 · p. 5

• For fixed A and Haar orthogonal Q, growth(QA) is usually not much bigger than n.Source: §2 · p. 5
• The main technical tool is a lemma about inverses of submatrices of Haar orthogonal matrices.Source: §2 · pp. 5–6
• The inverse-submatrix argument identifies a random-sphere distribution for the direction of an inverse applied to a coordinate vector.Source: §2 · p. 6
• The proof reduces A to upper triangular form, uses block inversion, and combines probabilistic bounds for the lower and upper triangular factors.Source: §2 · p. 6

3. Growth of Gaussian Matrices without Pivoting

• The section proves an asymptotic distribution result for the growth factor of a Gaussian matrix without pivoting, after the normalization described in the theorem.The supplied passage states that the growth factor is divided by n, but does not include the full limiting expression.Source: §3 · p. 7
• For k in [n − 1], the largest entry in row k + 1 of U is X_kY_k, with X_k independent of Y_k.The passages also state that the X_k variables are mutually independent.Source: §3 · p. 7
• The proof obtains Y_k from Gaussian inner products conditional on the first k columns, and establishes its independence from X_k.The vector x_k/X_k spans the relevant null space, and its inner products with the remaining Gaussian columns determine Y_k.Source: §3 · p. 7
• The analysis also shows that n^-3/2 times the maximum absolute entry of L converges to zero in probability.It uses this result alongside the convergence of the maximum absolute entry of G, scaled by 2√log n, to 1 in probability.Source: §3 · p. 8

4. Singular Values and Gaussian Matrices

• Σ_k(M) denotes the squared Frobenius norm of the inverse after truncating the k largest singular values of the inverse.By convention, Σ_k(M) = 0 when k ≥ n.Source: §4 · p. 8
• The lemmas provide Gaussian concentration bounds for matrix functions that are Lipschitz in the Gaussian matrix.The stated functions include the Frobenius norm and a function of the singular values; the bounds use the matrix norm of the fixed multiplier.Source: §4 · p. 9
• A pseudoinverse bound reduces control to a Gaussian matrix restricted to directions in the null space of the fixed mean.The proof selects orthonormal columns in the null space of Δ and bounds the pseudoinverse through the resulting Gaussian matrix.Source: §4 · p. 9
• A separate lemma bounds how appending Gaussian columns affects a matrix whose truncated inverse is already controlled.Its assumptions include a lower bound on a singular value and an upper bound on Σ_k(M).Source: §4 · p. 10

5. Growth of Gaussian Matrices under Partial Pivoting

• The growth factor of an n × n Gaussian matrix under partial pivoting is rarely much more than √n.The proof focuses on controlling most singular values of the leading pivot submatrices and uses the bound ∥L∥max = 1.Source: §5 · p. 11

5.1. A High-Level Outline of the Proof.

• Controlling truncated inverses of pivot blocks suffices to control the growth factor, completing the proof when paired with the truncated-inverse bound.The argument uses the conditional distribution of non-pivot rows and reveals new Gaussian columns during elimination.Source: §5.1 · p. 12, §5.2 · p. 13

5.2. Controlling the Truncated Inverse Bounds Growth.

• The elimination matrix is decomposed into a controlled part and a rank-at-most-r part; revealing 4r more Gaussian columns smooths the latter.The argument bounds the row norms after these additional steps and uses them to control entries of the Schur complements.Source: §5.1 · p. 12, §5.2 · pp. 13–14

5.3. Extending a Selected Block

• The selected pivot block can be extended with additional Gaussian columns under the lemma’s stated probability bounds.For the extension of the rows selected by π_m, the passage gives probability at least 1 − 3n^−(β+1) and notes that this cost is paid only once.Source: §5.3 · p. 15

5.4. A Bound for the Truncated Inverse.

• An induction over stages establishes the truncated-inverse bound with failure probability at most n^−γ.The induction uses the extension lemma to pass from an earlier stage to the desired stage.Source: §5.4 · pp. 16–17

5.5. A Proof of Theorem 1.4.

• The proof of the √n growth result combines the truncated-inverse bound with the proposition converting that control into growth control.The proof chooses r = ⌈√log n⌉ and applies the two propositions with their stated probability exponents.Source: §5.5 · p. 17

6. A Smoothed Analysis of Partial Pivoting

• For a fixed matrix A and ε > 0, the growth factor of A + εG is at most n^O(1)ε^−O(log log n) with overwhelming probability.This extends the preceding analysis to the smoothed setting.Source: §6 · p. 17

6.1. Adapting the Argument for General Means.

• The general-mean argument rescales A + εG to A/ε + G and incurs additional losses depending on K = ε^−1∥A∥2.The passages identify losses in both the truncated-inverse bound and the conversion from truncated-inverse control to growth control.Source: §6.1 · p. 17

6.2. Proof of Theorem 1.6.

• Theorem 6.1 bounds the growth for every mean matrix Δ, noise scale ε > 0, and its stated choice of r.The proof of Theorem 1.6 applies Theorem 6.1 with Δ = A and r = ⌈e^4λ⌉.Source: §6.1 · p. 17, §6.2 · p. 19

AI Usage Statement

• AI interaction extended a human-only proof sketch for the bottom-right o(n) entries of Uij into a proof covering all entries of Conjecture 1.1.The author describes this as an improvement through human–AI interaction.Source: AI Usage Statement · p. 20
• The other results followed a similar trajectory of human ideas and expertise improved through AI interaction.Source: AI Usage Statement · p. 20
• The author says the results in Sections 2 and 3 were not technically difficult and likely did not need human input.Source: AI Usage Statement · p. 20
• Conjecture 1.1 had been listed as open, challenging, and interesting on OpenProblemsInNLA and remained unsolved before the manuscript.The author notes that roughly half of the repository’s more than 200 open problems had been solved, largely with autonomous AI systems.Source: AI Usage Statement · p. 20
• The author wrote the entire manuscript.Source: AI Usage Statement · p. 20