Aug 2026· 2 citations· ⚡ 1 influential· 24 references
Mathematics
Abstract
We develop a novel approach to matrix discrepancy based on matrix small-ball estimates. Specifically, we use a determinantal weight (obtained from the log-barrier) to scale the small-ball probability into a partition function of a tilt of the Gaussian measure. We then employ matrix-weighted Poincar\'e inequalities to compare this partition function to that of a pinched or diagonal part of the matrix, obtaining \emph{dimension-free} constants. Our technique yields a hereditary small-ball estimate for Gaussian series that should be of independent interest. As the main application, we resolve the Matrix Spencer conjecture: for symmetric $n\times n$ matrices $A_1,\dots,A_n$ with $\|A_i\|\le1$, one can efficiently find a coloring $x\in\{\pm1\}^n$ with $\|\sum_{i=1}^n x_iA_i\|=O(\sqrt n)$.
The potential measures a soft spectral edge of the evolving discrepancy matrix perturbed by an operator-valued free semicircular element and combines Lehner's variational formula for the free edge with spectral Tsallis regularization, putting the discrepancy and remaining covariance in a single smooth optimization prob...
Harwit and Sloane conjectured that every nonsingular entrywise-nonnegative matrix $A\in\mathbb R^{n\times n}$ satisfies $\|A^{-1}\|_F\ge 2n(n+1)^{-1}\|A\|_{\max}^{-1}$, with equality precisely for positive multiples of $S$-matrices. Cheng proved the conjecture in odd dimensions, while Frankel and Urschel proved the eve...
A deterministic algorithm that finds signs with $\|A\varepsilon\|_\infty<99$ using $O(mn+n^{\omega+2}\log^3 n)$ arithmetic operations, where $\omega>2$ is any fixed attainable matrix-multiplication exponent; with the current bounds on $\omega$ this is $\widetilde O(mn+n^{4.372})$.
We study the distribution of the zeros of $\det P_N(z)$ where $P_N(z)$ is a random monic polynomial matrix, i.e., $P_N(z)=z^dI-\sum_{j=0}^{d-1}A_{j,N}z^j$ for possibly coupled random matrices $A_{j,N}$, scaled to have entrywise variance $O(1/N)$. We provide general conditions under which this distribution almost-surely...
Let $d_n=(n-1)^2+1$, the dimension of the real linear span of the $n\times n$ permutation matrices. We prove that $d_n$ independent uniformly random permutation matrices are linearly independent with probability $1-O(n^{-1/2})$. Conditioning on distinctness gives the same conclusion for a uniformly random $d_n$-element...
We consider the probability that a discrete random matrix $M_n(\xi)$ is \emph{strongly non-singular}, meaning all its leading principal submatrices are non-singular. This property is equivalent to the existence of an LU factorization. We show that for any discrete random variable $\xi$ with finite support and $|\xi|_\i...
S. Mateo, John Urschel, Nicholas West· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
