Submit progress

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

The statement

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]

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.