Random matrices: Universality of ESDs and the circular law

Introduction

This paper is concerned with the convergence of empirical spectral distributions of random matrices, both in the sense of convergence in probability and in the almost sure sense.

For each $n$, let $F_{n}$ be a random variable taking values in some Hausdorff topological space $X$, and let $F$ be another element of $X$.

We say that $F_{n}$ converges in probability to $F$ if for every neighbourhood $V$ of $F$, we have $\lim_{n\to\infty}{\mathbf{P}}(F_{n}\in V)=1$.

We say that $F_{n}$ converges almost surely to $F$ if we have ${\mathbf{P}}(\lim_{n\to\infty}F_{n}=F)=1$.

Similarly, if $X_{n}$ is a scalar random variable, we say that $X_{n}$ is bounded in probability if we have

In practice, our matrices $A_{n}$ will have bounded entries on the average, which suggests (by the Weyl comparision inequality, see Lemma A.2) that their eigenvalues should be of size about $O(\sqrt{n})$; thus the normalization by $\frac{1}{\sqrt{n}}$ is natural.

4. Universality

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 situation with this problem, so far, is that the analysis depends very much on which ensemble one is dealing with. In some cases such as when the entries have gaussian distribution, powerful group-theoretic structure (e.g. invariance under the orthogonal group $O(n)$ or unitary group $U(n)$) plays an essential role, as one can use it to derive an explicit formula for the joint distribution of the eigenvalues. The limiting distribution can then be computed directly from this formula. In the majority of cases, however, there is little symmetry, and such a formula is not available. Consequently, the problem becomes much harder and its analysis typically requires tools from various areas of mathematics.

On the other hand, there is a well-known intuition behind this problem (and many others concerning random matrices), the universality phenomenon, that asserts that the limiting distribution should not depend on the particular distribution of the entries. This phenomenon motivates many theorems and conjectures in the area. In the following, we mention two famous examples, Wigner’s semi-circle law and the Circular Law conjecture.

Wigner’s semi circle law. In the 1950’s, motivated by numerical experiments, Wigner proved that the ESD of an $n\times n$ hermitian matrix with (upper diagonal) entries being iid gaussian random variables converge to the semi-circle law $F$ whose density is given by

Wigner’s result (which holds for both modes of convergence) was later extended to many other ensembles. The most general form only requires the mean and variance of the entries :

Let $A_{n}$ be the $n\times n$ hermitian random matrix whose upper diagonal entries are iid complex random variables with mean 0 and variance 1. Then the ESD of $\frac{1}{\sqrt{n}}A_{n}$ converges (both in probability and in the almost sure sense) to the semi-circle distribution.

Circular Law Conjecture. The well-known Circular Law conjecture deals with non-hermitian matrices.

Let $A_{n}$ be the $n\times n$ random matrix whose entries are iid complex random variables with mean 0 and variance 1. Then the ESD of $\frac{1}{\sqrt{n}}A_{n}$ converges (both in probability and in the almost sure sense) to the uniform distribution on the unit disk.

Similarly to Wigner’s law, this conjecture was posed, based on numerical evidence, in the 1950’s. The case when the entries have complex gaussian distribution was verified by Mehta in 1967, using Ginibre’s formula for the joint density function of the eigenvalues of $A_{n}$ (see, for example, [2, Chapter 10]):

Another case where such a formula is available is when the entries have real gaussian distribution, and for this case the conjecture was confirmed by Edelman . For the general case when there is no formula, the problem appears much harder. Important partial results were obtained by Girko , Bai , and more recently Götze-Tikhomirov , Pan-Zhou and the authors . These results establish the conjecture (in almost sure or in probability forms) under additional assumptions on the distribution $x$. The strongest result in the previous literature is from in which the almost sure and in probability forms of the conjecture respectively were shown under the extra assumption that the entries have finite $(2+\epsilon)$-th moment for any positive constant $\epsilon$. An attempt to remove this extra $\epsilon$ (and thus proving Conjecture 1.6 in full generality) was a motivation for this paper.

A demonstration of the circular law for the Bernoulli and the Gaussian case appears in Figure 1.

In both the semi-circular law and the circular law, we observe that only the mean and variance of the entries play a role in the limiting distribution. This is a common situation, in fact, for many other conjectures in random matrix theory, such as Dyson’s conjecture [14, Chapter 1], and this phenomenon sometimes referred to as universality in the literature.

In this paper, we rigorously prove the universality phenomenon for the ESD of random matrices. More precisely, we show that the limiting distribution of the ESD of a random matrix ensemble $A_{n}$ depends only 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 iid entries.

For any matrix $A$, we define the Hilbert-Schmidt norm $\|A\|_{2}$ by the formula $\|A\|:=\operatorname{trace}(AA^{\ast})^{1/2}=\operatorname{trace}(A^{\ast}A)^{1/2}$.

Let $x$ and $y$ be complex random variables with zero mean and unit variance. Let $X_{n}=(x_{ij})_{1\leq i,j\leq n}$ and $Y_{n}:=(y_{ij})_{1\leq i,j\leq n}$ be $n\times n$ random matrices whose entries $x_{ij}$, $y_{ij}$ are iid copies of $x$ and $y$, respectively. For each $n$, let $M_{n}$ be a deterministic $n\times n$ matrix satisfying

Let $A_{n}:=M_{n}+X_{n}$ and $B_{n}:=M_{n}+Y_{n}$. Then $\mu_{\frac{1}{\sqrt{n}}A_{n}}-\mu_{\frac{1}{\sqrt{n}}B_{n}}$ converges in probability to zero. If furthermore we make the additional hypothesis that the ESDs

converge to a limit for almost every $z$, then $\mu_{\frac{1}{\sqrt{n}}A_{n}}-\mu_{\frac{1}{\sqrt{n}}B_{n}}$ converges almost surely to zero.

The theorem still holds if we restrict the size of the matrices to an infinite subsequence $n_{1}<n_{2}<\dots$ of positive integers. This freedom to pass to a subsequence is useful for technical reasons involving compactness arguments.

The condition (3) has the following useful consequence, which we shall use repeatedly:

By the Weyl comparison inequality (Lemma A.2) it suffices to show that $\frac{1}{n^{2}}\|A_{n}\|_{2}^{2}$ is almost surely bounded. By (3) and the triangle inequality it suffices to show that $\frac{1}{n^{2}}\|X_{n}\|_{2}^{2}$ is almost surely bounded. But this follows from the finite second moment of $x$ and the strong law of large numbers. ∎

As an immediate corollary of Theorem 1.7, we have

Let $x,y$ be complex random variables with zero mean and unit variance. Let $X_{n}$ and $Y_{n}$ be $n\times n$ random matrices whose entries are iid copies of $x$ and $y$, respectively. For each $n$, let $M_{n}$ be a deterministic $n\times n$ matrix satisfying (3). Let $A_{n}:=M_{n}+X_{n}$ and $B_{n}:=M_{n}+Y_{n}$. Then if $\mu_{\frac{1}{\sqrt{n}}B_{n}}$ converges in probability to a limiting measure $\mu$, then $\mu_{\frac{1}{\sqrt{n}}A_{n}}$ also converges in probability to $\mu$. If furthermore we make the additional hypothesis that the ESDs (4) converge to a limit for almost every $z$, then we can replace “in probability” by “almost surely” in the previous sentence.

A demonstration of this corollary appears in Figure 2.

One consequence of Corollary 1.10 (in the case when (4) converges to a limit) is that the ESD $\mu_{\frac{1}{\sqrt{n}}A_{n}}$ behaves asymptotically deterministicallyThe authors thank Oded Schramm for this observation. in the sense that there exists a deterministic measure $\mu_{n}$ for each $n$ such that $\mu_{\frac{1}{\sqrt{n}}A_{n}}-\mu_{n}$ converges almost surely to zero. Indeed, one can simply take $\mu_{n}$ to be an instance of $\mu_{\frac{1}{\sqrt{n}}B_{n}}$, where the $B_{n}$ are selected independently of the $A_{n}$, and the claim will hold almost surely. The question remains as to whether $\mu_{n}$ itself converges to some limit as $n\to\infty$; we partially address this issue in Theorem 1.23 below.

12. The Circular Law Conjecture

Thanks to Corollary 1.10, we can reduce the problem of computing the limiting distribution to the case when the entries are gaussianThe idea of establishing a limiting law by first replacing a general random variable with a gaussian one is sometimes referred to as the “Lindberg trick” in the literature. (or having any special distribution satisfying the variance bound). In particular, since the Circular Law is verified for random matrices with complex gaussian entries (see ), it follows that this law (both in probability and in the almost sure sense) holds in full generality. In other words, we have shown

Let $X_{n}$ be the $n\times n$ random matrix whose entries are iid complex random variables with mean 0 and variance 1. Then the ESD of $\frac{1}{\sqrt{n}}X_{n}$ converges (both in probability and in the almost sure sense) to the uniform distribution on the unit disk.

In (see also for an alternate proof for the in probability sense), this theorem was proven with the extra assumption that the entries have finite $(2+{\varepsilon})$-th moment for any fixed ${\varepsilon}>0$; earlier related results are appear in .

The proof of Theorem 1.7 actually shows that if $M_{n}$ and $M_{n}^{\prime}$ both obey (3) and have the property that the difference between the ESD (4) and the counterpart for $M^{\prime}_{n}$ converges to zero for almost every $z$, then Theorem 1.7 holds with $A_{n}:=M_{n}+X_{n}$ and $B_{n}:=M_{n}^{\prime}+Y_{n}$ (see Remark B.3).

This has the following interesting consequence. Assume that $M_{n}$ is a matrix with low rank, say $o(n)$. In this case, it is easy to see that the ESD (4) concentrates at $|z|^{2}$, since the matrix involved here is a self-adjoint low rank perturbation of $|z|^{2}I$. Thus, we can replace $M_{n}$ by the zero matrix and obtain

(Circular Law for shifted matrices) Let $X_{n}$ be the $n\times n$ random matrix whose entries are iid complex random variables with mean 0 and variance 1 and $M_{n}$ be a deterministic matrix with rank $o(n)$ and obeying (3). Let $A_{n}:=M_{n}+X_{n}$. Then the ESD of $\frac{1}{\sqrt{n}}A_{n}$ converges (in either sense) to the uniform distribution on the unit disk.

In particular, it shows that Theorem 1.13 still holds if the entries have (the same) non-zero mean. This extends a result of Chafaï , which in addition assumed that the entries had finite fourth moment.

16. Extensions

We can extend Theorem 1.7 in several ways. First, by conditioning, we can obtain a theorem for $M_{n}$ being a random matrix.

Let $x$ and $y$ be complex random variables with zero mean and unit variance. Let $X_{n}=(x_{ij})_{1\leq i,j\leq n}$ and $Y_{n}=(y_{ij})_{1\leq i,j\leq n}$ be $n\times n$ random matrices whose entries are iid copies of $x$ and $y$, respectively. For each $n$, let $M_{n}$ be a random $n\times n$ matrix, independent of $X_{n}$ or $Y_{n}$, such that $\frac{1}{n^{2}}\|M_{n}\|_{2}^{2}$ is bounded in probability (see Definition 1.2). Let $A_{n}:=M_{n}+X_{n}$ and $B_{n}:=M_{n}+Y_{n}$. Then $\mu_{\frac{1}{\sqrt{n}}A_{n}}-\mu_{\frac{1}{\sqrt{n}}B_{n}}$ converges in probability to zero. If we furthermore assume that $\frac{1}{n^{2}}\|M_{n}\|_{2}^{2}$ is almost surely bounded, and (4) converges almost surely to some limit for almost every $z$, then $\mu_{\frac{1}{\sqrt{n}}A_{n}}-\mu_{\frac{1}{\sqrt{n}}B_{n}}$ converges almost surely to zero.

We can also address a more general form of random matrices (cf. ). Let $K_{n},L_{n}$ be two sequences of matrices. Define $A_{n}:=M_{n}+K_{n}X_{n}L_{n}$ and $B_{n}:=M_{n}+K_{n}Y_{n}L_{n}$. We can show that under some mild assumptions on $M_{n},K_{n},L_{n}$, Theorem 1.7 still holds:

Let $x$ and $y$ be complex random variables with zero mean and unit variance. Let $X_{n}$ and $Y_{n}$ be $n\times n$ random matrices whose entries are iid copies of $x$ and $y$, respectively. Let $M_{n},K_{n},L_{n}$ be random $n\times n$ matrices (independent of $X_{n},Y_{n}$) and let $A_{n}:=M_{n}+K_{n}X_{n}L_{n}$ and $B_{n}:=M_{n}+K_{n}Y_{n}L_{n}$. Assume that the expressions

are bounded in probability. If furthermore we assume that (5) is almost surely bounded, and that for almost every $z$ the ESDs

converge almost surely to a limit, then $\mu_{\frac{1}{\sqrt{n}}A_{n}}-\mu_{\frac{1}{\sqrt{n}}B_{n}}$ converges almost surely to zero.

Note that Theorem 1.17 is the special case of Theorem 1.18 in which $K_{n}=L_{n}=I$. It seems of interest to see whether the hypotheses on (5) can be verified for various natural random or deterministic matrices $M_{n},K_{n},L_{n}$, normalised appropriately by a suitable power of $n$. We do not pursue this matter here.

A demonstration of the above theorem for the Bernoulli and the Gaussian case appears in Figure 3.

The proofs of these extensions are discussed in Section 7.

Another direction for generalization is to consider random matrices whose entries are independent, but not necessarily identically distributed. Most of the tools used in this paper (e.g. law of large numbers, Talagrand’s inequality, and the least singular value bound from ) extend without difficulty to this setting. Furthermore, Krishnapur pointed out that one can also prove a “universal” version of Theorem B.1. This leads to a generalization in Appendix C (written by Krishnapur).

For similar reasons, one expects to be able to extend the above results to the case when $X_{n}$ and $Y_{n}$ are sparse iid random matrices; for instance, the least singular value bounds from extend to this case, and the circular law for sparse iid matrices is already known in several cases , . We, however, will not pursue these matters here.

19. Computing the ESD of a random non-hermitian matrix via the ESD of a hermitian one

The ESD $\mu_{\frac{1}{\sqrt{n}}A_{n}}$ of $\frac{1}{\sqrt{n}}A_{n}$ converges in probability to $\mu$.

If furthermore the ESDs (4) converge to a limit for almost every $z$, then we can replace convergence in probability by almost sure convegence in the above equivalences.

We prove this result in Section 8. As a corollary, we have a criterion for when $\frac{1}{\sqrt{n}}A_{n}$ converges to a distribution $\mu$:

We verify the claim for almost sure convergence only; the proof for convergence in probability is similar and is left as an exercise to the reader.

By Lemma 1.9, we see that for fixed $z$, $|\frac{1}{n}\operatorname{trace}(\frac{1}{\sqrt{n}}A_{n}-zI)(\frac{1}{\sqrt{n}}A_{n}-zI)^{\ast}|$ is also almost surely bounded. Taking limits, we conclude that

Since the eigenvalues of $(\frac{1}{\sqrt{n}}A_{n}-zI)(\frac{1}{\sqrt{n}}A_{n}-zI)^{\ast}$ are the squares of the singular values of $\frac{1}{\sqrt{n}}A_{n}-zI$, we can also say that Theorem 1.20 reduces the problem of computing the limiting distribution of the eigenvalues of $\frac{1}{\sqrt{n}}A_{n}$ to that of the singular values of $\frac{1}{\sqrt{n}}A_{n}-zI$.

The big gain here is that the matrix $(\frac{1}{\sqrt{n}}A_{n}-zI)(\frac{1}{\sqrt{n}}A_{n}-zI)^{\ast}$ is hermitian. (Random matrices of this type are often called sample covariance matrices in the literature.) This allows one to use standard tools such as truncation, Wigner’s moment method and Stieljes transform (see, for instance, the proof of Theorem 1.5 in [2, Chapter 2]), or results such as Theorem B.1; techniques from free probability are also very powerful for such problems. These methods cannot be applied to non-hermitian matrices for various reasons (see [2, Chapter 10] for a discussion) and their failure has been the main difficulty in attacking problems such as the Circular Law conjecture.

One can use Corollary 1.21 to give another proof of Theorem 1.13, without relying on explicit formulas such as (2). We omit the details.

22. Existence of the limit

The results in the previous chapters provide two different ways to compute (explicitly) the limiting measure of the ESD of random matrices. In fact there is a simple compactness argument that guarantees the existence of the limit, assuming of course that the deterministic ESDs (4) already converge, although the argument does not provide too much information on what the limit actually is. More precisely, we have

Let $x$ be a complex random variable with zero mean and unit variance. Let $X_{n}$ be the $n\times n$ random matrix whose entries are iid copies of $x$. For each $n$, let $M_{n}$ be a deterministic $n\times n$ matrix satisfying

Applying Theorem 1.20, we conclude that for almost every $z$, the expression

24. Notation

The asymptotic notation is used under the assumption that $n\rightarrow\infty$, holding all other parameters fixed. Thus for instance, if we say that a quantity $a_{z,n}$ depending on $n$ and another parameter $z$ is equal to $o(1)$, this means that $a_{z,n}$ converges to zero as $n\to\infty$ for fixed $z$, but this convergence need not be uniform in $z$. As another example, the condition (3) is equivalent to asserting that $\|M_{n}\|=O(n)$ as $n\to\infty$.

The replacement principle

The first step toward Theorem 1.7 is the following result that gives a general criterion for two random matrix ensembles $\frac{1}{\sqrt{n}}A_{n},\frac{1}{\sqrt{n}}B_{n}$ to converge to the same limit.

is bounded in probability (resp. almost surely).

converges in probability (resp. almost surely) to zero. In particular, for each fixed $z$, these determinants are non-zero with probability $1-o(1)$ for all $n$ (resp. almost surely non-zero for all but finitely many $n$).

Then $\mu_{\frac{1}{\sqrt{n}}A_{n}}-\mu_{\frac{1}{\sqrt{n}}B_{n}}$ converges in probability (resp. almost surely) to zero.

We would like to remark here that we do not need to require independence among the entries of $A_{n}$ and $B_{n}$. The proof of this theorem is rather “soft” in nature, relying primarily on the Stieltjes transform technique (following Girko ) that analyses the ESD $\mu_{\frac{1}{\sqrt{n}}A_{n}}$ in terms of the log-determinants $\frac{1}{n}\log|\det(\frac{1}{\sqrt{n}}A_{n}-zI)|$, combined with tools from classical real analysis such as the dominated convergence theorem (see Lemma 3.1 for the precise version of this theorem that we need). The details are given in Section 3.

In view of Lemma 1.9, we see that Theorem 1.7 follows immediately from Theorem 2.1 and the following proposition.

converges in probability to zero. If furthermore we assume that (4) converges to a limit for this value of $z$, then (10) converges almost surely to zero.

For any square matrix $A$ of size $n$, let $\lambda_{i}(A)$ and $s_{i}(A)$ be the eigenvalues and singular values of $A$. Furthermore, let $d_{i}(A)$ be the distance from the $i$th row vector of $A$ to the subspace formed by the first $i-1$ row vectors. From linear algebra, we have the fundamental identity

We will need to study the singular values and distances of $\frac{1}{\sqrt{n}}A_{n}-zI$ and $\frac{1}{\sqrt{n}}B_{n}-zI$ in order to estimate their determinants. The proof of Proposition 2.2, which occupies Sections 4, 5 and 6, is the heart of the paper. This proof relies on the following three ingredients:

A result by Dozier and Silverstein that compares the ESD of the singular values of the matrices $\frac{1}{\sqrt{n}}A_{n}-zI$ and $\frac{1}{\sqrt{n}}B_{n}-zI$. This will let us handle all the rows from $1$ to $(1-\delta)n$ for some small $\delta>0$.

A lower tail estimate for the distance between a random vector and a fixed subspace of relatively large co-dimension, using a concentration inequality of Talagrand . This will handle the contribution of the rows between $(1-\delta)n$ and (say) $n-n^{0.99}$.

A polynomial lower bound for the least singular value of $\frac{1}{\sqrt{n}}A_{n}-zI$ and $\frac{1}{\sqrt{n}}B_{n}-zI$ from . This bound enables us to handle the contribution of the last $n^{0.99}$ rows.

The replacement principle

The purpose of this section is to establish Theorem 2.1. We begin with a version of the dominated convergence theorem.

(Uniform integrability) There exists $\delta>0$ such that $\int_{X}|f_{n}(x)|^{1+\delta}\ d\nu$ is bounded in probability (resp. almost surely).

(Pointwise convergence in probability) For $\nu$-almost every $x\in X$, $f_{n}(x)$ converges in probability (resp. almost surely) to zero.

Then $\int_{X}f_{n}(x)\ d\nu(x)$ converges in probability (resp. almost surely) to zero.

We first prove the claim for convergence in probability. We can normalise $\nu$ to be a probability measure. Let ${\varepsilon}>0$ be arbitrary. It suffices to show that

with probability $1-O({\varepsilon})-o(1)$.

By hypothesis (i), we already know that with probability $1-O({\varepsilon})-o(1)$, that

for some $C_{\varepsilon}$ depending on ${\varepsilon}$. This implies that

for any $M>0$, where ${\mathbf{I}}(E)$ denotes the indicator of an event $E$. In particular, for $M$ large enough we have

with probability $1-O({\varepsilon})-o(1)$, and so it will suffice to show that

Fix $M$. By hypothesis, we have $\lim_{n\to\infty}{\mathbf{P}}(|f_{n}(x)|\geq{\varepsilon})=0$ for $\nu$-almost every $x\in X$. By the dominated convergence theorem, we conclude that

with probability $1-o(1)$. The claim (12) easily follows.

Now we prove the claim for almost sure convergence. Again we let $\nu$ be a probability measure and ${\varepsilon}>0$ be arbitrary. With probability $1-O({\varepsilon})$ we have

for all sufficiently large $n$, and some $C_{\varepsilon}$ depending on $n$. Also, with probability $1$, $f_{n}(x)$ converges to zero for almost every $x$. The claim now follows by invoking (the deterministic special case of) the convergence in probability version of the lemma that we have just proven. ∎

Now we begin the proof of Theorem 2.1. We thus assume that $A_{n},B_{n}$ are as in that theorem. We shall first prove the claim for convergence in probability, and indicate later how to modify the proof to obtain the principle for almost sure convergence.

From the boundedness in probability of (9) and Weyl’s comparison inequality (Lemma A.2) we see that for every ${\varepsilon}>0$ there exists $C_{\varepsilon}>0$ such that for each $n$, the eigenvalues $\lambda_{1},\ldots,\lambda_{n}$ of $A_{n}$ obey the bound

with probability $1-O({\varepsilon})-o(1)$. Similarly we have

In particular, for each $n$ we see that with probability $1-O({\varepsilon})-o(1)$ we have the tightness bounds

thus the functions $m_{\frac{1}{\sqrt{n}}A_{n}},m_{\frac{1}{\sqrt{n}}B_{n}}$ are continuous and are bounded uniformly in magnitude by $1$.

Thanks to the tightness bounds (14)-(15), we can easily pass back and forth between convergence of ESDs and convergence of characteristic functions:

Let the notation and assumptions be as above. Then the following are equivalent:

$\mu_{\frac{1}{\sqrt{n}}A_{n}}-\mu_{\frac{1}{\sqrt{n}}B_{n}}$ converges in probability.

For almost every $u,v$, $m_{\frac{1}{\sqrt{n}}A_{n}}(u,v)-m_{\frac{1}{\sqrt{n}}B_{n}}(u,v)$ converges in probability.

We first show that (i) implies (ii). Fix $u,v$, and let ${\varepsilon}>0$ be arbitrary. From (14), (15) we can find an $R$ depending on $C_{\varepsilon}$ and ${\varepsilon}$ such that

with probability $1-O({\varepsilon})-o(1)$. In particular, with probability $1-O({\varepsilon})-o(1)$ we have

where $\psi$ is any smooth compactly supported function that equals one on the unit ball. But since $\mu_{\frac{1}{\sqrt{n}}B_{n}}-\mu_{\frac{1}{\sqrt{n}}A_{n}}$ converges in probability, the integral here converges to zero in probability. The claim follows.

for some smooth, rapidly decreasing function $\hat{f}$. In particular, the measure $d\nu=\hat{f}(u,v)\ dudv$ is finite. The claim now follows from dominated convergence (Lemma 3.1); note that the function $m_{\frac{1}{\sqrt{n}}A_{n}}-m_{\frac{1}{\sqrt{n}}B_{n}}$ is bounded and so clearly obeys the moment condition required in that lemma. ∎

Fix $u,v$. Since we can exclude a set of measure zero, we can assume that $u,v$ are non-zero. We allow all implied constants in the arguments below to depend on $u,v$.

We have the following fundamental identity:

where the inner integral is absolutely integrable for almost every $s$, and the outer integral is absolutely convergent.

for each complex number $w$, with an absolutely convergent inner integral and outer integral. But standard contour integration shows that

for every $s\neq{\operatorname{Re}}(w)$, and the claim follows by an elementary integration. ∎

We can of course define $g_{\frac{1}{\sqrt{n}}B_{n}}$ similarly, with analogous identities. To conclude the proof of Theorem 2.1, it thus suffices to show that for any ${\varepsilon}>0$ and any $n$, we have

with probability $1-O({\varepsilon})-o(1)$.

Fix ${\varepsilon}>0$. By (14), (15), we can find an $R>1$ large enough that with probability $1-O({\varepsilon})$,

We now condition on the event that (21) holds.

is of size $O(1)$, and (if $R$ is large enough) is of size $O({\varepsilon})$ when $|w|\leq R$.

is of size $O(1)$, and (if $R$ is large enough) is of size $O({\varepsilon})$ when $|w|\leq R$.

The claim (i) follows easily from (19), so we turn to (ii). We first verify the claim that (22) is bounded. Replacing everything by absolute values one sees that

(in fact one can obtain an explicit upper bound of $\pi$), so we can dispose of the region of integration in which $s={\operatorname{Re}}(w)+O(1)$. For the remaining values of $s$, we use repeated integration by parts, integrating the $e^{ivt}$ term and differentiating the others. After two such integrations we obtain the bound

Finally, if $|w|\leq R$, then one easily verifies (by repeated integration by parts) that

(say), and so the final claim of (ii) follows. ∎

From this lemma and (17), the triangle inequality and (21) we conclude that

From (23), (24) (and their counterparts for $g_{\frac{1}{\sqrt{n}}B_{n}}$) and the triangle inequality, we thus see that to prove (20), it suffices to show that

converges in probability to zero for every fixed $R\geq 1$. Note that the integrands here are now jointly absolutely integrable in $t,s$, and so we may now freely interchange the order of integration.

Fix $R$. Using (18) and integration by parts in the $s$ variable, we can rewrite (25) in the form

(Note that there are finitely many values of $t$ for which the integration by parts is not justified due to singularities in $g_{\frac{1}{\sqrt{n}}A_{n}}$ or $g_{\frac{1}{\sqrt{n}}B_{n}}$, but these values of $t$ clearly give a zero contribution at the end of the day.) Thus it will suffice to show that

and similarly for $B_{n}$. From the boundedness and compact support of $\phi_{u,v,R}$ we observe that

is bounded uniformly in $n$. Since by hypothesis $f_{n}(s,t)$ converges in probability to zero for almost every $s,t$, the claim now follows from dominated convergence (Lemma 3.1). The proof of Theorem 2.1 is now complete in the case of convergence in probability.

We now indicate how to adapt the above arguments to the case of almost sure convergence. Firstly, since (9) is now almost surely bounded instead of just bounded in probability, we can now say that for every ${\varepsilon}>0$ there exists $C_{\varepsilon}>0$ such that with probability $1-O({\varepsilon})$, (14), (15) holds for all sufficiently large $n$ (as opposed to these bounds holding with probability $1-O({\varepsilon})-o(1)$ for each $n$ separately).

Next, we observe the (well-known) fact that Lemma 3.2 continues to hold when convergence in probability is replaced by almost sure convergence throughout. Indeed the implication of (ii) from (i) is nearly identical and is left as an exercise to the reader. To deduce (i) from (ii) in the almost sure case, observe from the separability of the space of smooth compactly supported functions in the uniform topology that it suffices to show that (16) converges almost surely to zero for each $f$. On the other hand, from (ii) and Fubini’s theorem we know that with probability $1$, that $m_{\frac{1}{\sqrt{n}}A_{n}}(u,v)-m(u,v)$ converges to zero for almost every $u,v$, and the claim follows from the (ordinary) dominated convergence theorem.

Once again we use Girko’s identity, Lemma 3.3, and reduce to showing that for every ${\varepsilon}>0$, one has with probability $1-O({\varepsilon})$ that (20) holds for all but finitely many $n$. From our bounds on (14), (15) we see that with probability $1-O({\varepsilon})$, that (21) holds for all but finitely many $n$. We apply Lemma 3.4 (which is deterministic) and reduce to showing that (25) converges almost surely to zero for each fixed $R\geq 1$. The rest of the argument proceeds as in the convergence in probability case.

6. An alternate argument

There is an alternate derivationWe thank Manjunath Krishnapur for this simpler argument. of Theorem 2.1 that avoids Fourier analysis, and is instead based on the observation that for any complex polynomial $P(z)$, the distributional Laplacian $\Delta\log|P(z)|$ of the logarithm of the magnitude of $P$ is equal to the counting measure of the zeroes of $P$ (counting multiplicity). In particular, we see from Green’s theorem that

for any smooth, compactly supported $f$. Applying Lemma 3.1 we can then get convergence of this integral (either in probability or in the almost sure sense, as appropriate); the uniform integrability required can be established by repeating the computations used to bound (27). One can then easily take limits to replace smooth compactly supported $f$ to continuous compactly supported $f$; we omit the details.

Proof of Proposition 2.2

In this section we present the proof of Proposition 2.2, modulo several key lemmas. Let $x,y,M_{n},A_{n},B_{n},z$ be as in that proposition. By shifting $M_{n}$ by $\sqrt{n}zI$ if necessary we can assume $z=0$. Our task is now to show that

converges in probability to zero, and also almost surely to zero if $\mu_{\frac{1}{n}M_{n}M_{n}^{\ast}}$ converges.

Let us first remark that the almost sure convergence claim implies the convergence in probability claim. Indeed, suppose that convergence in probability failed, then there would exist an ${\varepsilon}>0$ such that

for a subsequence of $n$. By vague sequential compactness one can pass to a further subsequence along which $\mu_{\frac{1}{n}M_{n}M_{n}^{\ast}}$ converges, and hence by hypothesis one has almost sure (and hence in probability) convergence to zero along this sequence, contradicting (28). Thus it suffices to establish almost sure convergence assuming the convergence of $\mu_{\frac{1}{n}M_{n}M_{n}^{\ast}}$.

Let $Z_{1},\ldots,Z_{n}$ be the rows of $M_{n}$. By assumption (3) we have

In particular, at least half of the $Z_{i}$ have norm $O(\sqrt{n})$. By permuting the rows of $M_{n},A_{n},B_{n}$ if necessary, we may assume that it the last half of the rows have this property, thus

Let $\sigma_{1}(A)\geq\ldots\geq\sigma_{n}(A)\geq 0$ denote the singular values of a matrix $A$. We have the following fundamental lower bound:

for all but finitely many $n$. In particular, with probability $1$, $A_{n}$ and $B_{n}$ are invertible for all but finitely many $n$.

This follows immediately from [26, Theorem 2.1] or [27, Theorem 4.1] and the Borel-Cantelli lemma, noting from (3) of Proposition 2.2 that the operator norm of $M_{n}$ is of polynomial size $n^{O(1)}$. There are previous results in , , , , which handled special cases with more assumptions on $M_{n}$ and the underlying distributions $x,y$ (for instance, in some of the prior results $M_{n}$ was assumed to vanish, or $x,y$ were assumed to be integer-valued or to have finite higher moments). One can obtain explicit bounds on the tail probability and on the exponent $O(1)$; see . However, for our applications the above bounds will suffice. ∎

We also have with probability $1$ the crude upper bound

for all but finitely many $n$, which follows easily from the polynomial size of $M_{n}$ the bounded second moment of $x,y$, and the Borel-Cantelli lemma. Again, much sharper bounds are available, especially if $x$ and $y$ have finite fourth moment, but we will not need these bounds here.

Let $X_{1},\ldots,X_{n}$ be the rows of $A_{n}$, and for each $1\leq i\leq n$ let $V_{i}$ be the $i-1$-dimensional space generated by $X_{1},\ldots,X_{i-1}$. From (11) we have

where $Y_{1},\ldots,Y_{n}$ are the rows of $\frac{1}{\sqrt{n}}B_{n}$, and $W_{i}$ is spanned by $Y_{1},\ldots,Y_{i-1}$. Our task is then to show that

From (30), (31) and Lemma A.4 we almost surely obtain the bound

for all but finitely many $n$. Thus it suffices to show that

(say) converges almost surely to zero. This follows immediately from the following two lemmas.

For every ${\varepsilon}>0$ there exists $0<\delta<1/2$ such that with probability $1$, one has

for all but finitely many $n$. Similarly with $\operatorname{dist}(\frac{1}{\sqrt{n}}X_{i},V_{i})$ replaced by $\operatorname{dist}(\frac{1}{\sqrt{n}}Y_{i},W_{i})$.

For every ${\varepsilon}>0$ there exists $0<\delta<1/2$, such that with probability $1-O({\varepsilon})$, one has

The next two sections will be devoted to the proofs of these two lemmas.

Proof of Lemma 4.2

We now prove Lemma 4.2. We can of course take $n$ to be large depending on all fixed parameters. Let $0<\delta<1/2$ be a small number depending on ${\varepsilon}$ to be chosen later.

Clearly it suffices to prove this lemma for $\operatorname{dist}(\frac{1}{\sqrt{n}}X_{i},V_{i})$. We first prove the (much easier) bound for the positive component of the logarithm. By the Borel-Cantelli lemma it suffices to show that

To establish this, we use the crude bound

Thus if the left-hand side of (32) exceeds ${\varepsilon}$, we must have

(say) for some $m\geq 0$. On the other hand, from (29) and the second moment method we see that ${\mathbf{P}}(\|X_{i}\|\geq 2^{m}\sqrt{n})=O(2^{-2m})$, and thus by Hoeffding’s inequality we have

(say) for some constants $C,c>0$ depending on ${\varepsilon}$, if $\delta$ is chosen sufficiently small depending on ${\varepsilon}$. The claim follows.

It remains to establish the bound for the negative component of the logarithm. By the Borel-Cantelli lemma it suffices to show that

This will follow from the union bound and the following estimate.

(The implied constant of course depends on $c$.)

Indeed, since $X_{i}$ and $V_{i}$ are independent of each other, the proposition implies that

(say) for each $(1-\delta)n\leq i\leq n-n^{0.99}$, with probability $1-O(n^{-10})$ (say). Setting $\delta$ sufficiently small (compared to $\epsilon)$, taking logarithms and summing in $i$ and $n$ one obtains the claim.

It remains to prove the proposition. Similar lower bounds concerning the distance of a random vector to a fixed subspace have appeared in , , . Here, however, we have the complication that the coefficients of $X$ have non-zero mean and have no higher moment bounds than the second moment; in particular, they can be unbounded.

We first eliminate the problem that $X$ has non-zero mean. Write $X=v+X^{\prime}$, where $v:={\mathbf{E}}(X)$ is a deterministic vector (which could be quite large) and $X^{\prime}$ has mean zero. Then we have $\operatorname{dist}(X,W)\geq\operatorname{dist}(X^{\prime},\operatorname{span}(W,v))$. Thus Proposition 5.1 follows from the mean zero case (after making the harmless change of incrementing $d$ to $d+1$, and adjusting the parameters slightly to suit this).

Henceforth we assume that $X$ has mean zero, thus $X=(x_{1},\ldots,x_{n})$ for some iid copies $x_{1},\ldots,x_{n}$ of $x$. Now we deal with the problem that the $x_{1},\ldots,x_{n}$ can be unbounded. By Chebyshev’s inequality, we have ${\mathbf{P}}(|x_{i}|\geq n^{0.1})=O(n^{-0.2})$ for all $1\leq i\leq n$. The event $|x_{i}|\geq n^{0.1}$ are jointly independent in $i$. By Chernoff inequality (see, for instance, [23, Chapter 1]), we can show that with probability $1-O(\exp(-n^{0.01}))$, that there are at most $n^{0.9}$ indices $i$ for which $|x_{i}|\geq n^{0.1}$. (One can also verify this directly using binomial coefficients and Sterling’s formula.)

By conditioning on the various possible sets of indices for which $|x_{i}|\geq n^{0.1}$, we see that it suffices to show that

for each $I\subset\{1,\ldots,n\}$ of cardinality at most $n^{0.9}$, where $E_{I}$ is the event that $I=\{1\leq i\leq n:|x_{i}|\geq n^{0.1}\}$.

Without loss of generality we can take $I=\{n^{\prime}+1,\ldots,n\}$ for some $n-n^{0.9}\leq n^{\prime}\leq n$. We then observe that

To prove (33), we recall the following inequality of Talagrand.

This is the complex version of [13, Corollary 4.10], in which ${\mathbf{D}}$ was replaced by the unit interval $$. The proof is the same, with a slight modification that implies a worse the constant ($1/8$instead of$1/4$) in the exponent. ∎

for every $r>0$. On the other hand, we can easily compute the second moment (cf. [22, Lemma 2.5]):

Since $n-d\geq n^{0.99}$ and $c<1$, the claim (33) from follows from (34) and the above lemma. The proof of Lemma 4.2 is now complete.

Proof of Lemma 4.3

We now begin the proof of Lemma 4.3. Fix ${\varepsilon}$, and assume that $\delta$ is sufficiently small depending on ${\varepsilon}$. Write $n^{\prime}:=\lfloor(1-\delta)n\rfloor$. Observe that $\prod_{i=1}^{n^{\prime}}\operatorname{dist}(\frac{1}{\sqrt{n}}X_{i},V_{i})$ is the $n^{\prime}$-dimensional volume of the parallelepiped spanned by $X_{1},\ldots,X_{n^{\prime}}$, which is also equal to $\det(\frac{1}{n}A_{n,n^{\prime}}A_{n,n^{\prime}}^{\ast})^{1/2}$, where $A_{n,n^{\prime}}$ is the $n^{\prime}\times n$ matrix with rows $X_{1},\ldots,X_{n^{\prime}}$. Expressing this determinant as the product of singular values, we conclude the identity

Similarly for $Y_{i},W_{i}$, and $B_{n,n^{\prime}}$ (the matrix generated by $Y_{1},\ldots,Y_{n^{\prime}}$. Thus it suffices to show that with probability $1-O({\varepsilon})$, one has

for all but finitely many $n$. We rewrite (35) as

where $d\nu_{n,n^{\prime}}$ is the difference of two ESDs:

We control (35) by dividing the range of $t$ into several parts.

We now control the region where $t\geq R_{\varepsilon}$ for some large $R_{\varepsilon}$.

is also almost surely bounded. Thus, with probability $1-O({\varepsilon})$, we have

for all but finitely many $n$, and some $C_{\varepsilon}$ independent of $n$, which implies that

for all but finitely many $n$, and some $R_{\varepsilon}$ depending only on ${\varepsilon}$.

2. The region of intermediate t𝑡t

We now control the region ${\varepsilon}^{4}\leq t\leq R_{\varepsilon}$.

Let $\psi$ be a smooth function which equals $1$ on $[{\varepsilon}^{4},R_{\varepsilon}]$ and is supported on $[{\varepsilon}^{4}/2,2R_{\varepsilon}]$. Then with probability $1$, we have

if $\delta$ is sufficiently small depending on ${\varepsilon}$ and $\psi$.

From the interlacing property (Lemma A.1), we see that

if $\delta$ is sufficiently small depending on ${\varepsilon}$ and $\psi$.

We now apply the recent result in [3, Theorem 1.1]. For the reader’s convenience, we restate this result in the Appendix; see Theorem B.1. This result asserts under the above hypotheses that the ESDs $d\mu_{\frac{1}{n}A_{n}A_{n}^{\ast}}$ and $d\mu_{\frac{1}{n}B_{n}B_{n}^{\ast}}$ converge almost surely to the same limit (in fact, this limit is given explicitly in terms of the limiting distribution of $\mu_{\frac{1}{n}M_{n}M_{n}^{\ast}}$ via the inverse Stieltjes transform of (47)). In particular, $\nu_{n,n}$ converges almost surely to zero, and the claim follows. ∎

Note that for the convergence in probability case of Proposition 2.2, we need to apply Theorem B.1 to a subsequence of $n$ rather than to all $n$, thanks to the subsequence extraction performed at the beginning of Section 4.

5. The region of moderately small t𝑡t

We now control the region $\delta^{2}\leq t\leq{\varepsilon}^{4}$. For this we need some bounds on the low singular values of $A_{n,n^{\prime}}$ and $B_{n,n^{\prime}}$.

for all but finitely many $n$, and similarly with $A_{n,n^{\prime}}$ replaced by $B_{n,n^{\prime}}$.

Clearly it suffices to establish the claim for $A_{n,n^{\prime}}$. Using Proposition 5.1 and the Borel-Cantelli lemma, we see that with probability $1$, we have

for all but finitely many $n$, and all $1\leq i\leq n^{\prime}$. The claim then follows from Lemma A.4. ∎

Since the $\sigma_{i}(A_{n,n^{\prime}})$ are decreasing in $i$, and $n^{\prime}=\lfloor(1-\delta)n\rfloor$, we see that the above lemma implies that with probability $1$, we have

for all but finitely many $n$, and some absolute constant $c>0$. We can generalize this lower bound to handle higher singular values also:

There exists an absolute constant $c>0$ such that with probability $1$, we have

for all but finitely many $n$, and all $1\leq i\leq(1-2\delta)n$, and similarly with $A_{n,n^{\prime}}$ replaced by $B_{n,n^{\prime}}$.

Clearly it suffices to establish the claim for $A_{n,n^{\prime}}$. Using Proposition 5.1 and the Borel-Cantelli lemma, we see that with probability $1$, we have

for all but finitely many $n$, and all $1\leq i\leq n^{\prime\prime}$ and $n/2\leq n^{\prime\prime}\leq n^{\prime}$. Applying Lemma A.4, we conclude that we almost surely have

for all but finitely many $n$, and all $n/2\leq n^{\prime\prime}\leq n^{\prime}$. Using the crude bound

for all but finitely many $n$, all $n/2\leq n^{\prime\prime}\leq n^{\prime}$, and some absolute constant $c^{\prime}>0$. The claim now follows from the Cauchy interlacing property (Lemma A.1). ∎

If one assumes stronger moment assumptions (e.g subgaussian) on $x$, then more precise bounds are known, especially in the $M_{n}=0$ case: see , .

From this lemma we can now bound the relevant contribution to (35):

With probability $1$, and if $\delta$ is sufficiently small depending on ${\varepsilon}$, we have

By the triangle inequality and symmetry it suffices to show that with probability $1$, we have

for all but finitely many $n$. We rewrite the left-hand side as

where $f(t):=|\log t|{\mathbf{I}}(\delta^{2}\leq t^{2}\leq{\varepsilon}^{4})$. Since $f$ cannot exceed $|\log\delta|$, we see that the contribution of the case $i\geq(1-2\delta)n$ is acceptable if $\delta$ is small enough, so it suffices to show that we almost surely have

By Lemma 6.7, we may assume that $n$ is such that (40) holds. As a consequence, we see that the only terms in the above sum which are non-vanishing are those for which $i=(1-O({\varepsilon}^{2}))n$. But then if we apply (40) and crudely estimate $f(t)\leq-\log t$ we obtain the claim. ∎

10. The contribution of very small t𝑡t

Finally, we need to control the contribution when $t\leq\delta$.

With probability $1$, and if $\delta$ is sufficiently small depending on ${\varepsilon}$, we have

By arguing as in the proof of Lemma 6.9, it suffices to show that we almost surely have

for all but finitely many $n$, where $g(t):=|\log t|{\mathbf{I}}(t^{2}\leq\delta^{2})$.

By Lemmas 6.6, we may assume $n$ is such that (39) holds. On the other hand, if $\delta$ is small enough, we have the bound $g(t)\leq{\varepsilon}t^{-2}$. The claim now follows from (39). ∎

Putting together (37), (38), (41), (42) we see that with probability $1-O({\varepsilon})$, we have (36) for all but finitely many $n$, and the claim follows.

Extensions

The theorem in the case of almost sure convergence follows immediately from Theorem 1.7 by conditioning on $M_{n}$, so it remains to verify the theorem in the case of convergence in probability.

Let fix a test function $f$ (as in (1)) and a positive ${\varepsilon}$. By the boundedness in probability of $\frac{1}{n^{2}}\|M\|_{2}^{2}$, we can find a $C=C_{\varepsilon}$ such that ${\mathbf{P}}(M_{n}\in\Omega_{n})\geq 1-{\varepsilon}$, where

Let $M_{n}^{f}$ be the matrix in $\Omega_{n}$ which maximizesIf the maximum is not attained, one can instead choose $M_{n}^{f}$ to be a matrix which maximizes this quantity to within a factor of two (say). the quantity

Applying Theorem 1.7 to the sequence $M_{n}^{f}+X_{n}$ and $M_{n}^{f}+Y_{n}$, we see that this quantity is $o(1)$.

Theorem 1.17 follows by integrating over all possible values of $M_{n}$ using the definition of $M_{n}^{f}$, as well as the fact that ${\mathbf{P}}(\Omega_{n})\geq 1-{\varepsilon}$, and then letting ${\varepsilon}\to 0$.

2. Proof of Theorem 1.18

We first verify the claim for convergence in probability.

The condition (i) of Theorem 2.1 is satisfied thanks to the boundedness in probability of (5). In order to complete the proof, one needs to check (ii). Notice that

The term $\det L_{n}K_{n}$ also appears in $\det(\frac{1}{\sqrt{n}}B_{n}-zI)$ and becomes additive (and thus cancels) after taking logarithm. Therefore, one only needs to show that

One can obtain this by repeating the proof of Proposition 2.2. The slight change here is that $zI$ is replaced by $zK_{n}^{-1}L_{n}^{-1}$, but this has no significant impact, except that we need to show

almost surely (in order to guarantee (3)). But this is a consequence of the boundedness in probability of (5).

The proof of the almost sure convergence is established similarly, with the obvious changes (e.g. replacing boundedness in probability with almost sure boundedness). We omit the details.

Proof of Theorem 1.20

We first prove that (ii) implies (i) for almost sure convergence. Let $A_{n}$ and $\mu$ be as in Theorem 1.20. Construct a diagonal matrix $B^{\prime}_{n}$ whose diagonal entries are independent samples from $\mu$ and let $B_{n}:=\sqrt{n}B^{\prime}_{n}$. We wish to invoke Theorem 2.1. We first need to verify the almost sure boundedness of (9). The bound for $A_{n}$ follows from Lemma 1.9, and the bound for $B_{n}$ follows from the second moment hypothesis on $\mu$ and the (strong) law of large numbers. By Theorem 2.1, the problem now reduces to showing that for almost all complex numbers $z$,

converges almost surely to zero. The right hand side is easy to compute:

From Lemma 1.9, we know that $\frac{1}{n^{2}}\|A_{n}\|_{2}^{2}$ is almost surely bounded, and so for each $z$

is almost surely bounded also. From this we easily see that

converges almost surely to zero for some sequence $\delta_{n}$ (depending on ${\varepsilon}_{n}$) converging sufficiently slowly to zero. To conclude the almost sure convergence of (44) to zero, it thus suffices to show that

converges almost surely to zero. Using Lemma 4.1, we almost surely have $\sup_{i}\log\frac{1}{\sigma_{i}}\leq O(\log n)$ for all but finitely many $n$, so it suffices to show that

converges almost surely to zero. To do this, it suffices by the union bound and the Borel-Cantelli lemma to show that

for all $1\leq i\leq n-n^{0.99}$ and some $c>0$ independent of $n$.

For this we argue as in the proof of Lemma 6.7. Fix $i$. Let $A^{\prime}_{n}$ be the matrix form by the first $n-k$ rows of $A_{n}-z\sqrt{n}I$ with $k:=i/2$ and $\sigma^{\prime}_{j},1\leq j\leq n-k$ be the singular values of $A_{n}^{\prime}$(in decreasing order, as usual). By the interlacing law (Lemma A.1) and re-normalizing,

where $\operatorname{dist}_{j}$ is the distance from the $j$th row of $A^{\prime}_{n}$ to the subspace spanned by the remaining rows.

As shown in the proof of Lemma 4.2, with probability $1-\exp(-n^{-0.01})$, $\operatorname{dist}_{j}$ is bounded from below by $\Omega(\sqrt{k})=\Omega(\sqrt{i})$ for all $j$. Thus, with this probability, the right hand side in the above identity is $O(n/i)$. On the other hand, as the $\sigma_{j}^{\prime}$ are ordered decreasingly, the left hand side is at least

It follows that with probability $1-\exp(-n^{-0.01})$,

This and (46) complete the proof of (45), and so (44) converges almost surely to zero.

As previously observed, the convergence of (44) to zero shows that (ii) implies (iii) for almost sure convergence. An inspection of the argument shows the convergence of (44) to zero also lets us deduce (iii) from (ii). The claim for convergence in probability follows similarly. To conclude the proof of Theorem 1.20, it thus suffices to show that (i) implies (ii).

By repeating the arguments used to establish the almost sure convergence of (44) to zero, it suffices to show that

Let us order the eigenvalues $\lambda_{i}$ so that $|\lambda_{1}|\geq\ldots\geq|\lambda_{n}|$. From Lemma 4.1 and (45) (and the Borel-Cantelli lemma) we know that we almost surely have

for all but finitely many $n$ for any fixed $0<\kappa<1/2$, and hence by Weyl’s comparison inequality (Lemma A.3) that we almost surely have

for all but finitely many $n$ also. Since the left-hand side is bounded from below by $\kappa\log\frac{1}{|\lambda_{\lfloor(1-\kappa)n\rfloor}|}$ we almost surely conclude a lower bound of the form

for all but finitely many $n$. In particular (by setting $\delta$ to be a suitable power of $\kappa$) this implies that almost surely

for all but finitely many $n$ for any fixed $0<\delta\ll 1$ and some absolute constant $c>0$, and the claim follows. The analogous implication for convergence in probability is similar. The proof of Theorem 1.20 is now complete.

Appendix A Linear algebra inequalities

In this appendix we record some elementary identities and inequalities regarding the eigenvalues and singular values of matrices.

Let $A$ be an $n\times n$ matrix with complex entries and $A^{\prime}$ be the submatrix formed by the first $m:=n-k$ rows. Let $\sigma_{1}(A)\geq\ldots\geq\sigma_{n}(A)\geq 0$ denote the singular values of $A$, and similarly for $A^{\prime}$. Then we have

The claim follows easily from the minimax characterization

of the singular values, where $V_{i}$ range over $i$-dimensional complex subspaces. ∎

The two equalities here are clear, so it suffices to prove the inequality. By the Jordan normal form we can write $A=BUB^{-1}$ for some upper-triangular $U$ and invertible $B$. By the $QR$ factorization we can write $B=QR$ for some orthogonal $Q$ and upper triangular $R$. We conclude that $A=QVQ^{-1}$ for some upper triangular $V$. Conjugating by $Q$, we thus reduce to the case when $A$ is an upper triangular matrix, in which case the eigenvalues are simply the diagonal entries $a_{11},\ldots,a_{nn}$ and the claim is clear. ∎

We also have the following (stronger) variant of the above inequality:

It suffices to prove the former claim, as the latter then follows from (11). By arguing as in Lemma A.2 we may assume that $A$ is upper triangular, so that the diagonal entries are some permutation of $\lambda_{1},\ldots,\lambda_{n}$. Consider the symmetric minor $A^{\prime}$ of $A$ formed by the rows and columns corresponding to the entries $\lambda_{1},\ldots,\lambda_{J}$. The determinant of this matrix is then $\lambda_{1}\ldots\lambda_{J}$, and thus by (11) we have

The claim then follows from the Cauchy interlacing inequality (Lemma A.1). ∎

Now we record a useful identity for the negative second moment of a rectangular matrix.

Observe that the $n^{\prime}\times n^{\prime}$ matrix $(AA^{\ast})^{-1}$ has eigenvalues

Since $v_{j,j}=v_{j}\cdot e_{j}=(AA^{\ast})^{-1}e_{j}\cdot e_{j}$, the claim follows. ∎

Appendix B A result of Dozier and Silverstein

Here we reproduce Theorem 1.1 of which we used in the end of Section 6.

[3, Theorem 1.1] Let $c$ be a positive constant and $x$ be a random variable with variance one. Let $X_{n}$ be an $n\times r$ random matrix whose entries are iid copies of $x$, where $r=(c+o(1))n$. Let $M_{n}$ be a random $n\times r$ matrix independent from $X_{n}$ such that the ESD of $M_{n}M_{n}^{\ast}$ converges to a limiting distribution $H$. Define $C_{n}:=\frac{c}{n}(M_{n}+X_{n})(M_{n}+X_{n})^{\ast}$. Then the ESD of $C_{n}$ converges almost surely (and hence also in probability) to a limiting distribution $F$, whose Stieljes transform $m(z):=\int\frac{1}{\lambda-z}dF(\lambda)$ satisfies the integral equation