Cryer's growth conjecture for Hadamard matrices: is the complete-pivoting growth factor ρ(H) equal to n?

The growth factor ρ(A) of Gaussian elimination measures how large intermediate matrix entries can become relative to the input, and it is the quantity controlling the backward error of LU factorization. For Gaussian elimination with complete pivoting (GECP), Colin Cryer conjectured in 1968 that every n×n Hadamard matrix (a ±1 matrix with orthogonal columns, HH^T = nI) has growth factor exactly ρ(H) = n. The conjecture is proven for the Sylvester equivalence class at every order and for all Hadamard matrices of order at most 16; at order 20 the first six pivot values are completely characterized and over a thousand pivot patterns are known computationally; no counterexample is known. The general statement remains open. Peca-Medlin's 2026 study of butterfly matrices computes exact GECP growth for structured butterfly matrices and shows that (Sylvester-equivalent) Hadamard matrices are the growth-maximizing points of the simple butterfly class. The problem: prove that every Hadamard matrix has GECP growth factor equal to its order, or produce a Hadamard matrix whose exact-arithmetic growth factor differs from n.

Background

Gaussian elimination (GE) transforms a matrix $A\in\mathbb{R}^{n\times n}$ into an LU factorization by repeatedly eliminating entries below the diagonal. To keep the computation stable in floating-point arithmetic, elimination is combined with a pivoting strategy that permutes rows (and possibly columns) so that each division is by a relatively large pivot. With partial pivoting (GEPP) only rows are swapped, choosing at each step the largest-magnitude entry in the current column; with complete pivoting (GECP) both a row and a column are swapped so that the pivot is a largest-magnitude entry of the entire remaining untriangularized submatrix, giving a factorization $PAQ=LU$ with permutation matrices $P$ and $Q$. The quantity controlling the backward error of the computed solution is the growth factor

$$\rho(A)=\frac{\max_{k}\|A^{(k)}\|_{\max}}{\|A\|_{\max}},$$

where $A^{(k)}$ is the intermediate matrix after $k-1$ elimination steps and $\|C\|_{\max}=\max_{i,j}|C_{ij}|$: for a solve $A\mathbf{x}=\mathbf{b}$, the relative error of the computed solution satisfies a bound of the form $4n^{2}\epsilon_{\mathrm{machine}}\,\kappa_{\infty}(A)\,\rho(A)$, where $\kappa_{\infty}(A)=\|A\|_{\infty}\|A^{-1}\|_{\infty}$ is the condition number of $A$ and $\epsilon_{\mathrm{machine}}$ the machine precision. Under GECP the largest intermediate entry equals the largest pivot, so $\rho(A)=\max_{j}|U_{jj}|/|U_{11}|$.

The growth problem asks for the largest growth factor achievable by $n\times n$ matrices under a given pivoting strategy. Wilkinson (1961) settled the GEPP case (worst case $2^{n-1}$, attained), but for GECP only bounds are known: his upper bound $n^{0.25\log n(1+o(1))}$ stood for six decades until Bisain, Edelman, and Urschel (2025) improved it to $n^{0.2079\log n(1+o(1))}$, while the best lower bounds are linear in $n$ (Edelman and Urschel, 2024). The exact GECP maximum is known only for $n\le 4$ (values $1,2,2.25,4$); for $n=5$ the best upper bound is $4.84$, and the conjectured exact maximum $\approx 4.1325$ was recently identified as a root of a degree-61 polynomial (Chen, Edelman, and Urschel, 2026). For roughly three decades it was believed that GECP growth never exceeds $n$ and that equality is attained only by Hadamard matrices; Gould (1991) exhibited a floating-point $13\times13$ matrix with growth $\approx 13.0205$, and Edelman (1992) confirmed it in exact arithmetic, disproving the unrestricted belief — but leaving the bound $\rho\le n$ intact for the Hadamard (and orthogonal) class itself.

A Hadamard matrix $H$ of order $n$ is a $\pm1$ matrix with mutually orthogonal columns, $HH^{\top}=nI_n$; such matrices can exist only for $n=1,2$ or $n$ divisible by 4, and the conjecture that they exist for every multiple of 4 is itself a famous open problem (the smallest order with no known Hadamard matrix is 768; Đoković constructed one of order 764 in 2008). Hadamard matrices are extremal for the determinant (Hadamard's bound) and are the natural worst-case candidates for pivoting, since all entries already have maximal magnitude $1$ and yet elimination can still amplify entries. Cryer (1968) conjectured that the growth factor of an $n\times n$ Hadamard matrix is exactly $n$; since $\|H\|_{\max}=1$ and the first pivot is $1$, the conjecture asserts $\rho(H)=\max_{j}|U_{jj}|=n$ for every Hadamard matrix of every order.

The conjecture is invariant under Hadamard equivalence — simultaneous row/column permutations and row/column negations (signed permutation matrices $P_1,P_2$ with $P_1H_1=H_2P_2$), which relabel or sign-flip the elimination process without changing pivot magnitudes — so it can be pursued equivalence class by equivalence class. It is proven for: the Sylvester class (the Kronecker powers $\bigotimes^{k}\begin{bmatrix}1&1\\1&-1\end{bmatrix}$ and their equivalents) at every order (Day and Peterson, 1988); order 12 (Edelman and Mascarenhas, 1995); and order 16, all five equivalence classes (Kravvaritis and Mitrouli, 2009). Kravvaritis and Mitrouli (2012) added structural results — the leading principal minors of a completely pivoted Hadamard matrix form an increasing sequence, bounds for the sixth and seventh pivots, and a "good pivots" property that forces growth equal to the order — and at order 20 the complete lists of possible values for the first six pivots, together with at least 1246 computationally found pivot patterns, are now known (Lardas and Mitrouli, 2025). The technical bottleneck is that pivots of a completely pivoted matrix are ratios of leading principal minors, so certifying possible pivot values requires exhaustive minor computations that currently stall between orders 16 and 20, while the number of equivalence classes explodes (60 at order 24, 487 at order 28, 13,710,027 at order 32).

The source paper (Peca-Medlin, 2026) approaches this circle of questions through butterfly matrices — Kronecker-structured products of $2\times2$ rotation blocks introduced as random preconditioners intended to make pivoting unnecessary. For the simple scalar butterfly class $\operatorname{B}_{s}(N)$, $N=2^{n}$, the paper proves that under a monotonicity condition on the input angles the GECP, GEPP, rook-pivoting (a strategy that selects a pivot maximal in both its row and its column), and no-pivoting factorizations coincide, and the growth factor is exactly $\rho(B(\boldsymbol{\theta}))=\prod_{j=1}^{n}\max(|\sec\theta_{j}|,|\csc\theta_{j}|)^{2}$; the maximum $2^{n}=N$ over this class is attained precisely when all angles are $\pm\pi/4$, where the butterfly matrix is a Sylvester-equivalent Hadamard matrix. This recovers an alternate proof route for the Sylvester case and exhibits Hadamard matrices as the growth-maximizing points of a continuous model, but it leaves the general Hadamard conjecture untouched: as the paper states, for general Hadamard matrices the belief $\rho(H_n)=n$ has only been proven up to $n=16$.

Problem Statement

Let $H$ be an $n\times n$ Hadamard matrix: a matrix with all entries in $\{\pm1\}$ satisfying $HH^{\top}=nI_n$ (so $n=1$, $n=2$, or $n\equiv 0\pmod 4$). Apply Gaussian elimination with complete pivoting in exact arithmetic: at step $k$, choose as pivot a maximum-magnitude entry of the remaining $(n-k+1)\times(n-k+1)$ submatrix (breaking ties by the first maximum in column-major order), swap the corresponding rows and columns into the pivot position, and eliminate, producing $PAQ=LU$. Since $\|H\|_{\max}=1$ and the first pivot is $1$, the growth factor is $\rho(H)=\max_{j}|U_{jj}|$.

Question (Cryer's 1968 growth conjecture for Hadamard matrices): is $\rho(H)=n$ for every Hadamard matrix $H$ of every order $n$?

A single Hadamard matrix whose exact-arithmetic GECP growth factor differs from its order would refute the conjecture.

The growth factor is invariant under row/column permutations and sign changes, so claims may be reduced to Hadamard equivalence classes. A confirmation must cover all equivalence classes of all orders, including orders for which no Hadamard matrix has been constructed; a single valid witness settles the negative direction. The question is posed for the deterministic tie-breaking rule fixed above; an answer that is independent of the tie-breaking rule is also accepted.

References

1. John Peca-Medlin, 'Complete pivoting growth of butterfly matrices and butterfly Hadamard matrices', Linear and Multilinear Algebra 74 (2026) 934–958. DOI: 10.1080/03081087.2026.2660796; arXiv:2410.06477. https://doi.org/10.1080/03081087.2026.2660796 (source paper)
2. C. W. Cryer, 'Pivot size in Gaussian elimination', Numerische Mathematik 12 (1968) 335–345. DOI: 10.1007/BF02162514. https://doi.org/10.1007/BF02162514
3. J. H. Wilkinson, 'Error Analysis of Direct Methods of Matrix Inversion', Journal of the ACM 8 (1961) 281–330. DOI: 10.1145/321075.321076. https://doi.org/10.1145/321075.321076
4. Jane Day and Brian Peterson, 'Growth in Gaussian Elimination', American Mathematical Monthly 95 (1988) 489–513. DOI: 10.1080/00029890.1988.11972038. https://doi.org/10.1080/00029890.1988.11972038
5. Nick Gould, 'On Growth in Gaussian Elimination with Complete Pivoting', SIAM Journal on Matrix Analysis and Applications 12 (1991) 354–361. DOI: 10.1137/0612025. https://doi.org/10.1137/0612025
6. Alan Edelman, 'The Complete Pivoting Conjecture for Gaussian Elimination is False', The Mathematica Journal 2 (1992) 58–61. https://math.mit.edu/~edelman/publications/complete_pivoting.pdf (author's copy; also archived at https://escholarship.org/uc/item/9kd8c36w)
7. Alan Edelman and Walters Mascarenhas, 'On the complete pivoting conjecture for a Hadamard matrix of order 12', Linear and Multilinear Algebra 38 (1995) 181–187. DOI: 10.1080/03081089508818353. https://doi.org/10.1080/03081089508818353
8. Christos Kravvaritis and Marilena Mitrouli, 'The growth factor of a Hadamard matrix of order 16 is 16', Numerical Linear Algebra with Applications 16 (2009) 715–743. DOI: 10.1002/nla.637. https://doi.org/10.1002/nla.637
9. Christos Kravvaritis and Marilena Mitrouli, 'On the complete pivoting conjecture for Hadamard matrices: further progress and a good pivots property', Numerical Algorithms 62 (2012) 571–582. DOI: 10.1007/s11075-012-9643-1. https://doi.org/10.1007/s11075-012-9643-1
10. Christos D. Kravvaritis, 'Hadamard Matrices: Insights into Their Growth Factor and Determinant Computations', in Mathematical Analysis, Approximation Theory and Their Applications, Springer Optimization and Its Applications 111 (2016) 383–415. DOI: 10.1007/978-3-319-31281-1_17. https://doi.org/10.1007/978-3-319-31281-1_17
11. Emmanouil Lardas and Marilena Mitrouli, 'On the growth factor of Hadamard matrices of order 20', Applied Numerical Mathematics 208 (2025) 310–316. DOI: 10.1016/j.apnum.2024.01.019. https://doi.org/10.1016/j.apnum.2024.01.019
12. John Peca-Medlin and Thomas Trogdon, 'Growth Factors of Random Butterfly Matrices and the Stability of Avoiding Pivoting', SIAM Journal on Matrix Analysis and Applications 44 (2023) 945–970. DOI: 10.1137/22M148762X. https://doi.org/10.1137/22M148762X
13. John Peca-Medlin, 'Growth Factors of Orthogonal Matrices and Local Behavior of Gaussian Elimination with Partial and Complete Pivoting', SIAM Journal on Matrix Analysis and Applications 45 (2024) 1599–1620. DOI: 10.1137/23M1597733. https://doi.org/10.1137/23M1597733
14. Alan Edelman and John Urschel, 'Some New Results on the Maximum Growth Factor in Gaussian Elimination', SIAM Journal on Matrix Analysis and Applications 45 (2024) 967–991. DOI: 10.1137/23M1571903. https://doi.org/10.1137/23M1571903
15. Ankit Bisain, Alan Edelman, and John Urschel, 'A new upper bound for the growth factor in Gaussian elimination with complete pivoting', Bulletin of the London Mathematical Society 57 (2025) 1369–1387. DOI: 10.1112/blms.70034. https://doi.org/10.1112/blms.70034
16. James Chen, Alan Edelman, and John Urschel, 'The largest 5th pivot may be the root of a 61st degree polynomial', arXiv:2602.20390 (2026). https://arxiv.org/abs/2602.20390
17. Hadi Kharaghani and Behruz Tayfeh-Rezaie, 'Hadamard Matrices of Order 32', Journal of Combinatorial Designs 21 (2013) 212–221. DOI: 10.1002/jcd.21323. https://doi.org/10.1002/jcd.21323
18. Dragomir Ž. Đoković, 'Hadamard matrices of order 764 exist', Combinatorica 28 (2008) 487–489. DOI: 10.1007/s00493-008-2384-z. https://doi.org/10.1007/s00493-008-2384-z