# Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input

Preprint · Zhao Song, Lichen Zhang

- Archive id: arxiv:2609.15025
- Published: 2026-09-14
- arXiv: https://arxiv.org/abs/2609.15025
- Source URL: https://arxiv.org/abs/2609.15025
- PDF: https://arxiv.org/pdf/2609.15025
- Provenance: arxiv

## Abstract

The Matrix Spencer conjecture asserts that for all symmetric matrices $A\_1,\\ldots,A\_n\\in\\mathbb{R}^{n\\times n}$ with $\\\|A\_i\\\|\\le1$ there are signs $\\varepsilon\_1,\\ldots,\\varepsilon\_n\\in\\{-1,1\\}$ with $\\\|\\sum\_{i=1}^n\\varepsilon\_iA\_i\\\|=O(\\sqrt n)$. We prove it: a signing of discrepancy below $8\\sqrt n$ always exists. We also give a randomized algorithm that finds a signing of discrepancy below $12\\sqrt n$ with failure probability at most $p$. The algorithm uses $n^{3+o(1)}\\operatorname{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))\\sqrt{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\\in \\mathbb{R}^n:\\\|\\sum\_ix\_iA\_i\\\|\\le 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\\cdot10^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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.