A Sharp Small Deviation Inequality for the Largest Eigenvalue of a Random Matrix

Guillaume Aubrun

Université de Paris 6, Institut de Mathématiques, Équipe d’Analyse Fonctionnelle, Boite 186, 4 place Jussieu, 75005 PARIS

Summary. We prove that the convergence of the largest eigenvalue λ_{1} of a n × n random matrix from the Gaussian Unitary Ensemble to its Tracy-Widom limit holds in a strong sense, specifically with respect to an appropriate Wasserstein-like distance. This unifying approach allows us both to recover the limiting behaviour and to derive the inequality ℙ(λ_{1} ⩾ 2+t) ⩽ C exp(−cnt^{3/2}), valid uniformly for all n and t. This inequality is sharp for “small deviations” and complements the usual “large deviation” inequality obtained from the Gaussian concentration principle. Following the approach by Tracy and Widom, the proof analyses several integral operators, which converge in the appropriate sense to an operator whose determinant can be estimated.

Key words: Random matrices, largest eigenvalue, GUE, small deviations.

Introduction

Let H_{n} be the set of n-dimensional (complex) Hermitian matrices. The general element of H_{n} is denoted A^{(n)}, and its entries are denoted (a_{ij}^{(n)}).

We exclusively focus on the Gaussian Unitary Ensemble GUE, which can be defined by the data of a probability measure ℙ_{n} on H_{n} which fulfills the following conditions

1. The n^{2} random variables (a_{ii}^{(n)}), (ℜa_{ij}^{(n)})_{i<j}, (ℑa_{ij}^{(n)})_{i<j} are independent,

2. ∀i, a_{ii}^{(n)} follows the Gaussian law N(0, 1/n),

3. ∀i < j, ℜa_{ij}^{(n)} and ℑa_{ij}^{(n)} follow the Gaussian law N(0, 1/2n).

The measure ℙ_{n} is uniquely determined by these three conditions because of the extra symmetry constraint a_{ij} = \overline{a_{ji}} ; it can also be made explicit. H_{n} is a vector space on which the scalar product ⟨u, v⟩ := tr(uv) induces an Euclidean structure, hence a Lebesgue measure. The probability measure ℙ_{n} has a density with respect to this Lebesgue measure, which can be shown to equal

dℙ_{n} := \frac{1}{c_{n}} exp(−\frac{n}{2}trM^{2})dM

where c_{n} is a normalization constant.

The GUE has the wonderful property of invariance under rotation : indeed the measure ℙ_{n} is invariant under the conjugation action of the unitary group. This makes calculations easier and is very useful for the study of eigenvalues, which are also invariant under the same action.

From now on, “random matrix” means “element of (H_{n}, ℙ_{n})” seen as a probability space. Let (Ω, ℙ) denote the product of all these probability spaces ∏_{i=n}^{∞}(H_{n}, ℙ_{n}) ; an element of Ω is a sequence of random matrices, the nth matrix being of size n. However, for all the questions we shall consider, the relationships between the H_{n}’s for different n’s are immaterial.

For more background, we refer the reader to the monograph [10]. Throughout the argument, C, c, c′, … will stand for positive universal constants, independent of the dimension and any other parameters that may be involved. The values of these constants may change from occurrence to occurrence.

Let λ_{1}(A^{(n)}) ⩾ λ_{2}(A^{(n)}) ⩾ … ⩾ λ_{n}(A^{(n)}) be the ordered eigenvalues of a random matrix A^{(n)}. The global asymptotic behavior of these eigenvalues is well-known. The most famous result in this topic is the semi-circle law, which can be stated as follows : let N(A^{(n)}) be the probability measure on ℝ derived from the random matrix A^{(n)} in the following way (δ_{x} denotes the Dirac mass at point x)

N(A^{(n)}) := ∑_{k=1}^{n} δ_{λ_{k}(A^{(n)})}

Then, ℙ-almost surely, the sequence of probabilities (N(A^{(n)}) converges weakly to a deterministic measure μ_{c}, with a density with respect to Lebesgue measure given by

dμ_{c} := \frac{1}{2π} 1_{[−2,2]}\sqrt{4 − x^{2}}dx

We are interested here in the asymptotic behavior of the largest eigenvalue λ_{1}(A^{(n)}), which is a so-called local problem. Classical results (see e.g. [1], also for precise references to the original articles) claim that

lim_{n→∞} λ_{1}(A^{(n)}) = 2 ℙ-almost surely

The asymptotic behaviour of λ_{1}(A^{(n)}) was further clarified by Tracy and Widom, who proved the following result : there exists a continuous decreasing function ψ_{TW} from ℝ onto (0, 1) such that

lim_{n→∞} ℙ_{n}(λ_{1}(A^{(n)}) ⩾ 2 + xn^{−2/3}) = ψ_{TW}(x)  (1)

This function ψ_{TW} naturally arises as a determinant linked to the so-called “Airy kernel”, which will be defined later. The most difficult point of Tracy and Widom’s work was to show that this function ψ_{TW} can be written in terms of a Painlevé function (see [17]). From this point one can deduce asymptotic behavior of ψ_{TW} around +∞ and find universal positive constants C, c, C′, c′ such that for x large enough

c′ exp(−C′x^{3/2}) ⩽ ψ_{TW}(x) ⩽ c exp(−Cx^{3/2})  (2)

The remainder of this article is organized as follows : in section 1, we define an appropriate Wasserstein distance and state our main theorem which asserts that Tracy-Widom convergence holds in this strong distance. In section 2, we derive from this theorem the small deviation inequality and compare it with the classical one. Section 3 introduces the needed framework of determinantal kernels, which are classical in this field, and section 4 contains the proof of the main theorem. Finally, section 5 contains an alternative simple deviation of upper bounds (2) for Tracy-Widom distribution.

1 Convergence in Terms of a Wasserstein Distance

We call tail function of a measure μ on ℝ the function ψ_{μ} : ℝ → [0, 1] defined by ψ_{μ}(x) := μ((x, +∞)). Such a function is decreasing, left-continuous, tends to 1 at −∞ and to 0 at +∞. The tail function just equals 1 minus the cumulative distribution function. The function appearing in the r.h.s. of (1) is the tail function of the Tracy-Widom distribution on ℝ (we denote this distribution by T W).

We want to prove that the law of the rescaled largest eigenvalue tends to the Tracy-Widom law in a strong sense. As we only focus on the upper tail, we can consider truncated laws, supported on an interval [a, +∞) for some real a. Let Λ_{n}^{a} be the probability measure with tail function defined by

ψ_{Λ_{n}^{a}}(x) = \{ \begin{matrix}ℙ_{n}(λ_{1}(A^{(n)}) ⩾ 2 + xn^{−2/3}) & if x ⩾ a \\ 1 & if x < a \end{matrix}

Similarly, let T W^{a} be the truncated Tracy-Widom law defined by

ψ_{_{TW}a} (x) = \{ \begin{matrix}ψ_{TW}(x) & if x ⩾ a \\ 1 & if x < a \end{matrix}

We are going to show that for any a, Λ_{n}^{a} tends to T W^{a} with respect to the distance defined through a mass transportation problem in its Monge-Kantorovich formulation (see [12]).

A mass transportation problem is the question of optimizing the transshipment from a measure to another with respect to to a given cost. More precisely, let μ and ν be two probability measures on the same space X, and c : X × X → ℝ_{+} a symmetric function vanishing on the diagonal (c(x, y) represent the price to pay to transfer a unit of mass from x to y). Ways to carry μ onto ν are represented through probability measures π on the square space X × X having μ and ν as marginals (this means that for any measurable subset A of X, π(A × X) = μ(A) and π(X × A) = ν(A)). We denote by Π(μ, ν) the space of such π.

The Wasserstein distance associated with the problem is the “minimum cost to pay”, defined by

d(μ, ν) = inf_{π∈Π(μ,ν)} ∫_{X^{2}} c(x, y)dπ(x, y)

We are going to consider a very special case of this problem. Let us suppose that X = ℝ and that the cost c is defined as follows

c(x, y) := | ∫_{x}^{y} w(t)dt|  (3)

where w is a positive function.

We can now state the main result of this note

Theorem 1. Let w(x) := exp(γx^{3/2}) and let d be the Wasserstein distance associated with the cost induced by w via the formula (3). Then, for any fixed a ∈ ℝ, if γ > 0 is small enough, Λ_{n}^{a} tends to T W^{a} for the distance d

lim_{n→∞} d(Λ_{n}^{a}, T W^{a}) = 0

2 The Small Deviation Inequality

The simplest idea to get concentration inequalities for the largest eigenvalue of a GUE random matrix is to use Gaussian concentration ; it is a straightforward consequence of the measure concentration phenomenon in the Gaussian space (see [1]) that

∀t > 0, ∀n, ℙ_{n}(λ_{1}(A^{(n)}) ⩾ M_{n} + t) < exp(−nt^{2}/2)  (4)

where M_{n} is the median of λ_{1}(A^{(n)}) with respect to the probability measure ℙ_{n}. One has the same upper estimate is the median M_{n} is replaced by the expected value 𝔼_{n}λ_{1}(A^{(n)}).

The value of M_{n} can be controlled : for example we have M_{n} ⩽ 2 + c/\sqrt{n}. This will be for example a consequence of our Proposition. Plugging this into the equation (4), we get the following result, where C is a universal constant

∀t > 0, ∀n, ℙ_{n}(λ_{1}(A^{(n)}) ⩾ 2 + t) < C exp(−nt^{2}/2)  (5)

We ask the question whether in fact both 𝔼_{n}λ_{1}(A^{(n)}) and M_{n} are smaller than 2. Note that since the funcion λ_{1} is convex, its median with respect to ℙ_{n} does not exceed its expected value ([7]). A positive answer to this question would imply that one could choose C = 1 in the inequality (5). The answer to the analogous question is known to be positive for the GOE (Gaussian Orthogonal Ensemble), an ensemble of real symmetric matrices defined in a similar way as GUE (see [10] for a precise definition). The argument, due to Gordon, uses a result about comparison of Gaussian processes known as Slepian’s lemma (see [1]) and doesn’t carry over to the complex setting.

There are similar though not as simple results for ℙ_{n}(λ_{1}(A^{(n)}) ⩽ 2 − t), but in this paper we will concentrate on the “upper tail” estimates.

The result of Tracy and Widom (1) shows that the majoration (5) is not optimal for very small values of t. If for example t is equal to xn^{−2/3} for a fixed x, then the right-hand side in concentration inequality (5) tends to 1 when n grows to ∞, whereas the left-hand side tends to ψ_{TW}(x), which can be very small.

We would like to derive from our Theorem a deviation inequality which would improve the inequality (5) for small values of t. For this purpose, the uniform convergence in (1) (which, by Dini’s theorem, follows formally form the pointwise convergence) is not enough. But we will prove in this section that our Theorem implies the following Proposition :

Proposition 1. There exist positive universal constants C and c such that for every positive t and any integer n

ℙ_{n}(λ_{1}(A^{(n)}) ⩾ 2 + t) ⩽ C exp(−cnt^{3/2})  (6)

Of course, by symmetry of the law ℙ_{n}, similar results are true for the smallest eigenvalue λ_{n}(A^{(n)})

ℙ_{n}(λ_{n}(A^{(n)}) ⩽ −2 − t) ⩽ C exp(−cnt^{3/2})  (7)

Using the fact that for a Hermitian matrix A, the norm equals the maximum absolute value of an eigenvalue, we get a similar estimate for ||A^{(n)}||

ℙ_{n}(||A^{(n)}|| ⩾ 2 + t) ⩽ C exp(−cnt^{3/2})  (8)

We need the following lemma to prove the proposition, which will help us to explicitly compute Wasserstein distance

Lemma 1. Suppose that the measures μ and ν are defined on ℝ, and that the cost c is defined by an integral, as in (3). If μ and ν are regular enough, for example if ψ_{μ} and ψ_{ν} are piecewise C^{1}, then the Wasserstein distance for the cost c equals

d(μ, ν) = ∫_{−∞}^{∞} w(t)|ψ_{μ}(t) − ψ_{ν}(t)|dx  (9)

Proof. In fact, this transportation problem is explicitly solvable. For a onedimensional problem with a cost satisfying the Monge condition (which is always the case when the cost is defined using an integral as in (3)), the optimal transshipment is achieved through the map T defined as follows (see [12], chapter 3.1)

∫_{−∞}^{x} dμ = ∫_{−∞}^{T (x)} dν

Thus, we can compute the value of d(μ, ν)

d(μ, ν) = ∫_{0}^{1} c(ψ_{μ}^{−1}(u), ψ_{ν}^{−1}(u))du

Let us consider first the particular case when ψ_{μ} ⩽ ψ_{ν}. This allows us to drop the absolute values in the definition of c (see (3)) and unfold the calculations. Using the appropriate changes of variables, we come to the equality (9).

For general μ and ν, define μ ∧ ν and μ ∨ ν using their tail functions

ψ_{μ∧ν}(x) = min(ψ_{μ}(x), ψ_{ν}(x)) and ψ_{μ∨ν}(x) = max(ψ_{μ}(x), ψ_{ν}(x))

We easily check that ψ_{μ∧ν} ⩽ ψ_{μ∨ν}, d(ψ_{μ}, ψ_{ν}) = d(ψ_{μ∧ν}, ψ_{μ∨ν}) and that the value of the r.h.s. of (9) does not change if we replace ψ_{μ} and ψ_{ν} by ψ_{μ∧ν} and ψ_{μ∨ν}. This yields the conclusion for the general case. ⊓ ⊔

Using this lemma, we get from our theorem (with a = 0), using the upper bound (2) for ψ_{TW}, the uniform estimate

∫_{0}^{∞} w(x)ℙ_{n}(λ_{1}(A^{(n)}) ⩾ 2 + xn^{−2/3}) dx ⩽ C

which implies immediately for x ⩾ 1 (keep in mind that ψ_{n} is decreasing)

ψ_{n}(x) ⩽ C exp(−γ(x − 1)^{3/2}) ⩽ C′ exp(−γ′x^{3/2})  (10)

This is, up to the rescaling t = xn^{−2/3}, the content of the proposition.

Now we can also easily show that our theorem implies the Tracy-Widom limit (1) : using the uniform bound (10) and Lebesgue’s convergence theorem, we get from the Theorem that ψ_{TW} is the pointwise limit of the ψ_{n}’s on [a, +∞), and thus on the whole real line if we let a go to −∞.

It should be emphasized that recently (independently from and slightly preceding this work), this small deviations result has been proved by Ledoux in [8] using an argument based on the Harer-Zagier recurrence formula (see [5] for a simple proof of this formula). The same paper by Ledoux contains another proof based on hypercontractivity which gives the result up to a polynomial factor ; this method works also for the Laguerre Unitary Ensemble (see [8] for the definition). However, the existence of a Tracy-Widom limit does not follow from this approach. More generally, many contributions to this and related topics either address the limit behaviour or provide dimension-free bounds, rarely combining the two. Our technique captures both phenomena in a single “stroke”.

3 Relation to Determinants

The remainder of this note is devoted to the proof of the main theorem. For simplicity, we will prove only the case a = 0, and drop all the superscripts. The proof for a general a requires only routine modifications.

We are first going to express all involved quantities in terms of determinants of certain operators. This is quite classical work due to Gaudin and Mehta (see [10]). Part of the calculations done here are present, at least implicitly, in the paper by Tracy and Widom ([17]).

We need new notation. Let (H_{n}) be the Hermite polynomials, which are defined by

H_{n}(t) := (−1)^{n} exp(t^{2})(\frac{d}{dt})^{n} exp(−t^{2})

They are orthogonal for the measure on ℝ of density exp(−x^{2}) with respect to Lebesgue measure. Then we note

ϕ_{n}(t) := \frac{1}{\sqrt{d_{n}}} H_{n}(t) exp(−t^{2}/2)  (11)

where d_{n} := ∫_{ℝ} H_{n}(x)^{2}dx = 2^{n}n!\sqrt{π}. The family (ϕ_{n}) is therefore orthonormal in L^{2}(ℝ). We introduce

k_{n}(x, y) := ∑_{j=0}^{n−1} ϕ_{j}(x)ϕ_{j}(y)

We can associate to k_{n} an integral operator K_{n} acting on the Hilbert space L^{2}(ℝ) in the following way

(K_{n}f)(x) := ∫_{ℝ} k_{n}(x, y)f(y)dy  (12)

This operator K_{n} is nothing but the orthogonal projection in L^{2}(ℝ) onto the subspace spanned by (ϕ_{j})_{1⩽j⩽n}.

This is a very general setting : if we have a measure space (X, μ) and a “kernel” k ∈ L^{2}(X × X), we can define an operator K on L^{2}(X) using a formula similar to (12). From now on, all kernels are assumed to belong to L^{2}(X × X) and are denoted by small letters ; associated integral operators are denoted by the corresponding capital letter.

It is straightforward to prove that Hilbert-Schmidt operators on L^{2}(X) are exactly integral operators with a L^{2} kernel. Moreover, the Hilbert-Schmidt norm of the operator and the L^{2} norm of the kernel coincide. This fact is proved in [3], which is a good reference for a reader who wants more detail on integral operators. Let us just quote the formula for compositions of operators : if k and l are two kernels on the same space (X, μ), then the operator KL is an integral operator with kernel :

(kl)(x, y) = ∫_{X} k(x, z)l(z, y)dμ(z)  (13)

The tail function of λ_{1}(A^{(n)}) can now be expressed using the kernel k_{n}. The key formula is the following (see [10])

∀t ∈ ℝ, ℙ_{n}(\begin{matrix}√ & \overline{n} \\ √ & \overline{2} \end{matrix}λ_{1}(A^{(n)}) ⩽ t) = det_{[t,∞)}(Id − K_{n})  (14)

In the formula (14), the right-hand side must be understood as the determinant of the operator K_{n} acting on the space L^{2}([t, ∞)) (or equivalently of the operator with kernel equal to is the restriction of k_{n} to [t, ∞)^{2}). This restricted operator is denoted K_{n}^{[t]}.

It may not be immediately obvious how to define such a determinant, as the operator involved acts on an infinite-dimensional space. However, the operator K_{n} that we consider here has a finite rank, hence we can define its determinant as if it were acting on a finite-dimensional space.

A problem will arise when we want to consider limits of such operators, which might fail to have a finite rank. Fortunately, a whole theory of determinants (and traces) of integral operators exists (so-called “Fredholm” determinants). In fact, there are several possible ways to extend these concepts to the infinite-dimensional case. We will focus on a more algebraic approach, due to Grothendieck (see [4] or [13] for a complete exposition), which defines determinants of a nuclear (= trace class) perturbation of identity in terms of traces of its exterior powers (here N is a nuclear operator, for which trace is well-defined).

det(Id + N) := 1 + ∑_{k=1}^{∞} tr(Λ^{k}(N))

Of course, this definition coincides with the usual one in the finitedimensional case.

The presence of the factor \sqrt{n}/\sqrt{2} in equation (14) requires an explanation. It arose because there are several normalizations possible. We chose to define the GUE so that the first eigenvalue is about 2, while other authors, as Tracy and Widom in [17], prefer to locate it around \sqrt{2n} (there are still other normalizations but an exhaustive list would be too long). As we kept their notation for the kernels k_{n}, a scaling factor will appear when we pass from a normalization to the other one.

To get a nontrivial limit, we must replace the t in formula (14) by the following rescaling, as for the Tracy-Widom limit (1)

t = τ_{n}(x) := \begin{matrix}√ & \overline{n} \\ √ & \overline{2} \end{matrix}(2 + \frac{x}{n^{2/3}} )

Let also k̃_{n} be the rescaled kernel

k̃_{n}(x, y) := \frac{1}{\sqrt{2}n^{1/6}} k_{n}(τ_{n}(x), τ_{n}(y))

We can see using a change of variable that K̃_{n}^{[x]} and K_{n}^{[τ_{n}(x)]} have the same eigenvalues. More precisely, if f is a eigenfunction of K̃_{n}^{[x]}, then f ∘ τ_{n}^{−1} is a eigenfunction of K_{n}^{[τ_{n}(x)]}, with the same eigenvalue.

Plugging these renormalizations into the formula (14), we obtain

ℙ_{n}(λ_{1}(A^{(n)}) ⩽ 2 + xn^{−2/3}) = det_{[x,+∞)}(Id − K̃_{n})  (15)

Using the previous definition for the tail function ψ_{n}, we can write for a positive s

ψ_{n}(s) = 1 − det(Id − K̃_{n}^{[s]})

The following result was known before Tracy and Widom’s work (see for example [2])

lim_{n→∞} k̃_{n}(x, y) = k(x, y)  (16)

uniformly on compact subsets in x and y.

Here k is the kernel, often called Airy kernel, defined by

k(x, y) := \frac{Ai(x)Ai′(y) − Ai′(x)Ai(y)}{x − y}  (17)

The kernel k is extended by continuity to the diagonal. The function Ai is called the Airy function. It is very useful in physics and can be defined by several means. One of them is the following integral representation

Ai(z) := \frac{1}{2π} ∫_{−∞}^{∞} exp(i(zt + t^{3}/3))dt

It can also be written as a combination of Bessel functions. It satisfies the Airy ODE

\frac{∂^{2}}{∂x^{2}} y(x) = xy(x)  (18)

The asymptotic behavior of Ai is well-known, for example [16] contains the following formula, valid when x tends to +∞

Ai(x) ∼ \frac{1}{2}3^{−1/4}\sqrt{π}x^{−1/4} exp(−\frac{2}{3^{3/2}} x^{3/2})  (19)

The function ψ_{TW} can be defined using this Airy kernel

ψ_{TW}(x) := 1 − det(Id − K^{[x]})  (20)

In [17] Tracy and Widom found another expression for ψ_{TW}. Let q be the solution of the Painlevé II ODE

\frac{∂^{2}}{∂x^{2}} q(x) = xq(x) + 2q(x)^{3}

which is determined by the asymptotics q(x) ∼ Ai(x) for x close to +∞. Then we have the representation

ψ_{TW}(x) = 1 − exp(− ∫_{x}^{∞}(t − x)q(t)^{2}dt)  (21)

It is easy to get from (19) and (21) the bounds (2) for the asymptotic behavior of ψ_{TW}. However, as we do not really need all the depth of Tracy and Widom’s results and connections to Painlevé functions, we will reprove this fact in a more elementary way at the end of this note.

4 Convergence of the Operators

The convergence in (16) as determined in the existing literature is rather weak ; in particular, it does not imply convergence of the associated integral operators in the Hilbert-Schmidt norm or even in the operator norm on L^{2}. In particular, we are not a priori allowed to exchange limit and determinant in (15) when n tends to infinity.

Our main step will be to show that K̃_{n} tends to K with respect to the nuclear (trace class) norm. To that end we need several lemmas.

Lemma 2. The following equality holds

(\frac{∂}{∂x} + \frac{∂}{∂y} ) k_{n}(x, y) = −\sqrt{\frac{n}{2}} (ϕ_{n}(x)ϕ_{n−1}(y) + ϕ_{n−1}(x)ϕ_{n}(y))

Proof. We start with the Christoffel-Darboux formula (see [16])

k_{n}(x, y) = \sqrt{\frac{n}{2}} \frac{ϕ_{n}(x)ϕ_{n−1}(y) − ϕ_{n−1}(x)ϕ_{n}(y)}{x − y}

Then we apply the operator \frac{∂}{∂x} + \frac{∂}{∂y} to each term. We use the formula (11) and the following identities (those which are not obvious are shown in [16])

ϕ′_{n}(x) = −\frac{exp(−x^{2}/2)}{\sqrt{d_{n}}}(H′_{n}(x) − xH_{n}(x))

H′_{n−1}(x) = 2xH_{n−1}(x) − H_{n}(x)

H′_{n}(x) = 2nH_{n−1}(x)

We obtain exactly the expected result. ⊓ ⊔

Lemma 3. The following integral representation holds

k̃_{n}(x, y) = \frac{n^{1/6}}{2\sqrt{2}} ∫_{0}^{∞} ϕ_{n}(τ_{n}(x + z))ϕ_{n−1}(τ_{n}(y + z))  (22)
+ ϕ_{n−1}(τ_{n}(x + z))ϕ_{n}(τ_{n}(y + z))dz

Proof. If we apply the operator \frac{∂}{∂x} + \frac{∂}{∂y} to the right-hand side of (22) (there is no trouble with interchanging the operations “\frac{∂}{∂x} + \frac{∂}{∂y} ” and “∫_{0}^{∞}” since all the functions involved are Schwartz functions), we get after standard calculations

\frac{n^{1/6}}{2\sqrt{2}} (ϕ_{n}(τ_{n}(x))ϕ_{n−1}(τ_{n}(y)) + ϕ_{n−1}(τ_{n}(x))ϕ_{n}(τ_{n}(y)))

Lemma 2 asserts that we obtain exactly the same expression when we apply the operator \frac{∂}{∂x} + \frac{∂}{∂y} to the left member of (22). Thus, the two members of the equation are equal modulo a function (say, α) which only depends on x − y. But both members tend to zero when x et y tend to infinity in an independent way. Therefore the function α has to vanish identically and the lemma is proved. ⊓ ⊔

Let us introduce extra notation. The following kernels are defined on [s, +∞)^{2}, where s is any positive number

a_{n}^{[s]}(x, y) := \frac{n^{1/12}}{2^{1/4}} ϕ_{n}(τ_{n}(x + y − s))

b_{n}^{[s]}(x, y) := \frac{n^{1/12}}{2^{1/4}} ϕ_{n−1}(τ_{n}(x + y − s))

a^{[s]}(x, y) := Ai(x + y − s)

The equality (22) can be translated in terms of operators (this is just a consequence of the formula (13) for the composition of kernels)

K̃_{n}^{[s]} = \frac{1}{2}(A_{n}^{[s]}B_{n}^{[s]} + B_{n}^{[s]}A_{n}^{[s]})  (23)

A similar equality for the operator K is proved (exactly in the same way) in [17]

K^{[s]} = (A^{[s]})^{2}  (24)

We shall subsequently show that (for a fixed s) the operators A_{n}^{[s]} and B_{n}^{[s]} tend to A^{[s]} with respect to the Hilbert-Schmidt norm. To that end, we need estimates for ϕ_{n} contained in two lemmas that follow.

Lemma 4. The functions ϕ_{n}, after rescaling, converge to Ai, uniformly on compact subsets in y :

ϕ_{n}(τ_{n}(y))2^{−1/4}n^{1/12} → Ai(y) and ϕ_{n−1}(τ_{n}(y))2^{−1/4}n^{1/12} → Ai(y) (25)

Proof. This is an immediate consequence of the following asymptotic formulae for Hermite polynomials due to Plancherel and Rotach. They can be found, in a slightly different presentation, in the book by Szegö ([16])

If x = \sqrt{2n + 1} + \frac{y}{\sqrt{2}n^{1/6}} , then ϕ_{n}(x) = 2^{1/4}n^{−1/12}(Ai(y) + O(n^{−3/4}))

The O holds when n tends to +∞, uniformly in y on compact subsets. ⊓ ⊔

Lemma 5. We have a bound for ϕ_{n} which is uniform in n : there exists a positive constant c such that for any y > 0 and any integer n

\{ \begin{matrix}n^{1/12}ϕ_{n}(τ_{n}(y)) ⩽ C exp(−cy^{3/2}) \\ n^{1/12}ϕ_{n}(τ_{n−1}(y)) ⩽ C exp(−cy^{3/2}) \end{matrix}  (26)

Proof. Let us sketch a proof of the fisrt inequality in (26). We will use the following result, which is an exercise at page 403 in [11]. It is valid for x ⩾ 1

H_{n}(νx) ⩽ 1.13\sqrt{2π} exp(−ν^{2}/4)ν^{(3ν^{2}−1)/6} exp(ν^{2}x^{2}/2) (\frac{ζ}{x^{2} − 1})^{1/4} Ai(ν^{4/3}ζ)

where ν := \sqrt{2n + 1} and

ζ := (\frac{3}{4}x\sqrt{x^{2} − 1} − \frac{3}{4}Argchx)^{2/3}

Using the definition of ϕ_{n} given in formula (11) and Stirling’s formula to estimate d_{n}, we obtain

n^{1/12}ϕ_{n}(νx) ⩽ C (\frac{ζ}{x^{2} − 1})^{1/4} Ai(ν^{4/3}ζ)

We deduce from (19) a bound for Ai, and we also use the inequality ζ ⩾ c(x − 1) to get

n^{1/12}ϕ_{n}(\sqrt{2n + 1}x) ⩽ Cn^{−1/6} \frac{1}{(x − 1)^{1/4}} exp(−c(2n + 1)(x − 1)^{3/2}) (27)

We now return to our notation through the change of variable \sqrt{2n + 1} x = τ_{n}(y). We can estimate x in the following way

x ⩾ 1 − \frac{c}{n} + \frac{y}{\sqrt{2}n^{1/6}\sqrt{2n + 1}}

For y large enough, we even have

x ⩾ 1 + c\frac{y}{n^{2/3}}  (28)

Combining (27) and (28) yields

n^{1/12}ϕ_{n}(τ_{n}(y)) ⩽ C \frac{1}{y^{1/4}} exp(−cy^{3/2})

The factor y^{−1/4} can be deleted if c is made small enough. This inequality is only true for y large enough, but we keep in mind that convergence in (25) was uniform on compact subsets, so we can extend it to all positive y, and the inequality is proved. The same scheme of demonstration works for the second inequality, with τ_{n−1} instead of τ_{n}. ⊓ ⊔

We are now ready to prove our main theorem

Proof. We denote by ||.||_{HS} the Hilbert-Schmidt norm and by ν the nuclear norm.

We are first going to estimate the quantity |ψ_{n}(s) − ψ_{TW}(s)| = | det(Id − K̃_{n}^{[s]})−det(Id−K^{[s]})|. To reach this goal, we will use the following majoration (see [4]), valid for any two nuclear operators A and B

| det(Id + A) − det(Id + B)| ⩽ ν(A − B)e^{1+ν(A)+ν(B)}  (29)

It will be useful to notice that lemma 5 implies in particular the following remark : there is a positive C such that for any s ⩾ 0 and any integer n, all the quantities ||A_{n}^{[s]}||_{HS}, ||B_{n}^{[s]}||_{HS} and ||A^{[s]}||_{HS} are bounded by C (remember that the Hilbert-Schmidt norm is just the L^{2}-norm of the kernel). Using inequalities (23), (24) and the noncommutative Hölder inequality, we get that ν(K^{[s]}) and ν(K̃_{n}^{[s]}) are also bounded by the constant. Hence we can drop the exponential factor in formula (29)

|ψ_{n}(s) − ψ_{TW}(s)| ⩽ Cν(K̃_{n}^{[s]} − K^{[s]})

We need to estimate the quantity ν(K̃_{n}^{[s]} − K^{[s]}). The key to do this is to use the equalities (23) et (24) to get

K̃_{n}^{[s]} − K^{[s]} = \frac{1}{4}((A_{n}^{[s]} − A^{[s]})(B_{n}^{[s]} + A^{[s]}) + (A_{n}^{[s]} + A^{[s]})(B_{n}^{[s]} − A^{[s]})
+ (B_{n}^{[s]} + A^{[s]})(A_{n}^{[s]} − A^{[s]}) + (B_{n}^{[s]} − A^{[s]})(A_{n}^{[s]} + A^{[s]}))

The non-commutative Hölder inequality yields

ν(K̃_{n}^{[s]} − K^{[s]}) ⩽ \frac{1}{2}||A_{n}^{[s]} − A^{[s]}||_{HS}||B_{n}^{[s]} + A^{[s]}||_{HS}  (30)
+ \frac{1}{2}||A_{n}^{[s]} + A^{[s]}||_{HS}||B_{n}^{[s]} − A^{[s]}||_{HS}

The factors with a “+” are easy to get rid of : we can use the triangle inequality to write ||A_{n}^{[s]}+A^{[s]}||_{HS} ⩽ ||A_{n}^{[s]}||_{HS} +||A^{[s]}||_{HS}, which is uniformly bounded according to the remark following formula (29). We obtain

ν(K̃_{n}^{[s]} − K^{[s]}) ⩽ C(||A_{n}^{[s]} − A^{[s]}||_{HS} + ||B_{n}^{[s]} − A^{[s]}||_{HS})

We can now calculate the Wasserstein distance from Λ_{n} to T W, using the expression given by lemma 1

d(Λ_{n}, T W) = ∫_{0}^{∞} exp(γs^{3/2})|ψ_{n}(s) − ψ_{TW}(s)|ds
⩽ C ∫_{0}^{∞} exp(γs^{3/2})(||A_{n}^{[s]} − A^{[s]}||_{HS} + ||B_{n}^{[s]} − A^{[s]}||_{HS})ds

First deal with the term ||A_{n}^{[s]} − A^{[s]}||_{HS}. Using the definition of A_{n}^{[s]} and A^{[s]} we get

∫_{0}^{∞} exp(γs^{3/2})||A_{n}^{[s]} − A^{[s]}||_{HS}ds  (31)

= \sqrt{2} ∫_{0}^{∞} exp(γs^{3/2}) (∫_{0}^{∞} z ((\frac{n^{1/12}}{2^{1/4}} ϕ_{n} ∘ τ_{n} − Ai)(z + s))^{2} dz)^{1/2} ds

Fix an ε > 0 and use the uniform bound of lemma 5 : we get that for γ small enough, S large enough and any n

\sqrt{2} ∫_{S}^{∞} exp(γs^{3/2}) (∫_{0}^{∞} z ((\frac{n^{1/12}}{2^{1/4}} ϕ_{n} ∘ τ_{n} − Ai)(z + s))^{2} dz)^{1/2} ds ⩽ ε

Similarly, for Z large enough, any s smaller than S and any n

(∫_{Z}^{∞} z ((\frac{n^{1/12}}{2^{1/4}} ϕ_{n} ∘ τ_{n} − Ai)(z + s))^{2} dz)^{1/2} ⩽ \frac{ε}{\sqrt{2}S exp(S^{3/2})}

Now we can split the integral in (31) into three terms to get (remember than convergence in lemma 4 was uniform on compact subsets)

∫_{0}^{∞} exp(γs^{3/2})||A_{n}^{[s]} − A^{[s]}||_{HS}ds ⩽ 3ε for n large enough

We can write a similar estimate with B_{n} instead of A_{n}. We finally deduce that, for n large enough, d(Λ_{n}, T W) ⩽ 6Cε. Hence Λ_{n} tends to T W in the Wasserstein sense. This is the announced result. ⊓ ⊔

5 An Elementary Proof of Asymptotics for ψ_{TW}

To prove our theorem, we needed the upper asymptotics (2) for ψ_{TW}. It is possible to derive them from the representation (21) : keeping in mind that q ∼ Ai, we get from (19)

∫_{x}^{∞}(t − x)q^{2}(t)dt ⩽ C exp(−cx^{3/2})

Hence, (21) yields

ψ_{TW}(x) ⩽ 1 − exp(−C exp(−cx^{3/2})) ⩽ C′ exp(−cx^{3/2})

However, for sake of completeness, we are going to derive in this section this last result in a more elementary way, i.e. without using the Painlevé representation. To do this, we need some facts about integral operators. Of course, a general integral operator can fail to be nuclear (for example, any Hilbert-Schmidt operator from L^{2}(X) into itself can be written as an integral operator). Nevertheless, there exist several “nuclearity tests”, criteria ensuring that under some conditions, kernels generate nuclear operators ([3],[4]). The main result in this topic is Mercer’s theorem, which enables us to expand a continuous self-adjoint kernel (i.e. the associated operator is self-adjoint) as a series of eigenfuctions of the operator. Unfortunately, these results are usually stated when dealing with a compact space of finite measure, and we have to consider half-infinite intervals [s, +∞). However, the standard proofs work also in this setting with only slight modifications.

A result which fits the present context is the following

Lemma 6. Let X = [s, +∞), equipped with the Lebesgue measure, and k be a kernel on X × X which satisfies the following conditions

1. k ∈ L^{2}(X × X)

2. k is jointly continuous

3. K is positive self-adjoint as an operator on L^{2}(X)

4. There exists a continous positive function ϱ in L^{2}(X) such that |k(x, y)| ⩽ ϱ(x)ϱ(y) for every x, y in X.

Then the operator K is nuclear and the trace formula holds

tr(K) = ∫_{s}^{∞} k(x, x)dx  (32)

Proof. We are going to derive our result from the classical finite-measure case using a change of density trick. Let μ be the mesaure on X with density ϱ^{2} with respect to Lebesgue measure ; we have μ(X) < ∞. If we (isometrically) identify L^{2}(X, dx) with L^{2}(X, μ) sending f to f/ϱ, the integral operator K viewed from L^{2}(X, μ) into itself has kernel k(x, y)/ϱ(x)ϱ(y). To get the result we simply apply to the new kernel the following version of Mercer’s theorem (it can proved adapting straightforward the classical proof from [14]) : if μ is a finite Borel measure on X and k a continuous bounded positive self-adjoint kernel, then the associated operator K is nuclear and its trace is equal to the integral of the kernel along the diagonal. ⊓ ⊔

Lemma 7. The following estimation holds

∃C, c > 0, ∀s > 0, ψ_{TW}(s) ⩽ C exp(−cs^{3/2})

Proof. By definition (see [13]), we have

ψ_{TW}(s) = ∑_{k=1}^{∞}(−1)^{k−1}tr(Λ^{k}(K^{[s]}))

Using the fact that tr(Λ^{k}(K^{[s]})) ⩽ tr(K^{[s]})^{k}/k!, we get

|ψ_{TW}(s)| ⩽ exp(trK^{[s]}) − 1

Actually, formula (20) shows that ψ_{T W} is positive since we have 0 ⩽ K^{[s]} ⩽ 1. In the end, the convexity of the exponential function on [0, trK^{[0]}] yields for s ⩾ 0

ψ_{T W} (s) ⩽ CtrK^{[s]}

It is not hard to check that the kernel k^{[s]} satisfies the hypotheses of lemma 6 ; to check condition 4 we can cook up a function ϱ using Ai and its derivative.

Thus we can rewrite the trace of K^{[s]} as an integral

ψ_{T W} (s) ⩽ C ∫_{s}^{∞} ((Ai′(x))^{2} − xAi(x)) dx  (33)

The value of K on the diagonal comes from (17) and the Airy ODE (18). Using (19), we can write

∃C, c > 0 ∀s ⩾ 0 Ai(s) ⩽ C exp(−cs^{3/2})  (34)

A similar majoration holds for Ai′ : we only need to write Ai′(s) = ∫_{s}^{∞} Ai′′(x)dx and to use formulae (18) and (34)

∃C, c > 0 ∀s ⩾ 0 Ai′(s) ⩽ C exp(−cs^{3/2})  (35)

The conclusion comes when combining formulae (33), (34) and (35). ⊓ ⊔

Possible Generalizations

Of course, we expect the inequalities analogous to (6) to be true in a much more general setting. Basically, each time a Tracy-Widom-like behavior has been proved or is suspected, we can ask whether such an uniform estimate holds.

The most natural extension would be the setting of general Wigner matrices, for which universality of Tracy-Widom limit has been proved by Soshnikov ([15]). However, the bounds on moments he obtained are not enough to derive the small deviations inequality.

Tracy and Widom proved results similar to (1), involving a different limit law, for the matrix ensembles GOE and GSE (the real orthogonal and the symplectic cases) in [18].

Several authors investigated the behavior of the largest s-number (also called singular value) of a rectangular m×n matrix with independant entries, when the ratio m/n tends to a limit in (0, 1). The paper [6] contains an result anaologous to (1) for the Gaussian case (the so-called Wishart ensemble). There is strong numerical evidence indicating that a convergence on the scale n^{−2/3} as in Tracy-Widom behavior occurs also universally in this case, for the largest s-number, but also for the smallest one.

Another quantity of interest is the norm of a n × m random matrix when considered as a operator from ℓ_{p}^{n} to ℓ_{q}^{m}. Concentration results have been recently obtain in this case by Meckes (cf [9]).

In all these cases, we know concentration inequalities similar to (5), it would be interesting to prove the corresponding small deviation result.

Acknowledgements

I would like to express my sincere thanks and appreciation to my supervisor, Prof. Stanislaw J. Szarek, for our inspiring discussion and for his ongoing support. This paper will be part of my Ph.D. thesis prepared at the Équipe d’Analyse Fonctionnelle of the University Paris VI. I would also like to thank Charles-Antoine Louët for his assiduous proofreading.

References

1. Davidson, K.R. and Szarek, S.J. (2001). Local operator theory, random matrices and Banach spaces. In Handbook of the Geometry of Banach Spaces, vol. 1, pages 317–366.

2. Forrester, P.J. (1993). The spectrum edge of random matrix ensembles Nucl. Phys. B402, 709–728.

3. Gohberg, I. and Goldberg, S. (1981). Basic operator theory. Birkhaüser.

4. Gohberg, I., Goldberg, S. and Krupnik, N. (1998). Traces and Determinants of Linear Operators. Birkhaüser.

5. Haagerup, U, and Thorbjørnsen, S (1999). Random matrices with complex Gaussian entries. Preprint available at URL

    http://imada.sdu.dk/~haagerup/2000-.html

6. Johnstone, I.M. (2001). On the distribution of the largest eigenvalue in principal component analysis. Ann. Statist. 29, 295–327.

7. Kwapień, S. (1993). A remark on the median and the expecation of convex functions of Gaussian vectors. Probabilities in Banach spaces 9 (Sandjberg, 1993), Progr. Probab. 35, 271–272.

8. Ledoux, M. (2003). A remark on hypercontractivity and tail inequalities for the largest eigenvalues of random matrices. Séminaire de probabilités XXXVII. Lecture Notes in Mathematics, Springer.

9. Meckes, M.W. (2003). Concentration of norms and eigenvalues of random matrices. To appear in J. Funct. Anal.

10. Mehta, M.L. (1991). Random Matrices. Academic Press, Boston, MA, second edition.

11. Olver, F.W.J. (1974). Asymptotics and Special Functions. Cambridge University Press.

12. Rachev, S.T. and Rüschendorf, L. (1998). Mass Transportation Problems. Vol. 1, Springer-Verlag.

13. Simon, B. (1977). Infinite determinants. Advances in Math. 24, 244–273.

14. Smithies, F. (1959). Integral equations. Cambridge University Press.

15. Soshnikov, A. (1999). Universality at the edge of spectrum in Wigner random matrices. Comm. Math. Phys. 207, 697–733.

16. Szegö, G. (1967). Orthogonal Polynomials. American Mathematical Society, third edition.

17. Tracy, C.A. and Widom, H. (1994). Level-spacing distributions and the Airy kernel. Comm. Math. Phys. 159, 151–174.

18. Tracy, C.A. and Widom, H. (1996). On orthogonal and symplectic matrix ensembles. Comm. Math. Phys. 177, 727–754.