The optimal decay exponent for the conditioning of sign matrices
For $n \ge 1$ let $$h(n) = \min_{A \in \{-1, 1\}^{n \times n}} \kappa_2(A), \qquad \kappa_2(A) = \frac{\sigma_{\max}(A)}{\sigma_{\min}(A)},$$ with $\kappa_2(A) = +\infty$ for singular $A$, so that $h(n) = 1$ exactly when a Hadamard matrix of order $n$ exists. Alexeev, Jasper and Mixon proved that for every fixed $0 < \alpha < 17/92$, $h(n) \le 1 + n^{-\alpha}$ for all sufficiently large $n$, and that there is an absolute constant $c > 0$ with $h(n) \ge 1 + c(\log n)/n$ for all sufficiently large $n \not\equiv 0 \pmod 4$.
Problem. Determine $$\alpha_* = \sup\{\alpha \ge 0 : \text{there is } C > 0 \text{ with } h(n) - 1 \le C n^{-\alpha} \text{ for every } n \ge 1\}.$$
Source: Alexeev, Jasper and Mixon (2025), Problem 11, which asks for the largest α with h(n) = 1 + f(n)/n^α for some subpolynomial f; in this form, OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- CO — Combinatorics
- Secondary
- NA
- Keywords
- approximate Hadamard matrices, condition numbers, OpenProblemsInNLA, sign matrices
- Literature checked
- Oct. 7, 2026 by clemens-admin
References
@misc{alexeev2025,
author = {Alexeev, Boris and Jasper, John and Mixon, Dustin G.},
title = {Asymptotically optimal approximate {H}adamard matrices},
year = {2025},
eprint = {2511.14653},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-is05,
author = {Townsend, Alex},
title = {{IS-05}: The optimal decay exponent for the conditioning of sign matrices},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/eigenvalues-and-inverse-problems/IS-05/README.md},
note = {Read at commit 7336302, 2026-10-06},
}
Resolution claims
For every odd $n$, every nonsingular $n\times n$ sign matrix satisfies $\kappa_2(A)\ge\sqrt{1+(n-1)/n^2}+\sqrt{n-1}/n$. Hence $h(n)-1\ge\sqrt{n-1}/n$ along the odd orders, and the optimal uniform decay exponent satisfies $\alpha_*\le1/2$. The proof bounds the variance $v$ of the eigenvalues of the Gram matrix $A^TA$, whose mean is $n$, by $n^2(\kappa^2-1)^2/(4\kappa^2)$, and uses parity: for odd $n$ every off-diagonal Gram entry is an odd integer, …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Open → Partially resolved | The registry's curators | Parity obstructions for the conditioning of sign matrices v1 recorded from OpenProblemsInNLA @ eb7c9d6, IS-05/solution.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00150, "The optimal decay exponent for the conditioning of sign matrices", clopen.solutions.