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.
Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 15A52, 60G50
Retrieve articles in all journals with MSC (2000): 15A52, 60G50
Additional Information
Terence Tao
Affiliation:
Department of Mathematics, UCLA, Los Angeles, California 90095-1555
MR Author ID:
361755
ORCID:
0000-0002-0140-7641
Email:
tao@math.ucla.edu
Van Vu
Affiliation:
Department of Mathematics, Rutgers University, Piscataway, New Jersey 08854
Email:
vanvu@math.rutgers.edu
Received by editor(s):
October 16, 2008
Received by editor(s) in revised form:
January 1, 2009
Published electronically:
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
Article copyright:
© Copyright 2009
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.