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

Known lower bounds

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

Contribution notes

Prepared with assistance from ChatGPT 5.2 Pro.