Asymptotically Optimal Multi-Paving

Anderson's paving conjecture, now known to be true [14], asserts that every zero-diagonal matrix admits a nontrivial paving with dimension independent bounds. We study this problem for a collection of matrices and show that given k zero-diagonal nxn Hermitian matrices A(1),..., A(k) and epsilon > 0 there are diagonal projections P-1,..., P-r with Sigma(j <= r) P-j = I such that ||P(j)A(i)P(j)|| <= epsilon||A(i)|| for i <= k, j <= r, that is, a simultaneous paving of the matrices, with r <= 18k/epsilon(2). As a consequence, we get the optimal asymptotic estimates for paving a single zero-diagonal (not necessarily Hermitian) matrix: every square zero-diagonal complex matrix can be epsilon-paved using O(epsilon(-2)) blocks, improving the previously known bound of O(epsilon(-8)). We use our result to strengthen a result of Johnson-Ozawa-Schechtman on commutator representations of zero trace matrices.