Average-case matrix discrepancy: satisfiability bounds

Given a sequence of $d \times d$ symmetric matrices $\{\mathbf{W}_i\}_{i=1}^n$, and a margin $Δ> 0$, we investigate whether it is possible to find signs $(ε_1, \dots, ε_n) \in \{\pm 1\}^n$ such that the operator norm of the signed sum satisfies $\|\sum_{i=1}^n ε_i \mathbf{W}_i\|_\mathrm{op} \leq Δ$. Kunisky and Zhang (2023) recently introduced a random version of this problem, where the matrices $\{\mathbf{W}_i\}_{i=1}^n$ are drawn from the Gaussian orthogonal ensemble. This model can be seen as a random variant of the celebrated Matrix Spencer conjecture and as a matrix-valued analog of the symmetric binary perceptron in statistical physics. In this work, we establish a satisfiability transition in this problem as $n, d \to \infty$ with $n / d^2 \to τ> 0$. Our contributions are twofold. First, we prove that the expected number of solutions with margin $Δ=κ\sqrt{n}$ has a sharp threshold at a critical $τ_1(κ)$: for $τ< τ_1(κ)$ the problem is typically unsatisfiable, while for $τ> τ_1(κ)$ the average number of solutions becomes exponentially large. Second, combining a second-moment method with recent results from Altschuler (2023) on margin concentration in perceptron-type problems, we identify a second threshold $τ_2(κ)$, such that for $τ>τ_2(κ)$ the problem admits solutions with high probability. In particular, we establish for the first time that a system of $n = Θ(d^2)$ Gaussian random matrices can be balanced so that the spectrum of the resulting matrix macroscopically shrinks compared to the typical semicircle law. Our proofs rely on deriving concentration inequalities and large deviation properties for the law of correlated Gaussian matrices under spectral norm constraints, extending results in the literature and offering insights of independent interest.