A universality result for the smallest eigenvalues of certain sample covariance matrices

Part I Introduction

It has been long conjectured that some of the asymptotic statistical properties that are known for eigenvalues of large matrices with Gaussian entries should be valid, in particular, for more general random matrices with independent entries. This is part of a phenomenon called ‘universality’ in the physical literature; see for example Conjecture 1.2.1, Conjecture 1.2.2, and various remarks scattered in Mehta’s book .

In particular, the local statistics of the eigenvalues at the edge of the spectrum should be the same as in the Gaussian case (precise definitions are provided below.)

The first rigorous results of this kind are due to Soshnikov. In , he established a universality result at the edge for large Hermitian matrices with independent entries; we formulate his result as Theorem I.1.3 below. Universality at the edge for Hermitian random matrices with independent entries was further studied by Ruzmaikina and Khorunzhiy and Vengerovsky .

In the subsequent work , Soshnikov extended his method to the largest eigenvalues of the sample covariance matrices $XX^{\ast}$, under some restrictions on the dimensions of the matrices $X$. These restrictions were later disposed of by Péché ; see Theorem I.1.2 below.

In the Hermitian case, the largest and the smallest eigenvalues are identically distributed; Soshnikov’s result encompasses both the largest and the smallest eigenvalue. The state of affairs is different for sample covariance matrices, the smallest eigenvalue of which is much smaller in absolute value than the largest one. Therefore Soshnikov’s approach does not seem to be applicable to the smallest eigenvalue of a sample covariance matrix; we discuss this further below.

In this paper, we suggest a different approach, and apply it to prove a universality result for the smallest eigenvalue of a sample covariance matrix; see Theorem I.1.1 below. We also apply it to give another proof of the results of Soshnikov and Péché, Theorems I.1.3 and I.1.2.

In the special case of Gaussian matrices, alternative approaches are available, and most of the results are known. The asymptotic distribution of the extreme eigenvalues of Gaussian Hermitian matrices has been first studied by Bronk in the 1960-s, and more recently by Bowick and Brézin, Moore, Forrester, and finally by Tracy and Widom, who have established the conclusion of Theorem I.1.3 in the Gaussian case. Parallel results for Gaussian sample covariance matrices have been proved by Johansson, Johnstone, and Soshnikov, and Borodin and Forrester. We defer the precise references to Section I.3.

In fact, our argument (as well as those of Soshnikov and Péché) involves reduction to the Gaussian case. We discuss this in detail in Section I.3.

The entries of the random matrices that we shall consider in this paper will be (complex-valued) random variables $r$ satisfying the following assumptions:

the distribution of $r$ is symmetric (that is, $r$ and $-r$ are identically distributed);

Fix $\beta\in\{1,2\}$. Let $\{X^{(N)}\}_{N}$ be a sequence of $M(N)\times N$ matrices, $M(N)\leq N$, such that

$\lim_{N\to+\infty}M(N)=+\infty$; $\limsup_{N\to+\infty}M(N)/N<1$;

$\{X^{(N)}_{uv}\,|\,1\leq u\leq M(N),\,1\leq v\leq N\}$ are independent and satisfy (A1),(A2), and (A3β).

Let $\lambda_{1}^{(N)}$ be the smallest eigenvalue of $B^{(N)}=X^{(N)}{X^{(N)}}^{\ast}$. Then the random variable

converges in distribution to the Tracy–Widom law $TW_{\beta}$ (cf. Section I.4) as $N\to\infty$ $M(N)\leq N$, so the denominator is negative. This is not a typo..

Our method also yields new proofs of two known results. The complementary result for the largest eigenvalue was proved by Soshnikov (under additional restrictions on $M(N)$) and Péché (in this generality):

Fix $\beta\in\{1,2\}$. Let $\{X^{(N)}\}_{N}$ be a sequence of $M(N)\times N$ matrices, $M(N)\leq N$, such that

$\{X^{(N)}_{uv}\,|\,1\leq u\leq M(N),\,1\leq v\leq N\}$ are independent and satisfy (A1),(A2), and (A3β).

Let $\lambda_{M(N)}^{(N)}$ be the largest eigenvalue of $B^{(N)}=X^{(N)}{X^{(N)}}^{\ast}$. Then the random variable

converges in distribution to the Tracy–Widom law $TW_{\beta}$.

The analogous theorem for Hermitian matrices was also proved by Soshnikov , and was the first universality result at the edge of the spectrum for matrices with independent entries. It was further studied by Ruzmaikina , and Khorunzhiy and Vengerovsky .

Fix $\beta\in\{1,2\}$. Let $\{A^{(N)}\}_{N}$ be a sequence of Hermitian $N\times N$ matrices such that $\{A^{(N)}_{uv}\,|\,1\leq u\leq v\leq N\}$ are independent and satisfy (A1),(A2), and, for $u<v$, (A3β). Let

be the eigenvalues of $A^{(N)}$. Then the random variables

converge in distribution to the Tracy–Widom law $TW_{\beta}$.

Most of this paper is devoted to the proofs of Theorems I.1.1-I.1.3. In the following section (I.2), we state slightly more general results in terms of point processes. Some of the definitions are postponed to Section I.4. There we also explain why the formulations of Section I.2 imply those of Section I.1. In Section I.5 we formulate two technical statements, and deduce the results of Section I.2. A guide to the subsequent sections, which are mostly devoted to the proof of the two technical statements, is provided at the end of Section I.5.

I.2 Formulation of results: extended version

Let us recall the definition of a point process and introduce a (slightly unusual) topology.

Under the assumptions of Theorem I.1.1, let

be the eigenvalues of $B^{(N)}=X^{(N)}{X^{(N)}}^{\ast}$, and let

converge in distribution to the Airy point process $\mathfrak{Ai}_{\beta}$:

We shall recall the definition of $\mathfrak{Ai}_{\beta}$ in Section I.4.

Under the assumptions of Theorem I.1.2, let

be the eigenvalues of $B^{(N)}=X^{(N)}{X^{(N)}}^{\ast}$, and let

converge in distribution to the Airy point process $\mathfrak{Ai}_{\beta}$.

Under the assumptions of Theorem I.1.3, let

converge in distribution to the Airy point process $\mathfrak{Ai}_{\beta}$.

I.3 Some Remarks

The most important example of random matrices satisfying the assumptions of Theorems I.1.1,I.1.2 is the Wishart Ensemble:

For $\beta=1$, $X^{(N)}_{uv}\sim N(0,1)$;

For $\beta=2$, $X^{(N)}_{uv}\sim N(0,1/2)+iN(0,1/2)$ (meaning that the real and imaginary parts of $X^{(N)}_{uv}$ are independent Gaussian variables.)

We denote the random matrix $X^{(N)}$ by $X^{(N)}_{\text{inv}}$ (suppressing the dependence on $\beta$), and set $B^{(N)}_{\text{inv}}=X^{(N)}_{\text{inv}}{X^{(N)}_{\text{inv}}}^{\ast}$.

Similarly, the most important example of random matrices satisfying the assumptions of Theorem I.1.3 is the Gaussian Orthogonal/Unitary Ensemble:

$\beta=1$: in the Gaussian Orthogonal Ensemble (GOE),

$\beta=2$: in the Gaussian Unitary Ensemble (GUE),

We denote the matrix $A^{(N)}$ defined above by $A_{\text{inv}}^{(N)}$.

The main feature of these examples is the invariance property: the distribution of $A_{\text{inv}}^{(N)}$, $B^{(N)}_{\text{inv}}$ is invariant under conjugation by arbitrary orthogonal matrices (for $\beta=1$) or unitary matrices (for $\beta=2$). This feature facilitates the study of the eigenvalues of these matrices, and indeed, most of the results have been proved much earlier in this special case.

In particular, the conclusion of Theorem I.2.4 was proved for $A_{\text{inv}}^{(N)}$ in the early 90-s, by Bowick and Brézin, Forrester, Moore, and others, building on earlier work by Wigner, Dyson, and Mehta (see and references therein.)

The conclusion of Theorem I.2.3 was established for the invariant case $B^{(N)}_{\text{inv}}$ by Johansson (for $\beta=2$) and Johnstone (for $\beta=1$); see also Soshnikov . The conclusion of Theorem I.2.2 was proved for $B^{(N)}_{\text{inv}}$ by Borodin and Forrester , under the weaker assumption $N-M(N)\to+\infty$ (instead of $\limsup M(N)/N<1$).

It has been long conjectured that, in the asymptotic limit $N\to\infty$, some of the statistical properties that were proved for the eigenvalues of matrices with Gaussian entries should be valid, in particular, for more general random matrices with independent entries. See for example Conjecture 1.2.1, Conjecture 1.2.2, and various remarks scattered in Mehta’s book . In particular, this should be true for local statistics of the eigenvalues at the edge of the spectrum.

The first rigorous results of this kind are due to Soshnikov. In , he established Theorem I.2.4. The main step in his proof is to show that the asymptotics of the mixed moments

does not depend on the distribution of the entries of $A^{(N)}$, when $\beta$ is fixed and $m_{1},\cdots,m_{k}=O(N^{2/3})$. This reduces Theorem I.2.4 to the invariant case $A^{(N)}_{\text{inv}}$.

In the subsequent work , Soshnikov applied a similar method to the largest eigenvalues of the sample covariance matrices $B^{(N)}$, and proved Theorems I.1.2,I.2.3, under some additional restrictions on $M(N)$. These restrictions were later disposed of by Péché .

This method does not seem to be directly applicable to the smallest eigenvalue of $B^{(N)}$, since the asymptotics of (I.3.1) does not depend on the eigenvalues that are small in absolute value. In this paper, we make use of a modified technique, using traces of certain orthogonal polynomials of $A^{(N)}$, $B^{(N)}$. This technique is based on an idea going back to Bai and Yin , which was developed in several subsequent works; see and references therein.

I.4 More definitions

For the convenience of the reader, we provide some definitions; this section is copied, up to change of notation, from the work of Soshnikov .

In general, a point process is not uniquely defined by its correlation measures. However, a sufficient condition due to Lenard ensures uniqueness for the processes that we encounter in this paper.

For the sequel, let us introduce a topology on measures:

The Airy function $\operatorname{Ai}$ is (uniquely) defined by

The Airy point process $\mathfrak{Ai}_{2}$ is the (unique) point process such that, for every $k$ and any compact set

the restriction $\rho_{k}|_{T}$ is absolutely continuous with respect to the Lebesgue measure, and

The Tracy–Widom law $TW_{2}$ is defined by its cumulative distribution function

where $q(\cdot)$ is the solution to the II${}^{\text{nd}}$ Painlevé equation:

(the so-called Hastings–McLeod solution.)

For $\beta=1$, the density of $\rho_{k}$ can be expressed as the square root of the determinant of a $2k\times 2k$ block matrix, which is composed of $2\times 2$ blocks. Denote

The Airy point process $\mathfrak{Ai}_{1}$ is the (unique) point process such that, for every $k$ and any compact set

the restriction $\rho_{k}|_{T}$ is absolutely continuous with respect to the Lebesgue measure, and

The Tracy–Widom law $TW_{1}$ is defined by its cumulative distribution function

For $\beta\in\{1,2\}$, the distribution of the rightmost atom of $\mathfrak{Ai}_{\beta}$ is exactly $TW_{\beta}$.

The functional that sends a locally finite configuration of points (= locally finite integer-valued Borel measure) to its rightmost point (= atom) is continuous with respect to the convergence $\rightharpoonup$, and therefore Theorem I.2.2 implies Theorem I.1.1, Theorem I.2.3 implies Theorem I.1.2, Theorem I.2.4 implies Theorem I.1.3.

I.5 The main technical statements

The Chebyshev polynomials of the second kind are defined as follows:

The following elementary proposition may clarify the connection between $U_{n}$ and the spectra of the matrices considered in this paper. We shall not use it, and therefore omit the proof (see e.g. [20, §5.1].)

The polynomials $U_{n}$ are the orthogonal polynomials with respect to Wigner’s semicircle measure $\sigma_{\text{W}}$:

For $0\leq s\leq 1$, the polynomials $V_{n,s}=U_{n}+\sqrt{s}U_{n-1}$ are orthogonal with respect to the Marchenko–Pastur measure $\sigma_{\text{MP}}^{(s)}$:

In the next parts of this paper we shall prove the following two statements:

Fix $\beta\in\{1,2\}$, and let $\{A^{(N)}\}$ be a sequence of random matrices satisfying the assumptions of Theorem I.1.3. Fix $k\geq 1$, and let $\{(n_{1}^{(N)},\cdots,n_{k}^{(N)})\}_{N}$ be a sequence of $k$-tuples.

Suppose $\sum n_{i}^{(N)}=2n^{(N)}$. There exists a constant $C$ (depending only on $C_{0}$ in (A2)), such that

as $N\to+\infty$, where $A_{\text{inv}}^{(N)}$ is as in Example I.3.2, and the implicit constant in $o(\cdots)$ may depend on $k$, $C_{0}$, and $n/N^{1/3}$.

There are several ways to deduce Theorem I.2.4 from Theorem I.5.3. For example, one may use Levitan’s uniqueness theorem for the transform

which appears naturally from the asymptotics of $U_{n}$ near $\pm 1$. However, the justification of convergence makes this approach quite cumbersome.

We shall follow Soshnikov’s original argument and go back to moments and to the Laplace transform

We shall use the following simple identities (see e.g. Snyder ):

(This is more or less the content of Theorem 2 in .) Substitute

in (I.5.2) and take the expectation of the trace:

The inequality (I.5.5) also ensures that the contribution of

(with, say, $C^{\prime}=10$) is negligible. Hence one can restrict the sum to

and apply the third item. This proves 2. for even values of $m$; for odd values of $m$, both sides are zero.

Proceeding with Soshnikov’s argument, we deduce that the sequences $\{\xi^{(N)}\}$, $\{\eta^{(N)}\}$ are precompact, and that

for any limit points $\xi$, $\eta$, as long as $m_{N}/N^{2/3}\to\alpha$ and $m_{N}$ is of constant parity $p$. Therefore the Laplace transforms $\mathfrak{L}(\rho_{1,\xi}),\mathfrak{L}(\rho_{1,\eta})$ do not depend on the distribution of the entries of the matrix $A^{(N)}$. In exactly the same way we show that $\mathfrak{L}(\rho_{k,\xi}),\mathfrak{L}(\rho_{k,\eta})$ are defined uniquely for any $k\geq 1$, and hence are the same as for $A^{(N)}_{\text{inv}}$. Therefore (again, see ), we deduce that

Fix $\beta\in\{1,2\}$, and let $\{B^{(N)}\}$ be a sequence of random matrices satisfying the assumptions of Theorem I.1.2. Fix $k\geq 1$, and let $\{(n_{1}^{(N)},\cdots,n_{k}^{(N)})\}_{N}$ be a sequence of $k$-tuples.

Suppose $\sum n_{i}^{(N)}=n^{(N)}$. There exists a constant $C$ (depending only on $C_{0}$ in (A2)), such that

as $N\to+\infty$, where $B_{\text{inv}}^{(N)}$ is as in Example I.3.1, and the implicit constant in $o(\cdots)$ may depend on $k$, $C_{0}$, and $n/M(N)^{1/3}$.

Similarly to the above, Theorem I.5.4 implies Theorems I.2.2,I.2.3.

As in the proof of Theorem I.2.4, we consider moments. Expressing

one may check that the asymptotics of (I.5.7) is the same as for $B^{(N)}=B^{(N)}_{\text{inv}}$. If $M(N)/N<1-\eta<1$, the same is true for

(with the implicit constants depending on $\eta$.) From this point, proceed as in the proof of Theorem I.2.4. ∎

Taking Remarks II.3.5,IV.1.6 into account, one can actually avoid the use of any results for Wishart matrices, and compare the correlation measures to those in Theorem I.2.4.

Plan of the proceeding sections. Parts II,III are devoted to the proof of Theorem I.5.3. In Part II we focus on the special case of matrices the entries of which are uniformly distributed on the $(\beta-1)$-dimensional sphere (except for the diagonal entries, which are zero, see (II.0.1) below.) We discuss the asymptotics of the expectations in Theorem I.5.3 in detail, first for $k=1$, and obtain a certain “genus expansion”, Proposition II.2.5. In Section II.3 we extend these results to arbitrary $k\geq 1$. This part is based on the connection to non-backtracking paths on the complete graph, which is very explicit and simple in the special case (II.0.1) (see Claim II.1.2 below).

In Part III we show that the results of Part II can be extended to matrices with arbitrary distribution of entries (that satisfy the conditions of Theorem I.1.3.) The three main technical difficulties that appear are:

to express $\operatorname{tr}U_{n}(A/(2\sqrt{N-2}))$ as a sum over paths;

to show that multiple edges do not contribute to the part of the asymptotics that comes from non-backtracking paths.

to show that paths with backtracking do not contribute to the asymptotics of the expressions in Theorem I.5.3.

In Part IV we prove Theorem I.5.4. The asymptotics of the expressions in Theorem I.5.4 is closely connected to non-backtracking paths on the complete bipartite graph. Therefore the proofs mostly mimic the proofs in Parts II,III, and we mainly indicate the necessary modifications.

Part V is devoted to extensions and some remarks. We discuss additional results that can be proved using the methods of this paper, and indicate the modifications that should be made in the proofs. In particular, we discuss quaternionic random matrices (which correspond to $\beta=4$), and matrices with unequal real and imaginary part. In Section V.2 we discuss some deviation inequalities for the extreme eigenvalues.

Notation: The large parameter in this paper is $N\to\infty$. For quantities $\phi,\psi$ depending on $N$, we write $\phi\ll\psi$ for $\phi=o(\psi)$, and $\phi\sim\psi$ for $\phi/\psi=1+o(1)$; $\phi=\Theta(\psi)$ if $\phi=O(\psi)$ and $\psi=O(\phi)$. The letters $C,C^{\prime},C_{1},\cdots$ will stand for positive constants the value of which may vary from line to line. Some of these may depend on $C_{0}$ in (A2) or on other parameters; we mention it explicitly when this is the case.

Part II Matrices with uniform entries

In this part, we focus on the special cases

From this point, we suppress the dependence on $N$ in the notation.

Consider the following sequence of polynomials $P_{n}=P_{n,N}$:

where formally $U_{-2}\equiv U_{-1}\equiv 0$.

For $n=0,1,2$ the identity (II.1.2) follows directly from (II.1.1), (I.5.1). Next, (I.5.1) implies (cf. ) that

Taking $y=x/(2\sqrt{N-2})$, we see that the right-hand side of (II.1.2) satisfies the same recurrent relation as the left-hand side. ∎

For any Hermitian $N\times N$ matrix $A$ with zeros on the diagonal and other entries on the unit circle,

where the sum is over all paths $p_{n}=u_{0}u_{1}\cdots u_{n}$ such that

$u_{j}\neq u_{j-2}$ for $j=2,\cdots,n$ (the non-backtracking condition).

For $n=0,1$ the identity (II.1.4) is trivial. For $n\geq 2$ observe that

according to (II.1.3), and on the other hand

and hence the right-hand side of (II.1.4) also satisfies (II.1.5). ∎

Let $p_{2n}=u_{0}u_{1}\cdots u_{2n}$ be a path satisfying (a), (b), (c), (d${}_{\beta}^{1}$). Consider a directed multigraph $G=(V,E_{\text{dir}})$, where $V\subset\{1,\cdots,N\}$ is the set of all vertices $u_{j}$, and $E_{\text{dir}}$ is the set of edges $(u_{j-1},u_{j})$ (with multiplicities). A matching of $p_{2n}$ is a matching (= involution without fixed points) of $\{0,1,\cdots,2n-1\}$, so that

for $\beta=1$, every edge $(u,v)$ is matched either to a coincident edge $(u,v)$ or to $(v,u)$;

for $\beta=2$, an edge $(u,v)$ is matched to $(v,u)$.

A path together with a matching will be called a matched path.

Denote by ${\Sigma^{1m}_{\beta}}(2n)$ the number of matched paths (satisfying (a), (b), (c), (d${}_{\beta}^{1}$)), and denote by ${\Sigma_{\beta}}(2n)$ the number of paths satisfying (a), (b), (c) and the stronger condition (dβ):

Our next goal is to study the asymptotics of $\Sigma^{1m}_{\beta}(2n)$. In particular, we shall prove that

Let us introduce some more graph-theoretical notation.

A diagram of type $\beta$ is an (undirected) multigraph $\bar{G}=(\bar{V},\bar{E})$, together with a circuit $\bar{p}=\bar{u}_{0}\bar{u}_{1}\cdots\bar{u}_{0}$ on $\bar{G}$, such that

$\bar{p}$ is non-backtracking (meaning that no edge is followed by its reverse, unless the edge is $\bar{u}\bar{u}$ and $\beta=1$);

the degree of $\bar{u}_{0}$ in $\bar{G}$ is 1; the degrees of all the other vertices are equal to 3.

A weighted diagram is a diagram $\bar{G}$ together with a weight function $\bar{w}:\bar{E}\to\{-1,0,1,2,\cdots\}$.

Let us construct a mapping from the collection of matched paths satisfying (a), (b), (c), (d${}_{\beta}^{1}$) into the collection of weighted diagrams (of type $\beta$.)

(i) Start with the multigraph $G=G(p_{2n})=(V,E_{\text{dir}})$ corresponding to the path $p_{2n}$:

and unite each pair of matched edges into a single undirected edge.

(ii) If the degree of $u_{0}$ is greater than 1, add a vertex $r$ connected to $u_{0}$, and replace $p_{2n}$ with $ru_{0}u_{1}\cdots u_{0}r$. Otherwise set $r=u_{0}$.

(iii) For every vertex $u\neq r$ of degree $d>3$, replace $u$ with $\leq d-2$ vertices of degree $\leq 3$ using the inductive procedure illustrated in Figure 1.

There are at most $N^{\#\bar{V}+\sum_{\bar{e}}\bar{w}(\bar{e})}$ matched paths corresponding to a weighted diagram $(\bar{G},\bar{p},\bar{w})$. If $\bar{w}(\bar{e})\geq 1$ for every $\bar{e}\in\bar{E}$, there are exactly

such paths. In particular, if $\bar{w}(\bar{e})\geq 1$ for every $\bar{e}\in\bar{E}$, and if

the number of matched paths and the number of paths (without a matching) are both

II.2 Counting diagrams

Let us present an automaton which constructs all possible diagrams. Consider first the case $\beta=2$.

(“creation” of a new loop, see Figure 2):

(“annihilation” of the $j$-th loop, see Figure 3):

We impose the restriction $t>0$ all along the way, and demand that after some (even) number of steps $s=2g$ the automaton return to the original state and stop.

Every diagram (corresponding to $\beta=2$) is generated by the automaton. If the automaton stops after $s=2g$ steps, the diagram has $\#\bar{E}=6g-1=3s-1$ edges and $\#\bar{V}=4g=2s$ vertices.

It suffices to observe that the first (creation) step creates 3 edges and 3 vertices, the last (annihilation) step creates 2 edges and one vertex, and every other step creates 3 edges and 2 vertices. ∎

Denote by $D_{2}(s)$ the number of diagrams corresponding to $s$ steps (of course, $D_{2}(s)=0$ for odd values of $s$.)

For $\beta=1$, the transitions are slightly different. First, every time a loop is annihilated (transition 2.), the automaton has to choose a direction in which the loop is passed. That is, there are two possibilities: the one in Figure 3, and the one in Figure 4.

(“creation and annihilation”): $t\longleftarrow t^{\prime}\leq t+1$ (see Figure 5.)

Now the number of steps $s$ can be written as $s=2g+h$, where $g$ is the number of steps of the first kind, and $h$ is the number of steps of the third kind. Similarly to Claim II.2.2, we have

Every diagram (corresponding to $\beta=1$) is generated by the (new) automaton. If the automaton stops after $s=2g+h$ steps (with $g,h$ as above), the diagram has $\#\bar{E}=6g+3h-1=3s-1$ edges and $\#\bar{V}=4g+2h=2s$ vertices.

Denote by $D_{1}(s)$ the number of diagrams corresponding to $s$ steps (and $\beta=1$).

The following crude estimate will be of use:

Let us consider for example the case $\beta=2$ (the argument for $\beta=1$ is similar.) Let $s=2g$; the number of loops after $j$ steps is non-negative, and zero at the beginning and at the end. Hence the number of ways to order the transitions of the two types is exactly the Catalan number

The number of diagrams corresponding to a fixed order of transitions and fixed $m_{i}$ is at most $(6g)^{2g}$. This proves the upper bound.

To prove the lower bound, consider the fixed sequence of transitions $1.2.1.2.\cdots 1.2.$, and $m_{i}=0$ ($1\leq i<2g$.) It is not hard to check that the number of diagrams thus restricted is equal to

(see Figure 6.) Therefore the upper bound in Proposition II.2.3 can be formally improved to $D_{\beta}(s)\leq C^{s-1}s^{s}$ (perhaps, with a different constant $C>0$).

The preceding considerations allow to prove (a more precise form of) Theorem I.5.3 for the special case (II.0.1), $k=1$.

Let $\beta\in\{1,2\}$, and let the random matrix $A$ be as in (II.0.1). Then

Every matched path corresponds to some weighted diagram with a certain number of steps $1\leq s\leq n$. For this diagram, $\#\bar{V}=2s$ and $\#\bar{E}=3s-1$ by Claims II.2.2,II.2.1. Also,

The number of ways to place the weights on the diagram is at most

By Claim II.1.4, the number of ways to choose the vertices is at most $N^{2s+n-3s+1}=N^{n-s+1}$. Hence by Proposition II.2.3 (and Remark II.2.4)

Fix $1\ll n_{0}\ll N^{1/3}$. Suppose $n\ll N^{1/2}$. If $n>n_{0}$, choose $s_{0}$ so that

On the other hand, for every diagram corresponding to a certain $s\geq 1$, there are

ways to place the weights so that $\bar{w}(\bar{e})\geq 1$ for every $\bar{e}\in\bar{E}$; for $s\ll n^{1/2}$,

If the weights are placed in this way, the number of ways to choose the vertices is

according to the second part of Claim II.1.4. Every path thus constructed satisfies the condition (dβ) and hence has a unique matching. Therefore

where on the last step we have used Proposition II.2.3 again. The inequalities (II.2.1), (II.2.2) yield:

If $n\leq n_{0}$, a similar argument shows that

Applying Lemma II.1.1 as in the proof of the second statement of this proposition, we deduce the third statement.

II.3 Product of several traces

In this section, we shall consider the expectations

for $k>1$, which we need in order to study

Mutatis mutandis, the analysis will be quite similar to the case $k=1$, which we have considered in the two preceding sections.

where $\Sigma^{1}_{\beta}(n_{1},\cdots,n_{k})$ is the number of $k$-tuples of paths (or shortly: $k$-paths)

$u_{j}^{i}\neq u_{j-1}^{i}$ for $i=1,\cdots,k$ and $j=1,\cdots,n_{i}$;

$u_{j}^{i}\neq u_{j-2}^{i}$ for $i=1,\cdots,k$ and $j=2,\cdots,n_{i}$;

$u_{n_{i}}^{i}=u_{0}^{i}$ for $i=1,\cdots,k$;

As in Section II.1, we also consider matched $k$-paths, that is, $k$-paths together with a matching (= involution of ${\uplus_{i=1}^{n}}\{0,1,\cdots,n_{i}-1\}\times\{i\}$ without fixed points) such that

for $\beta=1$, every edge $(u,v)$ is matched either to a coincident edge $(u,v)$ or to $(v,u)$;

for $\beta=2$, an edge $(u,v)$ is matched to $(v,u)$.

Denote by $\Sigma_{\beta}^{1m}(n_{1},\cdots,n_{k})$ the number of matched $k$-paths satisfying (a), (b), (c), (d${}_{\beta}^{1}$), and by $\Sigma_{\beta}(n_{1},\cdots,n_{k})$ the number of $k$-paths satisfying (a), (b), (c), and (dβ) below:

Next, we extend the definition of a diagram (Definition II.1.3) in the following way:

A $k$-diagram of type $\beta$ is an (undirected) multigraph $\bar{G}=(\bar{V},\bar{E})$, together with a $k$-tuple of circuits

$\bar{p}$ is non-backtracking (meaning that in every circuit no edge is followed by its reverse, unless $\beta=1$ and the edge is $\bar{u}\bar{u}$);

the degree of $u_{0}^{i}$ in $\bar{G}$ is 1; the degrees of all the other vertices are equal to 3.

A weighted $k$-diagram is a $k$-diagram $\bar{G}$ together with a weight function $\bar{w}:\bar{E}\to\{-1,0,1,2,\cdots\}$.

The mapping from the collection of matched $k$-paths satisfying the (new) conditions (a), (b), (c), (d${}_{\beta}^{1}$) to the collection of weighted $k$-diagrams is constructed exactly as for $k=1$, and Claim II.1.4 remains true verbatim.

To make the automaton from Section II.2 generate $k$-diagrams, we start from the same initial state $t=k=0$, and demand that the automaton return to the same initial state after $s$ steps, and that $t=0$ exactly $k+1$ times during the procedure. That is, $t=0$ after $0$, $s_{1}$, $s_{1}+s_{2}$, $\cdots$, $s_{1}+\cdots s_{k}$ steps, where $s_{1},\cdots,s_{k}>0$ are some numbers such that $s_{1}+\cdots+s_{k}=s$.

Claims II.2.2 and II.2.1 take on the following form:

Every $k$-diagram is generated by the automaton, with the new restrictions. If the automaton stops after $s=s_{1}+\cdots+s_{k}$ steps (with $s_{1},\cdots,s_{k}$ as above), the $k$-diagram has $\#\bar{E}=\sum(3s_{i}-1)=3s-k$ edges and $\#\bar{V}=\sum 2s_{i}=2s$ vertices.

Denote by $D_{\beta,k}(s)$ the number of $k$-diagrams generated in $s$ steps, and let $D_{\beta}(s_{1},\cdots,s_{k})$ be the number of $k$-diagrams corresponding to $s_{1},\cdots,s_{k}$; that is,

Then Proposition II.2.3 can be extended in the following way:

Now we can extend Proposition II.2.5 to all $k\geq 1$, in the following (slightly weaker) form:

As in Proposition II.2.5, the first statement is obvious.

The weights $\bar{w}(\bar{e})$ satisfy a system of linear equations (depending on the diagram):

For every $\bar{e}\in\bar{E}$ and every $i$, the coefficient $c_{i}(\bar{e})$ of $\bar{w}(\bar{e})$ in the $i$-th equation is $0$, $1$, or $2$, and

where the sum is over all the edges except the first one in every circuit. Therefore

and the number of ways to place the weights is at most

The number of ways to choose the vertices is at most $N^{n-s+k}$; hence

The proof of the third statement is similar to the proof of the third statement in Proposition II.2.5. Choose $1\ll n_{0}\ll N^{1/3}$. We write

where $I_{1}$ is the set of indices such that $n_{i}\leq n_{0}$ (and $I_{2}$ is its complement). The circuits corresponding to $i\in I_{1}$ are (typically) trivial; for the circuits corresponding to $i\in I_{2}$, we consider the system of equations (II.3.2) and prove that most of its solutions satisfy $\bar{w}(\bar{e})\geq 1$. This is again similar to the proof of Proposition II.2.5; we omit the details. ∎

(e.g. $\phi_{\beta}(\varnothing,N)=1$, and $\phi_{\beta}(\{n\},N)$ is as in Remark II.2.6.)

The number $D_{2}(2g)$ is equal to the number of homotopically distinct ways to glue the boundary of a disk with a marked point on the boundary, obtaining a compact orientable surface of (orientable) genus $g$. There is a similar interpretation for $\beta=1$: $D_{1}(s)$ is the number of homotopically distinct ways to obtain a compact surface of non-orientable genus $s$.

One can extend this observation to $D_{\beta,k}(s)$ (which corresponds to gluing $k$ disks); this could be compared to the Harer–Zagier formulæ, cf. [15, 6.5.6].

Part III General matrices

In Part II, we have proved a version of Theorem I.5.3 for the special case (II.0.1). In this part, we extend the considerations of Part II to general matrices $A$ that satisfy the assumptions of Theorem I.1.3.

Unfortunately, the nice formula (II.1.4) is not valid for general matrices $A$. Instead, for every path $p$ and matrix $A$, we shall define an expression $\gamma(p,A)$, such that for every $1\leq u,v\leq N$ and every $n\geq 0$,

where the sum is over all paths $p$ of length $n$ from $u$ to $v$.

To any path $p_{n}=u_{0}u_{1}\cdots u_{n}$ we associate an expression $\gamma(p_{n},A)$ and a sub-path $\mathcal{C}(p_{n})$ that satisfies (a),(b). Namely, set

if $n\geq 2$ and $\mathcal{C}(p_{n-2})=u_{0}$, set

if $(u_{n},u_{n-1})$ is the last edge edge of $\mathcal{C}(p_{n-1})$,

if the previous step of type 2 was not of sub-type 2:1 (or did not exist), set

and again, $\mathcal{C}(p_{n})$ is $\mathcal{C}(p_{n-1})$ without the last edge;

and append $(u_{n-1},u_{n})$ to $\mathcal{C}(p_{n-1})$ in order to obtain $\mathcal{C}(p_{n})$.

For any Hermitian $N\times N$ matrix $A$,

where the sum is over all paths $p_{n}=u_{0}u_{1}\cdots u_{n}$.

We check the claim for $n=0,1$ and proceed by induction. Suppose (III.1.1) holds up to $n-1$. Then by (II.1.3)

where $\sum^{\prime}$ is over paths $p_{n-1}$ of length $n-1$ from $u_{0}$ to $u_{n-1}$, and $\sum^{\prime\prime}$ is over paths $q_{n-2}$ of length $n-2$ from $u_{0}$ to $u_{n}$.

In the first sum, set $p_{n}=p_{n-1}u_{n}$; it is then equal to

But the last sum in (III.1.2) is exactly $\sum^{1:1}$. Thus finally

where the sum is over all paths $p_{n}$ satisfying (c). Every path $p_{n}$ is decomposed into a non-backtracking part $\mathcal{C}(p_{n})$, the ‘loops’ these are called ‘loops’ in the standard graph-theoretical terminology, not to be confused with loops in the sense of Section II.2 $u_{n-1}=u_{n}$, and the remainder $\mathcal{F}_{1}(p_{n})$, which is a forest (= union of trees.)

III.2 Non-backtracking paths

where the sum is over all paths satisfying (c) in which every edge is passed an even number of times. This expression is zero for odd $n$. In this section, we let $\beta=1$ and focus on the sub-sum

over paths $p_{2n}$ satisfying (a), (b), (c), (d${}_{\beta}^{1}$).

$\Sigma_{1}^{2,A}(2n)\leq n\exp(C^{\prime}n^{3/2}/N^{1/2})$;

for $n=o(\sqrt{N})$, $\Sigma_{1}^{2,A}(2n)=\Sigma_{1}(2n)(1+o(1))$.

Here $C^{\prime}>0$ and the implicit constant in $o(1)$ depend only on $C_{0}$ from (A2).

(with $\Sigma^{1}_{1}(2n),\Sigma_{1}(2n)$ as in Section II.1). Therefore we only need to prove the upper bounds. For a constant $C>0$, denote

where now the sum is over matched paths $p_{2n}$, and $\#E(p_{2n})$ is the number of distinct edges in $p_{2n}$. By (A2),

for some constant $C$ depending only on $C_{0}$ (note that a factor $(k/C^{\prime})^{k}$ from (A2) is absorbed in the number of matchings.) Thus we may restrict our attention to $\Sigma_{1}^{1m,C}(2n)$.

For any weighted diagram corresponding to a path $p_{2n}$, $n-\#E(p_{2n})\leq b$, where $b$ is the number of edges $\bar{e}$ with $\bar{w}(\bar{e})=-1$. This allows us to follow the proof of Proposition II.2.5.

From this point proceed exactly as in the proof of Proposition II.2.5. ∎

III.3 Backtracking paths

Now let us estimate the contribution of all the other paths; we still assume that $\beta=1$.

Let $p_{2n}$ be a path that gives non-zero contribution to (III.1.3). We decompose it into $q_{2(n-m)}=\mathcal{C}(p_{2n})$, a forest $f_{2m}=\mathcal{F}(p_{2n})$, and the ‘loops’. Recall that $q_{2(n-m)}$ (which may degenerate to a single vertex) satisfies (a), (b), (c), (d${}_{1}^{1}$). Also,

These statements follow from the expression for $\gamma(p_{n},A)$ in Section III.1.

The paths for which $f_{2m}$ is empty correspond to the expression $\Sigma^{2,A}_{\beta}(2n)$ that we have studies in the previous section. Let us show that the contribution of the other paths is negligible. The basic idea is to show that the contribution of paths with forests is negligible with respect to the contribution of non-backtracking paths, where each tree of the forest is replaced by the simplest non-backtracking piece (Figure 6, right).

To start the computations, we need a new kind of diagrams (cf. Definitions II.1.3, II.3.1.)

A tree diagram (or shortly, t-diagram) is a rooted binary planar tree (that is, a binary rooted tree with fixed imbedding into the plane). A weighted t-diagram is a t-diagram together with a weight function $\bar{w}$ from the set of edges to $\{-1,0,1,2,\cdots\}$.

Similarly to Section II.1, we can attach a weighted t-diagram to every tree in the forest $f_{2m}$.

A t-diagram with $i+1$ leaves is obtained by gluing a leaf to a t-diagram with $i$ leaves. The new leaf can be glued to one of the edges on the branch connecting the root to the last-glued leaf (see Figure 7). Denote by $d_{i}$ the index of the latter edge on the branch, so that $d_{i}=1$ if the edge is adjacent to a leaf. Then

therefore the number of ways to choose the indices $d_{i}$ is at most

Thus the total number of trees is bounded by

A more careful computation (in the spirit of Section III.2) shows that the last estimate remains valid if we count every tree with a weight, depending on higher moments of $A$, and take the ‘loops’ into account.

Therefore the number of $t$-tuples of trees with $m$ edges is at most

and the total contribution of paths $p_{2n}$ with $t$ trees and $m$ edges on these trees is at most

It is not hard to check that the sum of these terms over $m,t>0$ is negligible with respect to $\Sigma_{1}(2n)$, for $n=o(\sqrt{N})$.

This proves the claim at the beginning of this section; namely, item 3. of Proposition II.2.5 is valid in the generality of Theorem I.1.3 (for $\beta=1$). A similar argument allows to extend item 2. of Proposition II.2.5.

We shall only sketch the argument for $k=1$; the extension is straightforward. For $\beta=1$, we have just proved the stronger conclusion of Proposition II.2.5.

For $\beta=2$, the error terms for $A$ are dominated by those for $\widetilde{A}$, where

and the random signs are independent above the diagonal; $\widetilde{A}$ satisfies the assumptions of the theorem with $\beta=1$. ∎

Part IV Sample covariance matrices

As in the Hermitian case, we start with the special cases

Define a sequence of polynomials $Q_{n}=Q_{n,M,N}$ as follows:

Similarly to Lemma II.1.1, Lemma IV.1.1 can be easily proved by induction.

Let $X$ be an $M\times N$ matrix with entries on the unit circle, $B=XX^{\ast}$. Then

where the sum is over paths $p_{n}=u_{0}v_{0}u_{1}v_{1}\cdots v_{n-1}u_{n}$ in the complete bipartite graph $K_{M,N}$ (that is, $1\leq u_{j}\leq M$, $1\leq v_{j}\leq N$), such that

$u_{j-1}\neq u_{j}$ for $1\leq j\leq n$ and $v_{j-1}\neq v_{j}$ for $1\leq j\leq n-1$.

For $n=0,1$, the verification is straightforward. Induction step:

where the sum is over paths $p_{n+1}$ that satisfy (b̂), except perhaps for the inequality $v_{n-1}\neq v_{n}$. Now separate the paths in 3 categories: $v_{n-1}\neq v_{n}$; $v_{n-1}=v_{n}$, $u_{n-1}\neq u_{n+1}$; $v_{n-1}=v_{n}$, $u_{n-1}=u_{n+1}$, which yield $Q_{n+1}(B)_{u_{0}u_{n+1}}$, $(M-2)Q_{n}(B)_{u_{0}u_{n+1}}$, and $(M-1)(N-1)Q_{n-1}(B)_{u_{0}u_{n+1}}$, respectively. ∎

Denote the number of such paths by $\hat{\Sigma}^{1}_{\beta}(n)$. The remainder of this section is devoted to the following analogue of Proposition II.2.5:

$\hat{\Sigma}_{\beta}^{1}(n)\leq Cn(MN)^{n/2}\exp(Cn^{3/2}/M^{1/2})$;

where $\phi_{\beta}$ is as in Remark II.2.6.

As in Section II.1, we consider matched paths; every (matched) path corresponds to a diagram. Let us study the number of paths corresponding to a given diagram. To place the weights, we need the following elementary lemma.

The number of ways to represent a non-negative integer $m$ as

with $m_{j}^{\prime}\equiv 1\mod 2$ and $m_{j}^{\prime\prime}\equiv 0\mod 2$ is given by

The first part is obvious. The second part follows from the equivalence between (IV.1.2) and

Now consider a diagram corresponding to a certain $s\geq 1$ (in the sense of Claims II.2.2,II.2.1.) Let $p_{n}$ be a path corresponding to this diagram. Denote by $V_{+}$ ($V_{-}$) the number of vertices of the 1${}^{\textrm{st}}$ (2${}^{\textrm{nd}}$) type (that is, $u_{j}$ or $v_{j}$, respectively). Denote by $\bar{V}_{+}$ ($\bar{V}_{-}=2s-\bar{V}_{+}$) the number of vertices of the 1${}^{\textrm{st}}$ (2${}^{\textrm{nd}}$) type on the diagram.

where the sum is over all the edges in the diagram. The root $\bar{u}_{0}$ is of the first type; every other vertex $\bar{w}$ is counted with coefficient $3\,\sigma(\bar{w})$. Hence

The collection of paths corresponding to a given diagram and given choice of types of the vertices $\bar{w}\in\bar{V}$ is non-empty iff $\bar{V}_{+}\equiv n\mod 2$. Therefore the number of ways to choose the vertices on the diagram is at most

Together with Lemma IV.1.4, this proves the first statement of Proposition IV.1.3. To prove the second part, we argue exactly as in the proof of Proposition II.2.5, item 3.

The extension to higher $k\geq 1$ is straightforward; instead of item 2., we obtain

To prove Theorem I.5.4, it remains to extend these considerations to general matrices $B$. This is done along the lines of Part III (actually, the argument is slightly simpler, since there can be no ‘loops’.)

Part V Extensions and further applications

In this section, we outline the proofs of some results that are more or less straightforward extensions of what we have already considered.

Matrices with quaternion entries. In addition to $\beta=1,2$, one can also consider $\beta=4$. Then Theorems I.1.1, I.1.2, I.1.3, I.2.2, I.2.3, I.2.4 remain valid, after the following modifications.

Instead of complex-valued random variables, the entries of the matrices will be random (real) quaternions $r=r^{(0)}+ir^{(1)}+jr^{(2)}+kr^{(3)}$. The assumptions (A1),(A2) still make sense, with

If $A$ is an $N\times N$ (real-) quaternionic matrix, and $\overline{A_{uv}}=A_{vu}$ ($A$ is “self-dual Hermitian”), one can consider the eigenvalues of $A$, which are real numbers $\lambda_{1}\leq\cdots\leq\lambda_{N}$ (see ). To define the Airy point process $\mathfrak{Ai}_{4}$ and the distribution $TW_{4}$, let

Then the density of the correlation measures $\rho_{k}$ of $\mathfrak{Ai}_{4}$ off the diagonals is given by

and the Tracy–Widom distribution $TW_{4}$,– by its cumulative distribution function

The Tracy–Widom theorem (formulated in Section I.4) holds also for $\beta=4$; see for more details.

The rôle of Examples I.3.2,I.3.1 is played by the Gaussian Symplectic Ensemble (GSE),

respectively. Theorems I.2.4,I.2.2,I.5.4 are known to be true in this particular case (of course, with $\beta=4$).

To prove the theorems for matrices with arbitrary entries, we extend Theorems I.5.3 and I.5.4. Note that, for any self-dual Hermitian quaternionic matrix $A$ with eigenvalues $\lambda_{1}\leq\cdots\leq\lambda_{N}$ and a (real) polynomial $P$, $P(A)$ is well-defined and

which are the quaternion analogue of (II.0.1). The relation (II.1.4) remains valid for these matrices. Multiplication of quaternions is non-commutative, hence the expectation of a product of random quaternions depends on the order of terms in the product; see e.g. Bryc and Pierce for a detailed analysis.

However, one can easily show the following:

For a path $p_{2n}=u_{0}u_{1}u_{2}\cdots u_{2n-1}u_{0}$, denote

If $A$ is as in (V.1.1), $|\mathfrak{e}(p_{2n})|\leq 1$ for any path $p_{2n}$.

Let $p_{2n}$ and $p_{2n^{\prime}}^{\prime}$ be two paths that satisfy (a), (b), (c), (d1) and have the same diagram. If the corresponding weights are non-negative, $\mathfrak{e}(p_{2n})=\mathfrak{e}(p_{2n^{\prime}}^{\prime})$.

The statements 1,2,3 are also true for $k$-paths, for any $k\geq 1$.

The first part follows from the multiplicativity of the absolute value and Jensen’s inequality. To prove the second part, note that, for any $\zeta\in S^{3}$,

(since $A_{uv}\sim\zeta^{-1}A_{uv}\zeta$.) Similarly, the third part is true since $rr^{\prime}\sim\textrm{unif}(S^{3})$ for independent $r,r^{\prime}\sim\textrm{unif}(S^{3})$. The same arguments are valid for the fourth part.

To extend these results to general matrices, we proceed as in Part III. First, observe that if $p_{2n}$ is a path without ‘loops’ on which every edge appears exactly twice, then

for any (Hermitian self-dual) random matrix $A$, the elements of which satisfy (A34). Hence the contribution of paths that satisfy (a), (b), (c), (d1) is asymptotically the same as in the uniform case (V.1.1). The contribution of other paths is dominated by the corresponding term for $\beta=1$, and hence is negligible.

These considerations show that Theorem I.5.3 is valid also for $\beta=4$. Similarly, Theorem I.5.4 can be extended. Theorems I.1.1, I.1.2, and I.1.3 follow by the arguments of Section I.5, which remain valid without any modification.

Matrices with unequal real and imaginary parts. In [15, Chapter 14], Mehta considers the following ensemble of random Hermitian matrices:

(where of course the entries above the diagonal are independent.) Taking $\alpha=0$, we recover GOE, $\alpha=1$ yields GUE, whereas $\alpha=\infty$ yields what is called the Anti-Symmetric Gaussian Orthogonal Ensemble (AGOE, cf. [15, Chapter 13].)

It may be natural to consider the following generalisation: again, $A$ will be a random Hermitian matrix as in Theorem I.1.3, with (A3β) replaced with

Exactly as in the preceding proofs, one can show that, for any $0\leq\alpha\leq+\infty$ (that may depend on $N$), the distribution of the largest eigenvalue of $A$ is asymptotically the same as in the Gaussian case (V.1.2). Again, the proof passes through an analogue of Theorem I.5.3, which yields a diagram expansion.

Let $A$ be a random matrix as in Theorem I.1.3, with (A3β) replaced with (A3${}_{1,2}^{\alpha}$), and let $\lambda_{N}$ be its largest eigenvalue.

That is, the crossover from GOE asymptotics to GUE asymptotics occurs at $\alpha\approx N^{-1/6}$. This is of course coherent with [15, (14.1.31)], which asserts that the crossover should occur for

(the average spacing at the edge is of order $N^{1/6}$, cf. Theorem I.2.4.) Also, the GUE asymptotics for the largest eigenvalues is valid up to $\alpha=+\infty$; this is coherent with the analysis in [15, 13.2.2].

If a path $p_{2n}=u_{0}u_{1}u_{2}\cdots u_{2n-1}u_{0}$ satisfies (a), (b), (c), (d1),

where $n_{1}$ is the number of edges passed twice in the same direction. For $n$ of order $N^{1/3}$, the diagrams of the paths that contribute to the asymptotics are generated by the automaton of Section II.1 that stops after $s=O(1)$ steps. If the diagram is not of type $\beta=2$, $n_{1}$ will be of order $N^{1/3}$, and hence the contribution of $p_{2n}$ will be of order

This expression is $1+o(1)$ for $0\leq\alpha\ll N^{-1/6}$, and negligible for

For $\alpha\gg 1$, the contribution of diagrams that are not of type $\beta=2$ is negligible for a different reason. Namely, if there is at least one “loop” (in the sense of Section II.2) that is passed twice in the same direction, the contribution of paths with even and odd weights on this loop nearly cancel each other.

The same applies to $k$-paths and $k$-diagrams. ∎

Forrester, Nagao and Honner have studied the extreme eigenvalues of the Gaussian ensemble (V.1.2) in the crossover regime $\alpha^{2}N^{1/3}\to t$. In particular, they have computed the limiting correlation measures for the point processes

Our argument shows that their results extend to general matrices $A^{(N)}$ that satisfy the assumptions of Corollary V.1.2.

Similar results can be proved for ensembles interpolating between $\beta=2$ and $\beta=4$, and for sample covariance matrices interpolating between $\beta=1$ and $\beta=2$ and between $\beta=2$ and $\beta=4$.

V.2 Deviation inequalities for extreme eigenvalues

Explicit upper bounds for the probability that the extreme eigenvalues deviate from their mean have various applications. The reader may refer to the lecture notes by Ledoux for an extensive discussion and references. The following estimates follow from Theorems I.5.3,I.5.4.

where the constant $C>0$ may depend on $C_{0}$ from (A2).

In slightly less general form, the estimate 1. follows from the recent work of Aubrun and Ledoux . Estimates similar to 1. and 2.(a) can be probably also derived from bounds on traces of high moments, similar to those considered by Soshnikov and Péché . The estimate 2.(b) seems to be new.

We shall only prove the first estimate (deducing it from Theorem I.5.3.) The estimates 2.(a), 2.(b) can be similarly deduced from Theorem I.5.4.

For $\varepsilon\leq CN^{-2/3}$, the atatements is trivial. For larger $\varepsilon$, we have by the estimate 1. in the proof of Theorem I.2.4,

Now take $m=\sqrt{\frac{\varepsilon}{C_{2}^{\prime}}}N$ and apply Chebyshev’s inequality. ∎

We conclude with a short discussion of the fluctuations of $\lambda_{1}(B)$ for $M$ approaching $N$, and (two forms of) an open question.

The inequality 2.(b) in Corollary V.2.1 shows that the order of the fluctuations of $\lambda_{1}(B)$ is at most $O(N^{1/3+o(1)})$. On the other hand, for the Gaussian case $B_{\textrm{inv}}$, the fluctuations are of order

which is strictly smaller when $M=N-o(N)$. It is therefore natural to ask whether (V.2.1) holds under the general assumptions of Theorem I.1.2. Recently, Rudelson and Vershynin have proved this for $N-M=O(1)$; to the best of our knowledge, the intermediate case $1\ll N-M\ll N$ is still open.

One may also ask whether the assumption $\limsup M/N<1$ in Theorems I.1.1,I.2.2 can be relaxed to $N-M\to\infty$ (as is the case for $B_{\textrm{inv}}$, cf. Borodin and Forrester ). A positive answer to this question would imply a positive answer to the previous one.