On the Structure of Bad Science Matrices

Abstract

The bad science matrix problem consists in finding, among all matrices $A\in {\mathbb{R}}^{n\times n}$ with rows having unit ${\ell }^2$ norm, one that maximizes ${\hat{I}}^2(A)=\frac{1}{2^n}{\sum }_{x\in \{-1,1{\}}^n}\Vert Ax{\Vert }_{\infty }$. Our main contribution is an explicit construction of an $n\times n$ matrix $A$ showing that ${\hat{I}}^2(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$.

17 pages, 2 figures. Closest to version to be published in Involve, a Journal of Mathematics