Minimal condition number decay for sign matrices ($C_{23b}$)

• 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 (from the repository page)

• [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}$.”

Repository table (commit 2c1968c, 26 September 2026): best known lower bound $\frac{17}{92}$; best known upper bound 1. Values marked with an asterisk have minimal verification.

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]

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]