Benaych-Georges Florent

Raj Rao Nadakuditi

THE EIGENVALUES AND EIGENVECTORS OF FINITE, LOW RANK PERTURBATIONS OF LARGE RANDOM MATRICES

Keywords: . 2000 Mathematics Subject Classification. 15A52, 46L54, 60F99 Random matrices, Haar measure, principal components analysis, informational limit, free probability, phase transition, random eigenvalues, random eigenvectors, random perturbation, sample covariance matrices

We consider the eigenvalues and eigenvectors of finite, low rank perturbations of random matrices. Specifically, we prove almost sure convergence of the extreme eigenvalues and appropriate projections of the corresponding eigenvectors of the perturbed matrix for additive and multiplicative perturbation models.

The limiting non-random value is shown to depend explicitly on the limiting eigenvalue distribution of the unperturbed random matrix and the assumed perturbation model via integral transforms that correspond to very well known objects in free probability theory that linearize non-commutative free additive and multiplicative convolution. Furthermore, we uncover a phase transition phenomenon whereby the large matrix limit of the extreme eigenvalues of the perturbed matrix differs from that of the original matrix if and only if the eigenvalues of the perturbing matrix are above a certain critical threshold. Square root decay of the eigenvalue density at the edge is sufficient to ensure that this threshold is finite. This critical threshold is intimately related to the same aforementioned integral transforms and our proof techniques bring this connection and the origin of the phase transition into focus. Consequently, our results extend the class of 'spiked' random matrix models about which such predictions (called the BBP phase transition) can be made well beyond the Wigner, Wishart and Jacobi random ensembles found in the literature. We examine the impact of this eigenvalue phase transition on the associated eigenvectors and observe an analogous phase transition in the eigenvectors. Various extensions of our results to the problem of non-extreme eigenvalues are discussed.

Introduction

Let X n be an n×n symmetric (or Hermitian) matrix with eigenvalues λ 1 (X n ), . . . , λ n (X n ) and P n be an n × n symmetric (or Hermitian) matrix with rank r ≤ n and non-zero eigenvalues θ 1 , . . . , θ r . A fundamental question in matrix analysis is the following [START_REF] Bunch | Rank-one modification of the symmetric eigenproblem[END_REF][START_REF] Arbenz | Restricted rank modification of the symmetric eigenvalue problem: theoretical considerations[END_REF]: How are the eigenvalues and eigenvectors of X n + P n related to the eigenvalues and eigenvectors of X n and P n ? When X n and P n are diagonalized by the same eigenvectors, we have λ i (X n + P n ) = λ j (X n )+λ k (P n ) for appropriate choice of indices i, j, k ∈ {1, . . . , n}. In the general setting, however, the answer is complicated by the fact that the eigenvalues and eigenvectors of their sum depend on the relationship between the eigenspaces of the individual matrices.

In this scenario, one can use Weyl's interlacing inequalities and Horn inequalities [START_REF] Horn | Matrix analysis[END_REF] to obtain coarse bounds for the eigenvalues of the sum in terms of the eigenvalues of X n . When the norm of P n is small relative to the norm of X n , tools from perturbation theory (see [START_REF] Horn | Matrix analysis[END_REF]Chapter 6] or [START_REF] Stewart | Matrix perturbation theory[END_REF]) can be employed to improve the characterization of the bounded set in which the eigenvalues of the sum must lie. Exploiting any special structure in the matrices allows us to refine these bounds [START_REF] Ipsen | Refined perturbation bounds for eigenvalues of Hermitian and non-Hermitian matrices[END_REF] but this is pretty much as far as the theory goes. Instead of exact answers we must resort to a system of coupled inequalities. Describing the behavior of the eigenvectors of the sum is even more complicated.

Surprisingly, adding some randomness to the eigenspaces permits further analytical progress. Specifically, if the eigenspaces are assumed to be "in generic position with respect to each other", then in place of eigenvalue bounds we have simple, exact answers that are to be interpreted probabilistically. These results bring into focus a phase transition phenomenon of the kind illustrated in Figure 1 for the eigenvalues and eigenvectors of X n + P n and X n × (I n + P n ). A precise statement of the results may be found in Section 2.

Examining the structure of the analytical expression for the critical values θ c and ρ in Figure 1 reveals a common underlying theme in the additive and multiplicative perturbation settings. The critical values θ c and ρ in Figure 1 are related to integral transforms of the limiting eigenvalue distribution µ X of X n . It turns out that the integral transforms that emerge in the respective additive and multiplicative cases are deeply related to very well known objects in free probability theory [START_REF] Voiculescu | Free random variables, volume 1 of CRM Monograph Series[END_REF][START_REF] Hiai | The semicircle law, free random variables and entropy[END_REF][START_REF] Anderson | An Introduction to Random Matrices[END_REF] that linearize free additive and multiplicative convolutions respectively. In a forthcoming paper [START_REF] Benaych-Georges | The extreme singular values and singular vectors of finite, low rank perturbations of large random rectangular matrices[END_REF], we consider the analogue of the problem for the extreme singular values of finite rank deformations of rectangular random matrices. There too, a phase transition occurs at a threshold determined by an integral transform which plays an analogous role in the computation of the rectangular additive free convolution [START_REF] Benaych-Georges | Rectangular random matrices, related convolution[END_REF][START_REF] Benaych-Georges | On a surprising relation between the Marchenko-Pastur law, rectangular and square free convolutions[END_REF][START_REF] Benaych-Georges | Rectangular R-transform at the limit of rectangular spherical integrals[END_REF]. The emergence of these transforms in the context of the study of the extreme or isolated eigenvalue behavior should be of independent interest to free probabilists. In doing so, we extend the results found in the literature about the so-called BBP phase transition (named after Baik, Ben Arous, Péché because of their seminal paper [START_REF] Baik | Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices[END_REF]) for the eigenvalue phase transition in such finite, low rank perturbation models well beyond the Wigner [START_REF] Péché | The largest eigenvalue of small rank perturbations of Hermitian random matrices[END_REF][START_REF] Hoyle | Statistical mechanics of learning multiple orthogonal signals: asymptotic theory and fluctuation effects[END_REF][START_REF] Péché | The largest eigenvalue of rank one deformation of large Wigner matrices[END_REF][START_REF] Capitaine | The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations[END_REF][START_REF] Bassler | Eigenvalue separation in some random matrix models[END_REF], Wishart [START_REF] Baik | Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices[END_REF][START_REF] Baik | Eigenvalues of large sample covariance matrices of spiked population models[END_REF][START_REF] Karoui | Tracy-Widom limit for the largest eigenvalue of a large class of complex sample covariance matrices[END_REF][START_REF] Paul | Asymptotics of sample eigenstructure for a large dimensional spiked covariance model[END_REF][START_REF] Nadler | Finite sample approximation results for principal component analysis: a matrix perturbation approach[END_REF] and Jacobi settings [START_REF] Nadakuditi | Fundamental limit of sample generalized eigenvalue based detection of signals in noise using relatively few signal-bearing and noise-only samples[END_REF]. In our situation, the distribution µ X in Figure 1 can be any probability measure. Consequently, the aforementioned results in the literature can be rederived rather simply using the formulas in Section 2 by substituting µ X with the semicircle measure [START_REF] Wigner | On the distribution of the roots of certain symmetric matrices[END_REF] (for Wigner matrices), the Marčenko-Pastur measure [START_REF] Marčenko | Distribution of eigenvalues in certain sets of random matrices[END_REF] (for Wishart matrices) or the free Jacobi measure (for Jacobi matrices [START_REF] Collins | Product of random projections, Jacobi ensembles and universality problems arising from free probability[END_REF]). Concrete computations are presented in Section 3.

The development of the eigenvector aspect is another contribution that we would like to highlight. Generally speaking, the eigenvector question has received less attention in random matrix theory and in free probability theory. A notable exception is the recent body of work on the eigenvectors of spiked Wishart matrices [START_REF] Paul | Asymptotics of sample eigenstructure for a large dimensional spiked covariance model[END_REF][START_REF] Hoyle | Statistical mechanics of learning multiple orthogonal signals: asymptotic theory and fluctuation effects[END_REF][START_REF] Nadler | Finite sample approximation results for principal component analysis: a matrix perturbation approach[END_REF] Assume that the limiting eigenvalue distribution of X n is µ X with largest eigenvalue b. Consider the matrix P n := θuu * with rank r = 1 and largest eigenvalue θ(> 0, say). The vector u is an n × 1 vector chosen uniformly at random from the unit n-sphere. The largest eigenvalue of X n + P n will differ from b if and only if θ is greater than some critical value θ c . In this event, the largest eigenvalue will be concentrated around ρ with high probability as in (a). The associated eigenvector u will, with high probability, lie on a cone around u as in (b). When θ ≤ θ c , a phase transition occurs so that with high probability, the largest eigenvalue of the sum will equal b as in (c) and the corresponding eigenvector will be uniformly distributed on the unit sphere as in (d).

corresponds to µ X being the Marčenko-Pastur measure. In this paper, we extend their results for multiplicative models of the kind (I + P n ) 1/2 X n (I + P n ) 1/2 to the setting where µ X is an arbitrary probability measure and obtain new results for the eigenvectors for additive models of the form X n + P n .

Our proofs rely on the derivation of master equation representations of the eigenvalues and eigenvectors of the perturbed matrix and the subsequent application of concentration inequalities for random vectors uniformly distributed on high dimensional unit spheres (such as the ones appearing in [START_REF] Guionnet | Character expansion method for the first order asymptotics of a matrix integral Probab[END_REF][START_REF] Guionnet | A Fourier view on the R-transform and related asymptotics of spherical integrals[END_REF]) to these implicit master equation representations. Consequently, our technique is simpler, more general and brings into focus the source of the phase transition phenomenon. The underlying methods can and have been adapted to study the extreme singular values and singular vectors of deformations of rectangular random matrices, as well as the fluctuations [START_REF] Benaych-Georges | Fluctuations of the extreme eigenvalues of finite rank deformations of random matrices[END_REF] and the large deviations [START_REF] Benaych-Georges | Large deviations of the extreme eigenvalues of finite rank deformations of random matrices[END_REF] of our model.

The paper is organized as follows. In Section 2, we state the main results and present the integral transforms alluded to above. Section 3 presents some examples. An outline of the proofs is presented in Section 4. Exact master equation representations of the eigenvalues and the eigenvectors of the perturbed matrices are derived in Section 5 and utilized in Section 6 to prove the main results. Technical results needed in these proofs have been relegated to the Appendix.

Main results

2.1. Definitions and hypotheses. Let X n be an n×n symmetric (or Hermitian) random matrix whose ordered eigenvalues we denote by

λ 1 (X n ) ≥ • • • ≥ λ n (X n ).
Let µ Xn be the empirical eigenvalue distribution, i.e., the probability measure defined as

µ Xn = 1 n n j=1 δ λ j (Xn) .
Assume that the probability measure µ Xn converges almost surely weakly, as n -→ ∞, to a non-random compactly supported probability measure µ X . Let a and b be, respectively, the infimum and supremum of the support of µ X . We suppose the smallest and largest eigenvalue of X n converge almost surely to a and b.

For a given r ≥ 1, let θ 1 ≥ • • • ≥ θ r be deterministic non-zero real numbers, chosen independently of n. For every n, let P n be an n × n symmetric (or Hermitian) random matrix having rank r with its r non-zero eigenvalues equal to θ 1 , . . . , θ r . Let the index s ∈ {0, . . . , r} be defined such that

θ 1 ≥ • • • ≥ θ s > 0 > θ s+1 ≥ • • • ≥ θ r .
Recall that a symmetric (or Hermitian) random matrix is said to be orthogonally invariant (or unitarily invariant) if its distribution is invariant under the action of the orthogonal (or unitary) group under conjugation.

We suppose that X n and P n are independent and that either X n or P n is orthogonally (or unitarily) invariant.

2.2. Notation. Throughout this paper, for f a function and c ∈ R, we set

f (c + ) := lim z↓c f (z) ; f (c -) := lim z↑c f (z),
we also let a.s.

-→ denote almost sure convergence. The ordered eigenvalues of an n × n Hermitian matrix M will be denoted by λ 1 (M) ≥ • • • ≥ λ n (M). Lastly, for a subspace F of a Euclidian space E and a vector x ∈ E, we denote the norm of the orthogonal projection of x onto F by x, F .

2.3.

Extreme eigenvalues and eigenvectors under additive perturbations. Consider the rank r additive perturbation of the random matrix X n given by

X n = X n + P n .
Theorem 2.1 (Eigenvalue phase transition). The extreme eigenvalues of X n exhibit the following behavior as n -→ ∞. We have that for each

1 ≤ i ≤ s, λ i ( X n ) a.s. -→      G -1 µ X (1/θ i ) if θ i > 1/G µ X (b + ), b otherwise, while for each fixed i > s, λ i ( X n ) a.s.
-→ b.

Similarly, for the smallest eigenvalues, we have that for each 0 ≤ j < r -s,

λ n-j ( X n ) a.s. -→      G -1 µ X (1/θ r-j ) if θ j < 1/G µ X (a -), a otherwise, while for each fixed j ≥ r -s, λ n-j ( X n ) a.s.
-→ a.

Here,

G µ X (z) = 1 z -t dµ X (t) for z / ∈ supp µ X ,
is the Cauchy transform of µ X , G -1 µ X (•) is its functional inverse so that 1/ ± ∞ stands for 0.

Theorem 2.2 (Norm of the eigenvector projection). Consider i 0 ∈ {1, . . . , r} such that 1/θ i 0 ∈ (G µ X (a -), G µ X (b + )). For each n, define

λ i 0 :=      λ i 0 ( X n ) if θ i 0 > 0, λ n-r+i 0 ( X n ) if θ i 0 < 0,
and let u be a unit-norm eigenvector of X n associated with the eigenvalue λ i 0 . Then we have, as n -→ ∞,

(a) | u, ker(θ i 0 I n -P n ) | 2 a.s. -→ -1 θ 2 i 0 G ′ µ X (ρ) where ρ = G -1 µ X (1/θ i 0 ) is the limit of λ i 0 ; (b) u, ⊕ i =i 0 ker(θ i I n -P n ) a.s.
-→ 0.

Theorem 2.3 (Eigenvector phase transition). When r = 1, let the sole non-zero eigenvalue of P n be denoted by θ. Suppose that

1 θ / ∈ (G µ X (a -), G µ X (b + )), and
     G ′ µ X (b + ) = -∞ if θ > 0, G ′ µ X (a -) = -∞ if θ < 0.
For each n, let u be a unit-norm eigenvector of X n associated with either the largest or smallest eigenvalue depending on whether θ > 0 or θ < 0, respectively. Then we have u, ker(θI n -P n ) a.s.

-→ 0, as n -→ ∞.

The following proposition allows to assert that in many classical matrix models, such as Wigner or Wishart matrices, the above phase transitions actually occur with a finite threshold. The proposition is phrased in terms of b, the supremum of the support of µ X , but also applies for a, the infimum of the support of µ X . The proof relies on a straightforward computation which we omit.

Proposition 2.4 (Square-root decay at edge and phase transitions). Assume that the limiting eigenvalue distribution µ X has a density f µ X with a power decay at b, i.e., that, as t → b with t < b, f µ X (t) ∼ c(b -t) α for some exponent α > -1 and some constant c. Then:

G µ X (b + ) < ∞ ⇐⇒ α > 0 and G ′ µ X (b + ) = -∞ ⇐⇒ α ≤ 1,
so that the phase transitions in Theorems 2.1 and 2.3 manifest for α = 1/2.

Remark 2.5 (Necessity of eigenvalue repulsion for the eigenvector phase transition). Under additional hypotheses on the manner in which the empirical eigenvalue distribution of X n a.s.

-→ µ X as n -→ ∞, Theorem 2.2 can be generalized to any eigenvalue with limit ρ equal either to a or b such that G ′ µ X (ρ) is finite. In the same way, Theorem 2.3 can be generalized for any value of r. The specific hypothesis has to do with requiring the spacings between the λ i (X n )'s to be more "random matrix like" and exhibit repulsion instead of being "independent sample like" with possible clumping. We plan to develop this line of inquiry in a separate paper.

Extreme eigenvalues and eigenvectors under multiplicative perturbations.

We maintain the same hypotheses as before so that the limiting probability measure µ X , the index s and the rank r matrix P n are defined as in Section 2.1. In addition, we assume that for every n, X n is a non-negative definite matrix and that the limiting probability measure µ X is not the Dirac mass at zero. Consider the rank r multiplicative perturbation of the random matrix X n given by

X n = X n × (I n + P n ).
Theorem 2.6 (Eigenvalue phase transition). The extreme eigenvalues of X n exhibit the following behavior as n -→ ∞. We have that for

1 ≤ i ≤ s, λ i ( X n ) a.s. -→      T -1 µ X (1/θ i ) if θ i > 1/T µ X (b + ), b otherwise, while for each fixed i > s, λ i ( X n ) a.s.
-→ b.

In the same way, for the smallest eigenvalues, for each 0 ≤ j < r -s,

λ n-r+j ( X n ) a.s. -→      T -1 µ X (1/θ j ) if θ j < 1/T µ X (a -), a otherwise,
while for each fixed j ≥ r -s, λ n-j ( X n ) a.s.

-→ a.

Here,

T µ X (z) = t z -t dµ X (t) for z / ∈ supp µ X , is the T-transform of µ X , T -1 µ X (•) is its functional inverse and 1/ ± ∞ stands for 0. Theorem 2.7 (Norm of eigenvector projection). Consider i 0 ∈ {1, . . . , r} such that 1/θ i 0 ∈ (T µ X (a -), T µ X (b + )). For each n, define λ i 0 :=      λ i 0 ( X n ) if θ i 0 > 0, λ n-r+i 0 ( X n ) if θ i 0 < 0,
and let u be a unit-norm eigenvector of X n associated with the eigenvalue

λ i 0 . Then we have, as n -→ ∞, a) | u, ker(θ i 0 I n -P n ) | 2 a.s. -→ -1 θ 2 i 0 ρT ′ µ X (ρ) + θ i 0 , where ρ = T -1 µ X (1/θ i 0 ) is the limit of λ i 0 ; b) u, ⊕ j =i 0 ker(θ j I n -P n ) a.s.
-→ 0.

Theorem 2.8 (Eigenvector phase transition). When r = 1, let the sole non-zero eigenvalue of P n be denoted by θ. Suppose that

1 θ / ∈ (T µ X (a -), T µ X (b + )), and
     T ′ µ X (b + ) = -∞ if θ > 0, T ′ µ X (a -) = -∞ if θ < 0.
For each n, let u be the unit-norm eigenvector of X n associated with either the largest or smallest eigenvalue depending on whether θ > 0 or θ < 0, respectively. Then, we have

u, ker(θI n -P n ) a.s. -→ 0 as n -→ ∞.
Proposition 2.9 (Square-root decay at edge and phase transitions). Assume that the limiting eigenvalue distribution µ X has a density f µ X with a power decay at b (or a or both), i.e., that, as t → b with t < b, f µ X (t) ∼ c(b -t) α for some exponent α > -1 and some constant c. Then:

T µ X (b + ) < ∞ ⇐⇒ α > 0 and T ′ µ X (b + ) = -∞ ⇐⇒ α ≤ 1
, so that the phase transitions in Theorems 2.6 and 2.8 manifest for α = 1/2. The analogue of Remark 2.5 also applies here.

Remark 2.10 (Eigenvalues and eigenvectors of a similarity transformation of X n ). Consider the matrix S n = (I n + P n ) 1/2 X n (I n + P n ) 1/2 . The matrices S n and X n = X n (I n + P n ) are related by a similarity transformation and hence share the same eigenvalues and consequently the same limiting eigenvalue behavior in Theorem 2.6. Additionally, if u i is a unit-norm eigenvector of X n then w i = (I n + P n ) 1/2 u i is an eigenvector of S n and the unit-norm eigenvector

v i = w i / w i satisfies | v, ker(θ i I n -P n ) | 2 = (θ i + 1)| u, ker(θ i I n -P n ) | 2 θ i u, ker(θ i I n -P n ) 2 + 1 .
It follows that we obtain the same phase transition behavior and that when 1

/θ i ∈ (T µ X (a -), T µ X (b + )), | v i , ker(θ i I n -P n ) | 2 a.s. -→ - θ i + 1 θ i T ′ µ X (ρ) and v i , ⊕ j =i ker(θ i I n -P n ) a.s.
-→ 0, so that the analogue of Theorems 2.7 and 2.8 for the eigenvectors of S n holds.

2.5. The Cauchy and T transforms in free probability theory.

The Cauchy transform and its relation to additive free convolution.

The Cauchy transform of a compactly supported probability measure µ on the real line is defined as:

G µ (z) = dµ(t) z -t for z / ∈ supp µ. If [a, b] denotes the convex hull of the support of µ, then G µ (a -) := lim z↑a G µ (z) and G µ (b + ) := lim z↓b G µ (z)
exist in [-∞, 0) and (0, +∞], respectively and G µ (•) realizes decreasing homeomorphisms from (-∞, a) onto (G µ (a -), 0) and from (b, +∞) onto (0, G µ (b + )). Throughout this paper, we shall denote by G -1 µ (•) the inverses of these homeomorphisms, even though G µ can also define other homeomorphisms on the holes of the support of µ.

The R-transform, defined as

R µ (z) := G -1 µ (z) -1/z
, is the analogue of the logarithm of the Fourier transform for free additive convolution. The free additive convolution of probability measures on the real line is denoted by the symbol ⊞ and can be characterized as follows.

Let A n and B n be independent n × n symmetric (or Hermitian) random matrices that are invariant, in law, by conjugation by any orthogonal (or unitary) matrix. Suppose that, as n -→ ∞, µ An -→ µ A and µ Bn -→ µ B . Then, free probability theory states that µ An+Bn -→ µ A ⊞ µ B , a probability measure which can be characterized in terms of the R-transform as

R µ A ⊞µ B (z) = R µ A (z) + R µ B (z).
The connection between free additive convolution and G -1 µ (via the R-transform) and the appearance of G -1 µ in Theorem 2.1 could be of independent interest to free probabilists.

The T -transform and its relation to multiplicative free convolution.

In the case where µ = δ 0 and the support of µ is contained in [0, +∞), one also defines its T -transform

T µ (z) = t z -t dµ(t) for z / ∈ supp µ X ,
which realizes decreasing homeomorphisms from (-∞, a) onto (T µ (a -), 0) and from (b, +∞) onto (0, T µ (b + )). Throughout this paper, we shall denote by T -1 µ the inverses of these homeomorphisms, even though T µ can also define other homeomorphisms on the holes of the support of µ.

The S-transform, defined as

S µ (z) := (1 + z)/(zT -1 µ (z))
, is the analogue of the Fourier transform for free multiplicative convolution ⊠. The free multiplicative convolution of two probability measures µ A and µ B is denoted by the symbols ⊠ and can be characterized as follows.

Let A n and B n be independent n×n symmetric (or Hermitian) positive-definite random matrices that are invariant, in law, by conjugation by any orthogonal (or unitary) matrix. Suppose that, as n -→ ∞, µ An -→ µ A and µ Bn -→ µ B . Then, free probability theory states that µ An•Bn -→ µ A ⊠ µ B , a probability measure which can be characterized in terms of the S-transform as

S µ A ⊠µ B (z) = S µ A (z)S µ B (z).
The connection between free multiplicative convolution and T -1 µ (via the S-transform) and the appearance of T -1 µ in Theorem 2.6 could be of independent interest to free probabilists.

2.6. Extensions.

Remark 2.11 (Phase transition in non-extreme eigenvalues). Theorem 2.1 can easily be adapted to describe the phase transition in the eigenvalues of X n + P n which fall in the "holes" of the support of µ X . Consider c < d such that almost surely, for n large enough, X n has no eigenvalue in the interval (c, d). It implies that G µ X induces a decreasing homeomorphism, that we shall denote by G µ X ,(c,d) , from the interval (c, d) onto the interval (G µ X (d -), G µ X (c + )). Then it can be proved that almost surely, for n large enough, X n + P n has no eigenvalue in the interval (c, d), except if some of the 1/θ i 's are in the interval (G µ X (d -), G µ X (c + )), in which case for each such index i, one eigenvalue of

X n + P n has limit G -1 µ X ,(c,d) (1/θ i ) as n -→ ∞. Remark 2.
12 (Isolated eigenvalues of X n outside the support of µ X ). Theorem 2.1 can also easily be adapted to the case where X n itself has isolated eigenvalues in the sense that some of its eigenvalues have limits out of the support of µ X . More formally, let us replace the assumption that the smallest and largest eigenvalues of X n tend to the infimum a and the supremum b of the support of µ X by the following one.

There exists some real numbers

ℓ + 1 , . . . , ℓ + p+ ∈ (b, +∞) and ℓ - 1 , . . . , ℓ - p -∈ (-∞, a) such that for all 1 ≤ j ≤ p + , λ j (X n ) a.s. -→ ℓ + j and for all 1 ≤ j ≤ p -, λ n+1-j (X n ) a.s. -→ ℓ - j . Moreover, λ 1+p + (X n ) a.s. -→ b and λ n-(1+p -) (X n ) a.s.
-→ a.

Then an attentive look at the proof of Theorem 2.1 shows that it still holds, in the following sense (we only present the point of view of the largest eigenvalues): the matrix X n still has eigenvalues tending to the ℓ + j 's, but also, for each 1

≤ i ≤ s such that θ i > 1/G µ X (b + ), one eigenvalue tending to G -1 µ X (1/θ i ),
all other largest eigenvalues tending to b. Remark 2.13 (Other perturbations of X n ). The previous remark forms the basis for an iterative application of our theorems to other perturbational models, such as X = √ X(I + P ) √ X + Q for example. Another way to deal with such perturbations is to first derive the corresponding master equations representations that describe how the eigenvalues and eigenvectors of X are related to the eigenvalues and eigenvectors of X and the perturbing matrices, along the lines of Proposition 5.1 for additive or multiplicative perturbations of Hermitian matrices.

Remark 2.14 (Random matrices with Haar-like eigenvectors). Let G be an n×m Gaussian random matrix with independent real (or complex) entries that are normally distributed with mean 0 and variance 1. Then the matrix X = GG * /m is orthogonally (or unitarily) invariant. Hence one can choose an orthonormal basis (U 1 , . . . , U n ) of eigenvectors of X such that the matrix U with columns U 1 , . . . , U n is Haar-distributed. When G is a Gaussian-like matrix, in the sense that its entries are i.i.d. with mean zero and variance one, then upon placing adequate restrictions on the higher order moments, for non-random unit norm vector x n , the vector U * x n will be close to uniformly distributed on the unit real (or complex) sphere [START_REF] Silverstein | Some limit theorems on the eigenvectors of large-dimensional sample covariance matrices[END_REF][START_REF] Silverstein | On the eigenvectors of large-dimensional sample covariance matrices[END_REF][START_REF] Silverstein | Weak convergence of random functions defined by the eigenvectors of sample covariance matrices[END_REF]. Since our proofs rely heavily on the properties of unit norm vectors uniformly distributed on the n-sphere, they could possibly be adapted to the setting where the unit norm vectors are close to uniformly distributed.

Remark 2.15 (Setting where eigenvalues of P n are not fixed). Suppose that P n is a random matrix independent of X n , with exactly r non-zero eigenvalues given by θ

(n) 1 , . . . , θ (n) r . Let θ (n) i a.s.
-→ θ i as n -→ ∞. Using [START_REF] Horn | Matrix analysis[END_REF]Cor. 6.3.8] as in Section 6.2.3, one can easily see that our results will also apply in this case.

The analogues of Remarks 2.11, 2.12, 2.14 and 2.15 for the multiplicative setting also hold here. In particular, Wishart matrices with c > 1 (cf Section 3.2) gives an illustration of the case where there is a hole in the support of µ X .

Examples

We now illustrate our results with some concrete computations. The key to applying our results lies in being able to compute the Cauchy or T transforms of the probability measure µ X and their associated functional inverses. In what follows, we focus on settings where the transforms and their inverses can be expressed in closed form. In settings where the transforms are algebraic so that they can be represented as solutions of polynomial equations, the techniques and software developed in [START_REF] Rao | The polynomial method for random matrices[END_REF] can be utilized. In more complicated settings, one will have to resort to numerical techniques.

3.1.

Additive perturbation of a Gaussian Wigner matrix. Let X n be an n × n symmetric (or Hermitian) matrix with independent, zero mean, normally distributed entries with variance σ 2 /n on the diagonal and σ 2 /(2n) on the off diagonal. It is known that the spectral measure of X n converges almost surely to the famous semi-circle distribution with density

dµ X (x) = √ 4σ 2 -x 2 2σ 2 π dx for x ∈ [-2σ, 2σ].
It is known that the extreme eigenvalues converge almost surely to the endpoints of the support [START_REF] Anderson | An Introduction to Random Matrices[END_REF]. Associated with the spectral measure, we have

G µ X (z) = z -sgn(z) √ z 2 -4σ 2 2σ 2 , for z ∈ (-∞, -2σ) ∪ (2σ, +∞), G µ X (±2σ) = ±σ and G -1 µ X (1/θ) = θ + σ 2 θ . Thus for a P n with r non-zero eigenvalues θ 1 ≥ • • • ≥ θ s > 0 > θ s+1 ≥ • • • ≥ θ r , by Theorem 2.1, we have for 1 ≤ i ≤ s, λ i (X n + P n ) a.s. -→ θ i + σ 2 θ i if θ i > σ 2σ otherwise,
as n -→ ∞. This result has already been established in [START_REF] Péché | The largest eigenvalue of rank one deformation of large Wigner matrices[END_REF] for the symmetric case and in [START_REF] Péché | The largest eigenvalue of small rank perturbations of Hermitian random matrices[END_REF] for the Hermitian case. Remark 2.14 explains why our results should hold for Wigner matrices of the sort considered in [START_REF] Péché | The largest eigenvalue of small rank perturbations of Hermitian random matrices[END_REF][START_REF] Péché | The largest eigenvalue of rank one deformation of large Wigner matrices[END_REF].

In the setting where r = 1 and P = θ uu * , let u be a unit-norm eigenvector of X n + P n associated with its largest eigenvalue. By Theorems 2.2 and 2.3, we have

| u, u | 2 a.s. -→ 1 -σ 2 θ 2 if θ ≥ σ, 0 if θ < σ.

3.2.

Multiplicative perturbation of a random Wishart matrix. Let G n be an n×m real (or complex) matrix with independent, zero mean, normally distributed entries with variance 1. Let X n = G n G * n /m. It is known [START_REF] Marčenko | Distribution of eigenvalues in certain sets of random matrices[END_REF] that, as n, m -→ ∞ with n/m → c > 0, the spectral measure of X n converges almost surely to the famous Marčenko-Pastur distribution with density

dµ X (x) := 1 2πcx (b -x)(x -a)½ [a,b] (x)dx + max 0, 1 - 1 c δ 0 , where a = (1 - √ c) 2 and b = (1 + √ c) 2 .
It is known [START_REF] Bai | Spectral Analysis of Large Dimensional Random Matrices[END_REF] that the extreme eigenvalues converge almost surely to the endpoints of this support.

Associated with this spectral measure, we have

T µ X (z) = z -c -1 -sgn(z -a) (z -a)(z -b) 2c T µ X (b + ) = 1/ √ c, T µ X (a -) = -1/ √ c and T -1 µ X (z) = (z + 1)(cz + 1) z .
When c > 1, there is an atom at zero so that the smallest eigenvalue of X n is identically zero. For simplicity, let us consider the setting when c < 1 so that the extreme eigenvalues of X n converge almost surely to a and b. Thus for P n with r non-zero eigenvalues

θ 1 ≥ • • • ≥ θ s > 0 > θ s+1 ≥ • • • ≥ θ r , with l i := θ i + 1, for c < 1, by Theorem 2.6, we have for 1 ≤ i ≤ s, λ i (X n (I n + P n )) a.s. -→ l i 1 + c l i -1 if |l i -1| > √ c b otherwise,
as n -→ ∞. An analogous result for the smallest eigenvalue may be similarly derived by making the appropriate substitution for a in Theorem 2.6. Consider the matrix S n = (I n + P n ) 1/2 X n (I n + P n ) 1/2 . The matrix S n may be interpreted as a Wishart distributed sample covariance matrix with "spiked" covariance I n + P n . By Remark 2.10, the above result applies for the eigenvalues of S n as well. This result for the largest eigenvalue of spiked sample covariance matrices was established in [START_REF] Baik | Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices[END_REF][START_REF] Paul | Asymptotics of sample eigenstructure for a large dimensional spiked covariance model[END_REF] and for the extreme eigenvalues in [START_REF] Baik | Eigenvalues of large sample covariance matrices of spiked population models[END_REF].

In the setting where r = 1 and P = θ uu * , let l = θ + 1 and let u be a unit-norm eigenvector of X n (I + P n ) associated with its largest (or smallest, depending on whether l > 1 or l < 1) eigenvalue. By Theorem 2.8, we have

| u, u | 2 a.s.
-→

(l-1) 2 -c (l-1)[c(l+1)+l-1] if |l -1| ≥ √ c, 0 if |l -1| < √ c.
Let v be a unit eigenvector of S n = (I n +P n ) 1/2 X n (I n +P n ) 1/2 associated with its largest (or smallest, depending on whether l > 1 or l < 1) eigenvalue. Then, by Theorem 2.8 and Remark 2.10, we have

| v, u | 2 a.s. -→    1-c (l-1) 2 1+ c l-1 if |l -1| ≥ √ c, 0 if |l -1| < √ c.
The result has been established in [START_REF] Paul | Asymptotics of sample eigenstructure for a large dimensional spiked covariance model[END_REF] for the eigenvector associated with the largest eigenvalue. We generalize it to the eigenvector associated with the smallest one.

We note that symmetry considerations imply that when X is a Wigner matrix then -X is a Wigner matrix as well. Thus an analytical characterization of the largest eigenvalue of a Wigner matrix directly yields a characterization of the smallest eigenvalue as well. This trick cannot be applied for Wishart matrices since Wishart matrices do not exhibit the symmetries of Wigner matrices. Consequently, the smallest and largest eigenvalues and their associated eigenvectors of Wishart matrices have to be treated separately. Our results facilitate such a characterization.

Outline of the proofs

We now provide an outline of the proofs. We focus on Theorems 2.1, 2.2 and 2.3, which describe the phase transition in the extreme eigenvalues and associated eigenvectors of X +P (the index n in X n and P n has been suppressed for brevity). An analogous argument applies for the multiplicative perturbation setting.

Consider the setting where r = 1, so that P = θ uu * , with u being a unit norm column vector. Since either X or P is assumed to be invariant, in law, under orthogonal (or unitary) conjugation, one can, without loss of generality, suppose that X = diag(λ 1 , . . . , λ n ) and that u is uniformly distributed on the unit n-sphere.

4.1.

Largest eigenvalue phase transition. The eigenvalues of X + P are the solutions of the equation det(zI -(X + P )) = 0.

Equivalently, for z so that zI -X is invertible, we have

zI -(X + P ) = (zI -X) • (I -(zI -X) -1 P ), so that det(zI -(X + P )) = det(zI -X) • det(I -(zI -X) -1 P ).
Consequently, a simple argument reveals that the z is an eigenvalue of X + P and not an eigenvalue of X if and only if 1 is an eigenvalue of the matrix (zI -X) -1 P . But (zI -X) -1 P = (zI -X) -1 θ uu * has rank one, so its only non-zero eigenvalue will equal its trace, which in turn is equal to θG µn (z), where µ n is a "weighted" spectral measure of X, defined by

µ n = n k=1 |u k | 2 δ λ k (the u k 's are the coordinates of u).
Thus any z outside the spectrum of X is an eigenvalue of X + P if and only if

n k=1 |u k | 2 z -λ k =: G µn (z) = 1 θ . (1)
Equation ( 1) describes the relationship between the eigenvalues of X + P and the eigenvalues of X and the dependence on the coordinates of the vector u (via the measure µ n ). This is where randomization simplifies analysis. Since u is a random vector with uniform distribution on the unit n-sphere, we have that for large n, |u k | 2 ≈ 1 n with high probability. Consequently, we have µ n ≈ µ X so that G µn (z) ≈ G µ X (z). Inverting equation [START_REF] Anderson | An Introduction to Random Matrices[END_REF] after substituting these approximations yields the location of the largest eigenvalue to be G -1 µ X (1/θ) as in Theorem 2.1. The phase transition for the extreme eigenvalues emerges because under our assumption that the limiting probability measure µ X is compactly supported on [a, b], the Cauchy transform G µ X is defined outside [a, b] and unlike what happens for G µn , we do not always have G µ X (b + ) = +∞. Consequently, when 1/θ < G µ X (b + ), we have that λ 1 ( X) ≈ G -1 µ X (1/θ) as before. However, when 1/θ ≥ G µ X (b + ), the phase transition manifests and

λ 1 ( X) ≈ λ 1 (X) = b.
An extension of these arguments for fixed r > 1 yields the general result and constitutes the most transparent justification, as sought by the authors in [START_REF] Baik | Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices[END_REF], for the emergence of this phase transition phenomenon in such perturbed random matrix models. We rely on concentration inequalities to make the arguments rigorous.

Eigenvectors phase transition.

Let u be a unit eigenvector of X + P associated with the eigenvalue z that satisfies [START_REF] Anderson | An Introduction to Random Matrices[END_REF]. From the relationship (X + P ) u = z u, we deduce that, for P = θ uu * , (zI -X) u = P u = θuu * u = (θu * u).u (because u * u is a scalar), implying that u is proportional to (zI -X) -1 u.

Since u has unit-norm,

u = (zI -X) -1 u u * (zI -X) -2 u (2)
and

| u, ker(θI -P ) | 2 = |u * u| 2 = (u * (zI -X) -1 u) 2 u * (zI -X) -2 u = G µn (z) 2 dµn(t) (z-t) 2 = 1 θ 2 dµn(t) (z-t) 2 . ( 3
)
Equation ( 2) describes the relationship between the eigenvectors of X + P and the eigenvalues of X and the dependence on the coordinates of the vector u (via the measure µ n ).

Here too, randomization simplifies analysis since for large n, we have

µ n ≈ µ X and z ≈ ρ. Consequently, dµ n (t) (z -t) 2 ≈ dµ X (t) (ρ -t) 2 = -G ′ µ X (ρ), so that when 1/θ < G µ X (b + ), which implies that ρ > b, we have | u, ker(θI -P ) | 2 a.s. -→ 1 θ 2 dµ X (t) (ρ-t) 2 = -1 θ 2 G ′ µ X (ρ) > 0,
whereas when 1/θ ≥ G µ X (b + ) and G µ X has infinite derivative at ρ = b, we have u, ker(θI -P ) a.s.

-→ 0.

An extension of these arguments for fixed r > 1 yields the general result and brings into focus the connection between the eigenvalue phase transition and the associated eigenvector phase transition. As before, concentration inequalities allow us to make these arguments rigorous.

The exact master equations for the perturbed eigenvalues and eigenvectors

In this section, we provide the r-dimensional analogues of the master equations ( 1) and (2) employed in our outline of the proof. Proposition 5.1. Let us fix some positive integers 1 ≤ r ≤ n. Let X n = diag(λ 1 , . . . , λ n ) be a diagonal n × n matrix and P n = U n,r ΘU * n,r , with Θ = diag(θ 1 , . . . , θ r ) an r × r diagonal matrix and U n,r an n × r matrix with orthonormal columns, i.e., U * n,r U n,r = I r ). a) Then any z / ∈ {λ 1 , . . . , λ n } is an eigenvalue of X n := X n + P n if and only if the r × r matrix

M n (z) := I r -U * n,r (zI n -X n ) -1 U n,r Θ (4)
the θ i 's are pairwise distinct, the multiplicities of the isolated eigenvalues are all equal to one.

6.1.

A continuity lemma for the zeros of certain analytic functions. We now prove a continuity lemma that will be used in the proof of Theorem 2.1. We note that nothing in its hypotheses is random. As hinted earlier, we will invoke it to localize the extreme eigenvalues of X n .

a) G(z) ∈ R ⇐⇒ z ∈ R, b) for all z ∈ R\[a, b], G ′ (z) < 0, c) G(z) -→ 0 as |z| -→ ∞. Let us define, for z ∈ C\[a, b], the r × r matrix M G (z) = diag(1 -θ 1 G(z), . . . , 1 -θ r G(z)), (8)
and denote by

z 1 > • • • > z p the z's such that M G (z) is singular, where p ∈ {0, . . . , r} is identically equal to the number of i's such that G(a -) < 1/θ i < G(b + ).
Let us also consider two sequences a n , b n with respective limits a, b and, for each n, a function M n (z), defined on z ∈ C\[a n , b n ], with values in the set of r × r complex matrices such that the entries of M n (z) are analytic functions of z. We suppose that d) for all n, for all z ∈ C\R, the matrix M n (z) is invertible,

e) M n (z) converges, as n -→ ∞, to the function M G (z), uniformly on {z ∈ C ; d(z, [a, b]) ≥
η}, for all η > 0.

Then (i) there exists p real sequences z n,1 > . . . > z n,p converging respectively to z 1 , . . . , z p such that for any ε > 0 small enough, for n large enough, the z'

s in R\[a -ε, b + ε] such that M n (z) is singular are exactly z n,1 , . . . , z n,p , (ii) for n large enough, for each i, M n (z n,i ) has rank r -1.
Proof. Note firstly that the z's such that M G (z) is singular are the z's such that for a certain j ∈ {1, . . . , r},

1 -θ j G(z) = 0. (9)
Since the θ j 's are pairwise distinct, for any z, there cannot exist more than one j ∈ {1, . . . , r} such that (9) holds. As a consequence, for all z, the rank of M G (z) is either r or r -1. Since the set of matrices with rank at least r -1 is open in the set of r × r matrices, once (i) will be proved, (ii) will follow.

Let us now prove (i). Note firstly that by c), there exists R > max{|a|, |b|} such that for z such that |z| ≥ R, |G(z)| ≤ min i

1 2|θ i | . For any such z, | det M G (z)| > 2 -r
. By e), it follows that for n large enough, the z's such that M n (z) is singular satisfy |z| > R. By d), it even follows that the z's such that M n (z) is singular satisfy

z ∈ [-R, R].
c,d = 1 2iπ γ ∂ z det M G (z) det M G (z) dz = lim n→∞ 1 2iπ γ ∂ z det M n (z) det M n (z) dz,
the last equality following from e). It follows that for n large enough, Card c,d (n) = Card c,d (note that since Card c,d = 0 or 1, no ambiguity due to the orders of the zeros has to be taken into account here).

6.2. Proof of Theorem 2.1.

6.2.1.

First step: consequences of Weyl's interlacing inequalities. Note that Weyl's interlacing inequalities imply that for all 1 ≤ i ≤ n,

λ i+(r-s) (X n ) ≤ λ i ( X n ) ≤ λ i-s (X n ), (10)
where we employ the convention that λ k (X n ) = -∞ is k > n and +∞ if k ≤ 0. It follows that the empirical spectral measure of X n a.s.

-→ µ X because the empirical spectral measure of X n does as well.

Since a and b belong to the support of µ X , we have, for all i ≥ 1 fixed, lim inf

n→∞ λ i (X n ) ≥ b and lim sup n→∞ lim sup n→∞ λ n+1-i (X n ) ≤ a.
By the hypotheses that

λ 1 (X n ) a.s. -→ b and λ n (X n ) a.s.
-→ a, it follows that for all i ≥ 1 fixed, λ i (X n ) a.s.

-→ b and λ n+1-i (X n ) a.s.

-→ a.

By [START_REF] Benaych-Georges | Fluctuations of the extreme eigenvalues of finite rank deformations of random matrices[END_REF], we deduce both following relation ( 11) and ( 12): for all i ≥ 1 fixed, we have lim inf

n→∞ λ i ( X n ) ≥ b and lim sup n→∞ λ n+1-i ( X n ) ≤ a (11)
and for all i > s (resp. i ≥ r -s) fixed, we have

λ i ( X n ) a.s. -→ b (resp. λ n-i ( X n ) a.s. -→ a). (12)
Equations ( 11) and ( 12) are the first step in the proof of Theorem 2.1. They state that any extreme eigenvalue of X n which does not tend to a limit in R\[a, b] tends either to a or b. Let us now prove the crux of the theorem related to the isolated eigenvalues.

6.2.2. Isolated eigenvalues in the setting where θ 1 , . . . , θ r are pairwise distinct. In this section, we assume that the eigenvalues θ 1 , . . . , θ r of the perturbing matrix P n to be pairwise distinct. In the next section, we shall remove this hypothesis by an approximation process.

For a momentarily fixed n, let the eigenvalues of X n be denoted by λ 1 ≥ . . . ≥ λ n . Consider orthogonal (or unitary) n × n matrices U X , U P that diagonalize X n and P n , respectively, such that

X n = U X diag(λ 1 , . . . , λ n )U * X , P n = U P diag(θ 1 , . . . , θ r , 0, . . . , 0)U * P .
The spectrum of X n + P n is identical to the spectrum of the matrix

diag(λ 1 , . . . , λ n ) + U * X U P denoted by Un diag(θ 1 , . . . , θ r , 0, . . . , 0)U * P U X . (13)
Since we have assumed that X n or P n is orthogonally (or unitarily) invariant and that they are independent, this implies that U n is a Haar-distributed orthogonal (or unitary) matrix that is also independent of (λ 1 , . . . , λ n ) (see the first paragraph of the proof of [START_REF] Hiai | The semicircle law, free random variables and entropy[END_REF]Th. 4.3.5] for additional details).

Recall that the largest eigenvalue λ 1 (X n ) a.s.

-→ b, while the smallest eigenvalue λ n (X n ) a.s.

-→ a. Let us now consider the eigenvalues of X n which are out of [λ n (X n ), λ 1 (X n )]. By Proposition 5.1-a) and an application of the identity in Proposition 5.1-b) these eigenvalues are precisely the numbers z / ∈

[λ n (X n ), λ 1 (X n )] such that the r × r matrix M n (z) := I r -[θ j G µ (n) i,j (z)] r i,j=1 (14)
is singular. Recall that in [START_REF] Capitaine | The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations[END_REF], G µ (n) i,j (z), for i, j = 1, . . . , r is the Cauchy transform of the random complex measure defined by

µ (n) i,j = n m=1 u (n) k,i u (n) k,j δ λ k (Xn) , (15)
where u k,i and u k,j are the (k, i)-th and (k, j)-th entries of the orthogonal (or unitary) matrix U n in (13) and λ k is the k-th largest eigenvalue of X n as in the first term in [START_REF] Bunch | Rank-one modification of the symmetric eigenproblem[END_REF].

By Proposition 9.3, we have that

µ (n) i,j a.s. -→ µ X for i = j, δ 0 otherwise. ( 16
)
Thus we have

M n (z) a.s. -→ M Gµ X (z) := diag(1 -θ 1 G µ X (z), . . . , 1 -θ r G µ X (z)), (17)
and by Lemma 9.1, this convergence is uniform on {z ∈ C ; d(z, [a, b]) ≥ η > 0} for each η > 0.

We now note that Hypotheses a), b) and c) of Lemma 6.1 are satisfied and follow from the definition of the Cauchy transform G µ X . Hypothesis d) of Lemma 6.1 follows from the fact that X n is Hermitian while hypothesis e) has been established in [START_REF] Karoui | Tracy-Widom limit for the largest eigenvalue of a large class of complex sample covariance matrices[END_REF].

By the triangular inequality, almost surely, for n large enough,

|λ i (X n + P n ) -ρ θ i | ≤ 3ε, so that λ i (X n + P n ) a.s.
-→ ρ θ i .

Proof of Theorem 2.2

As in Section 6.2.2, let

X n = U X diag(λ 1 , . . . , λ n )U * X , P n = U P diag(θ 1 , . . . , θ r , 0, . . . , 0)U * P .
The eigenvectors of X n + P n , are precisely U X times the eigenvectors of diag(λ 1 , . . . , λ n ) + U * X U P =Un diag(θ 1 , . . . , θ r , 0, . . . , 0)U * P U X .

Consequently, we have proved Theorem 2.2 by proving the result in the setting where X n = diag(λ 1 , . . . , λ n ) and P n = U n diag(θ 1 , . . . , θ r , 0, . . . , 0)U * n , where U n is a Haardistributed orthogonal (or unitary) matrix.

As before, we denote the entries of U n by [u

(n) i,j ] n i,j=1
. Let the columns of U n be denoted by u 1 , . . . , u n and the n × r matrix whose columns are respectively u 1 , . . . , u r by U n,r . Note that the u i 's, as u, depend on n, hence should be denoted for example by u (n) i and u (n) . The same, of course, is true for the λ i 's and the λ i 's. To simplify our notation, we shall suppress the n in the superscript. Let r 0 be the number of i's such that θ i = θ i 0 . Up to a reindexing of the θ i 's (which are then no longer decreasing -this fact does not affect our proof), one can suppose that i 0 = 1, θ 1 = • • • = θ r 0 . This choice implies that, for each n, ker(θ 1 I n -P n ) is the linear span of the r 0 first columns u 1 , . . . , u r 0 of U n . By construction, these columns are orthonormal. Hence, we will have proved Theorem 2.2 if we can prove that as n -→ ∞,

r 0 i=1 | u i , u | 2 a.s. -→ -1 θ 2 i 0 G ′ µ X (ρ) = 1 θ 2 i 0 dµ X (t) (ρ-t) 2 (18)
and

r i=r 0 +1 | u i , u | 2 a.s. -→ 0. ( 19
)
As before, for every n and for all z outside the spectrum of X n , define the r × r random matrix:

M n (z) := I r -[θ j G µ (n) i,j (z)] r i,j=1 ,
where, for all i, j = 1, . . . , r, µ

i,j is the random complex measure defined by [START_REF] Collins | Product of random projections, Jacobi ensembles and universality problems arising from free probability[END_REF]. In [START_REF] Karoui | Tracy-Widom limit for the largest eigenvalue of a large class of complex sample covariance matrices[END_REF] we established that:

M n (•) a.s. -→ M Gµ X (•) := diag(1 -θ 1 G µ X (•), . . . , 1 -θ r G µ X (•)) (20)
uniformly on {z ∈ C ; d(z, [a, b]) ≥ η} for all η > 0.

We have established in Theorem 2.1 that because

θ i 0 > 1/G µ X (b + ), λ i 0 a.s. -→ ρ = G -1 µ X (1/θ i 0 ) / ∈ [a, b] as n -→ ∞.
It follows that:

M n (z n ) a.s.
-→ diag(0, . . . , 0

r 0 zeros , 1 - θ r 0 +1 θ i 0 , . . . , 1 - θ r θ i 0 ). (21)
Proposition 5.1 a) states that for n large enough so that such that λ i 0 is not an eigenvalue of X n , the r × 1 vector

U * n,r u =   u 1 , u . . . u r , u   is in the kernel of the r × r matrix M n (z n ) with ||U * n,r u|| 2 ≤ 1.
Thus by [START_REF] Guionnet | A Fourier view on the R-transform and related asymptotics of spherical integrals[END_REF], any limit point of U * n,r u is in the kernel of the matrix on the right hand side of (21), i.e. has its r -r 0 last coordinates equal to zero.

Thus [START_REF] Guionnet | Character expansion method for the first order asymptotics of a matrix integral Probab[END_REF] holds and we have proved Theorem 2.2-b). We now establish [START_REF] Péché | The largest eigenvalue of rank one deformation of large Wigner matrices[END_REF]. By [START_REF] Bassler | Eigenvalue separation in some random matrix models[END_REF], one has that for all n, the eigenvector u of X n associated with the eigenvalue λ i 0 can be expressed as:

u = ( λ i 0 I n -X n ) -1 U n,r diag(θ 1 , . . . , θ r )U * n,r u = ( λ i 0 I n -X n ) -1 r j=1 θ j u j , u u j , = ( λ i 0 I n -X n ) -1 r 0 j=1 θ j u j , u u j denoted by u ′ + ( λ i 0 I n -X n ) -1 r j=r 1 +1
θ j u j , u u j denoted by u ′′ .

As λ i 0 a.s.

-→ ρ / ∈ [a, b], the sequence ( λ i 0 I n -X n ) -1 is bounded in operator norm so that by [START_REF] Guionnet | Character expansion method for the first order asymptotics of a matrix integral Probab[END_REF], u ′′ a.s.

-→ 0. Since u = 1, this implies that u ′ a.s.

-→ 1.

Since we assumed that θ i 0 = θ 1 = • • • = θ r 0 , we must have that:

u ′ 2 = θ 2 i 0 r 1 i,j=1 u i , u u j , u u * i (z n I n -X n ) -2 u j = 1 (zn-t) 2 dµ (n) i,j (t)
.

By Proposition 9.3, we have that for all i = j, µ

(n) i,j a.s.

-→ δ 0 while for all i, µ

(n) i,i a.s.
-→ µ X . Thus, since we have that z n a.s.

-→ ρ / ∈ [a, b], we have that for all i, j = 1, . . . , r 0 , dµ

(n) i,j (t) (z n -t) 2 a.s. -→ ½ i=j dµ(t) (ρ -t) 2 .
Combining the relationship in [START_REF] Horn | Matrix analysis[END_REF] with the fact that u ′ a.s.

-→ 1, yields (18) and we have proved Theorem 2.2-a).

Proof of Theorem 2.3

Let us assume that θ > 0. The proof supplied below can be easily ported to the setting where θ < 0.

We first note that the G

′ µ X (b + ) = -∞, implies that dµ X (t) (b-t) 2 = -G µ X (b + ) = +∞.
We adopt the strategy employed in proving Theorem 2.2, and note that it suffices to prove the result in the setting where X n = diag(λ 1 , . . . , λ n ) and P n = θuu * , where u is a n × 1 column vector uniformly distributed on the unit real (or complex) n-sphere.

We denote the coordinates of u by u

(n) 1 , . . . , u (n) n
and define, for each n, the random probability measure

µ (n) X = n k=1 |u (n) k | 2 δ λ k .
The r = 1 setting of Proposition 5.1-b) states that the eigenvalues of X n + P n which are not eigenvalue of X n are the solutions of

G µ (n) X (z) = 1 θ . Since G µ (n) X (z) decreases from +∞ to 0 for increasing values of z ∈ (λ 1 , +∞), we have that λ 1 (X n + P n ) =: λ 1 > λ 1 .
Reproducing the arguments leading to (3) in Section (4.2), yields the relationship:

| u, ker(θI n -P n ) | 2 = 1 θ 2 dµ (n) (t) ( λ 1 -t) 2 . ( 23
)
Thus, proving that:

dµ (n) (t) ( λ 1 -t) 2 a.s.
-→ +∞ as n -→ ∞ will yield the desired result.

By hypothesis, we have that 1 n n i=1 δ λ i a.s.

-→ µ X .

By Theorem 2.1, we have that λ 1 a.s.

-→ b so that

1 n n k=1 δ λ k +b-λ 1 a.s.
-→ µ X .

Hence, by [START_REF] Ledoux | The concentration of measure phenomenon[END_REF],

μ(n) := n k=1 |u (n) k | 2 δ λ k +b-λ 1 a.s.
-→ µ X .

This implies that almost surely,

lim inf n→∞ dµ (n) (t) ( λ 1 -t) 2 = lim inf n→∞ dμ (n) (t) (b -t) 2 ≥ dµ X (t) (b -t) 2 = +∞,
so that by [START_REF] Hoyle | Statistical mechanics of learning multiple orthogonal signals: asymptotic theory and fluctuation effects[END_REF], u, ker(θI n -P n ) | 2 a.s.

-→ 0 thereby proving Theorem 2.3.

We omit the details of the proofs of Theorems 2.6-2.8, since these are straightforward adaptations of the proofs of Theorems 2.1-Theorem 2.3 that can obtained by following the prescription in Proposition 5.1-c). 9. Appendix: convergence of weighted spectral measures 9.1. A few facts about the weak convergence of complex measures. Recall that a sequence (µ n ) of complex measures on R is said to converge weakly to a complex measure µ on R if, for any continuous bounded function f on R,

f (t)dµ n (t) -→ n→∞ f (t)dµ(t). ( 24
)
We now establish a lemma on the weak convergence of complex measures that will be useful in proving Proposition 9.3. We note that the counterpart of this lemma for probability measures is well known. We did not find any reference in standard literature to the "complex measures version" stated next, so we provide a short proof.

Recall that a sequence (µ n ) of complex measures on R is said to be tight if which can be made arbitrarily small by appropriately choosing g. The tightness hypothesis ensures that such a g can always be found. This proves that (µ n ) converges weakly to µ.

The uniform convergence follows from a straightforward application of Ascoli's Theorem. 9.2. Convergence of weighted spectral measures.

Lemma 9.2. For each n, let u (n) = (u 1 , . . . , u n ), v (n) = (v 1 , . . . , v n ) be the first two rows of a Haar distributed random orthogonal (or unitary) matrix. Let x (n) = (x 1 , . . . , x n ) be a set of real-valued random numbers 1 independent of (u (n) , v (n) ). We suppose that sup n,k |x k | < ∞ almost surely. a) Then as n -→ ∞,

u 1 v 1 x 1 + u 2 v 2 x 2 + • • • + u n v n x n a.s.
-→ 0.

b) Suppose that -→ l.

Proof. We prove a) by conditioning on the values of the x's. As a consequence, we can suppose the x (n) 's to be non-random. Let us define the random variable

Z n = u 1 v 1 x 1 + • • • + u n v n x n .
To establish a), it suffices to prove that E[Z 4 n ] = O(n -2 ). We have

E[Z 4 n ] = n i,j,k,l=1 x i x j x k x l E[u i u j u k u l v i v j v k v l ].
Since (u 1 , . . . , u n ) and (v 1 , . . . , v n ) are the first two rows of a Haar distributed random orthogonal (or unitary) matrix, we have that E[u i u j u k u l v i v j v k v l ] = 0 whenever one of the indices i, j, k, l, is different from the others [START_REF] Collins | Integration with respect to the Haar measure on unitary, orthogonal and symplectic group[END_REF]. It follows that

E[Z 4 n ] ≤ 3 i,j x 2 i x 2 j E u 2 i u 2 j v 2 i v 2 j ≤ 3 i,j x 2 i x 2 j E u 8 i E u 8 j E v 8 i E v 8 j 1 4 =E[u 8 1 ]
.

Since, by [START_REF] Collins | Integration with respect to the Haar measure on unitary, orthogonal and symplectic group[END_REF], E[u -→ 0.

To prove b), we employ a different strategy. In the setting where (u 1 , . . . , u n ) is the first row of a Haar distributed orthogonal matrix, the result follows from the application of a well-known concentration of measure result [START_REF] Ledoux | The concentration of measure phenomenon[END_REF]Th. 2.3 and Prop. 1.8] which states that there are positive constants C, c such that for n large enough, for any 1-Lipschitz function f n on the unit sphere of R n , for all ε > 0,

P {|f n (u 1 , . . . , u n ) -E[f n (u 1 , . . . , u n )]| ≥ ε} ≤ Ce -cnε 2 .
This implies that if E[f n (u 1 , . . . , u n )] converges, as n -→ ∞, to a finite limit, then f n (u 1 , . . . , u n ) converges almost surely to the same limit. In the complex setting, we note that a uniformly distributed random vector on the unity sphere of C n is a uniformly distributed random vector on the unit sphere of R 2n so that we have proved the results in the unitary setting as well. Proposition 9.3. Let, for each n, u (n) = (u 1 , . . . , u n ), v (n) = (v 1 , . . . , v n ) be the two first columns of a uniform random orthogonal (resp. unitary) matrix. Let also λ (n) = (λ 1 , . . . , λ n ) be a random family of real numbers 2 independent of (u (n) , v (n) ) such that almost surely, sup n,k |λ k | < ∞. We suppose that there exists a deterministic probability measure µ on R such that almost surely, as n -→ 0, 1 n n k=1 δ λ k converges weakly to µ. 2 As in Lemma 9.2, we have suppressed the index n for notational brevity. The set of continuous functions on the real line tending to zero at infinity admits a countable dense subset, so it suffices to prove that for any fixed such function f , the convergences of ( 25) and ( 26) hold almost surely when applied to f . This follows easily from Lemma 9.2.

  which

Figure 1 .

 1 Figure1. Assume that the limiting eigenvalue distribution of X n is µ X with largest eigenvalue b. Consider the matrix P n := θuu * with rank r = 1 and largest eigenvalue θ(> 0, say). The vector u is an n × 1 vector chosen uniformly at random from the unit n-sphere. The largest eigenvalue of X n + P n will differ from b if and only if θ is greater than some critical value θ c . In this event, the largest eigenvalue will be concentrated around ρ with high probability as in (a). The associated eigenvector u will, with high probability, lie on a cone around u as in (b). When θ ≤ θ c , a phase transition occurs so that with high probability, the largest eigenvalue of the sum will equal b as in (c) and the corresponding eigenvector will be uniformly distributed on the unit sphere as in (d).

ForLemma 6 . 1 .

 61 z ∈ C and E a closed subset of R, set d(z, E) = min x∈E |z -x|. Let us fix a positive integer r, a family θ 1 , . . . , θ r of pairwise distinct nonzero real numbers, two real numbers a < b, an analytic function G(z) of the variable z ∈ C\[a, b] such that

  Now, to prove (i), it suffices to prove that for all c, d ∈ R\([a, b] ∪ {z 1 , . . . , z p }) such that c < d < a or b < c < d, we have that as n -→ ∞: (H) the number of z's in (c, d) such that det M n (z) = 0, denoted by Card c,d (n) tends to Card c,d , the cardinality of the i's in {1, . . . , p} such that c < z i < d. To prove (H), by additivity, one can suppose that c and d are close enough to have Card c,d = 0 or 1. Let us define γ to be the circle with diameter [c, d]. By a) and since c, d / ∈ {z 1 , . . . , z p }, det M G (•) does not vanish on γ, thus Card

Lemma 9 . 1 .

 91 n |({t ∈ R ; |t| ≥ R}) = 0. Let D be a dense subset of the set of continuous functions on R tending to zero at infinity endowed with the topology of the uniform convergence. Consider a tight sequence (µ n ) of complex measures on R such that (|µ n |(R)) is bounded and (24) holds for any function f in D. Then (µ n ) converges weakly to µ. Moreover, the convergence of (24) is uniform on any set of uniformly bounded and uniformly Lipschitz functions.Proof. Firstly, note that using the boundedness of (|µ n |(R)), one can easily extend[START_REF] Ipsen | Refined perturbation bounds for eigenvalues of Hermitian and non-Hermitian matrices[END_REF] to any continuous function tending to zero at infinity. It follows that for any continuous bounded function f and any continuous function g tending to zero at infinity, we have lim supn→∞ f d(µ -µ n ) ≤ sup n |f (1 -g)|d(|µ| + |µ n |),

8 1 ]

 1 = O(n -4 ) and we have assumed that supn,k |x k | < ∞, u 1 v 1 x 1 + • • • + u n v n x n a.s.

  Then as n -→ ∞,µ U (n) := n k=1 |u k | 2 δ λ k converges almost surely weakly to µ, (25) µ U (n) ,V (n) := n k=1 u k v k δ λ k converges almost surely weakly to 0. (26)Proof. We use Lemma 9.1. Note first that almost surely, since sup n,k |λ k | < ∞, both sequences are tight. Moreover, we have|µ U (n) ,V (n) | = n k=1 |u k v k |δ λ k ,thus, by the Cauchy-Schwartz inequality, |µ U (n) ,V (n) |(R) ≤ 1.

  1 n (x 1 + x 2 + • • • + x n ) converges almost surely to a deterministic limit l. Then |u 1 | 2 x 1 + |u 2 | 2 x 2 + • • • + |u n | 2 x n a.s.

Note that for each k, u k , v k and x k obviously depend on n. We could have represented this dependence in the subscript as u n,k or u (n) k but we choose to suppress the n for notational brevity.

F.B.G's work was partially supported by the Agence Nationale de la Recherche grant ANR-08-BLAN-0311-03. R.R.N's research was partially supported by an Office of Naval Research postdoctoral fellowship award and grant N00014-07-1-0269. R.R.N thanks Arthur Baggeroer for his feedback, support and encouragement. We thank Alan Edelman for feedback and encouragement and for facilitating this collaboration by hosting F.B.G's stay at M.I.T. We gratefully acknowledge the Singapore-MIT alliance for funding F.B.G's stay.

is singular. In this case, dim ker(zI n -X n ) = dim ker M n (z) [START_REF] Baik | Eigenvalues of large sample covariance matrices of spiked population models[END_REF] and for all x ∈ ker(zI n -X n ), we have U * n,r x ∈ ker M n (z) and x = (zI n -X n ) -1 U n,r ΘU * n,r x.

k,l denote the (k, l)-th element of the n × r matrix U n,r for k = 1, . . . , n and l = 1, . . . , r. Then for all i, j = 1, . . . , r, the (i, j)-th entry of the matrix

where µ

(n) i,j is the complex measure defined by

is the Cauchy transform of µ

c) In the setting where X = X n × (I n + P n ) and P n = U n,r ΘU * n,r as before, we obtain the analog of a) by replacing every occurrence, in (4) and (6), of (zI n -X n ) -1 with (zI n -X n ) -1 X n . We obtain the analog of b) by replacing the Cauchy transform in [START_REF] Benaych-Georges | Rectangular random matrices, related convolution[END_REF] with the T -transform.

Proof. Part a) is proved, for example, in [2, Th. 2.3]. Part b) follows from a straightforward computation of the (i, j)-th entry of U * n,r (zI n -X n ) -1 U n,r Θ. Part c) can be proved in the same way.

Proof of Theorem 2.1

The sequence of steps described below yields the desired proof:

(1) The first, rather trivial, step in the proof of Theorem 2.1 is to use Weyl's interlacing inequalities to prove that any extreme eigenvalue of X n which does not tend to a limit in R\[a, b] tends either to a or b. (2) Then, we utilize the "master equations" of Section 5 to express the extreme eigenvalues of X n as the z's such that a certain random r × r matrix M n (z) is singular. (3) We then exploit convergence properties of certain analytical functions (derived in the appendix) to prove that almost surely, M n (z) converges to a certain diagonal matrix M Gµ X (z), uniformly in z. (4) We then invoke a continuity lemma (see Lemma 6.1 -derived next) to claim that almost surely, the z's such that M n (z) is singular (i.e. the extreme eigenvalues of X n ) converge to the z's such that M Gµ X (z) is singular. [START_REF] Baik | Eigenvalues of large sample covariance matrices of spiked population models[END_REF] We conclude the proof by noting that, for our setting, the z's such that M Gµ X (z) is singular are precisely the z's such that for some i ∈ {1, . . . , r}, G µ X (z) = 1 θ i . Part (ii) of Lemma 6.1, about the rank of M n (z), will be useful to assert that when Let us recall that the eigenvalues of X n which are out of [λ n (X n ), λ 1 (X n )] are precisely those values z n where the matrix M n (z n ) is singular. As a consequence, we are now in a position where Theorem 2.1 follows by invoking Lemma 6.1. Indeed, by Lemma 6.1, if

then their exists some sequences (z n,1 ),. . . , (z n,p ) converging respectively to z 1 , . . . , z p such that for any ε > 0 small enough, for n large enough, the eigenvalues of X n that are out of [a -ε, b + ε] are exactly z n,1 , . . . , z n,p . Moreover, (5) and Lemma 6.1-(ii) ensure that for n large enough, these eigenvalues have multiplicity one.

6.2.3. Isolated eigenvalues in the setting where some θ i 's may coincide. We now treat the case where the θ i 's are not supposed to be pairwise distinct.

We denote, for θ = 0,

We want to prove that for all 1 ≤ i ≤ s, λ i ( X n ) a.s.

-→ ρ θ i and that for all 0 ≤ j < r -s, λ n-j ( X n ) a.s.

-→ ρ θ r-j .

We shall treat only the case of largest eigenvalues (the case of smallest ones can be treated in the same way). So let us fix 1 ≤ i ≤ s and ε > 0.

There is η > 0 such that |ρ θ -

r such that for all j = 1, . . . , r, θ j and θ ′ j have the same sign and

With the notation in Section 6.2.2, for each n, we define P ′ n = U P diag(θ ′ 1 , . . . , θ ′ r , 0, . . . , 0)U P . Note that by [START_REF] Horn | Matrix analysis[END_REF]Cor. 6.3.8], we have, for all n, n j=1 (λ j (X n + P ′ n ) -λ j (X n + P n )) 2 ≤ Tr(P ′ n -P n ) 2 = r j=1 (θ ′ j -θ j ) 2 ≤ ε 2 .

Theorem 2.1 can applied to X n + P ′ n (because the θ ′ 1 , . . . , θ ′ r are pairwise distinct). It follows that almost surely, for n large enough,