Luca Ganassali
email: luca.ganassali@inria.fr

Marc Lelarge
email: marc.lelarge@ens.fr

Laurent Massoulié
email: laurent.massoulie@inria.fr

Spectral alignment of correlated Gaussian random matrices

come

Introduction

Motivation: graph alignment

The aim of graph alignment (or graph matching, network alignment) is to find a bijective mapping between the nodes of two graphs of same size N , such that connectivity between nodes is preserved. In the general case such a perfect mapping is impossible to recover because of random noise, the aim is thus to find a mapping that minimizes the error (or maximizes the overlap).

Many questions can be phrased as graph alignment problems. They are found in various fields, such as network privacy and data de-anonymization [START_REF] Narayanan | Robust de-anonymization of large sparse datasets[END_REF][START_REF] Narayanan | De-anonymizing social networks[END_REF], biology and protein-protein interaction networks [START_REF] Singh | Global alignment of multiple protein interaction networks with application to functional orthology detection[END_REF], natural language processing [START_REF] Aria | Robust textual inference via graph matching[END_REF], as well as pattern recognition in image processing [START_REF] Conte | Thirty Years Of Graph Matching In Pattern Recognition[END_REF].

A very common way to represent graphs and networks is through adjacency matrices, or more generally affinity matrices. For two graphs of size N with adjacency matrices A and B, the graph matching problem can be formalized as an optimization problem: max

Π∈S N A, ΠBΠ T , ( 1
)
where the maximum is taken over all N × N permutation matrices, and •, • is the classical matrix inner product. This formulation is a special case of the well studied quadratic assignment problem (QAP) [START_REF] Pardalos | The Quadratic Assignment Problem: A Survey and Recent Developments[END_REF], which is known to be NP-hard in the worst case, as well as some of its approximations [START_REF] Makarychev | Maximum quadratic assignment problem: Reduction from maximum label cover and lp-based approximation algorithm[END_REF].

Related work

Some general spectral methods for random graph alignment are presented in [START_REF] Feizi | Spectral alignment of networks[END_REF], one of which is based on low rank approximation. This method is tested over synthetic graphs and gene regulatory graphs across several species. However, no precise theoretical guarantee (e.g. an error control of the inferred mapping depending on the signal-to-noise ratio) can be found for such techniques. It is important to note that the signs of eigenvectors are ambiguous: in order to optimize A, ΠB ΠT in practice, it is necessary to test over all possible signs of eigenvectors. This additional complexity has no consequence when reducing A and B to rank-one matrices, but becomes costly when the reduction made is of rank k = ω [START_REF] Allez | Eigenvector dynamics under free addition[END_REF]. This combinatorial observation makes implementation and analysis of general rank-reduction methods (as the ones proposed in [START_REF] Feizi | Spectral alignment of networks[END_REF]) more difficult. We therefore focus on the rank-one reduction (EIG1 hereafter).

Most recently, a spectral method for matrix and graph alignment was proposed in [START_REF] Zhou Fan | Spectral graph matching and regularized quadratic relaxations i: The gaussian model[END_REF][START_REF] Zhou Fan | Spectral graph matching and regularized quadratic relaxations ii: Erdős-rényi graphs and universality[END_REF] and computes a similarity matrix which takes into account all pairs of eigenvalues (λ i , µ j ) and eigenvectors (u i , v j ) of both matrices. meeting the state-of-the-art performances for alignment of sparse Erdös-Rényi graphs in polynomial time, and improving the performances among spectral methods for matrix alignment. This method can tolerate a noise σ up to O (log N ) -1 to recover the entire underlying vertex correspondence. Since the computations of all eigenvectors is required, the time complexity of this method is at least O(N 3 ). Algorithm EIG1 is the simplest spectral graph alignment method, where only the leading eigenvectors are computed, with complexity O(N 2 ).

Random weighted graph matching : model and method

We now focus on the case where the two graphs are complete weight-correlated graphs. We can work in a symmetric matrix setup, with correlated Gaussian weights. In the matrix model of our study, A and H are two N × N independent normalized matrices of the Gaussian Orthogonal Ensemble (GOE) (Gaussian Orthogonal Ensemble), i.e. such that for all 1 ≤ i ≤ j ≤ N ,

A i,j = A j,i ∼    1 √ N N (0, 1) if i = j, √ 2 √ N N (0, 1) if i = j, ( 2
)
and H is an independent copy of A. A permutation matrix Π is a matrix such that Π i,j = δ i,π(j) (where δ is the Kronecker delta) with π a permutation of {1, . . . , N }. Let Π be a permutation matrix of size N × N , and B = Π T (A + σH) Π, where σ = σ(N ) is the noise parameter.

Let us now define the aligning permutation of two vectors: given two vectors x = (x 1 , . . . , x n ) and y = (y 1 , . . . , y n ) having all distinct coordinates, the permutation ρ which aligns x and y is the permutation such that for all 1 ≤ i ≤ n, the rank (for the usual order) of x ρ(i) in x is the rank of y i in y.

Remark 1.1. We note that in our case, since all the probability distributions are absolutely continuous with respect to Lebesgue measure, the eigenvectors of A and B all have almost surely (a.s.) pairwise distinct coordinates.

The aim of this problem is to infer the underlying permutation Π given the information in A and B, using a simple algorithm derived from [START_REF] Feizi | Spectral alignment of networks[END_REF], which we call EIG1, that can be thought as the relaxation of QAP (1) when reducing the information in A and B to rank-one matrices. Indeed, is it easy to see that arg max

Π∈S N v 1 , Πv 1 = ρ,
where ρ is the aligning permutation of the two vectors, as soon as v 1 and v 1 have pair wise distinct coordinates.

Computing the two normalized leading eigenvectors (i.e. corresponding to the highest eigenvalues) v 1 and v 1 of A and B, this algorithm returns the permutation Π that aligns v 1 and v 1 . The main question is: what are the conditions on the noise σ and the size N that guarantee that Π is close enough from Π, with high probability?

Notations, main results and proof scheme

In this section we introduce some notations that will be used throughout this paper and we mention the main results and the proof scheme. These notations and results will be recalled in the next parts in more detail.

First, let us describe the EIG1 Algorithm, mentioned above, that we will use for our matrix alignment problem.

Algorithm 1: EIG1 Algorithm for matrix alignment

Input: A, B two matrices of size N × N . Output: A permutation Π.

Compute v 1 a normalized leading eigenvector of A and v 1 a normalized leading eigenvector of B; Compute Π + the permutation that aligns v 1 and v 1 ; Compute Π -the permutation that aligns v 1 and -v 1 ;

If A, Π + BΠ T + ≥ A, Π -BΠ T -then return Π + ; Else return Π -;

Notations

Spectral and metric notations

Recall that A and H are two N × N matrices drawn under model (2) here above. The matrix B is equal to Π T (A + σH) Π, where Π is a N × N permutation matrix and σ is the noise parameter, depending on N .

In the following, (v

1 , v 2 , . . . , v N ) (resp. (v 1 , v 2 , . . . , v N )) denote two orthonormal bases of eigenvectors of A (resp. of B) with respect to the (real) eigenvalues λ 1 ≥ λ 2 ≥ . . . ≥ λ N of A (resp. λ 1 ≥ λ 2 ≥ . . . ≥ λ N of B). Through all the study, the sign of v 1 is fixed such that Πv 1 , v 1 = v 1 , v 1 > 0.
Denote by • the euclidean norm of R N . Let •, • denote the corresponding inner product.

For any estimator Π of Π, define its overlap:

L( Π, Π) := 1 N N i=1 1 Π(i)=Π(i) . ( 3
)
This metric is used to quantify the quality of a given estimator of Π.

Probabilistic notations

The equality

(d)
= will refer to equality in distribution. Most of the following results are valid with high probability (we will use the abbreviation "w.h.p."), which means that their probabilities converges to 1 when N → ∞.

For two random variables u = u(N ) and v = v(N ), we will use the notation

u = o P (v) if u(N ) v(N ) P -→ 0 when N → ∞. We also use this notation when X = X(N ) and Y = Y (N ) are N -dimensional random vectors: X = o P (Y ) if X(N ) Y (N ) P -→ 0 when N → ∞.
Finally we introduce a last asymptotic notation. Define

F := f : N → R | ∀t > 0, N t f (N ) → ∞, f (N ) N t → 0 . ( 4
)
For two random variables u = u(N ) and v = v(N ), u v refers to logarithmic equivalence in probability, meaning that there exists a function f ∈ F such that

P v(N ) f (N ) ≤ u(N ) ≤ f (N )v(N ) → 1 (5)
Throughout the paper, all limits are taken when N → ∞, and the dependency of all quantities in N will most of the time be eluded, as an abuse of notation.

Main results, proof scheme

The result shown can be stated as follows: there exists a condition on σ and N under which the EIG1 method enables us to recover Π, in terms of the overlap L defined in [START_REF] Anderson | An Introduction to Random Matrices[END_REF]. Over this condition, we show that EIG1 Algorithm cannot recover more than a vanishing part of Π.

Theorem I (0-1 law in the EIG1 method for Gaussian matrix alignment). For all N , Π N denotes an arbitrary permutation of size N , ΠN is the estimator obtained with Algorithm EIG1, for A and B of model [START_REF] Allez | The eigenvectors of Gaussian matrices with an external source[END_REF], with permutation Π N and noise parameter σ.

We have the following 0-1 law:

(i) If there exists > 0 such that σ = o(N -7/6-) then L( ΠN , Π N ) L 1 -→ 1.
(ii) If there exists > 0 such that σ = ω(N -7/6+ ) then

L( ΠN , Π N ) L 1 -→ 0.
This result is shown in section 5. In order to prove this theorem, it is necessary to establish two intermediate results, which could also be of independent interest. Remark 2.1. We can now underline that without loss of generality, we can assume that Π = Id. Indeed, one can return to the general case with the rotations A → ΠAΠ T and H → ΠHΠ T . From this point, in the rest of the paper, we will thus assume that Π = Id.

First of all, we study the behavior of v 1 with respect to v 1 , showing that under some conditions on σ and N , the difference v 1 -v 1 can be approximated by a renormalized Gaussian standard vector, multiplied by a variance term S, where S is a random variable which behavior is well understood in terms of N and σ when N → ∞. For this we work under the following assumption:

∃ α > 0, σ = o N -1/2-α , ( 6
)
Proposition I. Under the assumption [START_REF] Erdos | Rigidity of Eigenvalues of Generalized Wigner Matrices[END_REF], there exists a standard Gaussian vector Z ∼ N (0, I N ) independent from v 1 and a random variable S σN 1/6 , such that

v 1 = (1 + o P (1)) v 1 + S Z Z .
This proposition is established in section 3.

Further related work

This assumption (6) (or a tighter formulation) arises when studying the diffusion trajectories of eigenvalues and eigenvectors in random matrices, and corresponds to the microscopic regime in [START_REF] Allez | The eigenvectors of Gaussian matrices with an external source[END_REF]. Basically, this assumption ensures that all eigenvalues of B are close enough to the eigenvalues of A. This comparison term is justified from the random matrix theory (N -1/2 is the typical amplitude of the spectral gaps √ N (λ i -λ i+1 ) in the bulk, which are the smaller ones). Eigenvectors diffusions in similar models (diffusion processes arise with the scaling σ = √ t) are studied in [START_REF] Allez | The eigenvectors of Gaussian matrices with an external source[END_REF], where the main tool is the Dyson Brownian motion (see e.g. [START_REF] Anderson | An Introduction to Random Matrices[END_REF]) and its formulation for eigenvectors trajectories, giving stochastic differential equations for the evolutions of v j (t) with respect to vectors v i = v i (0). These equations lead to a system of differential equations for the overlaps v i , v j (t) , which is quite difficult to analyze rigorously. We use here an elementary method to get a expansion of v 1 around v 1 , where this very condition [START_REF] Erdos | Rigidity of Eigenvalues of Generalized Wigner Matrices[END_REF] arises.

This result thus suggests the study of v 1 as a Gaussian perturbation of v 1 . The main question is now formulated as follows: what is the probability that the perturbation on v 1 has an impact on the overlap of the estimator Π from the EIG1 method?

To answer this question, we introduce a correlated Gaussian vectors model (or toy model) of parameters s > 0 and N ≥ 1. In this model, we draw X a standard Gaussian vector of size N . Define Y = X + sZ where Z is an independent copy of X. We will use the notation (X, Y ) ∼ J (N, s).

Define r 1 the application that associates to any vector T = (t 1 , . . . , t p ) the rank of t 1 in T (for the usual order). For (X, Y ) ∼ J (N, s) we evaluate p(N, s)

:= P (r 1 (X) = r 1 (Y )) .
A second result is proved: there is a 0-1 law for the property of rank preservation in the toy model J (N, s).

Proposition II (0-1 law for p(N, s)). In the correlated Gaussian vectors model we have the following 0-1 law

(i) If s = o(1/N ) then p(N, s) → N →∞ 1. (ii) If s = ω(1/N ) then p(N, s) → N →∞ 0.
This proposition is shown in section 4 and illustrated in figure 1, showing the 0-1 law at s = N -1 .

Finally, in section 5, Propositions I and II enable us to show Theorem I, illustrated on figure 2 showing the 0-1 law at σ = N -7/6 . The convergence to the step function appears to be slow.

Behavior of the leading eigenvectors in the correlated matrices model

The main idea of this section is to find a first order expansion of v 1 around v 1 . Recall that we use the notations (v 1 , v 2 , . . . , v N ) for normalized eigenvectors of A, corresponding to the eigenvalues

λ 1 ≥ λ 2 ≥ . . . ≥ λ N . Similarly, (v 1 , v 2 , . . . , v N ) and λ 1 ≥ λ 2 ≥ . . . ≥ λ N
will refer to eigenvectors and some eigenvalues of B. We also recall that v 1 is taken such that v 1 , v 1 > 0.

Computation of a leading eigenvector of B

Let w be an (non normalized) eigenvector of B for the eigenvalue λ 1 of the form

w := N i=1 θ i v i ,
where we assume that θ 1 = 1. Such an assumption can be made a.s. since any hyperplane of R N has a null Lebesgue measure in R N (see Remark 1.1).

Recall now that we are working under assumption (6):

∃ α > 0, σ = o N -1/2-α .
We first obtain the following expansion.

Proposition 3.1. Under the assumption ( 6) one has the following:

w = v 1 + σ N i=2 Hv i , v 1 λ 1 -λ i v i + o P σ N i=2 Hv i , v 1 λ 1 -λ i v i . ( 7
)
Remark 3.1. Based on the studies of the trajectories of the eigenvalues and eigenvectors in the GUE [START_REF] Allez | The eigenvectors of Gaussian matrices with an external source[END_REF] and the GOE [START_REF] Allez | Eigenvector dynamics under free addition[END_REF], since we only look at the leading eigenvectors, we expect the result of Proposition 3.1 to hold under the weaker assumption σN 1/6+α → 0, for N -1/6 is the typical spectral gap √ N (λ 1 -λ 2 ) on the edge. However, our analysis doesn't require this more optimal assumption. We also know that the expansion (7) doesn't hold as soon as σ = ω(N -1/6 ). A result proved by Chatterjee ([4], Theorem 3.8) shows that the eigenvectors corresponding to the highest eigenvalues v 1 of A and v 1 of B = A + σH, when A and H are two independent matrices from the GUE, are delocalized (in the sense that v 1 , v 1 converges in probability to 0 as N → ∞), when σ = ω(N -1/6 ).

We will use the following lemmas:

Lemma 3.2. W.h.p., for all δ > 0, N j=2 1 λ 1 -λ j ≤ O N 1+δ . ( 8
)
Lemma 3.3. We have

N j=2 1 (λ 1 -λ j ) 2 N 4/3 . ( 9
)
Lemma 3.4. For any C > 0, w.h.p.

λ 1 -λ 2 ≥ N -2/3 (log N ) -C log log N . ( 10
)
Lemma 3.5. We have the following concentration

N i=2 Hv i , v 1 2 (λ 1 -λ i ) 2 N 1/3 . ( 11
)
Proof of proposition 3.1. Let us establish a first inequality: since the GOE distribution is invariant by rotation (see e.g. [START_REF] Anderson | An Introduction to Random Matrices[END_REF]), the random variables Hv j , v i are zero-mean Gaussian, with variance 1/N of i = j and 2/N if i = j. Hence, w.h.p.

sup 1≤i,j≤N | Hv j , v i | ≤ C 1 log N N . ( 12
)
Throughout this proof we will work under the event where inequalities implied by equations ( 8), ( 9), ( 10), ( 11) and ( 12) are satisfied. We also use the following short-hand notation for 1 ≤ i, j ≤ N :

m i,j := Hv j , v i ,
The defining eigenvector equations projected on vectors v i write

   θ i = σ λ 1 -λ i N j=1 θ j m i,j , λ 1 -λ 1 = σ N j=1 θ j m 1,j . (13)
In order to approximate the θ i variables, we define the following iterative scheme:

   θ k i = σ λ k-1 1 -λ i N j=1 θ k-1 j m i,j , λ k 1 -λ 1 = σ N j=1 θ k-1 j m 1,j , (14)
with initial conditions θ 0 i 2≤i≤N = 0 and λ 0 1 = λ 1 , and setting θ k 1 = 1 for all k.

For k ≥ 1, define ∆ k := i≥2 θ k i -θ k-1 i . and for k ≥ 0, S k := i≥1 θ k i .
Recall that under assumption ( 6), there exists α > 0 such that σ = o N -1/2-α . We define as follows:

= (N ) = σN 1/2+α .
We show the following result:

Lemma 3.6. With the same notations and under the assumption ( 6) of Proposition 3.1, one has w.h.p.

(i) ∀k ≥ 1, ∆ k ≤ ∆ 1 k-1 , (ii) ∀k ≥ 0, ∀ 2 ≤ i ≤ N, λ k 1 -λ i ≥ 1 2 |λ 1 -λ i | 1 --. . . -k-1 , (iii) ∀k ≥ 0, S k ≤ 1 + (1 + . . . + k-1 )∆ 1 , (iv) N i=2 θ i -θ 1 i 2 = o N i=2 θ 1 i 2 .
Equation (iv) of Lemma 3.6 yields

w = v 1 + N i=2 θ 1 i v i + N i=2 θ i -θ 1 i v i = v 1 + σ N i=2 Hv i , v 1 λ 1 -λ i v i + o P σ N i=2 Hv i , v 1 λ 1 -λ i v i .

Gaussian representation of v 1 -v 1

We still work under assumption [START_REF] Erdos | Rigidity of Eigenvalues of Generalized Wigner Matrices[END_REF]. After renormalization, we thus have

v 1 = w w .
A crucial point is now the computation of the scalar product v 1 , v 1 :

v 1 , v 1 = 1 + σ 2 (1 + o P (1)) N i=2 Hv i , v 1 2 (λ 1 -λ i ) 2 -1/2
Hence w.h.p.

v 1 , v 1 = 1 - σ 2 2 N i=2 Hv i , v 1 2 (λ 1 -λ i ) 2 + o P σ 2 N i=2 Hv i , v 1 2 (λ 1 -λ i ) 2 . ( 15
)
With Lemma 3.5 and with the same notations, we have

σ 2 N i=2 Hv i , v 1 2 (λ 1 -λ i ) 2 σ 2 N 1/3 (= o(1)).
Remark 3.2. The previous result can be seen as a first order expansion in the diffusion process found in the literature mentioned at the beginning of this section (see e.g. [START_REF] Allez | The eigenvectors of Gaussian matrices with an external source[END_REF]). The comparison between σ and N 1/6 (c.f. Chatterjee, [START_REF] Chatterjee | Superconcentration and related topics[END_REF]) clearly appears here, as σ 2 N 1/3 is the typical shift of v 1 with respect to v 1 .

Let us now introduce an useful lemma for the proof of Proposition I: Lemma 3.7. Given v 1 , when writing the decomposition

w = v 1 + N i=2 θ i v i =:w
, the distribution of w is invariant by rotation in the orthogonal complement of v 1 . This implies in particular that given v 1 , w and w w are independent, and that w w is uniformly distributed on S N -2 , the unit sphere of v ⊥ 1 .

We can now formulate and show the main result of this section:

Proposition I. Under the assumption [START_REF] Erdos | Rigidity of Eigenvalues of Generalized Wigner Matrices[END_REF], there exists a standard Gaussian vector Z ∼ N (0, I N ) independent from v 1 and a random variable S σN 1/6 , such that

v 1 = (1 + o P (1)) v 1 + S Z Z .
Proof of Proposition I. Recall the decomposition

w = v 1 + N i=2 θ i v i =:w .
According to Lemma 3.7, w w is uniformly distributed on the unit sphere of R N -2 . A classical result (see e.g. [START_REF] Rourke | Eigenvectors of random matrices: A survey[END_REF]) shows that there exist Z 2 , . . . , Z N standard Gaussian independent variables, independent from v 1 and w , such that:

w = v 1 + w N i=2 Z 2 i 1/2 N i=2 Z i v i .
Let Z 1 be another standard Gaussian variable, independent from everything else. Then

w =   1 - w Z 1 N i=2 Z 2 i 1/2    v 1 + w N i=2 Z 2 i 1/2 N i=1 Z i v i . Let Z = N i=1 Z i v i
, which is a standard Gaussian vector. Since the distribution of Z is invariant by permutation of indices of (Z i ) 1≤i≤N , Z and v 1 are independent. We have

v 1 = w w = w 1 + w 2 = 1 1 + w 2   1 - w Z 1 N i=2 Z 2 i 1/2    v 1 + w Z 1 + w 2 N i=2 Z 2 i 1/2 Z Z .
Taking

S = w Z N i=2 Z 2 i 1/2 -w Z 1 , we get v 1 = 1 1 + w 2   1 - w Z 1 N i=2 Z 2 i 1/2    v 1 + S Z Z .
The law of large numbers, Lemma 3.5 and Proposition 3.1, showing that w = o P (1), lead to

v 1 = (1 + o P (1)) v 1 + S Z Z .
Lemma 3.5 directly shows that S = (1 + o P (1)) w σN 1/6 and ends the proof.

Definition and analysis of a toy model

Now that we have established a expansion of v 1 with respect to v 1 , the following natural question remains: what is the probability that the perturbation on v 1 has an impact on the overlap (3) of the estimator Π from the EIG1 method? We thus study here the effect of a random Gaussian perturbation of a Gaussian vector in terms of rank of its coordinates: if these ranks are preserved, the permutation that aligns these two vectors will be Π = Id. Otherwise we want to understand the error made between Π and Π = Id.

Definitions and notations

We refer to section 2.1 for the definition of the toy model J (N, s). Recall that we want to compute, when (X, Y ) ∼ J (N, s), the probability

p(N, s) := P (r 1 (X) = r 1 (Y )) .
In this section, we denote by E the probability density function function of a standard Gaussian variable, and F its cumulative distribution function.

We explain hereafter the link between this toy model and our first matrix model (2) in section 3. Since v 1 is uniformly distributed on the unit sphere, we have the classical equality in law v 1 = X X where X is a standard Gaussian vector of size N , independent of Z. Proposition I writes

v 1 = X X , v 1 = (1 + o P (1)) X X + S Z Z .
Note that for all λ > 0, r 1 (λT ) = r 1 (T ), hence

r 1 (v 1 ) = r 1 (X), r 1 (v 1 ) = r 1 (X + sZ) , (16)
where

s = S X Z σN 1/6 .
Equation [START_REF] Rourke | Eigenvectors of random matrices: A survey[END_REF] shows that this toy model is thus relevant for our initial problem, up to the fact that the noise term s is random in the matrix model (though we know its order of magnitude to be σN 1/6 ).

Remark 4.1. The intuition for the 0-1 law for p(N, s) is as follows. If we sort the N coordinates of X on the real axis, they will all be w.h.p. in an interval of length O( √ log N ). All coordinates being typically perturbed by a factor s, it seems natural to compare s with the typical gap between two coordinates of order 1/N to decide whether the rank of the first coordinate of X is preserved in Y .

Let us show that this intuition is rigorously verified. For every couple (x, y) of real numbers, define

N +- N,s (x, y) := {1 ≤ i ≤ N, X i > x, Y i < y} , N -+ N,s (x, y) := {1 ≤ i ≤ N, X i < x, Y i > y} .
In the following, we omit all dependencies in N and s, with the abuses of notation N , N +-and N -+ . The corresponding regions are shown on figure 3. We will also need the following probabilities S +-(x, y) := P (X 1 > x, Y 1 < y) , and

N -+ (x, y) N +-(x, y) E T s (x, y)
S -+ (x, y) := P (X 1 < x, Y 1 > y) = S +-(-x, -y).
We recall that E refers to the probability density function of a standard Gaussian variable, and F its cumulative distribution function. In terms of distribution, the random vector N +-(x, y), N -+ (x, y), N -1 -N +-(x, y) -N +-(x, y) follows a multinomial law of parameters N -1, S +-(x, y), S -+ (x, y), 1 -S +-(x, y) -S -+ (x, y) .

In order to have r 1 (X) = r 1 (Y ), there must be the same number of points on the two domains on figure 3, for x = X 1 and y = Y 1 . We then have the following expression of p(N, s):

p(N, s) = E P N +-(X 1 , Y 1 ) = N -+ (X 1 , Y 1 ) = R R P(dx, dy)P(N +-(x, y) = N -+ (x, y)) = R R E(x)E(z)φ x,z (N, s) dx dz, with φ x,z (N, s) := (N -1)/2 k=0 N -1 k N -1 -k k S +- x,z k S -+ x,z k 1 -S +- x,z -S -+ x,z N -1-2k , ( 17

) using the notations S +-

x,z = S +-(x, x + sz) and S -+ x,z = S -+ (x, x + sz) .

A simple computation shows that

S +-(x, x + sz) = +∞ x 1 √ 2π e -u 2 /2 z+ x-u s -∞ 1 √ 2π e -v 2 /2 dv du = +∞ x E(u) F z - u -x s du, ( 18
) = s +∞ 0 E(x + vs) F (z -v) dv. ( 19
)
We have the integration result

z -∞ F (u)du = zF (z) + 1 √ 2π e -z 2 /2 . ( 20
)
From ( 18), ( 19) and (20) we derive the following easy lemma:

Lemma 4.1. For all x and z,

S +-(x, x + sz) = s→0 s [E(x) (zF (z) + E(z))] + o(s), S +-(x, x + sz) -→ s→∞ F (x) (1 -F (z)) , S -+ (x, x + sz) = s→0 s [E(x) (-z + zF (z) + E(z))] + o(s), S -+ (x, x + sz) -→ s→∞ F (z) (1 -F (x)) .
Moreover, both s → S +-(x, x + sz) and s → S -+ (x, x + sz) are increasing.

0-1 law for p(N, s)

We now establish the main result of this section.

Proposition II (0-1 law for p(N, s)). In the correlated Gaussian vectors model we have the following 0-1 law

(i) If s = o(1/N ) then p(N, s) → N →∞ 1. (ii) If s = ω(1/N ) then p(N, s) → N →∞ 0.
Proof of Proposition II. In the first case (i), if s = o(1/N ), we have the following inequality

p(N, s) ≥ R R dxdzE(x)E(z)P N +-(x, x + sz) = N -+ (x, x + sz) = 0 . ( 21
)
According to Lemma 4.1, for all x, z ∈ R

P N +-(x, x + sz) = N -+ (x, x + sz) = 0 = 1 -S +-(x, x + sz) -S -+ (x, x + sz) N -1 ∼ exp (-N sE(x) [z(2F (z) -1) + 2E(z)]) -→ N →∞ 1,
By applying the dominated convergence theorem in (21), we conclude that p(N, s) → 1.

In the second case (ii), if sN → ∞, recall that

p(N, s) = R R dxdzE(x)E(z)φ x,z (N, s), ( 22
)
with φ x,z defined in equation [START_REF] Pardalos | The Quadratic Assignment Problem: A Survey and Recent Developments[END_REF]. In the rest of the proof, we fix x and z two real numbers. Letting

b(N, s, k)

:= N -1 k S +- x,z k 1 -S +- x,z N -1-k and M (N, s) := max 0≤k≤N -1 b(N, s, k),
a classical computation shows that there exists C = C(x, z) > 0 such that for N large enough,

M (N, s) = b(N, s, N S +- x,z ) ≤ lim sup N C N S +- x,z (N ) 1/2 + C
, and the assumption (ii) (sN → ∞) together with Lemma 4.1 ensure that lim inf

N N S +- x,z (N ) = ∞ and that M (N, s) -→ N →∞
0. We obtain the following control

φ x,z (N, s) ≤ M (N, s) × (N -1)/2 k=0 N -1 -k k S -+ x,z k 1 -S +- x,z -S -+ x,z N -1-2k 1 -S +- x,z N -1-k (a) = M (N, s) × (1 -S +- x,z ) 1 - -S +- x,z 1-S -+ x,z N 1 + S -+ x,z -S +- x,z (b) = M (N, s) × O(1) -→ N →∞ 0.
We used in (b) the fact that S +- x,z + S -+ x,z is increasing in the variable s, and that given x and z, for all s > 0, S +-

x,z + S -+ x,z < F (x) (1 -F (z)) + F (z) (1 -F (x)) < 1, where F is the cumulative distribution function of a standard Gaussian variable (Lemma 4.1). We used in (a) the following combinatorial result: Lemma 4.2. For all α > 0,

(N -1)/2 k=0 N -1 -k k α k = 1 √ 1 + 4α   1 + √ 1 + 4α 2 N - 1 - √ 1 + 4α 2 N   . ( 23
)
To obtain (a) from Lemma 4.2, we apply (23) to α =

S -+ x,z (1-S +- x,z ) (1-S +- x,z -S -+ x,z ) 2 , with √ 1 + 4α = 1-S +- x,z +S -+ x,z 1-S +- x,z -S -+ x,z
. The dominated convergence theorem in (22) shows that p(N, s) → 0 and ends the proof.

Remark 4.2. The above computations also imply the existence of a non-degenerate limit of p(N, s) in the critical case where sN → c > 0.

Analysis of the EIG1 method for matrix alignment

By now, we come back to our initial problem, which is to infer the underlying permutation Π with EIG1 method. Recall that for any estimator Π of Π, its overlap is defined as follows

L( Π, Π) := 1 N N i=1 1 Π(i)=Π(i) .
We now show how the Propositions I and II lead to the main result of our study:

Theorem I (0-1 law in the EIG1 method for Gaussian matrix alignment). For all N , Π N denotes an arbitrary permutation of size N , ΠN is the estimator obtained with Algorithm EIG1, for A and B of model ( 2), with permutation Π N and noise parameter σ.

We have the following 0-1 law:

(i) If there exists > 0 such that σ = o(N -7/6-) then L( ΠN , Π N ) L 1 -→ 1.
(ii) If there exists > 0 such that σ = ω(N -7/6+ ) then

L( ΠN , Π N ) L 1 -→ 0.
Proof of Theorem I. In the first case (i), condition (6) holds. As detailed in Section 4, for rank preservation, one can identify v 1 and v 1 with the following vectors:

v 1 ∼ X, v 1 ∼ X + sZ, (24)
where X and Z are two independent Gaussian vectors the toy model, and where s σN 1/6 w.h.p. Recall that we work under the assumptions Π = Id and v 1 , v 1 > 0.

In this case, we expect Π + to be very close to Id. Let's take f ∈ F such that w.h.p., σN 1/6 f (N ) -1 ≤ s ≤ σN 1/6 f (N ). We have for all 1 ≤ i ≤ N ,

P (Π + (i) = Π(i)) = P (Π + (1) = Π(1)) = E dxdzE(x)E(z)φ x,z (N, s) 1 σN 1/6 f (N ) -1 ≤s≤σN 1/6 f (N ) + o(1) = dxdzE(x)E(z)E φ x,z (N, s) 1 σN 1/6 f (N ) -1 ≤s≤σN 1/6 f (N ) + o(1).
When σN 1/6 f (N ) -1 ≤ s ≤ σN 1/6 f (N ), sN a.s.

-→ 0 by condition (i) and φ x,z (N, s) a.s.

-→ 1 by Proposition I. Uniform integrability is guaranteed by the obvious domination |φ x,z (N, s)| ≤ 1, which gives

φ x,z (N, s) 1 σN 1/6 f (N ) -1 ≤s≤σN 1/6 f (N ) L 1 -→ 1,
which implies with the dominated convergence theorem that

E [L(Π + , Π)] → 1 and thus L(Π + , Π) L 1 → 1. Lemma 5.1. In the case (i), if v 1 , v 1 > 0, we have w.h.p. A, Π + BΠ T + > A, Π -BΠ T -,
so the Algorithm EIG1 returns w.h.p. Π = Π + .

With Lemma 5.1 we can conclude that

0 ≤ E 1 -L( Π, Π)1 Π=Π + ≤ E [1 -L(Π + , Π)] + 1 × E 1 -1 Π=Π + -→ 0. Hence E L( Π, Π) ≥ E L( Π, Π)1 Π=Π + → 1 and L( Π, Π) L 1 → 1.
Of course, this convergence also happens in probability, by Markov's inequality.

In the second case (ii), if condition ( 6) is verified then the identification (24) still holds and the proof of case (i) adapts well. However, if [START_REF] Erdos | Rigidity of Eigenvalues of Generalized Wigner Matrices[END_REF] is not verified, we can still make a link with the toy model studied in section 4. Let's use a simple coupling argument: if σ = ω(N -1/2-α ) for some α ≥ 0, let's take σ 1 , σ 2 > 0 such that

σ 2 = σ 2 1 + σ 2 2
and fix for instance σ 1 = N -1 . We will use the notation v 1 , now viewed as the leading eigenvector of the matrix

B = A + σ 1 H + σ 2 H,
where H is an independent copy of H. This has no consequence in terms of distribution : (A, B) is still drawn under model ( 2). Let's denote v 1 the leading eigenvector of

B 1 = A+σ 1 H, chosen so that v 1 , v 1 > 0.
It is clear that σ 1 satisfies (6). We have the following result, based on the invariance by rotation of the GOE:

Lemma 5.2. We still have the following equalities in distribution:

r 1 (v 1 ) (d) = r 1 (X), (25)
and

r 1 ( v 1 ) (d) = r 1 (X + sZ), (26)
where X, Z are two Gaussian vectors from the toy model, with w.h.p.

s ≥ s 1 σ 1 N 1/6 .
Since w.h.p. s ≥ s 1 and s 1 N σ 1 N 7/6 → ∞, we have for all 1 ≤ i ≤ N ,

P (Π + (i) = Π(i)) = P (Π + (1) = Π(1)) = E dxdzE(x)E(z)φ x,z (N, s)1 sN →∞ + o(1) = dxdzE(x)E(z)E [φ x,z (N, s)1 sN →∞ ] + o(1).
With the same arguments as in the case (i), we show that

φ x,z (N, s)1 sN →∞ L 1 -→ 0, which implies E [L(Π + , Π)] -→ N →∞ 0,
and thus

L(Π + , Π) L 1 -→ N →∞ 0.
Lemma 5.3. In the case (ii), if v 1 , v 1 > 0, we also have

L(Π -, Π) L 1 -→ N →∞ 0. Lemma 5.3 then gives E L( Π, Π) ≤ E [L(Π + , Π)] + E [L(Π -, Π)] -→ N →∞ 0,
and thus L( Π, Π)

L 1 -→ N →∞ 0.
Of course, this convergence also happens in probability, by Markov's inequality.

Proof of lemmas

Throughout all these proofs, variables denoted by C i with i a positive integer are positive universal constants (independent of everything else).

Proof of Lemma 3.4

Proof of Lemma 3.4. This lemma provides a control of the spectral gap λ 1 -λ 2 . Given a good rescaling (in N 2/3 ), the asymptotic joint law of the eigenvalues in the edge has been investigated in a great amount of research work, for Gaussian ensembles, and for more general Wigner matrices. The GOE case has been mostly studied by Tracy, Widom, and Forrester ; in [START_REF] Forrester | The spectrum edge of random matrix ensembles[END_REF] and [START_REF] Tracy | Correlation Functions, Cluster Functions, and Spacing Distributions for Random Matrices[END_REF], the convergence of the joint distribution of the first k eigenvalues towards a density distribution is established: [START_REF] Tracy | Correlation Functions, Cluster Functions, and Spacing Distributions for Random Matrices[END_REF]). For a given k ≥ 1, and all s 1 , . . . , s k real numbers,

Proposition 6.1 ([10],
P N 2/3 (λ 1 -2) ≤ s 1 , . . . , N 2/3 (λ k -2) ≤ s k -→ N →∞ F 1,k (s 1 , . . . , s k ), (27)
where the F 1,k are continuous and can be expressed as solutions of non linear PDEs. Thus the re-scaled spectral gap N 2/3 (λ 1 -λ 2 ) has a limit probability density law supported by R + , which implies that

P N 2/3 (λ 1 -λ 2 ) ≥ (log N ) -C log log N -→ N →∞ 1.

Proof of Lemma 3.3

Proof of Lemma 3.3. This result needs an understanding of the behavior of the spectral gaps of matrix A, in the bulk and in the edges (left and right). The eigenvalues in the edge correspond to indices i such that i = o(N ) (left) or i = N -o(N ) (right). Eigenvalues in the bulk are the remaining eigenvalues. For this, we use a result of rigidity of eigenvalues, due to L. Erdös et al. [START_REF] Erdos | Rigidity of Eigenvalues of Generalized Wigner Matrices[END_REF], which consists in a control of the probability of the gap between the eigenvales of A and the typical eigenvalues γ j of the semi-circle law, defined as follows ∀i ∈ {1, . . . , n} , 1 2π

γ j -2 4 -x 2 dx = 1 - j N . ( 28
)
Proposition 6.2 ([6]). For some positive constants C 5 > 0 and C 6 > 0, for N large enough,

P ∃j ∈ {1, . . . , n} | |λ j -γ j | ≥ (log N ) C 5 log log N (min (j, N + 1 -j)) -1/3 N -2/3 ≤ C 5 exp -(log N ) C 6 log log N . ( 29
)
Remark 6.1. Another similar result that goes in the same direction for the GOE is already known: it has been shown by O'Rourke in [START_REF] Sean | Gaussian Fluctuations of Eigenvalues in Wigner Random Matrices[END_REF] that the variables λ i -γ i behave as Gaussian variables when N → ∞. However, the rigidity result obtained in (29) can apply in more general models. This quantitative probabilistic statement was not previously known even for the GOE case. Remark 6.2. Let us note that one of the assumptions made in [START_REF] Erdos | Rigidity of Eigenvalues of Generalized Wigner Matrices[END_REF] is that variances of each column sum to 1, which is not directly the case in our model [START_REF] Allez | The eigenvectors of Gaussian matrices with an external source[END_REF]. Nevertheless, one may use (29) for the re-scaled matrix

à := A 1 + 1 N -1/2
, then easily check that there is a possible step back to A:

|λ j -γ j | ≤ λ j 1 + 1 N -1/2 -γ j + N -1 + o(N -1
), and

N -1 + o(N -1 ) ≤ 2 (min (j, N + 1 -j)) -1/3 N -2/3
for N big enough. Tolerating a slight increase of the constant C 5 , the result ( 29) is thus valid in the GOE.

Let us now compute an asymptotic expansion of γ j in the right edge, which is for

j = o(N ). Define G(x) := 1 2π x -2 4 -t 2 dt = x √ 4 -x 2 + 4 arcsin(x/2) 4π + 1 2 , ( 30
) for all x ∈ [-2, 2]. We have γ j = G -1 (1 -j/N ) = -G -1 (j/N
), observing that the integrand in ( 30) is an even function. We get the following expansion when x → -2,

G(x) = x→-2 2(x + 2) 3/2 3π + o (x + 2) 3/2
which implies that

G -1 (y) = y→0 -2 + 3πy 2 2/3
+ o y 2/3 , hence

γ j = j/N →0 2 - 3πj 2N 2/3 + o (j/N ) 2/3 . ( 31
)
Remark 6.3. One can observe the coherence of this result that arises naturally in [START_REF] Sean | Gaussian Fluctuations of Eigenvalues in Wigner Random Matrices[END_REF] as the expectation of the eigenvalues in the edge.

Let > 0, to be specified later. To establish our result we will split the variables j in three sets:

A 1 := 2 ≤ j ≤ (log N ) (C 5 +1
) log log N (a small part of the right edge),

A 2 := (log N ) (C 5 +1) log log N < j ≤ N 1-(a larger part of the right edge), A 3 := N 1-< j ≤ N (everything else).
We show that the sum over A 1 is the major contribution in [START_REF] Feizi | Spectral alignment of networks[END_REF]. the split in the right edge in A 1 and A 2 is driven by the error term of (29): this term is small compared to γ j if and only if (log N ) C 5 log log N = o(j).

Step 1: estimation of the sum over A 1 . According to (29) and Lemma 3.4, w.h.p.

N -4/3 (log N ) -C 6 log log N ≤ (λ 1 -λ 2 ) 2 ≤ C 7 N -4/3 (log N ) C 6 log log N ,
where C 6 , C 7 are positive constants. Hence, w.h.p.

N 4/3 C 7 (log N ) C 6 log log N ≤ j∈A 1 1 (λ 1 -λ j ) 2 ≤ j∈A 1 1 (λ 1 -λ 2 ) 2 ≤ N 4/3 (log N ) (C 5 +C 6 +1) log log N .
Step 2: estimation of the sum over A 2 . Let us show that the sum over A 2 is asymptotically small compared to the sum over A 1 : using ( 29) and (31), we know that there exists C 8 > 0 such that for all j ∈ A 2 , w.h.p.

λ j = 2 -C 8 j N 2/3 + o (j/N ) 2/3 ,
and we know furthermore (se e.g. [START_REF] Anderson | An Introduction to Random Matrices[END_REF]) that w.h.p.

λ 1 = 2 + o (j/N ) 2/3 , ∀j ∈ A 2 (32)
hence w.h.p.

j∈A 2 1 (λ 1 -λ j ) 2 = N 4/3 j∈A 2 1 C 9 j 4/3 (1 + o(1)) = N 4/3 (1 + o(1)) j∈A 2 1 C 9 j 4/3 = o N 4/3 ,
using in the last line the fact that the Riemann's series j -4/3 converges.

Step 3: estimation of the sum under A 3 . With the previous results (29), (31) and (32), assuming that < 1, we get w.h.p.

λ 1 -λ N 1-= C 8 N -2 /3 + O N -2 /3 ,
which gives w.h.p. the following control

j∈A 3 1 (λ 1 -λ j ) 2 ≤ N -N 1- 1 (λ 1 -λ N 1-) 2 = N -N 1- N 4 /3 C 9 (1 + o(1)) = O N 1+4 /3 = o N 4/3 ,
as long as < 1/4. Taking such a , these three controls end the proof.

Proof of Lemma 3.2

Proof of Lemma 3.2. We follow the same steps as in the proof of Lemma 3.3. Let's take δ > 0. We split the j variables in three sets:

A 1 := 2 ≤ j ≤ N 1/3 , A 2 := N 1/3 < j ≤ N 1-δ , A 3 := N 1-δ < j ≤ N .
We use Lemma 3.4 to obtain the following control w.h.p.

j∈A 1 1 λ 1 -λ j ≤ N 1/3 N 2/3 (log N ) C 5 log log N = O(N 1+δ ).
Similarly, for A 2

j∈A 2 1 λ 1 -λ j ≤ j∈A 2 1 o(N -2/3 ) + C 8 (j/N ) 2/3 + O (log N ) C 5 log log N N -2/3 j -1/3 = N 2/3 j∈A 2 1 o(1) + C 8 j 2/3 ≤ C 10 N 2/3 N (1-δ)/3 ≤ O(N 1+δ ).
Finally, using Cauchy-Schwarz inequality

j∈A 3 1 λ 1 -λ j ≤ √ N   j∈A 3 1 (λ 1 -λ j ) 2   1/2 ≤ √ N O(N 1/2+2δ/3 ) = O(N 1+δ ).

Proof of Lemma 3.6

Proof of Lemma 3.6. In this proof we will use the same notations, as defined in the proof of Proposition 3.1, and we make the assumption [START_REF] Erdos | Rigidity of Eigenvalues of Generalized Wigner Matrices[END_REF]. Recall that we work under the event (that occurs w.h.p.) on which the equations ( 8), ( 9), ( 10), ( 11) and ( 12) are satisfied. We show the following inequalities:

(i) ∀k ≥ 1, ∆ k ≤ ∆ 1 k-1 , (ii) ∀k ≥ 0, ∀ 2 ≤ i ≤ N, λ k 1 -λ i ≥ 1 2 |λ 1 -λ i | 1 --. . . -k-1 , (iii) ∀k ≥ 0, S k ≤ 1 + (1 + . . . + k-1 )∆ 1 .
Recall that is given by = (N ) = σN 1/2+α . We will denote by f i (N ), with i an integer, functions as defined in Lemma 3.3. All the following inequality will be valid for N large enough (uniformly in i and in k).

Step 1: propagation of the first equation. Let k ≥ 3.

θ k i -θ k-1 i ≤ σ λ k-1 1 -λ i N j=2 θ k-1 j -θ k-2 j m i,j + σ λ k-2 1 -λ k-1 1 λ k-1 1 -λ i λ k-2 1 -λ i N j=1 θ k-2 j m i,j ≤ σ λ k-1 1 -λ i C 1 log N N ∆ k-1 + σC 1 log N N S k-2 λ k-2 1 -λ k-1 1 λ k-1 1 -λ i λ k-2 1 -λ i ≤ σ 3 |λ 1 -λ i | (ii) to k -1 C 1 log N N ∆ k-1 + σC 1 log N N S k-2 9 λ k-2 1 -λ k-1 1 |λ 1 -λ i | 2 (ii) to k -1, k -2 ≤ σ 3 |λ 1 -λ i | C 1 log N N ∆ k-1 + σC 1 log N N 2 (iii) to k -2 9 λ k-2 1 -λ k-1 1 |λ 1 -λ i | 2 .
Note that

λ k-2 1 -λ k-1 1 = σ N j=1 θ k-2 j -θ k-3 j m i,j ≤ σC 1 log N N ∆ k-2 ,
which yields the inequality:

θ k i -θ k-1 i ≤ σ |λ 1 -λ i | f 1 (N )N -1/2 ∆ k-1 + σ 2 |λ 1 -λ i | 2 f 2 (N )N -1 ∆ k-2 .
We choose δ such that 0 < δ < α (where α is fixed by ( 6)), and we sum from i = 2 to N :

∆ k ≤ σf 1 (N )N 1/2+δ =o( ) ∆ k-1 + σ 2 f 3 (N )N 1/3 =o( 2 ) ∆ k-2 ≤ o( ) k-2 ∆ 1 (i) to k -1 +o( 2 ) k-3 ∆ 1 (i) to k -2 ≤ k-1 ∆ 1 .
Step 2: propagation of the second equation. Let k ≥ 2, and 0 < δ < α.

λ k 1 -λ k-1 1 ≤ σf 1 (N )N -1/2 ∆ k-1 ≤ σf 1 (N )N -1/2 k-2 ∆ 1 (i) to k -1 ≤ N -2/3 (log N ) -C log log N k-2 ∆ 1 ≤ λ 1 -λ 2 2 k-2 ∆ 1 ≤ λ 1 -λ i 2 k-2 ∆ 1 .
Note that

∆ 1 = N j=2 σ λ 1 -λ i |m i,1 | ≤ σf 1 (N )N 1/2+δ . ≤ o( ).
Applying (ii) to k -1, we get

λ k 1 -λ i ≥ λ 1 -λ k-1 1 -λ k 1 -λ k-1 1 ≥ λ 1 -λ i 2 1 --. . . -k-2 - λ 1 -λ i 2 k-1 ≥ λ 1 -λ i 2 1 --. . . -k-1 .
Step 3: propagation of the third equation. Let k ≥ 1.

S k = 1 + N j=2 θ k j ≤ 1 + ∆ k + S k-1 -1 ≤ k-1 ∆ 1 (i) to k + 1 + 1 + . . . + k-2 ∆ 1 (iii) to k -1 ≤ 1 + 1 + + . . . + k-1 ∆ 1 .
Step 4: Proof of (i) for k = 1, 2, (ii) for k = 0, 1 and (iii) for k = 0, 1. The equation (i) for k = 1 is obvious. For k = 2 :

θ 2 i -θ 1 i ≤ σ λ 1 1 -λ i N j=2 θ 1 j -θ 0 j m i,j + σ λ 0 1 -λ 1 1 λ 1 1 -λ i λ 0 1 -λ i N j=1 θ 0 j m i,j .
We have

λ 1 1 -λ i ≥ |λ 1 -λ i | -λ 1 -λ 1 1 ≥ |λ 1 -λ i | -σ |m 1,1 | ≥ |λ 1 -λ i | - 1 2 |λ 1 -λ 2 | ≥ 1 2 |λ 1 -λ i | ,
which shows (ii) for k = 0, 1. Thus, for 0 < δ < α:

θ 2 i -θ 1 i ≤ 2σ λ 1 -λ i C 1 log N N ∆ 1 + 4σ (λ 1 -λ i ) 2 σ |m 1,1 | |m i,1 | . ∆ 2 ≤ σf 1 (N )N 1/2+δ ∆ 1 + 4σ |m 1,1 | N i=2 σ |m i,1 | (λ 1 -λ i ) 2 ≤ σf 1 (N )N 1/2+δ ∆ 1 + 4σf 4 (N )N -1/2 N 2/3 N i=2 σ |m i,1 | (λ 1 -λ i ) ≤ σf 1 (N )N 1/2+δ ∆ 1 + 4σf 4 (N )N 1/6 ∆ 1 ≤ ∆ 1 .
The proof of (iii) for k = 0, 1 is obvious.

Step 5: Proof of equation (iv). Let k ≥ 2 and 2 ≤ i ≤ N . In the same way than in Step 1, we have

θ k i -θ k-1 i ≤ 2σC 1 λ 1 -λ i log N N k-2 ∆ 1 + 8σ 2 C 2 1 (λ 1 -λ i ) 2 log N N (k-3) + ∆ 1 .
In the right-hand term, the ratio of the second term on the first one is smaller that

4σC 1 λ 1 -λ i log N N -1 ≤ σN 1/6 f (N ) -1 ≤ → 0,
using Lemma 3.4, with f ∈ F. It follows that for N big enough (uniformly in k and i) one has

θ k i -θ k-1 i ≤ σf (N ) λ 1 -λ i N -1/2 k-2 ∆ 1 . ( 33
)
From equation (33) and proof of Lemma 3.6, we deduce that the scheme ( 14) converges, and that the limits are the solutions of the fixed-point equations, θ 1 = 1, θ 2 , . . . , θ N . By a simple summation of (33) over k ≥ 2 we have

θ i -θ 1 i ≤ 2σf (N ) λ 1 -λ i N -1/2 ≤ 2σ 2 f (N ) λ 1 -λ i N δ ,
where δ is a positive quantity of Lemma 3.2 specified later. Using Lemma 3.3 one has the following control

N i=2 θ i -θ 1 i 2 ≤ 4σ 4 N 2δ f (N )N 4/3 .
Moreover, Lemma 3.5 shows that

N i=2 θ 1 i 2 σ 2 N 1/3 ≥ g(N ) -1 σ 2 N 1/3 ,
where g is another function in F. This yields

N i=2 θ i -θ 1 i 2 ≤ N i=2 θ 1 i 2 4σ 2 N 2δ+1 f (N )g(N ).
The proof is completed by taking δ = α/2 and applying [START_REF] Erdos | Rigidity of Eigenvalues of Generalized Wigner Matrices[END_REF].

Proof of Lemma 3.5

Proof of Lemma 3.5. We show that w.h.p.

N i=2 Hv i , v 1 2 (λ 1 -λ i ) 2 - 1 N N i=2 1 (λ 1 -λ i ) 2 = o 1 N N i=2 1 (λ 1 -λ i ) 2 (34)
Let us recall that H is drawn according to the GOE, hence its law is invaraiant by rotation. This implies that the Hv i , v 1 are independent variables with variance 1/N , independent of λ 1 , . . . , λ N . Define

M N := N i=2 Hv i , v 1 2 -1/N (λ 1 -λ i ) 2 .
Computing the second moment of M N , we get

E M 2 N |λ 1 , . . . , λ N = Var(M N |λ 1 , . . . , λ N ) = 1 N 4 N i=2 2 (λ 1 -λ i ) 4 .
Adapting the proof of Lemma 3.3, following the same steps, one can also show that w.h.p.

N i=2 1 (λ 1 -λ i ) 4 N 8/3 . ( 35
)
Let = (N ) > 0 to be specified later. By Markov's inequality Furthermore, for any f, g bounded continuous functions

P |M N | ≥ N N i=2 1 (λ 1 -λ i ) 2 |λ 1 , . . . , λ N ≤ N 2 2 E M 2 N |λ 1 , . . . , λ N N i=2 1 (λ 1 -λ i ) 2
∀O ∈ O n-1 v ⊥ 1 , E f ( w )g w w = E f ( w )g Ow Ow = E f ( w ) O n-1( v ⊥ 1 ) dH(O)g Ow Ow = E f ( w ) S n-2 g(u)du Vol (S n-2 ) = E [f ( w )] E g w w .
This completes the proof of Lemma 3.7.

Proof of Lemma 4.2

Proof of Lemma 4.2. We fix α > 0 and we want to prove

(N -1)/2 k=0 N -1 -k k α k = 1 √ 1 + 4α   1 + √ 1 + 4α 2 N - 1 - √ 1 + 4α 2 N   . ( 36
)
We denote in the following φ

+ := 1+ √ 1+4α 2 and φ -:= 1- √ 1+4α 2
, and for all N ≥ 1:

u N = u N (α) := (N -1)/2 k=0 N -1 -k k α k .
We clearly have u N (α) ≤ (1 + α) N . For all t > 0 small enough (e.g. t < 1 1+α ), define

f (t) := ∞ N =1 u N t N .
On one hand,

t 1 -t -αt 2 = t ∞ m=0 (t + αt 2 ) m = ∞ m=0 m l=0 m l α l t l+m+1 = ∞ N =1     0≤l≤m l+m=N -1 m l α l     t N = ∞ N =1 u N t N = f (t).
On the other hand,

t 1 -t -αt 2 = t (1 -φ -t) (1 -φ + t) = 1 φ + -φ - 1 1 -φ + t - 1 1 -φ -t = 1 √ 1 + 4α ∞ N =1 φ N + -φ N -t N .
This proves (36).

Proof of Lemma 5.2

Proof of Lemma 5.2. Let us represent the situation in the plane spanned by v 1 and v 1 , as shown on figure 4. Since v 1 is taken such that v 1 , v 1 > 0 and σ 1 satisfies (6), we have v 1 , v 1 > 0 for N large enough. Let p := v 1 , v 1 2 and w := v 1 -√ pv 1 ∈ (v 1 ) ⊥ . By invariance by rotation we can obtain that w w = w √ 1-p is uniformly distributed on the unit sphere S N -2 of (v 1 ) ⊥ , and independent of p, v 1 and v 1 . Hence b, v 1 = b, w

(d) = 1 -p • Z 1 N -1 i=1 Z i 2 ,
where the Z i are independent Gaussian standard variables, independent from everything else. By section 3 we know that 1 -v 1 , v 1 σ 2 1 N 1/3 and thus v 1 , b σ 1 N 1/6 . This yields, for N large enough, w.h.p,

0 < v 1 , v 1 ≤ √ p v 1 , v 1 + 1 -p N Z 1 σ 1 N 1/6 f (N ) ≤ √ p v 1 , v 1 + 1 -pN -4/3 g(N ) ≤ max √ p, 1 -p v 1 , v 1 ≤ v 1 , v 1 ,
where f and g are two functions as defined in Lemma 3.3. From this point one can still make the link with the toy model, as done in the beginning of section 4. By invariance by rotation, letting t := v 1 -v 1 , v 1 v 1 , we know that t and t t are independent, and that t t is uniformly distributed on the unit sphere in v ⊥ 1 . We have the following equalities in distribution:

r 1 (v 1 ) (d)
= r 1 (X), and r 1 ( v 1 )

(d)
= r 1 (X + sZ), with w.h.p.

s ≥ s 1 = w X N i=2 Z 2 i 1/2 1 - w Z 1 N i=2 Z 2 i 1/2 σ 1 N 1/6 ,
where the X i , Z i and w are defined in section 4, for σ = σ 1 .

Proof of Lemma 5.1

Proof of Lemma 5.1. Recall that we work in the case (i) (σ = o(N -7/6-) for some > 0), with v 1 , v 1 > 0 and Π = Id. We want to show that w.h.p.

A, Π + BΠ T + > A, Π -BΠ T -. ( 37
)
Define G := {i, Π + (i) = Π(i) = i} .

We use Markov's inequality with (38) to show that P G ≤ N -N A 2 i,j + (i,j) / ∈G 2 (Π + (i),Π + (j)) =(j,i) A i,j A Π + (i),Π + (j) + (i,j) / ∈G 2 (Π + (i),Π + (j))=(j,i)

A 2 i,j + σ 1≤i,j≤N A i,j H Π + (i),Π + (j) ≥ C 1 ( G) 2 N -C 2 N 2 -( G) 2 log N N -C 2 σN 2 log N N .
We applied the law of large numbers for the first sum, lower-bounded the third sum by zero, and the classical inequality max i,j {A i,j , H i,j } ≤ C 2 log N N (which holds w.h.p.) for the two others. Inequality (39) and condition (i) lead to, w.h.p.

A, Π + BΠ T + ≥ C 1 N -2C 1 N 1-/2 -2C 2 N 1-/2 log N -C 2 N -1/6-log N ≥ C 3 N.
On the other hand, since by definition Π -(i) = Π + (N + 1 -i), w.h.p.,

A, Π -BΠ T -= (i,j)∈G 2 A i,j B N +1-i,N +1-j + (i,j) / ∈G 2 A i,j B Π -(i),Π -(j) ≤ O(log N ) + ( G) 2 N o(1) + C 2 N 2 -( G) 2 log N N .
For the first sum, we used the law of large numbers: the variables A i,j and B N +1-i,N +1-j are independent in all cases but at most N + 1, and this part of the sum is bounded by O(log N ). We used the same control on Gaussian variables as above. This gives A, Π -BΠ T -+

= o P (N ), where (x) + := max(0, x), which proves (37).

Proof of Lemma 5.3

Proof of Lemma 5.3. Recall that we work in the case (ii) (σ = ω(N -7/6+ ) for some > 0), with v 1 , v 1 > 0 and Π = Id. We want to show that the aligning permutation between v 1 and -v 1 has a very bad overlap. Taking the couple (X, -Y ) where (X, Y ) ∼ J (N, s), one can adapt the proof of Proposition II, with the new definitions S +-(x, y) := P (X 1 > x, -Y 1 < -y) , and S -+ (x, y) := P (X 1 < x, -Y 1 > -y) .

The analysis is even easier since for all x, z, there exist two constants c, C such that 0 < c ≤ S +-(x, x + sz), S -+ (x, x + sz) ≤ C < 1.

It is then easy to check that the proof of Proposition II, case (ii) adapts well.

Figure 1 :

 1 Figure 1: Behavior of the empirical p(N, s) in the toy model (Proposition II) with different values of N and s. 1367 iterations per value of s.

Figure 2 :

 2 Figure 2: Behavior of the empirical overlap L( Π, Π) for Π = Id in model (2) (Theorem I), for different values of N and σ. 200 iterations per value of σ for N = 100, 100 for N = 500, 90 for N = 2000 and 15 for N = 5000.

Figure 3 :

 3 Figure 3: Areas corresponding to N +-(x, y) and N -+ (x, y).

2 1 2 N 2 , 7

 2227 by3.3 and equation (35). Taking e.g. (N ) = N -1/2 concludes the proof.Proof of Lemma 3.Proof ofLemma 3.7. Let O be an orthogonal transformation of the hyperplane v ⊥ 1 (such that Ov 1 = v 1 ). Since the GOE's law is invariant by rotation and A and H are independent, B := O T AO + σO T HO has he same distribution than B = A + σH. Ow = v 1 + Ow is an eigenvector of B for the eigenvalue λ 1 . Since the distribution of the matrix of eigenvectors (v 2 , . . . , v n ) is the Haar measure on the orthogonal group O n-1 v ⊥ 1 denoted sy dH(O), the distribution of w is also invariant by rotation in the orthogonal complement of v 1 .

Figure 4 :

 4 Figure 4: Orthogonal projection of v 1 on P := span(v 1 , v 1 ).

and A := σN 1 / 6 f

 16 (N ) -1 ≤ s ≤ σN 1/6 f (N ) , with f ∈ F such that P (A) → 1.For N large enough, on the event A, we have 0 ≤ sN ≤ N -f (N ). Hence, retaking the proof of Proposition II, we haveφ x,z (N, s) ≥ P N +-(x, x + sz) = N -+ (x, x + sz) = 0 ∼ exp (-sN E(x) [z(2F (z) -1) + 2E(z)]) = 1 -O(N -f (N )).Thus, with dominated convergence, for N large enough,P (Π + (i) = Π(i)|A) = dxdzE(x)E(z)E [φ x,z (N, s) |A] ≥ 1 -O(N -f (N )).

  1-/2 | A ≤ O N -/2 f (N ) , hence w.h.p. G ≥ N -N 1-/2 . A i,j B Π + (i),Π + (j) = A i,j B Π + (i),Π + (j) ,

			(39)
	Splitting the sum
	A, Π + BΠ T + =	A i,j B i,j +
	i,j	(i,j)∈G 2	(i,j) / ∈G 2
	one has, w.h.p.,
	A, Π + BΠ T + =
	(i,j)∈G 2

Acknowledgments

This work was partially supported by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program, reference ANR19-P3IA-0001 (PRAIRIE 3IA Institute).