Block Complexity and Idempotent Schur Multipliers

Abstract We call a matrix blocky if, up to row and column permutations, it can be obtained from an identity matrix by repeatedly applying one of the following operations: duplicating a row, duplicating a column, or adding a zero row or column. Blocky matrices are precisely the boolean matrices that are contractive when considered as Schur multipliers. It is conjectured that any boolean matrix with Schur multiplier norm at most $\gamma $ is expressible as a signed sum $$ \begin{align*}&A = \sum_{i=1}^{L} \pm B_{i}\end{align*} $$ for some blocky matrices $B_{i}$, where $L$ depends only on $\gamma $. This conjecture is an analogue of Green and Sanders’ quantitative version of Cohen’s idempotent theorem. In this paper, we prove bounds on $L$ that are polylogarithmic in the dimension of $A$. Concretely, if $A$ is an $n\times n$ matrix, we show that one may take $L = 2^{O(\gamma ^{7})} \log (n)^{2}$.