Bulletin of the American Mathematical Society

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

Author(s): Terence Tao; Van Vu
Journal: Bull. Amer. Math. Soc. 46 (2009), 377-396.
MSC (2000): Primary 15A52, 60G50
Posted: February 24, 2009
Retrieve article in: PDF

Abstract: The famous circular law asserts that if

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}: \vert z\vert \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.

1.: L. Arnold, On the asymptotic distribution of the eigenvalues of random matrices, J. Math. Anal. Appl., 20 (1967), 262-268. MR 0217833 (36:922)
2.: L. Arnold, On Wigner's semi-cirle law for the eigenvalues of random matrices, Z. Wahrsch. Verw. Gebiete, 19 (1971), 191-198. MR 0348820 (50:1315)
3.: Z. D. Bai, Circular law, Ann. Probab. 25 (1997), 494-529. MR 1428519 (98k:60040)
4.: Z. D. Bai and J. Silverstein, Spectral analysis of large dimensional random matrices, Mathematics Monograph Series 2, Science Press, Beijing 2006.
5.: D. Bau and L. Trefethen, Numerical linear algebra. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1444820 (98k:65002)
6.: K. Costello, T. Tao and V. Vu, Random symmetric matrices are almost surely non-singular, Duke Math. J. 135 (2006), 395-413. MR 2267289 (2008f:15080)
7.: K. Costello and V. Vu, The ranks of random graphs, to appear in Random Structures and Algorthms.
8.: K. Costello and V. Vu, Concentration of random determinants and permanent estimators, submitted.
9.: P. Deift, Universality for mathematical and physical systems. International Congress of Mathematicians Vol. I, 125-152, Eur. Math. Soc., Zürich, 2007. MR 2334189 (2008g:60024)
10.: R. Dozier and J. Silverstein, On the empirical distribution of eigenvalues of large dimensional information-plus-noise-type matrices, J. Multivar. Anal. 98 (2007), 678-694. MR 2322123
11.: S. Chatterjee, A simple invariance principle. [arXiv:math/0508213]
12.: A. Edelman, Probability that a random real Gaussian matrix has real eigenvalues, related distributions, and the Circular Law, Journal of Multivariate Analysis 60 (1997), 203-232. MR 1437734 (98b:15025)
13.: P. Erdős, On a lemma of Littlewood and Offord. Bull. Amer. Math. Soc. 51 (1945), 898-902. MR 0014608 (7:309j)
14.: P. Erdős and L. Moser, Elementary problems and solutions: Solutions: E736. Amer. Math. Monthly 54 (1947), no. 4, 229-230. MR 1526680
15.: G. Freiman, Foundations of a structural theory of set addition. Translated from the Russian. Translations of Mathematical Monographs, Vol 37. American Mathematical Society, Providence, R. I., 1973. vii+108 pp. MR 0360496 (50:12944)
16.: 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 (89m:05002)
17.: J. Ginibre, Statistical ensembles of complex, quaternion, and real matrices, Journal of Mathematical Physics 6 (1965), 440-449. MR 0173726 (30:3936)
18.: V. L. Girko, Circular law, Theory Probab. Appl. (1984), 694-706.
19.: V. L. Girko, The strong circular law. Twenty years later. II. Random Oper. Stochastic Equations 12 (2004), no. 3, 255-312. MR 2085255 (2006e:60045)
20.: 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).
21.: F. Götze and A.N. Tikhomirov, On the circular law, preprint
22.: F. Götze and A.N. Tikhomirov, The Circular Law for random matrices, preprint
23.: G. Golub and C. van Loan, Matrix computations, 3rd Edtion, 1996, John Hopkins Univ. Press. MR 1417720 (97g:65006)
24.: 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 0494478 (58:13338)
25.: C. R. Hwang, A brief survey on the spectral radius and the spectral distribution of large random matrices with i.i.d. entries, Contemp. Math. vol. 50, Amer. Math. Soc., Providence, RI, 1986, 145-152. MR 841088 (87m:60080)
26.: J. Kahn, J. Komlós and E. 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 (95c:15047)
27.: G. Katona, On a conjecture of Erdős and a stronger form of Sperner's theorem. Studia Sci. Math. Hungar. 1 (1966), 59-63. MR 0205864 (34:5690)
28.: D. Kleitman, On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors, Advances in Math. 5 (1970), 155-157. MR 0265923 (42:832)
29.: J. Komlós, On the determinant of matrices. Studia Sci. Math. Hungar. 2 (1967), 7-21. MR 0221962 (36:5014)
30.: J. Griggs, J. Lagarias, A. Odlyzko, and J. Shearer, On the tightest packing of sums of vectors, European J. Combin. 4 (1983), no. 3, 231-236. MR 725071 (84m:52021)
31.: J. W. Lindeberg, Eine neue herleitung des exponentialgesetzes in der wahrscheinlichkeitsrechnung, Math. Z. 15 (1922), 211-225. MR 1544569
32.: 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 (1943), 277-286. MR 0009656 (5:179h)
33.: A. 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 (2006g:52009)
34.: M.L. Mehta, Random Matrices and the Statistical Theory of Energy Levels, Academic Press, New York, NY, 1967. MR 0220494 (36:3554)
35.: G. Pan and W. Zhou, Circular Law, extreme singular values and potential theory, preprint.
36.: L. A Pastur, On the spectrum of random matrices, Teoret. Mat. Fiz. 10 (1973), 102-112. MR 0475502 (57:15106)
37.: M. Rudelson, Invertibility of random matrices: Norm of the inverse. Annals of Mathematics, to appear.
38.: M. Rudelson and R. Vershynin, The Littlewood-Offord problem and the condition number of random matrices, Advances in Mathematics 218 (2008), 600-633. MR 2407948
39.: M. Rudelson and R. Vershynin, The smallest singular value of a rectangular random matrix, preprint.
40.: M. Rudelson and R. Vershynin, The least singular value of a random square matrix is $O(n^{-1/2})$ , preprint.
41.: R. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property, SIAM J. Algebraic Discrete Methods 1 (1980), no. 2, 168-184. MR 578321 (82j:20083)
42.: A. Sárközy and E. Szemerédi, Über ein Problem von Erdős und Moser, Acta Arithmetica 11 (1965), 205-208. MR 0182619 (32:102)
43.: A. Sankar, S. H. Teng, and D. A. Spielman, Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices, preprint.
44.: D. A. Spielman and S. H. Teng, Smoothed analysis of algorithms, Proceedings of the International Congress of Mathematicians, Vol. I (Beijing, 2002), 597-606, Higher Ed. Press, Beijing, 2002. MR 1989210 (2004d:90138)
45.: D. A. Spielman and S. H. Teng, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, J. ACM 51 (2004), no. 3, 385-463. MR 2145860 (2006f:90029)
46.: M. Talagrand, A new look at independence, Ann. Probab. 24 (1996), no. 1, 1-34. MR 1387624 (97d:60028)
47.: T. Tao and V. Vu, On random $\pm 1$ matrices: Singularity and determinant, Random Structures Algorithms 28 (2006), no. 1, 1-23. MR 2187480 (2006g:15048)
48.: T. Tao and V. Vu, Additive combinatorics, Cambridge University Press, 2006. MR 2289012 (2008a:11002)
49.: T. Tao and V. Vu, Inverse Littlewood-Offord theorems and the condition number of random discrete matrices, Annals of Mathematics, to appear.
50.: T. Tao and V. Vu, The condition number of a randomly perturbed matrix, STOC 2007. MR 2402448
51.: T. Tao and V. Vu, Random matrices: A general approach for the least singular value problem, preprint.
52.: T. Tao and V. Vu, On random matrices: Singularity and determinant, Random Structures and Algorithms 28 (2006), no 1, 1-23. MR 2187480 (2006g:15048)
53.: T. Tao and V. Vu, On the singularity probability of random Bernoulli matrices, J. Amer. Math. Soc. 20 (2007), 603-673. MR 2291914 (2008h:60027)
54.: T. Tao and V. Vu, Random matrices: The Circular Law, Communication in Contemporary Mathematics 10 (2008), 261-307. MR 2409368
55.: T. Tao and V. Vu, Random matrices: Universality of the ESD and the Circular Law (with an appendix by M. Krishnapur), submitted.
56.: T. Tao and V. Vu, paper in preparation.
57.: P. Wigner, On the distribution of the roots of certain symmetric matrices, The Annals of Mathematics 67 (1958), 325-327. MR 0095527 (20:2029)
58.: J. Wishart, The generalized product moment distribution in samples from a normal multivariate population, Biometrika 20 (1928), 32-52.

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 15A52, 60G50

Terence Tao
Affiliation: Department of Mathematics, UCLA, Los Angeles, California 90095-1555
Email: tao@math.ucla.edu

Van Vu
Affiliation: Department of Mathematics, Rutgers University, Piscataway, New Jersey 08854
Email: vanvu@math.rutgers.edu

DOI: 10.1090/S0273-0979-09-01252-X
PII: S 0273-0979(09)01252-X
Received by editor(s): October 16, 2008,
Received by editor(s) in revised form: January 1, 2009
Posted: February 24, 2009
Additional Notes: The first author is supported by NSF grant CCF-0649473 and a grant from the MacArthur Foundation
The second author is supported by an NSF Career Grant 0635606
Copyright of article: Copyright 2009, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-9485(e) ISSN 0273-0979(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues: 1891 - Present Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS