Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input
Abstract
The Matrix Spencer conjecture asserts that for all symmetric matrices A1,…,An∈ℝn× n with |Ai|≤1 there are signs ε1,…,εn∈{−1,1} with |∑i=1nεiAi|=O(√n). We prove it: a signing of discrepancy below 8√n always exists. We also give a randomized algorithm that finds a signing of discrepancy below 12√n with failure probability at most p. The algorithm uses n3+o(1)polylog(1/p) arithmetic operations in the real-arithmetic model. This matches the size n3 of the dense input up to subpolynomial factors. In the other direction, we prove that for every n there are collections of symmetric matrices such that every signing has discrepancy at least (2−o(1))√n. We present three different proofs of the matrix Spencer conjecture. The key to every proof is a hereditary small-ball estimate. This is a lower bound on the Gaussian measure of the spectral body {x∈ ℝn:|∑ixiAi|≤ R} that holds for every subfamily of the matrices. The other ingredient turns that Gaussian measure into a partial signing. We give three approaches to obtain such a signing. The first one covers the cube by partially signed faces through Gaussian concentration with a constant 7·109. The second proof replaces the covering by a projection lemma with explicit parameters for a constant $156000$. The third proof turns Gaussian measure into signs by a lossless coding, with no union bound. It proves the estimate at the right radius with smooth spectral barriers and certified coefficients. It gives a constant below $7.88$. For algorithms, the main idea is to project Gaussian points onto a smoothed spectral body. The n3+o(1) time algorithm tracks the Gibbs matrix of that body across coordinate-descent steps with sketched increments and random refreshes.
Related
- Three Standard Deviations Suffice While One Does Not
- A simpler proof of the Matrix Spencer Theorem
- A Proof of the Matrix Spencer Conjecture
- Large deviations of spectral determinants of matrix-valued random Schrödinger operators and Dyson Brownian motion in cubic potentials
- On the Gram matrix of standard inner products of asymmetrically-weighted Hermite functions
BibTeX
@misc{song2026matrix,
title = {{Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input}},
author = {Zhao Song and Lichen Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15025},
eprint = {2609.15025},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15025},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input
AU - Zhao Song
AU - Lichen Zhang
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2609.15025
UR - https://arxiv.org/abs/2609.15025
AB - The Matrix Spencer conjecture asserts that for all symmetric matrices A_1,…,A_n∈ℝ^n× n with |A_i|≤1 there are signs ε_1,…,ε_n∈{−1,1} with |∑_i=1^nε_iA_i|=O(√n). We prove it: a signing of discrepancy below 8√n always exists. We also give a randomized algorithm that finds a signing of discrepancy below 12√n with failure probability at most p. The algorithm uses n^3+o(1)polylog(1/p) arithmetic operations in the real-arithmetic model. This matches the size n^3 of the dense input up to subpolynomial factors. In the other direction, we prove that for every n there are collections of symmetric matrices such that every signing has discrepancy at least (2−o(1))√n. We present three different proofs of the matrix Spencer conjecture. The key to every proof is a hereditary small-ball estimate. This is a lower bound on the Gaussian measure of the spectral body {x∈ ℝ^n:|∑_ix_iA_i|≤ R} that holds for every subfamily of the matrices. The other ingredient turns that Gaussian measure into a partial signing. We give three approaches to obtain such a signing. The first one covers the cube by partially signed faces through Gaussian concentration with a constant 7·10^9. The second proof replaces the covering by a projection lemma with explicit parameters for a constant $156000$. The third proof turns Gaussian measure into signs by a lossless coding, with no union bound. It proves the estimate at the right radius with smooth spectral barriers and certified coefficients. It gives a constant below $7.88$. For algorithms, the main idea is to project Gaussian points onto a smoothed spectral body. The n^3+o(1) time algorithm tracks the Gibbs matrix of that body across coordinate-descent steps with sketched increments and random refreshes.
ER -