The matrix paving conjecture

About 13 years old · traced to

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 tr⁡Ai≤δ\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=1myiAi∥≤O(δ).\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.

References

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.