For a pivoting rule P and dimension n, let g_n^P(R) denote the supremum, over all nonsingular matrices A∈R^n× n, of the ratio between the largest absolute value of any entry produced during Gaussian elimination with rule P and max_i,j|a_ij|. Determine the asymptotic behavior of g_n^P(R), in particular for complete pivoting and rook pivoting, and determine the corresponding worst-case behavior for sparse matrices and randomized partial pivoting.

Worst-case growth factor in Gaussian elimination

The problem concerns the largest possible amplification during Gaussian elimination under different pivoting rules. The historical linear-growth conjecture for complete pivoting is false: explicit counterexamples exceed the conjectured bound.

Known results

Gould (1991) found a $13\times13$ example exceeding the conjectured complete-pivoting bound; Edelman (1992) confirmed it in exact arithmetic.
Complete pivoting satisfies $g_n^{\mathrm{CP}}(\mathbb R)\ge1.0045n$ for $n>10$ and $\limsup_{n\to\infty}g_n^{\mathrm{CP}}(\mathbb R)/n\ge3.317$ .
Complete pivoting has an improved upper bound with leading constant approximately $0.20781$ , replacing Wilkinson’s $0.25$ .
Rook pivoting has the lower bound $g_n^{\mathrm{RP}}(\mathbb R)>n^{1.669}/641$ .

August 2026 claimed asymptotic solution

The paper Entry growth in Gaussian elimination claims asymptotic results for complete and rook pivoting and resolves related sparse and randomized-pivoting questions. This is a substantial new claim, but the manuscript is unrefereed and its abstract does not precisely identify every subproblem settled, so the general resolution remains unverified.

Current status (as of August 2026): Classical bounds and counterexamples are settled, while the new paper’s claimed general asymptotic resolution remains unverified.

Worst-case growth factor in Gaussian elimination

Progress summary

Primary source

Additional references

Solutions 0