From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices
HTML articles powered by AMS MathViewer
- by Terence Tao and Van Vu PDF
- Bull. Amer. Math. Soc. 46 (2009), 377-396 Request permission
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.References
- Ludwig Arnold, On the asymptotic distribution of the eigenvalues of random matrices, J. Math. Anal. Appl. 20 (1967), 262–268. MR 217833, DOI 10.1016/0022-247X(67)90089-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 10.1007/BF00534107
- Z. D. Bai, Circular law, Ann. Probab. 25 (1997), no. 1, 494–529. MR 1428519, DOI 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, DOI 10.1137/1.9780898719574
- 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 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 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 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 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 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 10.2307/2304711
- G. A. Freĭman, Foundations of a structural theory of set addition, Translations of Mathematical Monographs, Vol 37, American Mathematical Society, Providence, R.I., 1973. Translated from the Russian. 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 10.2307/1971442
- Jean Ginibre, Statistical ensembles of complex, quaternion, and real matrices, J. Mathematical Phys. 6 (1965), 440–449. MR 173726, DOI 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 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 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 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 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 10.1016/0001-8708(70)90038-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 10.1016/S0195-6698(83)80017-1
- J. W. Lindeberg, Eine neue Herleitung des Exponentialgesetzes in der Wahrscheinlichkeitsrechnung, Math. Z. 15 (1922), no. 1, 211–225 (German). MR 1544569, DOI 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 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 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 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 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 10.1145/990308.990310
- Michel Talagrand, A new look at independence, Ann. Probab. 24 (1996), no. 1, 1–34. MR 1387624, DOI 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 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, DOI 10.1017/CBO9780511755149 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 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 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 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 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 10.2307/1970008 wish J. Wishart, The generalized product moment distribution in samples from a normal multivariate population, Biometrika 20 (1928), 32–52.
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 - © Copyright 2009
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 2507275