RANDOM MATRICES: THE CIRCULAR LAW

By Terence Tao, Van H. Vu. 2007

296 citations recorded by the source corpus.

Let x be a complex random variable with mean zero and bounded variance σ2. Let Nn be a random matrix of order n with entries being i.i.d. copies of x. Let λ1, …, λn be the eigenvalues of . Define the empirical spectral distributionμn of Nn by the formula The following well-known conjecture has been open since the 1950's: Circular Law Conjecture: μn converges to the uniform distribution μ∞ over the unit disk as n tends to infinity. We prove this conjecture, with strong convergence, under the slightly stronger assumption that the (2 + η)th-moment of x is bounded, for any η > 0. Our method builds and improves upon earlier work of Girko, Bai, Gotze–Tikhomirov, and Pan–Zhou, and also applies for sparse random matrices. The new key ingredient in the paper is a general result about the least singular value of random matrices, which was obtained using tools and ideas from additive combinatorics.

Subfields: Discrete Mathematics and Combinatorics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/0ef619ee01145fc10e2597394e41b88329d118dd

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Invertibility of Sparse non-Hermitian matrices (2015, background): “entries with finite second moment Tao and Vu in [29] established that for every C ′ > 0 there exists a C > 0 such that”
The single ring theorem (2009, methodology): “es. For the model of random matrices with i.i.d. entries having zero mean and ﬁnite variance, this has been achieved in stages by Bai [2], Go¨tze and Tikhomirov [11], Pan and Zhou [21] and Tao and Vu [24]. While we heavily borrow from that sequence, a major difﬁculty in the problem considered here i”
Circular law theorem for random Markov matrices (2008, unknown): “3) is partly but crucially based on a polynomial lower bound on the smallest singular value proved in [40]: for every a, d > 0, there exists b > 0 such that for any deterministic complex n× n matrix A with s1(A) 6 nd we have P(sn(X +A) 6 n −b) 6 n−a.”
Graphs with integral spectrum (2009, unknown): “We note that despite a recent series of very strong results [2, 9, 23, 24, 25, 26] treating various counting questions for 0, 1-matrices, no upper bounds on I(n) have been known prior to our work, which derives the following result:”
Small Ball Probability, Inverse Theorems, and Applications (2012, methodology): “[58, 60] Let 0 < ≤ 1/3 and C > 0 be constants.”
The Ginibre Ensemble of Real Random Matrices and its Scaling Limits (2008, background): “The circular law for N × N matrices with i.i.d Gaussian entries says that, when normalized by N − 1 / 2 the density of eigenvalues becomes uniform on the unit disk as N → ∞ (See [15] for a proof of this fact when the entries are i.i.d. more Gaussian, and [2] and [24] for general results).”
Spectrum of Markov Generators on Sparse Random Graphs (2012, background): “Results in this direction have been recently established in [38, 23, 45], where the convergence is proved under some extra assumptions including that n1−εσ2 → ∞ for some ε > 0.”
On the spectrum of sum and product of non-hermitian random matrices (2010, methodology): “It is a straightforward adaptation of [3, Lemma A.2].”
A Proof of the Block Model Threshold Conjecture (2013, background): “For example, semi-circle laws and local statistics are now known whenever a and b are growing at least logarithmically fast in n [29] (following earlier work that required polynomially fast growth [11,28]), and also for matrix ensembles with more general i.i.d. entries.”
Non-asymptotic theory of random matrices: extreme singular values (2010, background): “This was further extended to random variables having bounded moment 2 + ε in [35, 82].”
From the Littlewood-Offord problem to the Circular Law: universality of the spectral distribution of random matrices (2008, methodology): “By the word noise, we would like to refer to all kinds of errors occurring in a process, due to both humans and machines, including errors in measuring, errors caused by truncations, errors committed in transmitting and inputting the data, etc. Spielman and Teng [44] pointed out that when we are…”
Random matrices: Universality of ESDs and the circular law (2008, background): “In [26] (see also [10] for an alternate proof for the weak version), this theorem was proven with the extra assumption that the entries have finite (2+ε)-th moment for any fixed ε > 0; earlier related results are appear in [7, 8, 1, 2, 9].”
Universality and the circular law for sparse random matrices. (2010, methodology): “Lower bounds on dist( 1 √ n Xi,Vi) and dist( 1 √nYi,Wi) will now follow from lower bounds on the least singular values of An and Bn which were proven in [32].”
The Elliptic Law (2012, background): “is no formula, the problem appears much more dicult. Important results were obtained by Girko [12, 13], Bai [1, 3], and more recently by Gotze and Tikhomirov [19], Pan and Zhou [36], and Tao and Vu [45]. These results conrm the same limiting law under some moment or smoothness assumptions on the dis”
Random matrices: Law of the determinant (2011, background): “ity one do not violate the generality of Theorem 1.1. To start with, we need a very weak lower bound on |detAn|. Lemma A.1. There is a constant C such that P(|detAn|≤n−Cn)≤n−1. Proof. It follows from [25], Theorem 2.1, that there is a constant C such that P(σn(An)≤n−C)≤n−1. Since |detAn| is the prod”