Welcome, and Matrix Discrepancy (problems 1-2)

Welcome to Randomstrasse101, a math blog based out of a nearly homonymous address (see more at the About). As there will be a special emphasis on open problems, I chose to start with one of my favourites.

Conjecture 1 (Matrix Spencer)

There exists a positive universal constant $C$ such that, for all positive integers $n$, and all choices of $n$ self-adjoint $n\times n$ real matrices $A_1,\dots,A_n$ satisfying, for all $i\in[n]$, $\|A_i\|\leq 1$ (where $\|\cdot\|$ denotes the spectral norm) the following holds \begin{equation}\label{eq:matrixspencerbound} \min_{\varepsilon \in \{\pm1\}}^n \left\| \sum_{i=1}^n\varepsilon_iA_i\right\|\leq C\sqrt{n}. \end{equation}

I first learned about this question from Nikhil Srivastava at ICM 2014, who pointed me to this very nice blog post of Meka (Meka, 2014). To the best of my knowledge the question first appeared in a paper of Zouzias (Zouzias, 2012). I have also written about it in (Bandeira, 2016) and more recently in (Bandeira, 2024).

The non-commutative Khintchine inequality (or a matrix concentration inequality) gives the bound up to a $\sqrt{\log n}$ factor.

In the particular case of commutative matrices, one can simultaneously diagonalize the matrices and the question reduces to a vector problem (representing the diagonal of the respective matrices) where the spectral norm is replaced by the $\ell_\infty$ norm. This is precisely the setting of Joel Spencer’s celebrated “Six Standard Deviations Suffice” theorem (Spencer, 1985) which establishes the conjecture in that setting, for $C=6$. It is noteworthy that in the commutative setting a random choice does not give \eqref{eq:matrixspencerbound}, the argument is of entropic nature. In a sense, in the other extreme situation in which the matrices behave “very non-commutatively” (or, more precisely, “freely”) we know that a random choice of signs works, from our (myself, Boedihardjo, and van Handel) recent work on matrix concentration (A. S. Bandeira et al., 2023). The fact that the reason for the conjecture to be true in these two extreme situations appears to be so different (one based on entropy the other on concentration), together with the fact that we still do not know if it is true in general makes this (in my opinion) a fascinating question!

In recent work, Hopkins, Raghavendra, and Shetty (Hopkins et al., 2022) has established connections between this problem and Quantum Information, and Dadush, Jiang, and Reis (Dadush et al., 2022) establishes a connection with covering estimates for a certain notion of relative entropy.

More recently, Bansal, Jiang, and Meka (Bansal et al., 2023) has proved Conjecture 1 for low-rank matrices (whose rank is $n$ over a polylog factor) using the matrix concentration inequalities in (A. S. Bandeira et al., 2023) within a very nice decomposition argument.

Motivated by Conjecture 1 and the suspicion that “ammount of commutativity” may play an important role in this question, we (myself, Kunisky, Mixon, and Zeng) proposed a Group theoretic special case of this conjecture in (A. S. Bandeira et al., 2022).

Conjecture 2 (Group Spencer)

Let $G$ be a finite group of size $n$. Conjecture 1 holds in the particular case in which $A_1,\dots,A_n$ are the $n\times n$ matrices corresponding to the regular representation of $G$.

In (A. S. Bandeira et al., 2022) we prove Conjecture 2 for simple groups, but the general case is still open. While the commutative case follows from Spencer’s theorem, giving an explicit construction is not trivial (see this Mathoverflow post).

References

1. Meka, R. (2014). Discrepancy and beating the union bound. Windows On Theory Blog Post. Available at \Urlhttps://Windowsontheory.org/2014/02/07/Discrepancy-and-Beating-the-Union-Bound.
2. Zouzias, A. (2012). A Matrix Hyperbolic Cosine Algorithm and Applications. International Colloquium on Automata, Languages, and Programming.
3. Bandeira, A. S. (2016). Ten Lectures and Forty-Two Open Problems in the Mathematics of Data Science. Available at \Urlhttps://People.math.ethz.ch/ Abandeira/TenLecturesFortyTwoProblems.pdf.
4. Bandeira, A. S. (2024). Ten Open Problems involving Matrices, Randomness, Graphs, and more. Oberwolfach Report for Workshop 2417 (21.04.2024–26.04.2024). Available at \Urlhttps://Publications.mfo.de/Handle/Mfo/4149.
5. Spencer, J. H. (1985). Six standard deviations suffice. Transactions of the American Mathematical Society, 289, 679–706.
6. A. S. Bandeira, M. Boedihardjo, & R. van Handel. (2023). Matrix Concentration Inequalities and Free Probability. Inventiones Mathematicae, 234, 419–487.
7. Hopkins, S. B., Raghavendra, P., & Shetty, A. (2022). Matrix discrepancy from quantum communication. STOC.
8. Dadush, D., Jiang, H., & Reis, V. (2022). A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent. STOC.
9. Bansal, N., Jiang, H., & Meka, R. (2023). Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank. STOC.
10. A. S. Bandeira, Kunisky, D., Mixon, D., & Zeng, X. (2022). On the concentration of Gaussian Cayley matrices. Preprint, Available on ArXiv.