Asymptotically Optimal Multi-Paving

Abstract

Anderson's paving conjecture, now known to hold due to the resolution of the Kadison-Singer problem asserts that every zero diagonal Hermitian matrix admits non-trivial pavings with dimension independent bounds. In this paper, we develop a technique extending the arguments of Marcus, Spielman and Srivastava in their solution of the Kadison-Singer problem to show the existence of non-trivial pavings for collections of matrices. We show that given zero diagonal Hermitian contractions $A^{(1)},\cdots ,A^{(k)}\in M_n(\mathbb{C})$ and $\epsilon >0$, one may find a paving $X_1⨿\cdots ⨿X_r=[n]$ where $r\le 18k{\epsilon }^{-2}$ such that, \[λ_{max} (P_{X_i} A^{(j)} P_{X_i}) < ε, \quad i \in [r], \, j \in [k].\] As a consequence, we get the correct asymptotic estimates for paving general zero diagonal matrices; zero diagonal contractions can be $(O({\epsilon }^{-2}),\epsilon )$ paved. As an application, we give a simplified proof wth slightly better estimates of a theorem of Johnson, Ozawa and Schechtman concerning commutator representations of zero trace matrices.

23 pages. In the previous version, we had erroneously claimed that the main theorem in this paper implies a polylogarithmic bound in the commutator theorem of Johnson, Ozawa and Schechtman. This has been corrected with a weaker bound. The main results in the paper are unchanged