A Note on Approximate Hadamard Matrices

A Hadamard matrix is a scaled orthogonal matrix with ± 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 < ∞ so that for all n ≥ 1, there is a matrix A ∈ \-1,1 × n satisfying, for all x ∈ Rⁿ, c √n \|x\|₂ ≤ \|Ax\|₂ ≤ C √n \|x\|₂. We observe that, as a consequence of the existence of flat Littlewood polynomials, circulant approximate Hadamard matrices exist for all n ≥ 1.