The Littlewood-Offord Problem and invertibility of random matrices
Skip to main content
eScholarship
Open Access Publications from the University of California

Department of Mathematics

Faculty bannerUC Davis

The Littlewood-Offord Problem and invertibility of random matrices

Published Web Location

https://arxiv.org/pdf/math/0703503.pdf
No data is associated with this publication.
Abstract

We prove two basic conjectures on the distribution of the smallest singular value of random n times n matrices with independent entries. Under minimal moment assumptions, we show that the smallest singular value is of order n^{-1/2}, which is optimal for Gaussian matrices. Moreover, we give a optimal estimate on the tail probability. This comes as a consequence of a new and essentially sharp estimate in the Littlewood-Offord problem: for i.i.d. random variables X_k and real numbers a_k, determine the probability P that the sum of a_k X_k lies near some number v. For arbitrary coefficients a_k of the same order of magnitude, we show that they essentially lie in an arithmetic progression of length 1/p.

Item not freely available? Link broken?
Report a problem accessing this item