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 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. Ludwig Arnold, On the asymptotic distribution of the eigenvalues of random matrices, J. Math. Anal. Appl. 20 (1967), 262–268. MR 217833, https://doi.org/10.1016/0022-247X(67)90089-3
2. L. Arnold, On Wigner’s semicircle law for the eigenvalues of random matrices, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 19 (1971), 191–198. MR 348820, https://doi.org/10.1007/BF00534107
3. Z. D. Bai, Circular law, Ann. Probab. 25 (1997), no. 1, 494–529. MR 1428519, https://doi.org/10.1214/aop/1024404298
4. Z. D. Bai and J. Silverstein, Spectral analysis of large dimensional random matrices, Mathematics Monograph Series 2, Science Press, Beijing 2006.
5. Lloyd N. Trefethen and David Bau III, Numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1444820
6. 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, https://doi.org/10.1215/S0012-7094-06-13527-5
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. 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, https://doi.org/10.4171/022-1/7
10. 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, https://doi.org/10.1016/j.jmva.2006.09.006
11. S. Chatterjee, A simple invariance principle. [arXiv:math/0508213]
12. Alan Edelman, The probability that a random real Gaussian matrix has 𝑘 real eigenvalues, related distributions, and the circular law, J. Multivariate Anal. 60 (1997), no. 2, 203–232. MR 1437734, https://doi.org/10.1006/jmva.1996.1653
13. P. Erdös, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898–902. MR 14608, https://doi.org/10.1090/S0002-9904-1945-08454-7
14. Paul Erdos and Leo Moser, Elementary Problems and Solutions: Solutions: E736, Amer. Math. Monthly 54 (1947), no. 4, 229–230. MR 1526680, https://doi.org/10.2307/2304711
15. 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
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, https://doi.org/10.2307/1971442
17. Jean Ginibre, Statistical ensembles of complex, quaternion, and real matrices, J. Mathematical Phys. 6 (1965), 440–449. MR 173726, https://doi.org/10.1063/1.1704292
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, https://doi.org/10.1163/1569397042222477
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. 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
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 494478, https://doi.org/10.1007/BF02018403
25. 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, https://doi.org/10.1090/conm/050/841088
26. Jeff Kahn, János Komlós, and Endre Szemerédi, On the probability that a random ±1-matrix is singular, J. Amer. Math. Soc. 8 (1995), no. 1, 223–240. MR 1260107, https://doi.org/10.1090/S0894-0347-1995-1260107-2
27. 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
28. 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, https://doi.org/10.1016/0001-8708(70)90038-1
29. J. Komlós, On the determinant of (0,1) matrices, Studia Sci. Math. Hungar. 2 (1967), 7–21. MR 221962
30. 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, https://doi.org/10.1016/S0195-6698(83)80017-1
31. J. W. Lindeberg, Eine neue Herleitung des Exponentialgesetzes in der Wahrscheinlichkeitsrechnung, Math. Z. 15 (1922), no. 1, 211–225 (German). MR 1544569, https://doi.org/10.1007/BF01494395
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(54) (1943), 277–286 (English, with Russian summary). MR 0009656
33. 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, https://doi.org/10.1016/j.aim.2004.08.004
34. M. L. Mehta, Random matrices and the statistical theory of energy levels, Academic Press, New York-London, 1967. MR 0220494
35. G. Pan and W. Zhou, Circular Law, extreme singular values and potential theory, preprint.
36. L. A. Pastur, The spectrum of random matrices, Teoret. Mat. Fiz. 10 (1972), no. 1, 102–112 (Russian, with English summary). MR 475502
37. M. Rudelson, Invertibility of random matrices: Norm of the inverse. Annals of Mathematics, to appear.
38. Mark Rudelson and Roman Vershynin, The Littlewood-Offord problem and invertibility of random matrices, Adv. Math. 218 (2008), no. 2, 600–633. MR 2407948, https://doi.org/10.1016/j.aim.2008.01.010
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. 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, https://doi.org/10.1137/0601021
42. 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, https://doi.org/10.4064/aa-11-2-205-208
43. A. Sankar, S. H. Teng, and D. A. Spielman, Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices, preprint.
44. 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
45. 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, https://doi.org/10.1145/990308.990310
46. Michel Talagrand, A new look at independence, Ann. Probab. 24 (1996), no. 1, 1–34. MR 1387624, https://doi.org/10.1214/aop/1042644705
47. Terence Tao and Van Vu, On random ±1 matrices: singularity and determinant, Random Structures Algorithms 28 (2006), no. 1, 1–23. MR 2187480, https://doi.org/10.1002/rsa.20109
48. Terence Tao and Van Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012
49. T. Tao and V. Vu, Inverse Littlewood-Offord theorems and the condition number of random discrete matrices, Annals of Mathematics, to appear.
50. 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, https://doi.org/10.1145/1250790.1250828
51. T. Tao and V. Vu, Random matrices: A general approach for the least singular value problem, preprint.
52. Terence Tao and Van Vu, On random ±1 matrices: singularity and determinant, Random Structures Algorithms 28 (2006), no. 1, 1–23. MR 2187480, https://doi.org/10.1002/rsa.20109
53. 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, https://doi.org/10.1090/S0894-0347-07-00555-3
54. Terence Tao and Van Vu, Random matrices: the circular law, Commun. Contemp. Math. 10 (2008), no. 2, 261–307. MR 2409368, https://doi.org/10.1142/S0219199708002788
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. Eugene P. Wigner, On the distribution of the roots of certain symmetric matrices, Ann. of Math. (2) 67 (1958), 325–327. MR 95527, https://doi.org/10.2307/1970008
58. J. Wishart, The generalized product moment distribution in samples from a normal multivariate population, Biometrika 20 (1928), 32-52.