Cryer's Hadamard complete-pivoting conjecture
A real Hadamard matrix of order $n$ is a matrix $H \in \{-1, 1\}^{n \times n}$ with $HH^T = nI$. Let $\rho(H)$ be the growth factor of Gaussian elimination with complete pivoting on $H$ in exact arithmetic: the largest entry modulus of the successive active Schur complements $S_1 = H, S_2, \dots, S_n$, divided by that of $H$, which is $1$. It depends on the pivoting path, that is, on which entry of largest modulus is taken as pivot at each step where there is a tie. On every path the last pivot has modulus $n$, so $\rho(H) \ge n$. The equality below holds for every Hadamard matrix of order $n \le 16$ and every path; the orders $12$ and $16$ are Edelman and Mascarenhas's and Kravvaritis and Mitrouli's.
Problem. Is $\rho(H) = n$ for every Hadamard matrix $H$, of every order $n$, and every complete-pivoting path?
Source: Cryer (1968), the Hadamard case of his conjecture that the complete-pivoting growth factor of a real n × n matrix is at most n, with equality if and only if the matrix is a Hadamard matrix; in this form, Edelman and Mascarenhas (1995). See Higham (2002), Section 9.4 and Problem 9.17.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- CO
- Keywords
- Gaussian elimination, growth factors, Hadamard matrices, OpenProblemsInNLA
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{cryer1968,
author = {Cryer, Colin W.},
title = {Pivot size in {G}aussian elimination},
journal = {Numer. Math.},
volume = {12},
number = {4},
year = {1968},
pages = {335--345},
doi = {10.1007/BF02162514},
}
@article{edelman1995,
author = {Edelman, Alan and Mascarenhas, Walter},
title = {On the complete pivoting conjecture for a {H}adamard matrix of order 12},
journal = {Linear Multilinear Algebra},
volume = {38},
number = {3},
year = {1995},
pages = {181--187},
doi = {10.1080/03081089508818353},
}
@book{higham2002,
author = {Higham, Nicholas J.},
title = {Accuracy and Stability of Numerical Algorithms},
edition = {2nd},
publisher = {SIAM},
address = {Philadelphia},
year = {2002},
doi = {10.1137/1.9780898718027},
note = {Section 9.4 and Problem 9.17},
}
@article{kravvaritis2009,
author = {Kravvaritis, Christos and Mitrouli, Marilena},
title = {The growth factor of a {H}adamard matrix of order 16 is 16},
journal = {Numer. Linear Algebra Appl.},
volume = {16},
number = {9},
year = {2009},
pages = {715--743},
doi = {10.1002/nla.637},
}
@article{edelman2024,
author = {Edelman, Alan and Urschel, John},
title = {Some new results on the maximum growth factor in {G}aussian elimination},
journal = {SIAM J. Matrix Anal. Appl.},
volume = {45},
number = {2},
year = {2024},
pages = {967--991},
doi = {10.1137/23M1571903},
eprint = {2303.04892},
archivePrefix = {arXiv},
}
@article{pecamedlin2026,
author = {Peca-Medlin, John},
title = {Complete pivoting growth of butterfly matrices and butterfly {H}adamard matrices},
journal = {Linear Multilinear Algebra},
volume = {74},
number = {7},
year = {2026},
pages = {934--958},
doi = {10.1080/03081087.2026.2660796},
eprint = {2410.06477},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ie03,
author = {Townsend, Alex},
title = {{IE-03}: Cryer's Hadamard complete-pivoting conjecture},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/linear-systems-and-elimination/IE-03/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00188, "Cryer's Hadamard complete-pivoting conjecture", clopen.solutions.