Press "Enter" to skip to content

20 search results for "circular law"

Around the circular law : an update

plot(eig(randn(n,n)+i*randn(n,n))/sqrt(2*n)))
plot(eig(randn(n,n)+i*randn(n,n))/sqrt(2*n)))

This post gathers comments and updates about the survey Around the circular law (2012). This is done at the occasion of a mini-course on non-normal random matrices during the Workshop on Brown measures and non-normal random matrices, held in Toulouse from November 7 to 9, 2018, and organized by the GDR CNRS MEGA.

The circular law theorem states that the empirical spectral distribution of a \( {n\times n} \) random matrix with iid entries of variance \( {1/n} \) tends to the uniform law on the unit disc of the complex plane as the dimension \( {n} \) tends to infinity. This phenomenon is the non-Hermitian counterpart of the semi circular limit for Wigner random Hermitian matrices, and the quarter circular limit for Marchenko-Pastur random covariance matrices. The Gaussian case goes back to Ginibre and Mehta, while the universal case was studied notably by Girko, and by Tao and Vu, among others. We try to give below a glimpse over related and recent problems, and a list of open problems.

Note that there is an erratum on Around the circular law (2012), available as a blog post.

In what follows, for simplicity, we always assume that \( {\xi} \) is a random variable in \( {\mathbb{C}} \), and that for all \( {n\geq1} \), \( {M^{(n)}} \) be an \( {n\times n} \) random matrix whose entries are iid copies of \( {\xi} \). The complex Ginibre ensemble corresponds to take \( {\xi} \) standard complex Gaussian.

Open problem: necessary condition for circular law. Posed by Mark Rudelson in July 2018. Suppose that the empirical measure of the eigenvalues of \( {\frac{1}{\sqrt{n}}M^{(n)}} \) tends weakly in probability to the uniform distribution on the unit disc of \( {\mathbb{C}} \). Does it implies that \( {\xi} \) has finite variance, and that this variance is one? There is obviously a link with the analogue of the circular law when \( {\xi} \) is heavy tailed in BCC-2011.

Open problem: spectral radius. We denote by \( {s_{\max}} \) and \( {|\lambda_{\max}|} \) the maximum of the singular values (operator norm) and the maximum of the moduli of the eigenvalues (spectral radius) of \( {\frac{1}{\sqrt{n}}M^{(n)}} \). It is well known that if \( {\mathbb{E}(\xi)=0} \) and \( {\mathbb{E}(|\xi|^2)=1} \), then, a.s.

\[ \lim_{n\rightarrow\infty}s_{\max}= \begin{cases} 1 & \text{if }\mathbb{E}(|\xi|^4)<\infty\\ +\infty & \text{if }\mathbb{E}(|\xi|^4)=\infty \end{cases}, \]

see for instance Chapter 5, page 113 in BS-2010. If follows that a.s.

\[ \lim_{n\rightarrow\infty}|\lambda_{\max}|= 1 \quad\text{if }\quad \mathbb{E}(|\xi|^4)<\infty. \]

Surprisingly, it was discovered in BCCT-2018 that (there is a quantitative statement) a.s.

\[ \lim_{n\rightarrow\infty}|\lambda_{\max}|= 1 \quad\text{if }\mathbb{E}(|\xi|^{2+\varepsilon})<\infty \text{ and }\xi\text{ is symmetric}. \]

The proof is combinatorial via the method of moments. It is tempting to conjecture that this is true without the symmetry assumption and with \( {\varepsilon=0} \). It is moreover tempting to try to give an analytic proof based on the resolvent or Cauchy–Stieltjes transform. It is furthermore tempting to study the asymptotic nature of the point process of the largest eigenvalues in modulus when \( {\xi} \) is heavy tailed as in BCC-2011.

Open problem: universality of Gumbel fluctuation. It is known that if \( {\mathbb{E}(\xi)=0} \), \( {\mathbb{E}(|\xi|^2)=1} \), and \( {\mathbb{E}(|\xi|^4)<\infty} \), then the spectral radius of \( {n^{-1/2}M^{(n)}} \) tends almost surely to \( {1} \) as \( {n} \) tends to infinity. It is also known that if \( {\xi} \) is a standard complex Gaussian then the fluctuation of the spectral radius is just like for the maximum of iid Gaussian random variables, in particular the fluctuation law is Gumbel. The universality of this fluctuation phenomenon is an open problem. It is in particular open when \( {\xi} \) is symmetric \( {\pm1} \) Rademacher. Moreover the necessity of the finite fourth moment is questionable. The analogous problem for non-Gaussian Coulomb gases obtained by generalizing the complex Ginibre ensemble is considered in CP-2014, see also JQ-2017. The same question can be asked for the other classical non-Hermitian model, such as the single ring model, etc, and lead to different answers and open questions. For instance, for random polynomials, the largest root in modulus can be heavy tailed, see B-2018.

Open problem: concentration for linear statistics. If \( {f:\mathbb{C}\rightarrow\mathbb{R}} \) is nice enough, are there concentration inequalities for \( {\frac{1}{n}\sum_{k=1}^nf(\lambda_k(M^{(n)}))} \)? Special choices of \( {f} \)? For an answer in the case of the complex Ginibre ensemble, see CHM-2018.

Open problem: CLT for linear statistics. The Central Limit Theorem for linear spectral statistics \( {\sum_{k=1}^nf(\lambda_k(M^{(n)}))} \) of \( {M^{(n)}} \) is still open when \( {f} \) and \( {\xi} \) are generic. In particular we could ask if in contrast with the Hermitian case, the fourth cumulant of \( {\xi} \) may do not appear in the asymptotic variance. One of the last result to date on the CLT seems to be a paper by Coston and O’Rourke arXiv:1809.08367. Note that some few comments about the Central Limit Theorem and the Gaussian Free Field for linear statistics of Coulomb gases and in particular of the complex Ginibre ensemble can be bound in another blog post. The proof of the CLT in the complex Ginibre ensemble by Rider and Virag is based on the approximation of the test function with a polynomial and the computation of cumulants by using the determinantal structure of the complex Ginibre ensemble. Update 2019-12-12: it seems that the CLT was proved recently in arXiv:1912.04100 and the variance involves the fourth cumulant for non analytic test functions! See also arXiv.2002.02438 for the real entries case.

Open problem: invertibility. The invertibility problem for Rademacher matrices is one of the most outstanding problems in discrete random matrix theory, see for instance the introduction of Ferber & Jain arXiv:1809.04718 and references therein. What was quickly mentioned in Around the circular law is still up to date apparently. More precisely, if \( {\xi} \) follows a symmetric Rademacher law \( {\frac{1}{2}\delta_{-1}+\frac{1}{2}\delta_{+1}} \), then the consideration of the event of equality of two rows or of two columns gives the lower bound

\[ c_n=\mathbb{P}(\det(M_n)=0)\geq (1+o(1))n^22^{1-n}, \]

and it is conjectured that this is tight, in the sense that

\[ c_n=(2+o(1))^{-n}. \]

The world record due to Bourgain, Vu, and Wood BVW-2010 is still \( {c_n\geq(2+o(1))^{-n/2}} \). Update 2018-12-25: it seems that Kostantin Tikhomirov has solved the conjecture in arXiv:1812.09016.

Open problem: oriented Kesten-McKay theorem. Let \( {G_{n,d}} \) be a random uniform \( {d} \)-regular oriented graph with \( {n} \) vertices. Let \( {\mu_{n,d}} \) be the empirical distribution of the eigenvalues of its adjacency matrix divided by \( {\sqrt{d}} \). It is conjectured in Around the circular law (2012) that for all fixed \( {d} \), the law \( {\mu_{n,d}} \) converges weakly as \( {n\rightarrow\infty} \) to a probability measure \( {\mu_{\infty,d}=\nu^{\boxplus d}} \) where \( {\boxplus} \) is the free convolution and \( {\nu} \) is the uniform distribution on the unit circle. The law \( {\mu_{\infty,d}} \) is the oriented analogue of the Kesten-McKay distribution, which by the way satisfies the same formula with \( {\nu} \) being the arcsine law. The law \( {\mu_{\infty,d}} \) has a nice density, and there is a nice formula for it, just like for the Kesten-McKay distribution. This distribution tends to the uniform law on the unit disc when \( {d\rightarrow\infty} \). A very close model is obtained by looking at the spectrum of the sum of \( {d} \) iid \( {n\times n} \) uniform permutation matrices. One of the main difficulty in this problem is the fact that the amount of randomness in very limited, making non-trivial the analysis for instance of the singularity.

The rank of random regular digraphs of constant degree is considered by Litvak-Lytova-Tikhomirov-Tomczak-Jaegermann-Youssef in arXiv:1801.05577. On the opposite side, one may expect that the circular law holds if \( {d} \) tends to infinity with \( {n} \). This was shown by Cook in arXiv:1703.05839 when \( {\log(n)^C\leq d\leq n/2} \), and later on by Basak-Cook-Zeitouni arXiv:1705.09053 when \( {\log(n)^{12}/\log(\log(n))^4\leq d\leq\mathcal{O}(n)} \). The circular law for sparse random regular digraphs is considered by Litvak-Lytova-Tikhomirov-Tomczak-Jaegermann-Youssef in arXiv:1801.05576.

Open problem: random Markov generators with heavy tailed conductances. Let \( {{(X_{j,k})}_{j,k\geq1}} \) be iid non-negative random variable with finite variance and mean \( {m>0} \). Following BCC-2014, for all \( {n\geq1} \), we define a random Markov generator \( {L^{(n)}} \) by

\[ L^{(n)}_{j,k}=\frac{X_{j,k}}{X_{j,1}+\cdots+X_{j,n}} \quad\text{if}\quad j\neq k \]

and \( {L^{(n)}_{jj}=-\sum_{k\neq j}L^{(n)}_{jk}} \). With this definition we have

\[ L^{(n)}=X^{(n)}-D^{(n)} \]

where \( {D^{(n)}} \) is the diagonal matrix with \( {D^{(n)}_{jj}=\sum_{k=1}^nX^{(n)}_{jk}} \). From the formula

\[ \frac{L^{(n)}+nmI^{(n)}}{\sqrt{n}} =\frac{X^{(n)}}{\sqrt{n}}-\frac{D^{(n)}-nmI^{(n)}}{\sqrt{n}} \]

we see that a good candidature for the limiting empirical spectral distribution of \( {\frac{1}{\sqrt{n}}L^{(n)}} \) as \( {n\rightarrow\infty} \) is the Brown spectral distribution of the free convolution of a circular operator with a Hermitian Gaussian operator. This was actually proved in BCC-2014. It seems that the study of the heavy tailed case for which \( {X_{j,k}} \) has an infinite variance is still open. The analogous question for Markov transition matrices is studied in BCC-2018.

Progress on outliers since 2012. The outliers for the circular law were studied for instance by Bordenave-Capitaine BC-2016 and by Nemish N-2018.

Progress on elliptic law since 2012. If \( {G_1} \) and \( {G_2} \) are two independent copies of GUE then \( {G_1+iG_2} \) follows the complex Ginibre ensemble. By using different factors for \( {G_1} \) and \( {G_2} \), we get a model that interpolates between GUE and complex Ginibre. The empirical spectral distribution of this model tends to a law known as the elliptic law, which interpolations between the Wigner semicircle and the uniform law on the disc. The universal version of this model consists in taking iid entries with a special variance structure, see for instance Nguyen and O’Rourke arXiv:1208.5883. Since 2012, several works were devoted to the elliptic law, including the CLT for linear statistics by Renfrew and O’Rourke ROR-2014, the empirical spectral distribution of products, by O’Rourke-Renfrew-Soshnikov-Vu ORRSV-2015, the outiliers, by Renfrew and O’Rourke ROR-2014 and by Benaych-Georges-Cébron-Rochet BGCR-2018.

Progress on models with non iid entries since 2012. The elliptic law mentioned earlier enters this category. Since 2012, several works were devoted to non-iid models, such as AC-2015 about log-concave random matices, and ACW-2015 about random matrices with exchangeable entries. There are also works on variance profile by Cook-Hachem-Najim-Renfrew arXiv:1612.04428, and on local inhomogeneous circular law by Alt-Erdős-Krüger AEK-2018.

The asymptotic spectral analysis of polynomial of random matrices is studied by Götze, Kösters, and Tikhomirov in GKT-2015. Note that this work concerns essentially universality, and does not provide a proof of convergence in the Gaussian case (polynomials of Gaussian matrices)!

The analogue of the circular law for random Markov generators is studied in BCC-2014, while an analogue for random Markov transition matrices from heavy tailed conductances is studiend in BCC-2018.

Progress on local laws since 2012. Tao and Vu have proved in TV-2014 the convergence of \( {k} \)-point correlation functions to the determinantal point process on \( {\mathbb{C}} \) with kernel

\[ K(z,w)=\pi^{-1}\mathrm{e}^{-\frac{1}{2}|z|^2-\frac{1}{2}|w|^2+z\overline{w}}. \]

The proof involves a four moment theorem for log-determinant, and strong concentration for log-determinant in the Ginibre case obtained via the study of a stochastic differential equation. The local circular law is also studied by Bourgade-Yau-Yin in BYY-2014, BYY-2014-bis, and by Yin Y-2014 who obtained at the end the local circular law up to the scale \( {n^{-1/2+\varepsilon}} \). See also Nemish N-2017, and Götze-Naumov-Tikhomirov arXiv:1708.06950 for alternative approach and extension to products. See also Bao-Erdős-Schnelli BES-2017 for the local law for sums at optimal scales.

Progress around the single ring theorem since 2012. The single ring theorem is a nice result which says something about the global behavior of the eigenvalues when one prescribes the singular values. Since 2012, several works were devoted to various aspects of this model. For instance the local single ring theorem was obtained by Benaych-Georges in BG-2017, see also the work of Bao-Erdős-Schnelli in arXiv:1612.05920. The fluctuation of linear statistics for the single ring theorem was obtained by Benaych-Georges-Rochet in BGR-2017, and the convergence of the spectral edge in the single ring theorem was obtained by Benaych-Georges in BG-2015.

Progress on delocalization of eigenvectors since 2012. Since 2012, a substantial progress was made on the proof of delocalization of eigenvectors or approximate eigenvectors of \( {M^{(n)}} \), in the sense that each subset of coordinates carries a non negligible part of the Euclidean norm. We can cite Rudelson and Vershynin RV-2015 RV-2016, Lytova and Tikhomirov arXiv:1810.01590, Benaych-Georges-Zeitouni arXiv:1806.06806, and Luh-O’Rourke arXiv:1810.00489. The structure of eigenvectors of random regular digraphs is considered by Litvak-Lytova-Tikhomirov-Tomczak-Jaegermann-Youssef in arXiv:1801.05575.

Progress on sparsity since 2012. The incorporation of sparsity leads to consider a random matrix with \( {\xi^{(n)}} \) with a law which may depend on \( {n} \), obtained say by multiplying the original \( {\xi} \) by a Bernoulli of parameter \( {p_n} \). The circular law should hold for \( {\frac{1}{\sqrt{np_n}}M^{(n)}} \) when \( {np_n\rightarrow\infty} \). This was considered by several authors including Tao and Vu in their first paper on the circular law TV-2008, see also BCC-2014. An optimal result is obtained in Rudelson and Tikhomirov in arXiv:1807.08085. Note that the invertibility of sparse non-Hermitian matrices is also considered by Basak-Rudelson in BR-2017.

Progress on speed of convergence since 2012. For the complex Ginibre ensemble, the best rate control known to date seem to be \( {\mathrm{W}_1(\mu_N,\mu_\infty)=\mathcal{O}(\sqrt{\log(N)/N})} \) obtained by using large deviation techniques in CHM-2018, and \( {\mathrm{W}_2(\mu_N,\mu_\infty)=\mathcal{O}(\sqrt{\log(N)}/N^{1/4})} \) obtained by Meckes and Meckes by coupling in MM-2017.

Link between eigenvalues and singular values. There is a nice study of the joint law of the eigenvalues and the singular values for biunitary invariant ensembles in a work by Kieburg and Kösters KK-2016.

Something missing in Around the circular law (2012). The formula of the density of the complex Ginibre ensemble appears as a special case of the wave function in the fractional quantum hall effect discovered by the Nobel prize in physics Robert B. Laughlin.

Something else missing in Around the circular law (2012). The spectral radius of non-Hermitian random matrices with independent entries is at the heart of famous and slightly controversial works by Robert May in mathematical biology. We refer to the works by Cohen and Newman for a mathematical perspective CE-1985, CE-1984.

Historical comments. The proof of the mean circular law for the complex Ginibre ensemble, by using the exponential series, can be found in the seminal 1965 paper of Jean Ginibre pages 443-443. His computations were retyped by Madan Lal Mehta in his book (chapter 15, page 272). Amusingly, the 1965 paper by Jean Ginibre was reviewed for the Mathematical Reviews by Jean Dieudonné. The simplest way to write this proof with the exponential series is to use the law of large numbers for Poisson random variables, see this post.

Note. This blog post is highly unperfect. I will be happy to update it and correct it.

3 Comments

Around the circular law : erratum

O'Rourke Arms
O’Rourke Arms

Sean O’Rourke pointed out on December 30, 2017 that a notation should be corrected in the statement of Lemma A.1 in the probability survey Around the circular law (2012) that I wrote years ago in collaboration with Charles Bordenave.

Indeed the definition of \( {\sigma^2} \) should be corrected to

\[ \sigma^2 :=\min_{1\leq i,j\leq n}\mathrm{Var}(X_{ij}\mid|X_{i,j}|\leq a)>0. \]

It was erroneously written

\[ \sigma^2 :=\min_{1\leq i,j\leq n}\mathrm{Var}(X_{ij}\mathbf{1}_{|X_{i,j}|\leq a})>0. \]

Let us take this occasion for a back to basics about conditional variance and variance of truncation. Let \( {X} \) be a real random variable on \( {(\Omega,\mathcal{F},\mathbb{P})} \) and \( {A\in\mathcal{F}} \) be an event. First the real number \( {\mathbb{E}(X\mid A)=\mathbb{E}(X\mid\mathbf{1}_A=1)} \) is not the random variable \( {\mathbb{E}(X\mid\mathbf{1}_A)} \). We have

\[ \mathbb{E}(X\mid\mathbf{1}_A) =\underbrace{\frac{\mathbb{E}(X\mathbf{1}_A)}{\mathbb{P}(A)}}_{\mathbb{E}(X\mid A)}\mathbf{1}_A +\underbrace{\frac{\mathbb{E}(X\mathbf{1}_{A^c})}{\mathbb{P}(A^c)}}_{\mathbb{E}(X\mid A^c)}\mathbf{1}_{A^c}. \]

Note that this formula still makes sense when \( {\mathbb{P}(A)=0} \) or \( {\mathbb{P}(A)=1} \).

The quantity \( {\mathbb{E}(X\mid A)} \) makes sense only if \( {\mathbb{P}(A)>0} \), and in this case, the conditional variance of \( {X} \) given the event \( {A} \) is the real number given by

\[ \begin{array}{rcl} \mathrm{Var}(X\mid A) &=&\mathbb{E}((X-\mathbb{E}(X\mid A))^2\mid A)\\ &=&\mathbb{E}(X^2\mid A)-\mathbb{E}(X\mid A)^2\\ &=&\frac{\mathbb{E}(X^2\mathbf{1}_A)}{\mathbb{P}(A)} -\frac{\mathbb{E}(X\mathbf{1}_A)^2}{\mathbb{P}(A)^2}\\ &=& \frac{\mathbb{E}(X^2\mathbf{1}_A)\mathbb{P}(A)-\mathbb{E}(X\mathbf{1}_A)^2}{\mathbb{P}(A)^2}\\ &=&\mathbb{E}_A(X^2)-\mathbb{E}_A(X)^2=:\mathrm{Var}_A(X) \end{array} \]

where \( {\mathbb{E}_A} \) is the expectation with respect to the probability measure with density \( {\mathbf{1}_A/\mathbb{P}(A)} \) with respect to \( {\mathbb{P}} \). In particular, by the Cauchy–Schwarz inequality,

\[ \mathrm{Var}(X\mid A) \geq 0 \]

with equality if and only if \( {X} \) and \( {\mathbf{1}_A} \) are colinear.

Of course \( {\mathrm{Var}(X\mid A)=0} \) if \( {X} \) is constant. However \( {\mathrm{Var}(X\mid A)} \) may vanish for a non-constant \( {X} \). Indeed if \( {A=\{|X|\leq a\}} \) and if \( {X\sim\frac{1}{2}\delta_{a/2}+\frac{1}{2}\delta_{2a}} \) then \( {X\mid A} \) is constant and equal to \( {a/2} \). In this example, since \( {X\mathbf{1}_A} \) is not a constant, this shows also that one cannot lower bound \( {\mathrm{Var}(X\mid A)} \) with the variance of the truncation

\[ \mathrm{Var}(X\mathbf{1}_A)=\mathbb{E}(X^2\mathbf{1}_A)-\mathbb{E}(X\mathbf{1}_A)^2. \]

Another notable correction. Mylène Maïda pointed out to me on February 27 2018 that at the bottom of page 14, just before the statement

\[ \sup_{z\in C}|n\varphi_{n,1}(\sqrt{n}z)-\pi^{-1}\mathbf{1}_{[0,1]}(|z|)|=0 \]

the compact set \( {C} \) must be taken in \( {\{z\in\mathbb{C}:|z|\neq1\}} \) and not on the whole complex plane \( {\mathbb{C}} \). Indeed, when \( {|z|=1} \), \( {n\varphi_{n,1}(\sqrt{n}z)} \) tends as \( {n\rightarrow\infty} \) to \( {1/2} \), and not to \( {\pi^{-1}} \), see for instance this former post for a one formula proof based on the central limit theorem for Poisson random variables. Anyway this is really not surprising since a sequence of continuous functions cannot converge uniformly to a discontinuous function.

Yet another correction. Page 39 line 9 replace $M_\mu(a)$ by $M_\mu(q)$.

Leave a Comment

Circular law for unconditional log-concave random matrices

Warsaw, Poland
Warsaw, Poland

Recently I had the great pleasure to upload on arXiv a joint work arXiv:1303.5838 with Radek Adamczak in which we explore the validity of the circular law for random matrices with non i.i.d. entries. Recall that among the basic results of random matrix theory, the circular law is the simplest to state and also the hardest to prove. It states that the empirical distribution of the eigenvalues of an \( {n\times n} \) random matrix with i.i.d. entries of variance \( {1} \), when scaled by \( {\sqrt{n}} \), tends as \( {n\rightarrow\infty} \) to the uniform distribution on the unit disc of the complex plane.

Our main result is as follows. Let \( {A} \) be a random \( {n\times n} \) real matrix having as a random vector in \( {\mathbb{R}^{n\times n}} \) a log-concave isotropic unconditional law. Then with probability one, as \( {n\rightarrow\infty} \), the empirical spectral distribution of \( {\frac{1}{\sqrt{n}}A} \) tends to the uniform distribution on the unit disc.

About the assumptions. The entries of \( {A} \) are uncorrelated and have a symmetric law of zero mean and unit variance. This allows for some dependence and non equidistribution among the entries, while keeping the special case of i.i.d. standard Gaussian (or exponential) entries. If one drops the unconditionality assumption then the limiting spectral measure needs not be the circular law (there are examples in a paper by Feinberg and Zee (eq. (5.8) p. 654) and Guionnet-Krishnapur-Zeitouni. This is in contrast with the model of random matrices with i.i.d. log-concave rows (see Adamczak) for which it turned out that the circular law holds without assuming unconditionality.

Method of proof. We prove our main result using the Tao and Vu version of the Hermitization method of Girko, presented in a recent survey on the circular law. This boils down the problem to define the Hermitian matrix

\[ B_n(z):=\sqrt{\left(\frac{1}{\sqrt{n}}A_n-zI_n\right)\left(\frac{1}{\sqrt{n}}A_n-zI_n\right)^\ast} \]

for every \( {z\in\mathbb{C}} \), and to check the following couple of properties:

  • (i) For all \( {z \in \mathbb{C}} \) the spectral measure \( {\nu_{z,n}} \) of \( {B_n(z)} \) converges almost surely to some deterministic probability measure \( {\nu_z} \) on \( {\mathbb{R}_+} \) which depends only on \( {z} \) (universality). Moreover, for almost all \( {z\in \mathbb{C}} \),

    \[ U(z) := -\int_{\mathbb{R}_+} \log (s) \nu_z(ds) = -(\log|z|)\mathbf{1}_{|z|>1}+\frac{1-|z|^2}{2}\mathbf{1}_{|z|\leq1}. \]

  • (ii) For all \( {z \in \mathbb{C}} \), with probability one the function \( {s \mapsto \log(s)} \) is uniformly integrable with respect to the family of measures \( {\{\nu_{z,n}\}_{n\ge 1}} \).

The link between \( {A_n} \) and \( {B_n(z)} \) is given by the Girko Hermitization identity:

\[ U_n(z) :=-\log|\det(A_n)| =-\log\det(B_n(z)) =-\int_0^\infty\!\log(s)\,\nu_{z,n}(ds). \]

The quantity \( {U_n(z)} \) is the logarithmic potential at point \( {z} \) of the empirical spectral distribution formed with the eigenvalues of \( {A_n} \). To prove (i), we use concentration of measure for the Cauchy-Stieltjes transform of \( {B_n(z)} \) to get the convergence to a universal limit, and the well known Gaussian case with i.i.d. entries to get the formula. To prove (ii), we need to control the largest and smallest and a bunch of small eigenvalues of \( {B_n(z)} \). This is done by using remarkable properties of unconditional log-concave distributions regarding tails and densities.

About log-concavity. We say that a probability measure \( {\mu} \) on \( {\mathbb{R}^d} \) is log-concave when for all nonempty compact sets \( {A,B} \) and \( {\theta \in (0,1)} \),

\[ \mu(\theta A + (1-\theta)B) \ge \mu(A)^\theta\mu(B)^{1-\theta}. \]

A measure \( {\mu} \) not supported on a proper affine subspace of \( {\mathbb{R}^d} \) is log-concave iff it has density \( {e^{-V}} \) where \( {V \colon \mathbb{R}^d \rightarrow \mathbb{R}\cup\{+\infty\}} \) is a convex function, see for instance the lecture notes by Giannopoulos. We say that \( {\mu} \) is isotropic if it is centered and its covariance matrix is the identity, in other words if the coordinates are uncorrelated, centered, and have unit variance. Recall finally that \( {\mu} \) is called unconditional if \( {X=(X_1,\ldots,X_d)} \) and \( {(\varepsilon_1 X_1,\ldots,\varepsilon_d X_d)} \) have the same law when \( {X} \) has law \( {\mu} \) and \( {\varepsilon_1,\ldots,\varepsilon_d} \) are i.i.d. Rademacher random variables (signs) independent of \( {X} \). This means that the law of \( {X} \) has the symmetries of the cube. The isotropy and the unconditionality are related to the canonical basis of \( {\mathbb{R}^d} \), while the log-concavity is not. Note that unconditionality together with unit variances imply automatically isotropy.

Log-concave distributions play an essential role in high dimensional and asymptotic geometric analysis. The uniform probability distribution on a convex and compact set (such as \( {\ell_p(\mathbb{R}^d)} \) balls) is always log-concave. Beyond convex bodies, the most basic examples of log-concave measures are products of Gaussian measures \( {\exp(-\|x\|_2^2-\frac{d}{2}\log(\pi))} \) and products of symmetric exponential measures \( {\exp(-\|x\|_1-d\log(2))} \). The dogma is that most high dimensional properties of isotropic log-concave measures are similar to the ones of these two basic examples. A good way to understand this phenomenon is to take a look at the central limit theorem for convex bodies say for simplicity when the body is an \( {\ell_p} \) ball.

The log-concave property is stable by many common transformations such as by tensor product, by convolution product, by taking marginals, projections, affine images, conditional distributions, etc. The geometric and probabilistic analysis of log-concave measures is a well developed area of research. What we will need for our analysis is properties related to the behavior of densities and concentration of measure results. Many of such questions are difficult and related to famous open problems in asymptotic geometric analysis. Fortunately, unconditional log-concave measures behave in a much more rigid way than general ones, in particular some of the conjectures have been answered either completely or up to terms which are logarithmic in the dimension and as such do not cause difficulties in the problems we are about to deal with. Below we present the ingredients we will use throughout the proof.

  • Sub-exponential tails. If \( {X} \) is mean zero and variance one log-concave real random variable then for all \( {t \ge 0} \),

    \[ \mathbb{P}(|X| \ge t) \le 2\exp(-ct). \]

    A proof can be found in an old paper by Christer Borell (not Émile Borel);

  • Comparison of tails. If \( {X} \) is an isotropic unconditional log-concave random vector in \( {\mathbb{R}^n} \) and if \( {\mathcal{E}} \) is a standard \( {n} \)-dimensional symmetric exponential vector (i.e. with i.i.d. components following a symmetric exponential distribution with variance one), then for any semi-norm \( {\|\cdot\|} \) on \( {\mathbb{R}^n} \) and any \( {t > 0} \),

    \[ \mathbb{P}(\|X\| \ge Ct) \le C\mathbb{P}(\|\mathcal{E}\| \ge t) \]

    where \( {C} \) is a universal constant. A proof can be found in a paper by Rafal Latala. We use it in order to control the largest eigenvalue of \( {B_n(z)} \);

  • Density bound. If \( {X} \) is an isotropic unconditional log-concave random vector in \( {\mathbb{R}^n} \) then its density is bounded from above by \( {C^n} \), where \( {C} \) is a universal constant. A proof can be found in Bobkov and Nazarov. We use this property to control small ball probabilities. The famous slicing conjecture states that such a bound is valid even without unconditionality.
  • Poincaré inequality. If \( {X} \) is an isotropic unconditional log-concave random vector in \( {\mathbb{R}^n} \), then for every smooth \( {f\colon \mathbb{R}^n \rightarrow \mathbb{R}} \),

    \[ \mathrm{Var}(f(X)) \le C\log^2(n+1)\mathbb{E}(|\nabla f(X)|^2) \]

    where \( {C} \) is a universal constant. A proof can be found in a paper by Klartag. The famous Kannan-Lovasz-Simonovits (KLS) conjecture states that this holds even without unconditionality and without the logarithm! We use the Poincaré inequality above in order to get concentration of measure for Lipschitz functions, via upper bounds on the Laplace transform (Herbst argument). Namely, this gives that for any 1-Lipschitz function \( {g\colon \mathbb{R}^n \rightarrow \mathbb{R}} \) and all \( {t > 0} \),

    \[ \mathbb{P}(|g(X)-\mathbb{E}(g(X))| \ge t) \le 2\exp(-ct/\log(n+1)) \]

    where \( {c} \) is a constant. We will use it with the random version \( {X=A} \) in \( {\mathbb{R}^{n^2}} \), and with \( {g(X):=m_A(\xi)} \), the Cauchy-Stieltjes transform of the empirical spectral distribution of \( {\sqrt{AA^*}} \) at point \( {\xi\in\mathbb{C}_+} \).

About unconditionality again, in order to control a bunch of small eigenvalues of \( {B_n(z)} \), we need a bound for the distance of a row of \( {A_n} \) to the span of a bunch of rows of \( {A_n} \). Here unconditionality enters the scene via a very well known trick: it allows to introduce artificially Rademacher random variables (i.e. random signs) and then to use for instance the Khintchine-Kahane inequality and Talagrand concentration inequality on the discrete cube.

Warsaw, Poland
Warsaw, Poland
Leave a Comment

Around the circular law

I have uploaded lecture notes entitled Around the circular law written with Charles Bordenave (hal-00623894 & arXiv:1109.3343). These lecture notes are the expanded version of a joint course that we gave at the occasion of the France-China summer school held in Changchun. They incorporate some posts from this blog. It was a great pleasure for us to write down this synthesis, accumulating few years of thinking on the subject, sometimes with our friend Pietro Caputo (I will remember this stimulating week in Rome!). I hope to reduce my time turning around the circular law in 2012, even if I am still fascinated by few of the open problems 😉

Group photo in Jilin province, near Changchun
Jilin province, on the road for Changbaishan, China. Photo by Jamal Najim. From left to right: Charles Bordenave, Djalil Chafaï, Hayat Cheballah, Maxime Février, Damien Passemier, Camille Mâle, Adrien Hardy, Shurong Zheng, Ningning Zhao, Zhengdong Wang.

Girko (1946 – ) contributed substantially to the solution of the circular law problem. His interest in random matrices came from his early works on random determinants, motivated at the origin by the van der Waerden conjecture: among all \(n\times n\) doubly stochastic matrices, the matrix with all entries equal to \(1/n\) has minimal permanent. It turns out that the van der Waerden conjecture was solved around 1980 by another Ukrainian mathematician: Falikman. Personally (author of this blog), I have two favorites (still open) problems on doubly stochastic matrices:

  • find an exact representation of the uniform law on the polytope of doubly stochastic matrices (similar to what we have for the \(\ell^1\) ball with i.i.d. exponentials),
  • show that the empirical spectral distribution of random doubly stochastic matrices (distributed according to the uniform law) tends to the circular law.

This is why I came to random matrix theory… A proof of the van der Waerden conjecture can be found in the last chapter of the book Matrix inequalities by Zhan. Coincidentally, this book contains also somewhere (proof of theorem 3.32) an inequality (for singular values and rows norms) which turned out to be a crucial ingredient in the solution of the heavy tailed analogue of the circular law theorem (obtained in collaboration with Bordenave and Caputo). I knew this book from my postdoc (by simple curiosity), but it became useful only ten years later!

Van der Waerden is famous for his heorem in Ramsey theory about the structure of integers.

Vyacheslav Girko
The Ukrainian mathematician V. L. Girko who spent many years around the circular law
1 Comment

Can't find what you're looking for? Try refining your search:

Syntax · Style · .