Parity obstructions for the conditioning of sign matrices
Recorded by the registry's curators from GitHub; the authors did not submit it here.
Matthew J. Colbrook
For every odd $n$, every nonsingular $n\times n$ sign matrix satisfies $\kappa_2(A)\ge\sqrt{1+(n-1)/n^2}+\sqrt{n-1}/n$. Hence $h(n)-1\ge\sqrt{n-1}/n$ along the odd orders, and the optimal uniform decay exponent satisfies $\alpha_*\le1/2$. The proof bounds the variance $v$ of the eigenvalues of the Gram matrix $A^TA$, whose mean is $n$, by $n^2(\kappa^2-1)^2/(4\kappa^2)$, and uses parity: for odd $n$ every off-diagonal Gram entry is an odd integer, so $v\ge n-1$. For $n\equiv2\pmod4$, no three columns are pairwise orthogonal, so the orthogonality graph is triangle-free; at least $n(n-2)/4$ column pairs then have nonzero even inner products, giving $\kappa_2(A)\ge\sqrt{1+2(n-2)/n^2}+\sqrt{2(n-2)}/n$. With the known construction exponent, $17/92\le\alpha_*\le1/2$; the exact value and a matching construction remain open.
Claims
Files and sources
- Paper
- OpenProblemsInNLA @ eb7c9d6, IS-05/solution.pdf ↗
- Posted on GitHub
- 11 September 2026
No verification run is on record for this version.