A lower bound for the Balan--Jiang matrix problem

Abstract

We prove the existence of a positive semidefinite matrix $A\in {\mathbb{R}}^{n\times n}$ such that any decomposition into rank-1 matrices has to have factors with a large ${\ell }^1-$norm, more precisely $$\sum _k{x}_k{x}_k^{\ast }=A⟹\sum _k\Vert x_k{\Vert }_1^2\ge c\sqrt{n}\Vert A{\Vert }_1,$$ where $c$ is independent of $n$. This provides a lower bound for the Balan--Jiang matrix problem. The construction is probabilistic.