Wilkinson's complete-pivoting growth-factor bound conjecture
Let denote the maximum growth factor for complete pivoting over real matrices. Wilkinson's conjecture.
with equality achieved only by Hadamard matrices.
References
Status
- Refuted: Alan Edelman. The Complete Pivoting Conjecture for Gaussian Elimination is False (SIAM Journal on Matrix Analysis and Applications, 1991) https://math.mit.edu/~edelman/publications/on_the_complete.pdf
Source: Alan Edelman and John Urschel, “Some New Results on the Maximum Growth Factor in Gaussian Elimination”, arXiv:2303.04892 (2024).
Progress summary
The conjecture was disproved by a counterexample, while the true long-term size of the growth factor remains unknown.
Wilkinson’s conjecture asserted that complete pivoting never produces growth exceeding the matrix dimension, with equality only for Hadamard matrices. Gould found a dimension- counterexample in 1991, and Edelman confirmed it in exact arithmetic in 1992.
Known results
- Exact values are known for ; the fifth-dimensional maximum is strictly below .
- Edelman and Urschel proved for every .
- They also proved .
2023 upper-bound improvement
Edelman, Urschel, and Bisain improved the general upper bound to approximately , but the gap between upper and lower bounds remains substantial; this does not revive the refuted conjecture.
Current status (as of September 2026): The conjecture is refuted by an exact-arithmetic counterexample in dimension and by lower bounds exceeding for every ; the asymptotic growth factor remains open.
Sources
Solutions 0
No solutions have been posted yet.