On the Structure of Bad Science Matrices

The bad science matrix problem consists in finding, among all matrices $A\in {\mathbb{R}}^{n\times n}$ with rows having unit ${\mathrm{\ell }}^2$ norm, one that maximizes $\beta (A)=\frac{1}{2^n}{\sum }_{x\in \{-1,1{\}}^n}\mathrm{\parallel }Ax{\mathrm{\parallel }}_{\mathrm{\infty }}$. Our main contribution is an explicit construction of an $n\times n$ matrix $A$ showing that $\beta (A)\ge \sqrt{{\log }_2(n+1)}$, which is only 18% smaller than the asymptotic rate. We prove that every entry of any optimal matrix is a square root of a rational number, and we find provably optimal matrices for $n\le 4$.