Asymptotically optimal approximate Hadamard matrices

Abstract

An approximate Hadamard matrix is a well-conditioned square matrix with all entries in $\{\pm 1\}$. We measure the quality of a matrix by its condition number, i.e., the ratio of its largest and smallest singular values. We prove that for any fixed positive $\alpha <17/92$, every sufficiently large dimension admits an approximate Hadamard matrix with condition number at most $1+n^{-\alpha }$. In particular, the smallest possible condition number tends to $1$ as $n\to \infty$. Conversely, there exists an absolute constant $c>0$ such that for every sufficiently large $n\not\equiv 0(\mathrm{mod}4)$, every $n\times n$ matrix with entries in $\{\pm 1\}$ has condition number at least $1+c(\log n)/n$. Along the way, we resolve a problem of Jaming and Matolcsi concerning flat orthogonal matrices, and we conclude by describing several explicit infinite families of approximate Hadamard matrices.

See the ancillary files for best known matrices and Lean code