From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices

Tao, Terence; Vu, Van

doi:10.1090/S0273-0979-09-01252-X

From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices

Authors: Terence Tao and Van Vu
Journal: Bull. Amer. Math. Soc. 46 (2009), 377-396
MSC (2000): Primary 15A52, 60G50
DOI: https://doi.org/10.1090/S0273-0979-09-01252-X
Published electronically: February 24, 2009
MathSciNet review: 2507275
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The famous circular law asserts that if $M_n$ is an $n \times n$ matrix with iid complex entries of mean zero and unit variance, then the empirical spectral distribution of the normalized matrix $\frac {1}{\sqrt {n}} M_n$ converges both in probability and almost surely to the uniform distribution on the unit disk $\{ z \in \mathbf {C}: |z| \leq 1 \}$. After a long sequence of partial results that verified this law under additional assumptions on the distribution of the entries, the circular law is now known to be true for arbitrary distributions with mean zero and unit variance. In this survey we describe some of the key ingredients used in the establishment of the circular law at this level of generality, in particular recent advances in understanding the Littlewood-Offord problem and its inverse.

Ludwig Arnold, On the asymptotic distribution of the eigenvalues of random matrices, J. Math. Anal. Appl. 20 (1967), 262–268. MR 217833, DOI https://doi.org/10.1016/0022-247X%2867%2990089-3
L. Arnold, On Wigner’s semicircle law for the eigenvalues of random matrices, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 19 (1971), 191–198. MR 348820, DOI https://doi.org/10.1007/BF00534107
Z. D. Bai, Circular law, Ann. Probab. 25 (1997), no. 1, 494–529. MR 1428519, DOI https://doi.org/10.1214/aop/1024404298

BS Z. D. Bai and J. Silverstein, Spectral analysis of large dimensional random matrices, Mathematics Monograph Series 2, Science Press, Beijing 2006.

Lloyd N. Trefethen and David Bau III, Numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1444820
Kevin P. Costello, Terence Tao, and Van Vu, Random symmetric matrices are almost surely nonsingular, Duke Math. J. 135 (2006), no. 2, 395–413. MR 2267289, DOI https://doi.org/10.1215/S0012-7094-06-13527-5

CV1 K. Costello and V. Vu, The ranks of random graphs, to appear in Random Structures and Algorthms.

CV2 K. Costello and V. Vu, Concentration of random determinants and permanent estimators, submitted.

Percy Deift, Universality for mathematical and physical systems, International Congress of Mathematicians. Vol. I, Eur. Math. Soc., Zürich, 2007, pp. 125–152. MR 2334189, DOI https://doi.org/10.4171/022-1/7
R. Brent Dozier and Jack W. Silverstein, On the empirical distribution of eigenvalues of large dimensional information-plus-noise-type matrices, J. Multivariate Anal. 98 (2007), no. 4, 678–694. MR 2322123, DOI https://doi.org/10.1016/j.jmva.2006.09.006

chat S. Chatterjee, A simple invariance principle. [arXiv:math/0508213]

Alan Edelman, The probability that a random real Gaussian matrix has $k$ real eigenvalues, related distributions, and the circular law, J. Multivariate Anal. 60 (1997), no. 2, 203–232. MR 1437734, DOI https://doi.org/10.1006/jmva.1996.1653
P. Erdös, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898–902. MR 14608, DOI https://doi.org/10.1090/S0002-9904-1945-08454-7
Paul Erdos and Leo Moser, Elementary Problems and Solutions: Solutions: E736, Amer. Math. Monthly 54 (1947), no. 4, 229–230. MR 1526680, DOI https://doi.org/10.2307/2304711
G. A. Freĭman, Foundations of a structural theory of set addition, American Mathematical Society, Providence, R. I., 1973. Translated from the Russian; Translations of Mathematical Monographs, Vol 37. MR 0360496
P. Frankl and Z. Füredi, Solution of the Littlewood-Offord problem in high dimensions, Ann. of Math. (2) 128 (1988), no. 2, 259–270. MR 960947, DOI https://doi.org/10.2307/1971442
Jean Ginibre, Statistical ensembles of complex, quaternion, and real matrices, J. Mathematical Phys. 6 (1965), 440–449. MR 173726, DOI https://doi.org/10.1063/1.1704292

Girko1 V. L. Girko, Circular law, Theory Probab. Appl. (1984), 694–706.

V. L. Girko, The strong circular law. Twenty years later. II, Random Oper. Stochastic Equations 12 (2004), no. 3, 255–312. MR 2085255, DOI https://doi.org/10.1163/1569397042222477

Girkodet1 V. L. Girko, A refinement of the central limit theorem for random determinants, Teor. Veroyatnost. i Primenen. 42 (1997), no. 1, 63–73 (Russian); translation in Theory Probab. Appl. 42 (1997), no. 1, 121–129 (1998).

GT1 F. Götze and A.N. Tikhomirov, On the circular law, preprint

GT2 F. Götze and A.N. Tikhomirov, The Circular Law for random matrices, preprint

Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
G. Halász, Estimates for the concentration function of combinatorial number theory and probability, Period. Math. Hungar. 8 (1977), no. 3-4, 197–211. MR 494478, DOI https://doi.org/10.1007/BF02018403
Chii-Ruey Hwang, A brief survey on the spectral radius and the spectral distribution of large random matrices with i.i.d. entries, Random matrices and their applications (Brunswick, Maine, 1984) Contemp. Math., vol. 50, Amer. Math. Soc., Providence, RI, 1986, pp. 145–152. MR 841088, DOI https://doi.org/10.1090/conm/050/841088
Jeff Kahn, János Komlós, and Endre Szemerédi, On the probability that a random $\pm 1$-matrix is singular, J. Amer. Math. Soc. 8 (1995), no. 1, 223–240. MR 1260107, DOI https://doi.org/10.1090/S0894-0347-1995-1260107-2
Gy. Katona, On a conjecture of Erdős and a stronger form of Sperner’s theorem, Studia Sci. Math. Hungar. 1 (1966), 59–63. MR 205864
Daniel J. Kleitman, On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors, Advances in Math. 5 (1970), 155–157 (1970). MR 265923, DOI https://doi.org/10.1016/0001-8708%2870%2990038-1
J. Komlós, On the determinant of $(0,\,1)$ matrices, Studia Sci. Math. Hungar. 2 (1967), 7–21. MR 221962
Jerrold R. Griggs, Jeffrey C. Lagarias, Andrew M. Odlyzko, and James B. Shearer, On the tightest packing of sums of vectors, European J. Combin. 4 (1983), no. 3, 231–236. MR 725071, DOI https://doi.org/10.1016/S0195-6698%2883%2980017-1
J. W. Lindeberg, Eine neue Herleitung des Exponentialgesetzes in der Wahrscheinlichkeitsrechnung, Math. Z. 15 (1922), no. 1, 211–225 (German). MR 1544569, DOI https://doi.org/10.1007/BF01494395
J. E. Littlewood and A. C. Offord, On the number of real roots of a random algebraic equation. III, Rec. Math. [Mat. Sbornik] N.S. 12(54) (1943), 277–286 (English, with Russian summary). MR 0009656
A. E. Litvak, A. Pajor, M. Rudelson, and N. Tomczak-Jaegermann, Smallest singular value of random matrices and geometry of random polytopes, Adv. Math. 195 (2005), no. 2, 491–523. MR 2146352, DOI https://doi.org/10.1016/j.aim.2004.08.004
M. L. Mehta, Random matrices and the statistical theory of energy levels, Academic Press, New York-London, 1967. MR 0220494

PZ G. Pan and W. Zhou, Circular Law, extreme singular values and potential theory, preprint.

L. A. Pastur, The spectrum of random matrices, Teoret. Mat. Fiz. 10 (1972), no. 1, 102–112 (Russian, with English summary). MR 475502

Rud M. Rudelson, Invertibility of random matrices: Norm of the inverse. Annals of Mathematics, to appear.

Mark Rudelson and Roman Vershynin, The Littlewood-Offord problem and invertibility of random matrices, Adv. Math. 218 (2008), no. 2, 600–633. MR 2407948, DOI https://doi.org/10.1016/j.aim.2008.01.010

RV2 M. Rudelson and R. Vershynin, The smallest singular value of a rectangular random matrix, preprint.

RV3 M. Rudelson and R. Vershynin, The least singular value of a random square matrix is $O(n^{-1/2})$, preprint.

Richard P. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property, SIAM J. Algebraic Discrete Methods 1 (1980), no. 2, 168–184. MR 578321, DOI https://doi.org/10.1137/0601021
A. Sárközi and E. Szemerédi, Über ein Problem von Erdős und Moser, Acta Arith. 11 (1965), 205–208 (German). MR 182619, DOI https://doi.org/10.4064/aa-11-2-205-208

SST A. Sankar, S. H. Teng, and D. A. Spielman, Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices, preprint.

Daniel A. Spielman and Shang-Hua Teng, Smoothed analysis of algorithms, Proceedings of the International Congress of Mathematicians, Vol. I (Beijing, 2002) Higher Ed. Press, Beijing, 2002, pp. 597–606. MR 1989210
Daniel A. Spielman and Shang-Hua Teng, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, J. ACM 51 (2004), no. 3, 385–463. MR 2145860, DOI https://doi.org/10.1145/990308.990310
Michel Talagrand, A new look at independence, Ann. Probab. 24 (1996), no. 1, 1–34. MR 1387624, DOI https://doi.org/10.1214/aop/1042644705
Terence Tao and Van Vu, On random $\pm 1$ matrices: singularity and determinant, Random Structures Algorithms 28 (2006), no. 1, 1–23. MR 2187480, DOI https://doi.org/10.1002/rsa.20109
Terence Tao and Van Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012

TVinverse T. Tao and V. Vu, Inverse Littlewood-Offord theorems and the condition number of random discrete matrices, Annals of Mathematics, to appear.

Terence Tao and Van Vu, The condition number of a randomly perturbed matrix, STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 248–255. MR 2402448, DOI https://doi.org/10.1145/1250790.1250828

TVgeneral T. Tao and V. Vu, Random matrices: A general approach for the least singular value problem, preprint.

Terence Tao and Van Vu, On random $\pm 1$ matrices: singularity and determinant, Random Structures Algorithms 28 (2006), no. 1, 1–23. MR 2187480, DOI https://doi.org/10.1002/rsa.20109
Terence Tao and Van Vu, On the singularity probability of random Bernoulli matrices, J. Amer. Math. Soc. 20 (2007), no. 3, 603–628. MR 2291914, DOI https://doi.org/10.1090/S0894-0347-07-00555-3
Terence Tao and Van Vu, Random matrices: the circular law, Commun. Contemp. Math. 10 (2008), no. 2, 261–307. MR 2409368, DOI https://doi.org/10.1142/S0219199708002788

TVcir2 T. Tao and V. Vu, Random matrices: Universality of the ESD and the Circular Law (with an appendix by M. Krishnapur), submitted.

TVinversestrong T. Tao and V. Vu, paper in preparation .

Eugene P. Wigner, On the distribution of the roots of certain symmetric matrices, Ann. of Math. (2) 67 (1958), 325–327. MR 95527, DOI https://doi.org/10.2307/1970008

wish J. Wishart, The generalized product moment distribution in samples from a normal multivariate population, Biometrika 20 (1928), 32–52.