Asymptotically optimal approximate Hadamard matrices

Abstract

An approximate Hadamard matrix is a well-conditioned square matrix with all entries in $\{\pm1\}$. 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 $α<17/92$, every sufficiently large dimension admits an approximate Hadamard matrix with condition number at most $1+n^{-α}$. 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\equiv0\pmod4$, every $n\times n$ matrix with entries in $\{\pm1\}$ 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.