Rate at which $\kappa(n)$ approaches $1$
Description of constant
Given a real matrix $A$, let its condition number be \(\kappa(A):=\frac{\sigma_{\max}(A)}{\sigma_{\min}(A)},\) where $\sigma_{\min}(A)$ and $\sigma_{\max}(A)$ denote the smallest and largest singular values of $A$, respectively (with $\kappa(A)=\infty$ if $\sigma_{\min}(A)=0$). [AJM2025-def-kappaA]
For each positive integer $n$, let \(\kappa(n):=\min_{A\in\{\pm 1\}^{n\times n}}\kappa(A).\) [AJM2025-def-kappan]
Equivalently, $\kappa(n)=1$ precisely when there exists a Hadamard matrix of order $n$. [AJM2025-kappan-hadamard]
Problem 11 of [AJM2025] asks for the optimal decay exponent of $\kappa(n)-1$:
Problem 11. What is the largest $\alpha$ for which \(\kappa(n)=1+\frac{f(n)}{n^\alpha}\) for some subpolynomial $f$? [AJM2025-prob11]
Define $C_{23b}$ to be the largest $\alpha$ for which such a representation holds. [AJM2025-prob11]
Known upper bounds
| Bound on $\alpha$ | Reference | Comments |
|---|---|---|
| $1$ | [AJM2025] | Stated in the discussion of Problem 11. [AJM2025-prob11] (A supporting mechanism is the lower bound $\kappa(n)\ge 1+c\frac{\log n}{n}$ for $n\not\equiv 0 \pmod 4$.) [AJM2025-thm6] |
| $1/2$ | [Pat2026] | For odd $n$ every off-diagonal entry of $G=A^TA$ is odd, so with $\lambda_k$ the eigenvalues of $G$: $\sum(\lambda_k-n)=0$ and $\sum(\lambda_k-n)^2\ge n(n-1)$. The Bhatia–Davis inequality gives $(\lambda_{\max}-n)(n-\lambda_{\min})\ge n-1$, hence $\kappa(A)^2\ge 1+2\sqrt{n-1}/n$ and $\kappa(n)\ge 1+(2-\sqrt2)/\sqrt n$ for every odd $n\ge3$. So $\kappa(n)=1+f(n)/n^\alpha$ with subpolynomial $f$ forces $\alpha\le 1/2$. |
Known lower bounds
| Bound on $\alpha$ | Reference | Comments |
|---|---|---|
| $0$ | Trivial | Take $\alpha=0$ and $f(n)=\kappa(n)-1$. Since $\kappa(n)\to 1$ as $n\to\infty$, $f$ is bounded (hence subpolynomial). [AJM2025-abstract-kappa-to-1] |
| $17/92 \approx 0.18478$ | [AJM2025] | The authors state that (unconditionally) their method permits $\kappa(n)\le 1+\frac{1}{n^\alpha}$ for all sufficiently large $n$ with $\alpha=17/92-\delta$ for any small $\delta>0$. [AJM2025-thm1-alpha] |
Additional comments and links
-
Current range stated by the authors. The paper states \(\frac{17}{92}\le \alpha \le 1.\) [AJM2025-prob11]
-
Dependence on Hadamard-matrix existence gaps. The authors note: “Better upper bounds on gaps between Hadamard matrices will increase this lower bound.” [AJM2025-prob11]
-
Conditional lower bound (Hadamard conjecture). Conditioned on the Hadamard conjecture, the authors state their method permits $\alpha=1/4-\delta$ for any small $\delta>0$. [AJM2025-thm1-alpha] [AJM2025-prob11]
-
[Speculation] Exponent $1/2$ suggested by a structured family. The authors write: “our explicit construction involving symmetric conference matrices suggests taking $\alpha$ to be $1/2$.” [AJM2025-prob11] In particular, they show that whenever a symmetric conference matrix of order $n$ exists, one gets $\kappa(n)=1+O(1/\sqrt{n})$. [AJM2025-conf-kappan]
References
- [AJM2025] Alexeev, Boris; Jasper, John; Mixon, Dustin G. Asymptotically optimal approximate Hadamard matrices. arXiv:2511.14653 (2025). Google Scholar. arXiv PDF.
- [AJM2025-abstract-kappa-to-1]
loc: arXiv v1 PDF p.1, Abstract.
quote: “In this paper, we study approximate Hadamard matrices, that is, well-conditioned $n \times n$ matrices with all entries in $\{\pm 1\}$. We show that the smallest-possible condition number goes to $1$ as $n \to \infty$, and we identify some explicit infinite families of approximate Hadamard matrices.” - [AJM2025-def-kappaA]
loc: arXiv v1 PDF p.1, Section 1 (Introduction).
quote: “Given a real matrix $A$, let $\kappa(A) \in [1,\infty]$ denote the condition number of $A$: \(\kappa(A)=\frac{\sigma_{\max}(A)}{\sigma_{\min}(A)},\) where $\sigma_{\min}(A)$ and $\sigma_{\max}(A)$ denote the smallest and largest singular values of $A$, respectively. (If $\sigma_{\min}(A)=0$, we put $\kappa(A)=\infty$.)” - [AJM2025-def-kappan]
loc: arXiv v1 PDF p.1, Section 1 (Introduction).
quote: “For each positive integer $n$, let $\kappa(n)$ denote the smallest possible condition number of an $n \times n$ matrix with all entries in $\{\pm1\}$, that is, $ \kappa(n):=\min_{A\in{\pm 1}^{n\times n}}\kappa(A). $” - [AJM2025-kappan-hadamard]
loc: arXiv v1 PDF p.1, Section 1 (Introduction).
quote: “Observe that $\kappa(n)\ge 1$, with equality precisely when there exists a Hadamard matrix of order $n$.” -
[AJM2025-thm1-alpha]
loc: arXiv v1 PDF p.2, Section 2 (Upper bound), Theorem 1 and following paragraph.
quote: “Theorem 1. There exists $\alpha>0$ such that $\kappa(n)\le 1+\frac{1}{n^\alpha}$ for all sufficiently large $n$.As we will see, with known constructions of Hadamard matrices, we can take $\alpha=\frac{17}{92}-\delta$ for any small $\delta>0$, while conditioned on the Hadamard conjecture, we can take $\alpha=\frac{1}{4}-\delta$.”
- [AJM2025-thm6]
loc: arXiv v1 PDF p.5, Section 3 (Lower bound), Theorem 6.
quote: “Theorem 6. There exists $c>0$ such that $\kappa(n)\ge 1+\frac{c\log n}{n}$ for all sufficiently large $n\not\equiv 0 \bmod 4$.” -
[AJM2025-conf-kappan]
loc: arXiv v1 PDF p.6, Section 4 (Explicit approximate Hadamard matrices), Lemma 10 and following paragraph.
quote: “Lemma 10. Given a symmetric conference matrix $C\in\mathbb{R}^{n\times n}$, it holds that $\kappa(C+I)=\frac{\sqrt{n-1}+1}{\sqrt{n-1}-1}$.Notably, this implies $\kappa(n)=1+O\bigl(\frac{1}{\sqrt{n}}\bigr)$ whenever there exists a symmetric conference matrix of order $n$.”
-
[AJM2025-prob11]
loc: arXiv v1 PDF p.10, Section 6 (Discussion), Problem 11 and following sentences.
quote: “Problem 11. What is the largest $\alpha$ for which $\kappa(n)=1+\frac{f(n)}{n^\alpha}$ for some subpolynomial $f$?We currently know that $\frac{17}{92}\le \alpha \le 1$. Better upper bounds on gaps between Hadamard matrices will increase this lower bound, but with our proof technique, the Hadamard conjecture only increases the lower bound to $\frac{1}{4}$. Meanwhile, our explicit construction involving symmetric conference matrices suggests taking $\alpha$ to be $\frac{1}{2}$.”
- [AJM2025-abstract-kappa-to-1]
- [Pat2026] Patankar, V. Rigorous lower bounds for constants 16a, 20a, 20c and 70a, and an upper bound for 23b, with verification scripts. GitHub repository (2026): https://github.com/vidigoat/optimization-records/tree/main/tao.
Contribution notes
Prepared with assistance from ChatGPT 5.2 Pro. The bound from [Pat2026] was found with search and proof assistance from Claude (Anthropic); its value is recomputed by the scripts linked in that reference.