×

Random matrices: universality of ESDs and the circular law. (English) Zbl 1203.15025

This paper is concerned with the convergence of empirical spectral distributions (ESD) of random matrices, both in the sense of convergence in probability and in the almost sure sense.
Recall that for each \(n\in {\mathbb N}\), if \(F_n\) is a random variable taking values in some Hausdorff topological space \(X\) and let \(F\in X\), then we say that 5mm
1)
\(F_n\) converges in probability to \(F\) if \(\lim_{n\to \infty} P(F_n\in V) = 1\) for every neighborhood \(V\) of \(F\).
2)
\(F_n\) converges almost surely to \(F\) if \(P(\lim _{n\to \infty} F_n=F) = 1\).
A fundamental problem in the theory of random matrices is to determine the limiting distribution of the ESD of a random matrix ensemble (either in probability or in the almost sure sense) as the size of the random matrix tends to infinity. The universality phenomenon (a well-known intuition) asserts that the limiting distribution should not depend on the particular distribution of the entries. In the 1950s Wigner proved that the ESD of an \(n\times n\) Hermitian matrix with (upper diagonal) entries being i.i.d. Gaussian random variables converge to the semicircle law \(F\) with density
\[ \rho(x)=\begin{cases} \frac 1{2\pi} \sqrt {4-x^2}, &|x|\leq 2\\ 0 &|x|>0 \end{cases} \]
Wigner’s result was then extended in different forms and one of them is:
Theorem 1.3. Let \(A_n\) be the \(n \times n\) Hermitian random matrix whose upper diagonal entries are i.i.d. complex random variables with mean \(0\) and variance \(1\). The ESD of \(\frac 1{\sqrt n}A_n\) then converges (in both convergence modes) to the semicircle distribution.
The well-known circular law conjecture asserts that Theorem 1.3 deals with the non-Hermitian matrices:
Conjecture 1.4. (Circular law conjecture) Let \(A_n\) be the \(n \times n\) random matrix whose entries are i.i.d. complex random variables with mean \(0\) and variance \(1\). The ESD of \(\frac 1{\sqrt n}A_n\) then converges (in both convergence modes) to the uniform distribution on the unit disk.
Works towards the circular law conjecture have been done by many authors including Mehta, Edelman, Girko, Bai, Götze and Tikhomirov, Pan and Zhou and the present authors (see the references) under some assumptions on the distribution. For example, Mehta (complex Gaussian distribution), Edelman (real Gaussian distribution).
The authors prove the above conjecture (Theorem 1.10). They first establish some universality principles (Theorem 1.5 and Corollary 1.8). It turns out the limit distribution of the ESD of a random matrix ensemble \(A_n\) depends only on the mean and variance of its entries, under a mild size condition on the mean \({\mathbf E}A_n\) and under the assumption that the matrix \(A_n-{\mathbf E}A_n\) has i.i.d. entries. Because of Corollary 1.8, the proof is reduced to the case where the entries are Gaussian (Lindeberg trick). Thus from Mehta’s result the circular law conjecture follows.
As a related result, they show how laws for this ESD follow from laws for the singular value distribution of \(\frac 1{\sqrt n}A_n-zI\) for complex \(z\) (see Theorem 1.15). Other interesting results are obtained.
Appendix A reviews some matrix inequalities and Appendix B is authored by M. Krishnapur.
Some typos and comments on Appendix A: Lemma A.2 “generalized eigenvalues” should be “eigenvalues”. In the proof, “orthogonal \(Q\)” should be “unitary \(Q\)” (indeed the proof follows directly from Schur’s triangularization theorem). In the proof of Lemma A.4, \(X_j\), \(W_j\) should be \(X_j^*\), \(W_j^*\) respectively. Indeed the majorization between the vectors \((\sigma_1(A)^{-1},\dots , \sigma_{n'}(A)^{-2})\) and \((\text{dist} (X_1,W_1)^{-2}, \dots, \text{dist} (X_{n'},W_{n'})^{-2})\) holds by applying Schur’s result on the positive definite matrix \((AA^*)^{-1}\).

MSC:

15B52 Random matrices (algebraic aspects)
60F15 Strong limit theorems
60B20 Random matrices (probabilistic aspects)
15A18 Eigenvalues, singular values, and eigenvectors
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bai, Z. D. (1997). Circular law. Ann. Probab. 25 494-529. · Zbl 0871.62018 · doi:10.1214/aop/1024404298
[2] Bai, Z. D. and Silverstein, J. (2006). Spectral Analysis of Large Dimensional Random Matrices. Mathematics Monograph Series 2 . Science Press, Beijing. · Zbl 1196.60002
[3] Dozier, R. B. and Silverstein, J. W. (2007). On the empirical distribution of eigenvalues of large dimensional information-plus-noise-type matrices. J. Multivariate Anal. 98 678-694. · Zbl 1115.60035 · doi:10.1016/j.jmva.2006.09.006
[4] Chatterjee, S. (2005). A simple invariance principle. Available at .
[5] Chafai, D. (2008). Circular law for non-central random matrices.
[6] Edelman, A. (1988). Eigenvalues and condition numbers of random matrices. SIAM J. Matrix Anal. Appl. 9 543-560. · Zbl 0678.15019 · doi:10.1137/0609045
[7] Girko, V. L. (1984). The circular law. Theory Probab. Appl. 29 694-706. · Zbl 0565.60034
[8] Girko, V. L. (2004). The strong circular law. Twenty years later. II. Random Oper. Stochastic Equations 12 255-312. · Zbl 1065.60026 · doi:10.1163/1569397042222477
[9] Götze, F. and Tikhomirov, A. N. (2007). On the circular law.
[10] Götze, F. and Tikhomirov, A. N. (2007). The circular law for random matrices. · Zbl 1118.15022
[11] Krishnapour, M. and Vu, V. Manuscript in preparation.
[12] Ledoux, M. (2001). The Concentration of Measure Phenomenon. Mathematical Surveys and Monographs 89 . Amer. Math. Soc., Providence, RI. · Zbl 0995.60002
[13] Mehta, M. L. (1967). Random Matrices and the Statistical Theory of Energy Levels . Academic Press, New York. · Zbl 0925.60011
[14] Pan, G. and Zhou, W. (2010). Circular law, extreme singular values and potential theory. J. Multivariate Anal. 101 645-656. · Zbl 1203.60011 · doi:10.1016/j.jmva.2009.08.005
[15] Pastur, L. A. (1972). The spectrum of random matrices. Teoret. Mat. Fiz. 10 102-112.
[16] Rudelson, M. (2008). Invertibility of random matrices: Norm of the inverse. Ann. of Math. (2) 168 575-600. · Zbl 1175.15030 · doi:10.4007/annals.2008.168.575
[17] Rudelson, M. and Vershynin, R. (2008). The least singular value of a random square matrix is O ( n - 1/2 ). C. R. Math. Acad. Sci. Paris 346 893-896. · Zbl 1152.60042 · doi:10.1016/j.crma.2008.07.009
[18] Rudelson, M. and Vershynin, R. (2009). Smallest singular value of a random rectangular matrix. Comm. Pure Appl. Math. 62 1707-1739. · Zbl 1183.15031 · doi:10.1002/cpa.20294
[19] Rudelson, M. and Vershynin, R. (2010). The Littlewood-Offord problem and the condition number of random matrices. Adv. Math. 218 600-633. · Zbl 1139.15015 · doi:10.1016/j.aim.2008.01.010
[20] Speicher, R. Survey in preparation.
[21] Tao, T. and Vu, V. (2006). On random \pm 1 matrices: Singularity and determinant. Random Structures Algorithms 28 1-23. · Zbl 1086.60008 · doi:10.1002/rsa.20109
[22] Tao, T. and Vu, V. (2006). Additive Combinatorics. Cambridge Studies in Advanced Mathematics 105 . Cambridge Univ. Press, Cambridge. · Zbl 1127.11002
[23] Tao, T. and Vu, V. H. (2009). Inverse Littlewood-Offord theorems and the condition number of random discrete matrices. Ann. of Math. (2) 169 595-632. · Zbl 1250.60023 · doi:10.4007/annals.2009.169.595
[24] Tao, T. and Vu, V. (2007). The condition number of a randomly perturbed matrix. In STOC’ 07 -Proceedings of the 39 th Annual ACM Symposium on Theory of Computing 248-255. ACM, New York. · Zbl 1232.15030
[25] Tao, T. and Vu, V. (2008). Random matrices: The circular law. Commun. Contemp. Math. 10 261-307. · Zbl 1156.15010 · doi:10.1142/S0219199708002788
[26] Tao, T. and Vu, V. (2010). Random matrices: The distribution of the smallest singular values. Geom. Funct. Anal. 20 260-297. · Zbl 1210.60014 · doi:10.1007/s00039-010-0057-8
[27] Wigner, E. P. (1958). On the distribution of the roots of certain symmetric matrices. Ann. of Math. (2) 67 325-327. JSTOR: · Zbl 0085.13203 · doi:10.2307/1970008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.