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
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

2

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

to appear in Random Structures and Algorthms

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
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

Theory Probab. Appl.

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

Teor. Veroyatnost. i Primenen.

42

Theory Probab. Appl.

42

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

preprint

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

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
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

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

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
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

submitted

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

Biometrika

20