The matrix paving conjecture

Let A1,,AmA_1,\ldots,A_m be Hermitian, positive semi-definite matrices of the same size satisfying

i=1mAi=I\sum_{i=1}^m A_i = I

and trAiδ\operatorname{tr} A_i \leq \delta for all ii. The matrix paving conjecture. There exists y{1,+1}my \in \{-1,+1\}^m such that

i=1myiAiO(δ).\left\|\sum_{i=1}^m y_i A_i\right\| \leq O(\sqrt{\delta}).

This conjecture is presented as a common generalization of the matrix discrepancy statement of Marcus, Spielman, and Srivastava and the diagonal-matrix case of the paper’s theorem. The source does not state that it has been resolved.

Sources & referencesView supporting material

Primary source

Nicholas J. A. Harvey, “A note on the discrepancy of matrices with bounded row and column sums”, arXiv:1307.2159 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.