Press "Enter" to skip to content

Category: Uncategorized

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 one can conjecture that 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.

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}} \).

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.

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

3 Comments

High Dimensional Probability and Algorithms

Logo PSL

This tiny post to announce a forthcoming summer school on High Dimensional Probability and Algorithms. It will take place in École Normale Supérieure from July 1-5, 2019. It consists in…

  • 9-hour lecture by Sébastien Bubeck (Microsoft Research)
  • 9-hour lecture by Joel Tropp (California Institute of Technology)
  • additional 45-minute talks (to be announced)

A website is available at https://hdpa2019.sciencesconf.org/. The registration is free but mandatory. There will be some limited support for young students. The targeted audience is young and less young mathematicians, starting from the PhD level.

This school is funded by the PSL-math program (PSL University), and is additionally supported by CNRS. It is co-organized by Claire Boyer, Joseph Lehec, and myself.

Leave a Comment

DOI for EJP and ECP papers from volumes 1-22

EJP www logo designed by PKP

The Digital object identifier (DOI) is a unique identifier attributed to every published electronic document such as research articles. The worldwide DOI database is known as CrossRef. The DOI is the best way to link papers in a web-page or in a curriculum.

For instance, the paper by Jeffrey Lin entitled A negative answer to a problem of Aldous on determination of exchangeable sequences published in 2016 in Electronic Journal of Probability has DOI 10.1214/16-EJP4403 (the part before the slash indicates the publisher). This means that it is available via http://dx.doi.org/10.1214/16-EJP4403. This URL redirects to the right page on the publisher website. This redirection is handled by the CrossRef system.  The CrossRef database is updated by all the publishers around the world. By this way, if a publisher changes his website, he will update the CrossRef database and DOI users have nothing to do. This resembles in a way the Domain name system (DNS) used for the Internet protocol.

When Electronic Journal of Probability (EJP) and Electronic Communications in Probability (ECP) were launched in 1995, the DOI/CrossRef system did not exist, and the papers were using a university URL. More than twenty years later, all the papers published in EJP and ECP are stored and distributed by Project Euclid, and all have a DOI. If you would like to find the DOI of a paper published in EJP or ECP in volume 1 to 22 you may browse metadata pages in Project Euclid, or use this Javascript code.

Recently, in collaboration with Project Euclid, I have managed to add the DOI to the first page of the PDF file of all “old” ECP and EJP papers published in volumes 1 to 16. This was done on my Debian distribution using essentially the PDFtk utility.

Project Euclid Logo

Leave a Comment

How to give a bad talk

A serious man.

Using BeamerBeamer is a great $\LaTeX$ standard, allowing automation of bad talks.

  • try to maximize the total number of slides, in particular avoid the rule of 2 minutes per slide, and do not hesitate to use hundreds of slides for a one hour talk;
  • try to use as much sections and subsections as possible;
  • try to maximize the total number of words and formulas is each slide;
  • never use the telegraphic style, write complete sentences everywhere;
  • write exactly what you will say and say exactly what you wrote;
  • use lots of \pause in your slides to make sure people follow exactly what you are saying word by word, and do not start to think about what you claimed 20 seconds ago;
  • possibly put just one sentence per slide, to make sure you often have to change: people will have no way of remembering what was just written in the previous ones;
  • you may also prepare once and for all 100 slides and then just select some at random depending on the length of your talk;
  • put lots of colors, in particular those which will never be rendered correctly on a beamer;
  • avoid intuitive and structural explanations, focus as soon as possible on technical aspects showing your technical skills;
  • never spend time in presentation of the domain and context, this is useless;
  • never present elementary facts in the domain, start with your own technical stuff;
  • never spend time on the interpretation of your graphics;
  • put tiny pictures with an embedded legend that nobody will ever be able to read;
  • use nice pictures and do not worry about their origin (probably from Google anyway);
  • forget to cite the ground-breaking results of your colleagues in the room;
  • keep in mind that aesthetics is useless, superficial, a waste of time;
  • never take into account the background of your public;
  • never take into account how other people give talks;
  • never watch yourself on video giving a talk.

Using the blackboard.

  • write as small as possible;
  • change as much as possible your notations;
  • use abbreviations, and never hesitate to avoid standards;
  • always erase the part of the blackboard that you have just used;
  • never use the blackboard linearly;
  • never think about the way you will use the blackboard before your talk;
  • the best is to avoid written notes, and to avoid to prepare the talk;
  • never speak loudly, and never face the public;
  • never use your hands when speaking, this is a silly Latin habit;
  • pick other good ideas in the Beamer list above: never spend time on intuition or structure, go straight to the technical side, etc.

Further material.

Credit. This post was written in collaboration with my colleague Mathieu Lewin.

2 Comments
Syntax · Style · Tracking & Privacy.