Towards a characterization of idempotent Schur multipliers
This provides a partial characterization of idempotent Schur multipliers, advancing the understanding of their structure and connecting to communication complexity.
The authors prove that any boolean matrix with bounded factorization norm can be expressed as a signed sum of a small number of blow-ups of identity matrices, with the number of terms depending only on the norm and the iterated logarithm of the matrix size. This yields that sequences of such matrices lie in the communication complexity class P^EQ.
It is conjectured that every idempotent Schur multiplier can be written as a finite sum of contractive idempotents. This conjecture is equivalent to the statement that any boolean matrix $A$ with factorization norm $\lVert A\rVert_{γ_2}$ at most $γ$ can be expressed as a signed sum $$A = \sum_{i=1}^L \pm B_i,$$ where, up to permutation of rows and columns, each $B_i$ is a blow-up of an identity matrix, and $L$ depends only on $γ$. In this note we show that if $A$ is an $n\times n$ boolean matrix with $\lVert A\rVert_{γ_2} \le γ$, then it admits such an expression with $L = 2^{O(γ^9) + \log^*\! n}$, where $\log^*$ is the iterated logarithm function. As an application, any sequence of matrices with bounded factorization norm belongs to the complexity class $\mathrm{P}^\mathrm{EQ}$ of communication problems with polylogarithmic equality-oracle complexity.