Average‐Case Matrix Discrepancy: Satisfiability Bounds

ABSTRACT Given a sequence of symmetric matrices , and a margin , we investigate whether it is possible to find signs such that the operator norm of the signed sum satisfies . Kunisky and Zhang (2023) recently introduced a random version of this problem, where the matrices 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 (SBP) in statistical physics. In this work, we establish a satisfiability transition in this problem as with . Our main results are twofold. First, we prove that the expected number of solutions with margin has a sharp threshold at a critical : for the problem is typically unsatisfiable, while for 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 , such that for the problem admits solutions with high probability. In particular, we establish that a system of Gaussian random matrices can be balanced so that the spectrum of the resulting matrix macroscopically shrinks compared to the typical semicircle law. Finally, under a technical assumption, we show that there exist values of for which the number of solutions has large variance, implying the failure of the second‐moment method and uncovering a richer picture than in the vector‐analog SBP problem. Our proofs rely on concentration inequalities and large deviation properties for the law of correlated Gaussian matrices under spectral norm constraints.