Around the circular law : an update

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.