A Note on Approximate Hadamard Matrices

Abstract

A Hadamard matrix is a scaled orthogonal matrix with $\pm 1$ entries. Such matrices exist in certain dimensions: the Hadamard conjecture is that such a matrix always exists when $n$ is a multiple of 4. A conjecture attributed to Ryser is that no circulant Hadamard matrices exist when $n>4$. Recently, Dong and Rudelson proved the existence of approximate Hadamard matrices in all dimensions: there exist universal $0<c<C<\infty$ so that for all $n\ge 1$, there is a matrix $A\in {\left\{-1,1\right\}}^{n\times n}$ satisfying, for all $x\in {\mathbb{R}}^n$, $$c\sqrt{n}\Vert x{\Vert }_2\le \Vert Ax{\Vert }_2\le C\sqrt{n}\Vert x{\Vert }_2.$$ We observe that, as a consequence of the existence of flat Littlewood polynomials, circulant approximate Hadamard matrices exist for all $n\ge 1$.