A condition number of two for a sign matrix in every dimension
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$. Then $h(n) \ge 1$, with equality exactly when a Hadamard matrix of order $n$ exists. Dong and Rudelson showed that $h$ is bounded, and Alexeev, Jasper and Mixon that $h(n) \to 1$ as $n \to \infty$, so $h(n) \le 2$ for all but finitely many $n$. Since $h(3) = 2$, the problem asks whether $h(n) \le 2$ for every $n$. It suffices to consider odd $n$: Kronecker products with a $2 \times 2$ Hadamard matrix give $h(2n) \le h(n)$ (Alexeev, Jasper and Mixon).
Problem. Is $\sup_{n \ge 1} h(n) = 2$?
Source: Alexeev, Jasper and Mixon (2025), Problem 12, which asks for sup h(n), the optimal form of Dong and Rudelson's (2024) bound; the authors believe it is 2.
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},
}
@article{dong2024,
author = {Dong, Xiaoyu and Rudelson, Mark},
title = {Approximately {H}adamard matrices and {R}iesz bases in random frames},
journal = {Int. Math. Res. Not. IMRN},
volume = {2024},
number = {3},
year = {2024},
pages = {2044--2065},
doi = {10.1093/imrn/rnad080},
eprint = {2207.07523},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-is04,
author = {Townsend, Alex},
title = {{IS-04}: A condition number of two for a sign matrix in every dimension},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/eigenvalues-and-inverse-problems/IS-04/README.md},
note = {Read at commit 7336302, 2026-10-06},
}
Resolution claims
For each odd prime $p\ge13$, an explicit real sign matrix $A_p$ of order $p^2$ is built as a convolution matrix over the additive group $\mathbb F_p^2$. Its kernel is the quadratic character of the anisotropic form $x^2-dy^2$, with $d$ a nonsquare, with the origin filled and with the signs flipped on the quadratic-residue points of a parabola on which the …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Open → Partially resolved | The registry's curators | Explicit odd-order sign matrices with condition numbers tending to one v1 recorded from OpenProblemsInNLA @ eb7c9d6, manuscripts/IS-04-explicit-odd-family-partial.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00149, "A condition number of two for a sign matrix in every dimension", clopen.solutions.