Spectra of adjacency and Laplacian matrices of Erdős-Rényi hypergraphs
Soumendu Sundar Mukherjee Dipranjan Pal Himasish Talukdar











§ ABSTRACT 
We study adjacency and Laplacian matrices of Erdős-Rényi r-uniform hypergraphs on n vertices with hyperedge inclusion probability p, in the setting where r can vary with n such that r / n → c ∈ [0, 1). Adjacency matrices of hypergraphs are contractions of adjacency tensors and their entries exhibit long range correlations. We show that under the  Erdős-Rényi model, the expected empirical spectral distribution of an appropriately normalised hypergraph adjacency matrix converges weakly to the semi-circle law with variance (1 - c)^2 as long as d_/r^7→∞, where d_ = n-1r-1 p. In contrast with the Erdős-Rényi random graph (r = 2), two eigenvalues stick out of the bulk of the spectrum. When r is fixed and d_≫ n^r - 2log^4 n, we uncover an interesting Baik-Ben Arous-Péché (BBP) phase transition at the value r = 3. For r ∈{2, 3}, an appropriately scaled largest (resp. smallest) eigenvalue converges in probability to 2 (resp. -2), the right (resp. left) end point of the support of the standard semi-circle law, and when r ≥ 4, it converges to √(r - 2) + 1/√(r - 2) (resp. -√(r - 2) - 1/√(r - 2)). Further, in a Gaussian version of the model we show that an appropriately scaled largest (resp. smallest) eigenvalue converges in distribution to c/2ζ + [c^2/4ζ^2 + c(1 - c)]^1/2 (resp. c/2ζ - [c^2/4ζ^2 + c(1 - c)]^1/2), where ζ is a standard Gaussian. We also establish analogous results for the bulk and edge eigenvalues of the associated Laplacian matrices.


[NO \title GIVEN]
    [NO \author GIVEN]
    September 9, 2024
======================





§ INTRODUCTION



 §.§ Hypergraphs and associated matrices and tensors

A hypergraph = (V, E) consists of a vertex set V and a set E ⊆ 2^V of  hyperedges. If |e| = r for all e ∈ E, then  is called r-uniform. If hyperedges of different sizes exist, then it is called non-uniform. Usually V is taken to be the set [n] := {1, …, n }. Hypergraphs are generalisations of graphs (indeed, a simple undirected graph is just a 2-uniform hypergraph) and are very useful for modelling higher-order interactions in various types of complex networks. In particular, hypergraphs have been used for community detection in networks <cit.>, in biology <cit.>, for modelling chemical reactions <cit.>, in modelling citation networks <cit.>, in recommendation systems <cit.> and for processing image data <cit.>, among other areas.

Adjacency matrices of graphs naturally generalise to adjacency tensors for hypergraphs. Let  be an r-uniform hypergraph, where r ≥ 3 is an integer. The adjacency tensor 𝒜∈{0,1}^n^r associated with  is defined as

    _i_1, i_2, ⋯, i_r   = 
           1     if  {i_1, i_2, …, i_r}∈ E, 
    
           0     otherwise,

and _i_1, i_2, ⋯, i_r = _σ(i_1), σ(i_2), ⋯, σ(i_r) for any σ∈_n, where _n is the set of all permutations of [n]. This is a tensor of order r and dimension n. In this article, we consider an adjacency matrix A associated to , which is a contraction of the adjacency tensor  and is defined as follows:

    A_ij = 1/(r - 2)!∑_i_3, i_4, ⋯, i_r_i, j, i_3, i_4 ⋯, i_r.

Observe that

    A_ij = ∑_e ∈ E(i, j ∈ e)    if  i  j, 
    
            0    otherwise.

We note that different aspects of the matrix A have been studied in the literature <cit.>.

Let M = nr and {e_1, …, e_M} be an enumeration of the hyperedges of the complete r-uniform hypergraph on n vertices. Consider the following matrices

    Q_ℓ := _ℓ_ℓ^⊤ - (_ℓ),    1 ≤ℓ≤ M,

where

    (_ℓ)_i = 
        1    if  i ∈ e_ℓ, 
     
        0    otherwise,

and for a vector , () denotes the diagonal matrix whose diagonal entries are given by . Note then that A admits the following representation:

    A = ∑_ℓ = 1^M h_ℓ  Q_ℓ,

where h_ℓ= (e_ℓ∈ E) indicates if hyperedge e_ℓ is present in the hypergraph . 

We also consider the associated Laplacian matrices. Recall that for r = 2, i.e. when A is the adjacency matrix of a simple undirected graph, the associated (combinatorial) graph Laplacian is defined as

    L_A = (A) - A.

Where  is an n × 1 vector with all entries 1. More generally, for any matrix X, define the associated Laplacian matrix as

    L_X := (X ) - X.

We also consider the variant

    L̃_X := 1/r - 1(X ) - X.

Note that for r = 2, L_X = L̃_X, as such both of these matrices generalise the graph Laplacian.



 §.§ Preliminaries on random matrices
 Let A_n be an n × n Hermitian matrix with ordered eigenvalues λ_1 ≥⋯≥λ_n. The probability measure 

    μ_A_n := 1/n∑_i = 1^n δ_λ_i

is called the Empirical Spectral Distribution (ESD) of A_n. If entries of A_n are random variables defined on a common probability space (Ω, , ) then μ_A_n is a random probability measure. In that case, there is another probability measure associated to the eigenvalues, namely the Expected Empirical Spectral Distribution (EESD) of A_n, which is defined via its action on bounded measurable test functions f as follows:

    ∫ f   d_A_n = ∫ f   dμ_A_n,

where  denotes expectation with respect to . In random matrix theory, one is typically interested in an ensemble (A_n)_n ≥ 1 of such matrices of growing dimension n. If the weak limit, say μ_∞, of the sequence (_A_n)_n ≥ 1, exists, then it is referred to as the Limiting Spectral Distribution (LSD). Often one is able to show that the random measure μ_A_n also converges weakly (in probability or in almost sure sense) to μ_∞. For a comprehensive introductory account of the theory of random matrices, we refer the reader to <cit.>.

The preeminent model of random matrices is perhaps the Wigner matrix. For us a Wigner matrix W_n will be a Hermitian random matrix whose upper triangular entries W_n, i, j are i.i.d. zero mean unit variance random variables and the diagonal entries W_n, i, i are i.i.d. zero mean random variables with finite variance. Moreover, the diagonal and the off-diagonal entries are mutually independent. If the entries are jointly Gaussian with the diagonal entries having variance 2, then resulting ensemble of matrices is called the Gaussian Orthogonal Ensemble (GOE). In this article, we will denote the centered Gaussian distribution with variance σ^2 by ν_, σ^2.

We also define the semi-circle distribution with variance σ^2, henceforth denoted by ν_, σ^2, as the probability distribution on  with density

    f(x) := 1/2πσ^2√(4 σ^2 - x^2)   if  |x| ≤ 2 σ, 
    
        0     otherwise.

E. Wigner proved in his famous paper <cit.> that the EESD of n^-1/2 W_n converges weakly to the standard semi-circle distribution ν_, 1. It is well known that 2k-th moment of the standard semi-circle distribution is the k-th Catalan number, defined as

    C_k := 1/k + 12kk.

Catalan numbers have many interesting combinatorial interpretations. Most notably, C_k counts the number of Dyck paths of length 2k, i.e. the number of non-negative Bernoulli walks of length 2k that both start and end at the origin.



 §.§ Note on asymptotic notation

Before proceeding further, we define here various asymptotic notations used throughout the paper. For functions f, g : →, we write (i) f(n) = O(g(n)), if there exist positive constants n_0 and C such that |f(n)| ≤ C |g(n)| for all n ≥ n_0; (ii) f(n) = o(g(n)) or f(n) ≪ g(n) if lim_n →∞f(n)/g(n) = 0 (we also write f(n) ≫ g(n) if g(n) ≪ f(n)); (iii) f(n) = Θ(g(n)) or f(n) ≍ g(n) if f(n) = O(g(n)) and g(n) = O(f(n)); (iv) f(n) ∼ g(n) if lim_n →∞f(n)/g(n) = 1; (v) f(n) ≫ g(n) if lim_n →∞g(n)/f(n) = 0.

For a sequence of random variables {X_n}_n ≥ 1, we write X_n = O_P(1) if for any ϵ > 0, there exists M > 0 such that sup_n (|X_n| > M) ≤ϵ. For two sequence of random variables {X_n}_n ≥ 1 and {Y_n}_n ≥ 1 we write X_n = O(Y_n) to mean X_n = Z_n Y_n with Z_n = O_P(1). 



 §.§ Our random matrix model
 In this article, our main objective is to study the ESDs of adjacency matrices of Erdős-Rényi random r-uniform hypergraphs, where each hyperedge is included independently with probability p, i.e. h_ℓi.i.d.∼(p). Towards that end, consider the centered (and normalised) matrix

    Ã = A - [A]/√(p(1 - p))= ∑_ℓ=1^M(h_ℓ - [h_ℓ])/√((h_ℓ))  Q_ℓ = ∑_ℓ = 1^M Y_ℓ  Q_ℓ.

Note that Y_ℓ's are i.i.d. zero mean unit variance random variables. Thus

    Ã_ij = ∑_ℓ = 1^M Y_ℓ·(i, j ∈ e_ℓ)    if  i  j, 
    
        0    otherwise.

Note that

    ( Ã_ij ) = ( ∑_ℓ = 1^M Y_ℓ·(i, j ∈ e_ℓ)) = ∑_ℓ = 1^M(Y_ℓ) (i, j ∈ e_ℓ) = n-2r-2.

Therefore, we shall consider the following normalised matrix (viewed as a matrix-valued function of the vector = (Y_ℓ)_1≤ℓ≤ M)

    H_n ≡ H_n() := Ã/√(N) = 1/√(N)∑_ℓ = 1^M Y_ℓ  Q_ℓ,

where N = n - 2r - 2, so that the all off-diagonal entries of H_n have zero mean and unit variance. This normalisation ensures that the variance of the EESD of H_n is of order n^2 (comparable to that of a usual Wigner matrix).


Let = (Y_ℓ)_1 ≤ℓ≤ M be independent zero mean unit variance random variables. The matrix H_n = H_n() defined in (<ref>) will be referred to as a Generalised Hypergraph Adjacency Matrix (GHAM). 

A principal feature of this ensemble is that the entries show long-range correlation. Indeed,

    (Ã_ij, Ã_i'j') 
        = ∑_ℓ = 1^M∑_ℓ' = 1^M(Y_ℓ,  Y_ℓ')  (i, j ∈ e_ℓ) (i', j' ∈ e_ℓ') 
       =  ∑_ℓ = 1^M(Y_ℓ)  (i, j ∈ e_ℓ) (i', j' ∈ e_ℓ) 
       = n-4r-4   if  |{i, j}∩{i', j' }| = 0, 
    n-3r-3   if  |{i, j}∩{i', j' }| = 1.

Therefore

    (H_n, ij, H_n, i^'j^')    = n-4r-4/n-2r-2 = (r-2)(r-3)/(n-2)(n-3) =: ρ_n    if  |{i, j}∩{i^', j^'}| = 0, 
    n-3r-3/n-2r-2 = r-2/n-2 =: γ_n    if  |{i, j}∩{i^', j^'}| = 1.


In this article, we are interested in the spectrum of n^-1/2 H_n in the regime where r grows with n in such a way that r/n→ c ∈ [0, 1). Our main result regarding the bulk spectrum of n^-1/2 H_n is the following.

    Suppose the entries (Y_ℓ)_1 ≤ℓ≤ M satisfy the Pastur-type condition given in Assumption <ref>. Then the EESD of n^-1/2 H_n converges weakly to ν_, (1 - c)^2.

For two probability measures μ an ν, let μ⊞ν denote their free additive convolution (defined in Section <ref>).

  
Suppose the entries (Y_ℓ)_1 ≤ℓ≤ M satisfy the Pastur-type condition given in Assumption <ref>.
   
       
  (i) Suppose that r is fixed. Then the EESD of n^-1/2L_H_n converges weakly to ν_, r - 1⊞ν_, 1 and the EESD of n^-1/2L̃_H_n converges weakly to ν_,1/r - 1⊞ν_, 1. 
       
  (ii) Suppose r →∞ such that r/n → c ∈ [0, 1).
       Then the EESD of (nr)^-1/2 L_H_n converges weakly to ν_, 1⊞ν_, c and the EESD of n^-1/2L̃_H_n converges weakly to ν_, (1 - c)^2.

In fact, for L_H_n we only need the weaker Assumption <ref> on the entries.


Theorems <ref> and <ref> follow from a universality result (see Theorem <ref>) and an analysis of the Gaussian case, where (Y_ℓ)_1 ≤ℓ≤ M are i.i.d. standard Gaussians (see Theorems <ref> and <ref>).
In the regime r/n → 0, we also prove effective concentration inequalities for the ESD (see Corollary <ref>)  assuming further conditions on the entries Y_ℓ, which enable us to show in-probability weak convergence of the ESDs (see Corollary <ref>). Further, if r √(log n) / n → 0, we have almost sure weak convergence of the ESDs. The question of almost sure weak convergence of the ESDs in the full regime r / n → c ∈ [0, 1) will be considered in a future work. In Figure <ref>, we show the ESDs of 300 × 300 GHAMs with Gaussian entries for various choices of r. 



Let us now briefly comment on the implications of the above result in the context of hypergraphs. Let the hyperedge inclusion probability p be potentially dependent on both n and r. Let us also assume for simplicity that p is bounded away from 1. In analogy with random graphs, the quantity d_ = n - 1r - 1 p may be thought of as the “average degree” of a vertex. In fact, it is the expected number of hyperedges containing the said vertex. For r = 2, i.e. random graphs, it is well known that the limit of the EESD is the semi-circle law as long as d_ = (n - 1) p →∞, see <cit.> for more details. We show in Example <ref> that our assumptions on the entries are satisfied as long as d_ / r^7 →∞ (in fact, for the Laplacian L_H_n we only need that d_/r^4 →∞). In the setting of fixed r, we thus have a semi-circle limit as long as d_→∞. However the the factor r^7 is likely sub-optimal and an artefact of the Lindeberg exchange argument <cit.> that we employ. Consider also the setting where r / n → c ∈ (0, 1). Let I(x) = - x log x - (1 - x) log (1 - x) denote the entropy of a (p) random variable. Then note that

    d_/r^7∼exp(I(c) n)/n^15/2 c^7 √(c(1 - c)) p.

Thus for obtaining the limit ν_, (1 - c)^2, we need

    p ≫ n^15/2exp(- I(c) n).

It would be interesting to understand what happens at complementary regimes of sparsity. We leave this for future work.

Unlike the random graph setting (r = 2), two eigenvalues stick out of the bulk of the spectrum. We can derive limits of appropriately scaled largest and smallest eigenvalues for the Gaussian GHAM. The following is an abridged version of Theorem <ref>.

Let H_n be a Gaussian GHAM and suppose that ζ is a standard Gaussian. In the regime r/n → c ∈ (0,1), we have 
  
    λ_1(H_n)/nc/2ζ + √(c^2/4ζ^2 +c(1-c))  and  λ_n(H_n)/nc/2ζ - √(c^2/4ζ^2 + c(1-c)).

  When r →∞ and r/n → 0, we need a rescaling:
 
    λ_1(H_n)/√(nr) 1   and  λ_n(H_n)/√(nr) -1.

 Finally, when r is fixed, we have
     
    λ_1(H_n)/√(n)   √(r-2) + 1/√(r-2)    if  r ≥ 4, 
    
                2     if  r ≤ 3,
            
    λ_n(H_n)/√(n)   
                -√(r-2) - 1/√(r-2)    if  r ≥ 4, 
    
                -2     if  r ≤ 3.


Noteworthy here is the phase transition at r = 3. The underlying reason for this is the so-called Baik-Ben Arous-Péché (BBP) transition for deformed Wigner matrices. This phase transition result remains valid for the original hypergraph adjacency matrix as well due to the strong universality results proved in <cit.>, provided that p ≫log^4 n/n which in terms of d_ reads d_≫ n^r - 2log^4 n (see the discussion in Section <ref>).

The behaviour of the extreme eigenvalues of the two Laplacian matrices is given in Theorem <ref>.



 §.§ Related works on hypergraph and tensor spectra

Spectra of hypergraphs had drawn the attention of researchers at least twenty years ago. Indeed, <cit.>
studied the spectrum of (d,r)-regular hypergraphs and identified the LSD, which generalizes the work of <cit.> for random regular graphs. <cit.> studied the spectra of the so-called loose Laplacians of an Erdős-Rényi hypergraph. <cit.> studied the adjacency tensor of (deterministic) uniform hypergraphs. <cit.> studied various aspects of the adjacency tensor for random k-uniform hypergraphs.

Friedman <cit.> was the first to define the “second eigenvalue" of a multilinear form, analogous to the bilinear forms associated with the adjacency matrix of a graph, for both deterministic and random d-regular r-uniform hypergraphs, and provided explicit expressions for it. In a follow-up work, <cit.> introduced the notion of regular infinite hypertrees and established that the “first eigenvalue” of an infinite hypertree agrees with the “second eigenvalue" of a random regular hypergrpah of the same degree within a logarithmic factor. On the other hand, <cit.> attempted to define an analogue of the Laplacian for hypergraphs, but encountered various obstacles that made the generalisation difficult. It was Chung <cit.>, who paved the way by defining the Laplacian for hypergraphs in full generality using homological considerations. <cit.> further enriched the study by introducing an adjacency graph of hypergraphs, examining the spectra of the Laplacian for d-regular hypergraphs, and improving the lower bound for the “spectral value” of the Laplacian defined in <cit.>. <cit.> proposed another definition of a Laplacian tensor associated with even and uniform hypergraphs and analysed its connection with edge and vertex connectivity. <cit.> examined the eigenvalues of adjacency tensor also known as 'hypermatrix' of uniform hypergraphs and established several natural analogues of basic results in spectral graph theory. <cit.> introduced another definition for the Laplacian tensor of an even uniform hypergraph, proved a variational formula for its second smallest Z-eigenvalue, and used it to provide lower bounds for the bipartition width of the hypergraph. <cit.> proposed a definition for the signless Laplacian tensor of an even uniform hypergraph, studied its largest and smallest H-eigenvalues and Z-eigenvalues, as well as its applications in the edge cut and the edge connectivity of the hypergraph. In <cit.> they also investigated the largest and the smallest Z-eigenvalues of the adjacency tensor of a uniform hypergraph. Pearson and Zhang <cit.> studied the H-eigenvalues and the Z-eigenvalues of the adjacency tensor of a uniform hypergraph. <cit.> studied H^+-eigenvalues of normalized Laplacian tensor of uniform hypergraphs and showed that the second smallest H^+-eigenvalue is positive if and only if the hypergraph is connected. Until now, the literature has primarily focused on uniform hypergraphs. <cit.> was the first to introduce adjacency hypermatrix, Laplacian hypermatrix and normalized Laplacian hypermatrix for general hypergraphs, and extensively studied various spectral properties of these tensors. In addition to adjacency and Laplacian tensors, researchers have also suggested different types of adjacency and Laplacian matrices associated with hypergraphs. 

In a series of papers <cit.>, Rodríguez introduced an n × n Laplacian matrix similar to ours and studied how the spectrum of this Laplacian relates to various structural properties of hypergraphs such as the diameter, the mean distance, excess, etc., as well as its connection to the hypergraph partition problem.  <cit.> also studied adjacency and Laplacian matrices, which are the same as the matrices we consider up to minor scaling factors and showed how the various structural notions of connectivity, vertex chromatic number and diameter are related to the eigenvalues of these matrices. Building on the work of <cit.>, 
<cit.> examined the spectral properties of the Laplacian matrix in greater detail. Specifically, they obtained bounds on the spectral radius of uniform hypergraphs in terms of some invariants of hypergraphs such as the maximum degree, the minimum degree, etc. A more general treatment is provided in <cit.>, where the authors generalized the concepts of adjacency and Laplacian matrices for hypergraphs by introducing general adjacency operators and general Laplacian operators.

The study of Laplacian matrix for Wigner matrices was initiated in <cit.>. Later, <cit.> considered the Laplacian matrix for sparse Erdős-Réyni random graphs. The normalized Laplacian in the non-sparse setting was studied in <cit.>. For Wigner matrices with a variance profile, the spectrum  of the Laplacian matrix was analysed in <cit.>.

More generally, in the random tensor front, <cit.> considered a tensor version of the Gaussian Orthogonal Ensemble (GOE). He showed that the expectation of an appropriate generalisation of the resolvent can be described by a generalised Wigner law, whose even moments are the Fuss-Catalan numbers. There has been a flurry of activity surrounding random tensors in the past few years <cit.>. Among these, the most relevant to our setting are <cit.>. The papers <cit.> considered contractions of random tensors to form random matrices. <cit.> considered the above-mentioned tensor version of the GOE and showed that for any contraction along a direction ∈^n - 1, one gets a semi-circle law as the LSD. This result also follows from the work of <cit.> who studied more general contractions. <cit.> obtained the same result for more general entries. They also established joint convergence of a family of contracted matrices in the sense of free probability.

The only difference between our adjacency tensor  and a Wigner random tensor is that for us

    _i_1, …, i_r = 0  if  |{i_1, …, i_r}| < r.

Modulo this difference, it is clear that one obtains our hypergraph adjacency matrix A by contracting the adjacency tensor  along the direction / √(n). Using the Hoffmann-Wielandt inequality it is not difficult to show that if r is fixed, then zeroing out the elements _i_1, …, i_r of a Wigner random tensor  for any (i_1, …, i_r) such that |{i_1, …, i_r}| < r does not affect the bulk spectra of its contractions. Therefore for fixed r, our Theorem <ref> follows from the Theorem 1.5 of <cit.>
 (or Theorem 2 of <cit.> or Theorem 4 of <cit.> in the tensor GOE case).

We emphasize that unlike our setting where the order r of the tensor grows with the dimension n, the above-mentioned existing works on random tensors or contractions thereof consider the setting of fixed r. To the best of our knowledge only two lines of work consider settings where r, the common size of the hyperedges, grow with n, namely in quantum spin glasses <cit.> and in the Sachdev-Ye-Kitaev (SYK) model for black holes <cit.>. Both of these models consider matrices representable as random linear combinations of deterministic matrices, with the i.i.d. random weights being indexed by the hyperedges of a complete r-uniform hypergraph (exactly like the representation (<ref>) of a GHAM). In both of these works, a phase transition phenomenon is observed at the phase boundary r ≍√(n): When r ≪√(n), the LSD is Gaussian; when r ≫√(n), the LSD is the standard semi-circle law; and when r/√(n)→ c > 0, a different LSD emerges.



 §.§ Related works on Hermitian matrices with dependent entries


We will refer to Hermitian random matrices with dependent entries as dependent/correlated Wigner matrices. Various different types of correlated Wigner matrices has been studied in the literature in great detail. Here we will recall some of these existing works and compare them to our results.

Chapter 17 of <cit.> considered a class of random n × n real symmetric matrices of the form

    H = H^(0) + n^-1/2 W,

where H^(0) is a given real symmetric matrix and W = {W_jk}_j,k = -m^m, n = 2m + 1, is a real symmetric random matrix, the n × n central block of the double-infinite matrix W_∞ = {W_jk}_j,k = -∞^∞ whose entries are Gaussian random variables with

    W_jk = 0,   W_j_1 k_1 W_j_2 k_2 = C_j_1k_1 ; j_2 k_2.

The authors assume that

    C := sup_j_1,k_1 ∈∑_j_2, k_2 ∈|C_j_1k_1 ; j_2 k_2| < ∞.

Approximate versions of conditions like these are clearly not satisfied by our model where  the sum of the pairwise absolute correlations between a given entry and all the other entries grows like r^2.

<cit.> and <cit.> considered correlated Gaussian Wigner models where the entries come from stationary Gaussian fields. However, this specific structural assumption makes their models incompatible with ours. (Further, they also require summability of the pairwise correlations.)

Another dependent model was considered by <cit.> where the entries (X_ij)_1 ≤ i ≤ j ≤ n form a dependent random field. One of their main assumptions however is that [X_ij |_ij ] = 0, where _ij is the σ-algebra generated by the entries other than X_ij. This implies that

    [X_ij X_i'j'] =  [ [X_ij X_i'j' | _ij] ] =  [X_i'j' [X_ij|_ij]] = 0,

i.e. the matrix entries are uncorrelared. This rules out a direct application of their method to our set-up. Notably, their proof technique for showing universality, which uses an interpolation between their random matrix model and a Wigner matrix, can be modified to work in a situation where [X_ij|_ij]  0 (we note here that the same result can also be proved by the Lindeberg exchange argument of <cit.>). However, the resulting universality result turns out to be too weak to be applicable to our setting (in our notation, it requires r to go to 0).

To the best of our knowledge, bulk universality results for the most general correlated model is obtained in <cit.> with appropriate decay conditions on the joint cumulants of the entries. For a Gaussian model, they require the operator norm of the covariance matrix of the entries to be O(N^ϵ) for any ϵ > 0. In our setting the operator norm is of order r^2 and hence their results do not apply to the setting of polynomially growing r.

It is also worth mentioning the remarkably general work of
<cit.>, who consider matrices of the form X = Z_0 + ∑_i= 1^n Z_i, where Z_0 is a deterministic matrix and Z_i's are d× d independent self-adjoint random matrices. Under appropriate conditions on these matrices the authors of <cit.> prove strong universality results. Owing to the representation (<ref>), our adjacency matrix clearly falls under this rather general model. Unfortunately, the universality results proved in <cit.> do not work beyond the regime r ≪ n^1/4. This is still powerful enough to give us universality of the edge eigenvalues for fixed r and hence of the BBP-type phase transition at r = 3 described earlier. Below we quickly work out this universality result, assuming that the Y_ℓ's are uniformly bounded.

Let d_H(A, B) denote the Hausdorff distance between two subsets A, B ⊂. For a symmetric matrix A, let (A) denote its spectrum. Theorem 2.6 of <cit.> shows that if the matrices Z_i are uniformly bounded, then

    (d_H((X), (G)) > C ε(t)) ≤ d e^-t,

where G is a Gaussian random matrix with the same expectation and covariance structure as X and 

    ε(t) = σ_*(X) t^1/2 + R(X)^1/3σ(X)^2/3 t^2/3 + R(X) t,

with

    v(X)    := (X)_^1/2, 
    σ(X)    := [(X -  X)^2]_^1/2, 
    σ_*(X)    = sup_v = w = 1[|⟨ v, (X -  X) w⟩|]^1/2, 
    
        R(X)    := max_1 ≤ i ≤ nZ_i__∞.

Let us now calculate these parameters for X = n^-1/2 H_n. First note that 

    v(X)    = (X)_^1/2 = O([maximum row sum of (X)]^1/2) 
       = 1/√(n)· O([Θ(n) ·r/n + Θ(n^2) ·r^2/n^2]^1/2) 
       = O(r/√(n)).

Since (H_n^2)_ij = ∑_k  i, j H_n, ik H_n, kj = (r - 2) and (H_n^2)_ii = ∑_k  i H_n, ik^2 = (n - 1), we have

    H_n^2 = (n - 1) I + (r - 2) (J - I) = (n - r + 1) I + (r - 2) J,

where J = ^⊤. It follows that

    σ(X):= [(X -  X)^2]^1/2 = 1/√(n)· H_n^2 _^1/2 = √(n + r - 1 + n (r - 2))/√(n) = Θ(√(r)).

We also have

    σ_*(X) ≤ v(X) = O(r/√(n)).

Finally, assuming that the Y_ℓ's are uniformly bounded, by say K, we have

    R(X) := 1/√(n)·max_1 ≤ℓ≤ MY_ℓ Q_ℓ__∞≤K r/√(n).

Thus

    ε(t) = O( r t^1/2/√(n) + (Kr/√(n))^1/3· r^1/3 t^2/3 + K r t/√(n)).

Choosing t = 2 log n, yields that with probability at least 1 - 1/n, we have

    d_H((n^-1/2H_n()), (n^-1/2 H_n()) = O( r √(log n)/√(n) + K^1/3·(r^2 log^2 n/√(n))^1/3 + K r log n/√(n)).

It is evident that the above upper bound is small if r ≪n^1/4/√(K)log n, assuming that K is constant, which is, for instance, the case for the hypergraph, where one can take K = max{√(p/1 - p), √(1 - p/p)}. Assuming that p < 1/2, the above condition for universality simplifies to r ≪(np)^1/4/log n.



 §.§ Organisation of the paper.

The rest of the paper is organised as follows: In Section <ref>, we formally describe the main results of this paper. Section <ref> contains the proofs of these results. Finally, in Appendix <ref>, we collect some useful results from matrix analysis and concentration of measure which are used throughout the paper, and in Appendix <ref> we provide proofs of some technical results.



§ MAIN RESULTS

In the first three subsections, we study the bulk of the spectrum. In the last subsection, we study the edge eigenvalues.


 §.§ Replacing general entries with Gaussians

We first employ a Lindeberg swapping argument <cit.> to replace the independent zero mean unit variance random variables Y_ℓ in the definition of H_n by i.i.d. standard Gaussians. Recall that M = nr and N = n - 2r - 2. We will need a Pastur-type condition on the entries (Y_ℓ)_1≤ℓ≤ M.

[A Pastur-type condition]

Suppose (Y_ℓ)_1 ≤ℓ≤ M are independent zero mean unit variance random variables satisfying the following condition: For every ε > 0,

    r^4/n^2 N∑_ℓ = 1^M [Y^2_ℓ(|Y_ℓ| > ε K_n)] → 0   as   n →∞,

where K_n = √(n N)/r^4.

For dealing with the Laplacian L_H_n we need a weaker assumption.
[A (weaker) Pastur-type condition]

Suppose (Y_ℓ)_1 ≤ℓ≤ M are independent zero mean unit variance random variables satisfying the following condition: For every ε > 0,

    r^3/2/n^2 N∑_ℓ = 1^M [Y^2_ℓ(|Y_ℓ| > ε K_n')] → 0   as   n →∞,

where K_n' = √(n N)/r^5/2.


    For r fixed, Assumptions  <ref> and <ref> are clearly equivalent. For r = 2, they become Pastur's condition <cit.>. In general, Assumption <ref> is stronger than Assumption <ref>. Indeed, K_n' > K_n and hence

    r^3/2/n^2 N∑_ℓ = 1^M [|Y_ℓ|^2 (|Y_ℓ| > ε K_n')]    ≤r^3/2/n^2 N∑_ℓ = 1^M [|Y_ℓ|^2 (|Y_ℓ| > ε K_n)] 
       ≤1/r^5/2r^4/n^2 N∑_ℓ = 1^M [|Y_ℓ|^2 (|Y_ℓ| > ε K_n)].

    So if (Y_ℓ)_1 ≤ℓ≤ M satisfy Assumption <ref>, then they also trivially satisfy (<ref>).


    For i.i.d. random variables (Y_ℓ)_1 ≤ℓ≤ M with mean 0 and variance 1, Assumption <ref> becomes the following tail condition:
    
    [Y_1^2 (|Y_1| > ε K_n)] = o(r^-2)

    for any ε > 0.


Our first result shows the universality of the EESD in the limit, assuming that the entries satisfy Assumption <ref>, i.e. the limiting EESD, if it exists, is the same as that of a GHAM with Gaussian entries. The proof of this result is via a comparison of Stieltjes transforms. Recall that the Stieltjes transform S_μ of a probability measure μ on  is an analytic function defined for z ∈ℂ_+ := {z ∈ : (z) > 0} as follows:

    S_μ(z) := ∫dμ(x)/x-z.

Suppose {μ_n}_n ≥ 1, μ are probability measures on ℝ with Stieltjes transforms {S_μ_n}_n ≥ 1 and S_μ, respectively. It is well known than S_μ_n→ S_μ pointwise on _+ if and only if μ_n →μ weakly (see, e.g., <cit.>). With this result in mind, the universality of the limiting EESD is given by our first theorem.


Suppose r/n → c ∈ [0, 1). Suppose = (Y_ℓ)_1 ≤ℓ≤ M satisfies Assumption <ref>. Let = (Z_ℓ)_1 ≤ℓ≤ M be a vector of i.i.d. standard Gaussians. Then for any z ∈_+,
    
    lim_n → 0| S__B_n()(z) - S__B_n()(z)| = 0

    where B_n() is any one of the matrices n^-1/2 H_n(), (nr)^-1/2L_H_n() or n^-1/2L̃_H_n(). In fact, for the result with B_n() = (nr)^-1/2 L_H_n(), we only need Assumption <ref> on the entries of .


We now look at some situations where Assumption <ref> holds.

    Clearly, the tail condition in (<ref>) (and hence Assumption <ref>) is satisfied by i.i.d. bounded random variables (Y_ℓ)_1 ≤ℓ≤ M with zero mean and unit variance. This already covers the case of dense hypergraphs, where the hyperedge inclusion probability p is bounded away from zero. 



    Suppose that (Y_ℓ)_1 ≤ℓ≤ M are i.i.d. zero mean unit variance random variables with |Y_1|^2 + δ≤ C for some δ, C > 0. Then Assumption <ref> is satisfied for any sequence r_n satisfying 2 ≤ r_n < n - ⌈ 3 + 2/δ⌉. As a consequence, i.i.d. standard Gaussians satisfy Assumption <ref> for 2 ≤ r_n ≤ n - 4.

    Indeed, by Hölder's inequality, we have for conjugate exponents p, q ≥ 1 satisfying 1/p + 1/q = 1,
    
    [Y_1^2 (|Y_1| > K_n)]    ≤ ( |Y_1|^2p)^1/p   (|Y_1| > K_n)^1/q
       ≤ ( |Y_1|^2p)^1/p   (|Y_1|^2 + δ)^1/q    K_n^-(2 + δ)/q  (by Markov's inequality).

    For 2p = 2 + δ (which gives q = (2 + δ) / δ), this gives
    
    [Y_1^2 (|Y_1| > ε K_n)] ≤ |Y_1|^2 + δ/ε^δ K_n^δ =  |Y_1|^2 + δ/ε^δ (nN)^δ/2 r^-4δ.

    The right hand side is o(r^-2) if
    
    r^2 + 4 δ/(nN)^δ = o(1).

    Now since
    
    r^2 + 4 δ/(nN)^δ = (r/n)^δ   r^2 + 3 δ/N^δ≤r^2 + 3 δ/N^δ,

    we need
    
    nr≫ r^3 + 2/δ.

    We claim that this is always true. Let a = ⌈ 3 + 2 /δ⌉+ 1. Then for a ≤ r ≤n/2,
    
    nr≥na≥n^a/a^a≥ C_δ n^⌈ 3 + 2 / δ⌉ + 1≫ n^3 + 2 / δ≥ r^3 + 2/δ.

    On the other hand, for 2 ≤ r < a, (<ref>) is trivially true. 

    For n/2 < r < n - ⌈ 3 + 2/δ⌉, by symmetry of the binomial coefficients,
    
    nr = nn - r≥na≫ n^3 + 2/δ,
  
    as before.



    Suppose that (Y_ℓ)_1 ≤ℓ≤ M are i.i.d. zero mean unit variance random variables and consider the regime where r ∼ c n, where c ∈ (0, 1), we have N = n - 2r - 2∼c^2 exp(I(c) n)/√(c(1 - c) n), where I(x) = -x log x - (1 - x) log (1 - x) is the entropy of a (x) random variable. In this regime, K_n = Θ(e^C n) for some constant C > 0 (depending on c) and the tail condition (<ref>) becomes rather mild:
    
    [Y_1^2 (|Y_1| > ε e^C n) ] = o(n^-2)   for any ε > 0.

    For instance, a random variable whose density decays as fast as 1/|x|^3 (log |x|)^3 + δ as |x| →∞, for some δ > 0 will satisfy this condition. Such random variables need not possess a (2 + η)-th moment for any η > 0.


[Dependence on sparsity] 
    Consider the setting of hypergraphs, where (Y_ℓ)_1 ≤ℓ≤ M are i.i.d. with Y_1 = B - p/√(p(1 - p)), where B ∼(p). If p is not bounded away from 0 and 1, then |Y_1| is not uniformly bounded anymore. Instead,
    
    |Y_1|≤max{√(p/1-p),√(1-p/p)}≤1/√(min{p, 1-p}).

    The left hand side of (<ref>) vanishes for every ε > 0 as long as
    
    nN/r^8min{p,1-p}→∞.

    Assume now that p is bounded away from 1. For d_ = n - 1r - 1 p, the average degree of a vertex, we note that
    
    d_ = n - 1r - 1 p ≍n/r N p ≍ r^7 ·nN/r^8min{p, 1 - p}.

   The condition (<ref>) thus becomes equivalent to the condition d_ / r^7 →∞. For comparison, in the random graph case (i.e. r = 2), it is well known that the semi-circle law emerges as the LSD of the adjacency matrix as long as the average degree d_ = (n - 1) p →∞. Thus in the setting of fixed r, we do get a semi-circle limit as long as d_→∞.

    We note here that Assumption <ref> is implied by the condition d_/r^4→∞. Thus for the Laplacian matrix (nr)^-1/2 L_H_n, we only need this weaker condition on d_.




 §.§ LSD of the Gaussian GHAM

In view of of the universality result of Theorem <ref>, it sufficient to consider the Gaussian GHAM. Let (, d) be a metric space. For a real-valued function f on , define its Lipschitz seminorm by f_ := sup_x ≠ y|f(x) - f(y)|/d(x,y). A function f is called l-Lipschitz if f_≤ l. Define the class of Bounded Lipschitz functions as 

    _ := { f ∈^ : f_ + f_∞≤ 1 }.

Then the bounded Lipschitz metric on the set () of probability measures on  is defined as follows:

    d_(μ, ν) := sup_f ∈_{|∫ f  dμ - ∫ f  dν|}.

It is well known that d_ metrises weak convergence of probability measures on (
) (see, e.g., <cit.>). Below we have =.


    Let = (Z_ℓ)_1≤ℓ≤ M be a vector of i.i.d. Gaussians. Suppose r/n → c ∈ [0, 1). Then the EESD of n^-1/2 H_n converges weakly to ν_, (1 - c)^2. In fact, one has
    
    d_(_n^-1/2 H_n(), ν_, (1 - c)^2) = O(max{|r/n - c|, 1/√(n)}).


Theorem <ref> is proved by representing the Gaussian GHAM via an ANOVA-type decomposition as a low rank perturbation of a scaled Gaussian Wigner matrix minus its diagonal. 

We will now consider the Laplacian matrix L̃_H_n. To describe the limit we need the concept of free additive convolution of measures. Let μ_1 and μ_2 be two probability measures on  with Stieltjes transforms S_μ_1(z) and S_μ_2(z) respectively. Then there exists a probability measure μ whose Stieltjes transform is the unique solution of the system

    f(z)    = S_μ_1( z - Δ_2(z)/f(z)), 
    
        f(z)    = S_μ_2( z - Δ_1(z)/f(z)), 
    
        f(z)    = 1 - Δ_1(z) - Δ_2(z)/-z,

where the functions Δ_i(z), i = 1, 2, are analytic for (z) ≠ 0 and satisfy

    Δ_i(z) → 0  as (z) →∞.

The measure μ is denoted by μ_1 ⊞μ_2 and  is called the free additive convolution of μ_1 and μ_2. For further details, we refer the reader to <cit.>, <cit.>. 



Let H_n be a Gaussian GHAM. 
   
       
  (i) Suppose that r is fixed. Then EESD of n^-1/2L_H_n converges weakly to ν_, r - 1⊞ν_, 1 and  the EESD of n^-1/2L̃_H_n converges weakly to ν_,1/r - 1⊞ν_, 1.
       
  (ii) Suppose r →∞ such that r/n → c ∈ [0, 1). Then the EESD of (nr)^-1/2 L_H_n converges weakly to ν_, 1⊞ν_, c and the EESD of n^-1/2L̃_H_n converges weakly to ν_, (1 - c)^2.



    It is well known <cit.> that the LSD of the Laplacian of Erdős-Rényi random graphs is the free additive convolution of the standard Gaussian and the standard semi-circle laws. Theorem <ref> generalises this result to the hypergraph setting.




 §.§ Concentration of the ESD

In this section, we study concentration of the ESDs around the EESDs. Our main result in this regard is the following.

  

    
  (i) The map T_1 : (^M, ·_2) → (_n(), ·_F) defined by T_1() = n^-1/2 H_n() is r/√(n)-Lipschitz. 
    
  (ii) The map T_2 : (^M, ·_2) → (_n(), ·_F) defined by T_2() = (nr)^-1/2L_H_n() is √(r)-Lipschitz.
    
  (iii) The map T_3 : (^M, ·_2) → (_n(), ·_F) defined by T_3() = n^-1/2L̃_H_n() is √(r/r - 1 + r^2/n)-Lipschitz.


With the aid of Theorem <ref>, one can easily obtain concentration of the ESD around the EESD via standard techniques (see, e.g., <cit.>).

Recall that a probability measure ν on  satisfies a logarithmic Sobolev  inequality (LSI) with (not necessarily optimal) constant κ, if for any differentiable function f,

    ∫ f^2 logf^2/∫ f^2  dν dν≤ 2κ∫ |f'|^2   dν.

We say in this case that ν satisfies _κ. Via the so-called Herbst argument, a measure ν satisfying an LSI can be shown to possess sub-Gaussian tails (see, e.g., <cit.>). Examples of probability measures satisfying an LSI include the Gaussian <cit.> and any probability measure ν that is absolutely continuous with respect to the Lebesgue measure and satisfies the so-called Bobkov and Götze condition <cit.>. See, e.g., <cit.> for more on logarithmic Sobolev inequalities in the context of concentration of measure.
(Concentration of the ESD)
  
Suppose each entry of = (Y_ℓ)_1 ≤ℓ≤ M satisfies _κ for some κ > 0. There are universal constants C_j, Ĉ_j, C̃_j > 0, j = 1, 2, such that for any t > 0,

    
  (i) (d_(μ_n^-1/2H_n(),_n^-1/2H_n()) > t) ≤C_1/t^3/2exp(- C_2 n^2 t^2/κ r^2);
    
  (ii) (d_(μ_(nr)^-1/2 L_H_n(), _(nr)^-1/2 L_H_n()) > t) ≤Ĉ_1/t^3/2exp(-Ĉ_2 n t^2/κ r);
    
  (iii) (d_(μ_n^-1/2L̃_H_n(),_n^-1/2L̃_H_n()) > t) ≤C̃_1/t^3/2exp(- C̃_2 min{n, n^2/r^2} t^2/κ).

Suppose now that the entries of  are uniformly bounded by K > 0. There exist absolute constants C_j, Ĉ_j, C̃_j > 0, j = 3, 4, 5, 6, such that with δ_1(n) = C_5 K/n, δ̂_1(n) = Ĉ_5 K/n, δ̃_1(n) = C̃_5 K/n and Q = C_6 K, Q̂ = Ĉ_6 K, Q̃ = C̃_6 K we have for any t, t̂, t̃ > 0 satisfying t > (C_3 (Q + √(t)) δ_1(n))^2/5, t̂ > (Ĉ_3 (Q̂ + √(t̂)) δ̂_1(n))^2/5 and t̃ > ( C̃_3 (Q̃ + √(t̃))δ̃_1(n))^2/5 that

    
  (iv) (d_(μ_n^-1/2H_n(), _n^-1/2H_n()) > t) ≤C_3 (Q + √(t))/t^3/2exp(- C_4 n^2/r^2·(t^5/2/C_3 (Q + √(t)) - δ_1(n))^2);
    
  (v) (d_(μ_(nr)^-1/2 L_H_n(), _(nr)^-1/2 L_H_n()) > t̂) ≤Ĉ_3 (Q̂ + √(t̂))/t̂^3/2exp(- Ĉ_4 n/r·(t̂^5/2/Ĉ_3 (Q̂ + √(t̂)) - δ̂_1(n))^2);
    
  (vi) (d_(μ_n^-1/2L̃_H_n(), _n^-1/2L̃_H_n()) > t̃) ≤C̃_3 (Q̃ + √(t̃))/t̃^3/2exp(- C̃_4 ·min{n, n^2/r^2}·(t̃^5/2/C̃_3 (Q̃ + √(t̃)) - δ̃_1(n))^2).




    We note that the concentration inequalities of Corollary <ref> are only effective in the regime r/n → 0. As such we are able to show in-probability convergence of the ESDs only in this regime.



    Suppose that the entries of = (Y_ℓ)_1 ≤ℓ≤ M satisfy Assumption <ref>. Further suppose that they are either uniformly bounded or each of them satisfy _κ for some κ > 0.
    
        
  (i) If r/n → 0, then
            
    d_(μ_n^-1/2 H_n(), ν_, 1)  0,

            and if r √(log n)/n→ 0, then
            
    d_(μ_n^-1/2 H_n(), ν_, 1)  0.

        
  (ii) For the Laplacian L_H_n, we have the following:
            For fixed r,
            
    d_(μ_n^-1/2 L_H_n(), ν_, r - 1⊞ν_, 1)  0.

            If r →∞ and r/n→ 0, then
            
    d_(μ_(nr)^-1/2 L_H_n(), ν_, 1)  0,

            and if r →∞ and r log n/n→ 0, then
            
    d_(μ_(nr)^-1/2 L_H_n(), ν_, 1)  0.

        
  (iii) For the Laplacian L̃_H_n, we have the following:
            For fixed r,
            
    d_(μ_n^-1/2L̃_H_n(), ν_,1/r - 1⊞ν_, 1)  0.

            If r →∞ and r/n→ 0, then
            
    d_(μ_n^-1/2L̃_H_n(), ν_, 1)  0,

            and if r →∞ and r√(log n)/n→ 0, then 
            
    d_(μ_n^-1/2L̃_H_n(), ν_, 1)  0.

    



Recall that a d-dimensional random vector  satisfies a Poincaré inequality with constant σ^2 if for any bounded smooth function g on ^d one has

    (g()) ≤σ^2 ∇ g()_2^2,

We say that  satisfies (σ^2). Suppose each of the entries Y_ℓ satisfies (σ^2). Combining Theorem <ref> with Lemma 7.1 of <cit.>, it follows that the n-dimensional vector of the eigenvalues of n^-1/2H_n() satisfies (σ^2 r^2 / n). Let d_(μ, ν) := sup_x |F_μ(x) - F_ν(x)| denote the Kolmogorov-Smirnov distance between two probability measures μ and ν on , where F_μ(x) = μ((-∞, x]) is the distribution function of μ. As a consequence of Corollary 6.2 of <cit.>, we have

    [d_(μ_n^-1/2H_n(), _n^-1/2 H_n())] ≤ C (σ r/n)^2/3log^2(n/σ r)

for some constant C > 0. Unfortunately, C depends on the Lipschitz constant of F__n^-1/2H_n(). 




 §.§ Asymptotics for the edge eigenvalues

Using the low rank representation of a Gaussian GHAM, we study its spectral edge.  Our results generalise the results of <cit.> for Erdős-Rényi random graphs.

For any n × n symmetric matrix B, let λ_1(B) ≥λ_2(B) ≥⋯≥λ_n(B) denote its eigenvalues in non-increasing order. We first present our results on the extreme eigenvalues of a Gaussian GHAM. 

     Let H_n be a Gaussian GHAM. Let c_n := r/n and suppose that lim sup c_n <1. Let ζ denote a standard Gaussian variable.
     
     
  (i)
     If c_n → c∈ (0,1), then
    
    λ_1(H_n)/nc/2ζ + √(c^2/4ζ^2 + c(1-c)),
       λ_n(H_n)/nc/2ζ -√(c^2/4ζ^2 +c(1-c)).

    
  (ii)
    If r →∞ and c_n→ 0, then
    
    λ_1(H_n)/√(nr) 1, 
       λ_n(H_n)/√(nr) -1.

    
  (iii) If r is fixed, then
    
    λ_1(H_n)/√(n)   √(r-2) + 1/√(r-2)    if  r ≥ 4, 
    
                2     if  r ≤ 3,
            
    λ_n(H_n)/√(n)   
                -√(r-2) - 1/√(r-2)    if  r ≥ 4, 
    
                -2     if  r ≤ 3.

    
  (iv)
    Let k ∈. Then, 
    
    √(n/log n)(λ_1+k(H_n)/√(n) - 2(1-c_n)) = O_P(1), 
       √(n/log n)(λ_n-k(H_n)/√(n) + 2(1-c_n)) = O_P(1).

    

As mentioned in Section <ref>, these results remain valid for a GHAM where the entries Y_ℓ are uniformly bounded, by say K, and r ≪n^1/4/√(K)log n.

Now we present our results on the extreme eigenvalues of the two types of Laplacians of a Gaussian GHAM.

    Let H_n be a Gaussian GHAM. Let c_n := r/n and suppose that lim sup c_n < 1. Let k ∈ and ζ be a standard Gaussian variable.
    
    
  (A) We have the following estimates for the extreme eigenvalues of L_H_n:
    
    √(log n)( λ_k(L_H_n)/n√( 2 log n) -√(c_n(1-c_n)))    =O_P(1), 
    √(log n)( λ_n+1-k(L_H_n)/n√( 2 log n) +√(c_n(1-c_n)))    =O_P(1).

    
  (B) We have the following estimates for the largest and smallest eigenvalues of L̃_H_n. 
    5pt
    
    
  (i)
    If r ≪√(log n), then
    
    √(log n)/r((r-1) λ_1(L̃_H_n)/n√(2 log n) -√(c_n(1-c_n)))    = O_P(1), 
    √(log n)/r((r-1) λ_n(L̃_H_n)/n√(2 log n) +√(c_n(1-c_n)))    = O_P(1).

    
  (ii)
    If c_n → c ∈ (0,1), then
    
    λ_1(L̃_H_n)/nc/2ζ +√(c^2/4ζ +c(1-c)), 
    λ_1(L̃_H_n)/nc/2ζ -√(c^2/4ζ +c(1-c)).

    
    
  (C)
    We have the following estimates for the other extreme eigenvalues of L̃_H_n.
    5pt
    
    
  (i)
    If r ≪√(n), then
    
    min{√(n log n)/r, √(log n)}((r-1) λ_1+k(L̃_H_n)/n√(2 log n) -√(c_n(1-c_n)))    = O_P(1), 
    min{√(n log n)/r, √(log n)}((r-1) λ_n-k(L̃_H_n)/n√(2 log n) +√(c_n(1-c_n)))    = O_P(1).

    
  (ii)
    If r ≫√(n log n), then
    
    r/√(n log n)(λ_1+k(L̃_H_n)/√(n) -2 (1-c_n))    =O_P(1), 
    r/√(n log n)(λ_n-k(L̃_H_n)/√(n) +2 (1-c_n))    =O_P(1).

    
    




§ PROOFS



 §.§ Proof of Theorem <ref>

The proofs are based on Propositions <ref> and <ref> below, whose proofs are extensions of the argument given in <cit.> to the GHAM setting. We first recall the main Lindeberg swapping result for <cit.>.
Let 𝐗 = (X_1, …, X_n) and 𝐘 = (Y_1,…, Y_n) be two vectors of independent random variables with finite second moments, taking values in some open interval I and satisfying, for each i, X_i =  Y_i and X^2_i =  Y^2_i.

Let f: I^n → be thrice differentiable in each argument. If we set U= f(𝐗) and V= f(𝐘), then for any thrice differentiable g : → and any K >0,

    | g(U) -  g(V)|    ≤ C_1(g) λ_2(f) ∑_i = 1^n [[X_i^2 (|X_i|> K)] +  [Y_i^2 (|Y_i|> K)] ] 
            + C_2(g) λ_3(f) ∑_i = 1^n [[|X_i|^3 (|X_i|≤ K)] + [|Y_i|^3 (|Y_i| ≤ K)] ],

where C_1(g) = g^'_∞ + g^''_∞, C_2(g) = 1/6g^'_∞ + 1/2g^''_∞ + 1/6g^'''_∞ and 

    λ_s(f) ;= sup{|∂^q_i f()|^s/q : 1 ≤ i ≤ n, 1 ≤ q ≤ s, x ∈ I^n},

where ∂^q_i denotes q-fold differentiation with respect to the i-th coordinate. 


Let z = u + iv ∈_+. For 𝐱 = (x_1, …, x_M)^⊤, consider the functions H_n(𝐱) = 1/√(N)∑_ℓ = 1^M x_ℓ Q_ℓ, R_n(𝐱) = (1/√(n)H_n(𝐱) - z I)^-1 and G_n(𝐱) = 1/n R_n(𝐱). Let 𝐘 = (Y_1, Y_2, …, Y_M)^⊤ and 𝐙 = (Z_1, Z_2, …, Z_M)^⊤, where the Y_ℓ's are independent zero mean and unit variance random variables and they satisfy Assumption <ref> and  the Z_ℓ's are i.i.d. standard Gaussians. Then, we have for any K > 0,

    |(G_n   (𝐘)) - (G_n(𝐙))| 
       ≤ 4 max(v^-3, v^-4) r^2(r - 1)^2/n^2 N∑_ℓ = 1^M [ [Y^2_ℓ(|Y_ℓ| > K)] + [Z^2_ℓ(|Z_ℓ| > K)] ] 
          + 12 max(v^-6, v^-9/2, v^-4) r^3(r - 1)^3/n^5/2 N^3/2∑_ℓ = 1^M [ [|Y_ℓ|^3(|Y_ℓ| ≤ K)] + [|Z_ℓ|^3(|Z_ℓ| ≤ K)] ].




Let f() = G_n(). We will apply Theorem <ref> separately on the real and imaginary parts of f. Writing f() =  f() + ι f() (with ι := √(-1)), it is easy to see that max{|∂^q_i  f|, |∂^q_i  f|}≤ |∂^q_i f| for any 1 ≤ i ≤ M and 1 ≤ q ≤ 3. As a result,

    max{λ_2( f),  λ_2( f) }≤λ_2(f)   and  max{λ_3( f), λ_3( f)}≤λ_3(f).

In view of this, it is enough to show that 

    λ_2(f)    = sup_{|∂_ℓ f()|^2, |∂^2_ℓ f()| : 1 ≤ℓ≤ M }≤ 2max( v^-3, v^-4) r^2(r - 1)^2/n^2N, 
    λ_3(f)    = sup_{ |∂_ℓ f()|^3, |∂^2_ℓ f()|^3/2, |∂^3_ℓ f()| : 1 ≤ℓ≤ M }≤ 6 max( v^-6, v^-9/2, v^-4) r^3(r - 1)^3/n^5/2N^3/2.

First note that

    ∂^q f()/∂ x_ℓ^q = 1/n∂^q R_n()/∂ x_ℓ^q,    q ≥ 1.

Differentiating the relation (1/√(n) H_n() - z I) R_n() = I, one obtains that

    ∂ R_n() /∂ x_ℓ   = - 1/√(n)  R_n() ∂ H_n() /∂ x_ℓ R_n(), 
    ∂^2 R_n() /∂ x^2_ℓ   = 2/n  R_n() ∂ H_n() /∂ x_ℓ R_n() ∂ H_n() /∂ x_ℓ R_n(), 
    ∂^3 R_n() /∂ x^3_ℓ   = - 6/n^3/2  R_n() ∂ H_n() /∂ x_ℓ R_n() ∂ H_n() /∂ x_ℓ R_n()∂ H_n() /∂ x_ℓ R_n().

Therefore

    ∂ f() /∂ x_ℓ = - 1/n√(n)( R_n() ∂ H_n() /∂ x_ℓ R_n()) = - 1/n^3/2(∂ H_n() /∂ x_ℓ R^2_n()),

and similarly,

    ∂^2 f() /∂ x^2_ℓ   = 2/n^2( ∂ H_n() /∂ x_ℓ R_n() ∂ H_n() /∂ x_ℓ R^2_n()), 
    ∂^3 f() /∂ x^3_ℓ   = - 6/n^5/2(∂ H_n()/∂ x_ℓ R_n()  ∂ H_n() /∂ x_ℓ R_n() ∂ H_n() /∂ x_ℓ R^2_n()).

Observe that 

    (∂ H_n() /∂ x_ℓ R^2_n()) = ∑_1 ≤ i, j ≤ n( ∂ H_n() /∂ x_ℓ)_ij( R^2_n())_ji.

Let Λ = ( λ_1, …, λ_n), where λ_i's are the eigenvalues of 1/√(n) H_n(). Then from the spectral decomposition 1/√(n)H_n() = U Λ U^⊤, we have R^2_n() = U (Λ - zI)^-2 U^⊤. Note that |((Λ - zI)^-2)_ii| = |1/λ_i - z|^2 ≤1/v^2. Therefore

    |(R^2_n())_ij| = |∑_k ((U - zI)^-2)_kk U_ik U_kj| ≤1/v^2∑_k|U_ik| |U_kj| ≤1/v^2((∑_k U_ik^2) (∑_k U_kj^2))^1/2 = 1/v^2.

Hence

    |(∂ H_n() /∂ x_ℓ R^2_n()) | ≤1/v^2∑_1 ≤ i, j ≤ n| ( ∂ H_n() /∂ x_ℓ)_ij|.

Note that ∂ H_n() /∂ x_ℓ = 1/√(N) Q_ℓ and for any ℓ,

    ∑_1 ≤ i, j ≤ n|( ∂ H_n() /∂ x_ℓ)_ij| = r(r - 1)/√(N).

Therefore

    ∂ f() /∂ x_ℓ_∞≤1/v^2r(r - 1)/n^3/2√(N).

For bounding ∂^q f()/∂ x_ℓ^q_∞, q = 2, 3, we will need the the Frobenius and operator norms of ∂ H_n()/∂ x_ℓ. The Frobenius norm is easy to calculate:

    ∂ H_n()/∂ x_ℓ_F = 1/√(N)Q_ℓ_F = √(r(r - 1)/N).

Also, relabeling the vertices if necessary, we may assume that

    Q_ℓ = [ J_r - I_r         0;         0         0 ].

Hence Q_ℓ_op = r - 1 and so

    ∂ H_n()/∂ x_ℓ_op = 1/√(N)Q_ℓ_op = r - 1/√(N).

Now,

    (∂ H_n()/∂ x_ℓ   R_n() ∂ H_n()/∂ x_ℓ R^2_n()) 
       ≤∂ H_n()/∂ x_ℓ_F ·R_n() ∂ H_n()/∂ x_ℓ R^2_n()_F     (by Cauchy-Schwartz)
       ≤∂ H_n()/∂ x_ℓ_F ·R_n()_op·∂ H_n()/∂ x_ℓ R^2_n()_F 
       ≤∂ H_n()/∂ x_ℓ_F ·R_n()_op·∂ H_n()/∂ x_ℓ_F ·R^2_n()_op
       ≤∂ H_n()/∂ x_ℓ_F^2 ·R_n()_op^3 
       ≤r(r - 1)/N1/v^3.

This gives

    ∂^2 f() /∂ x^2_ℓ_∞≤2 r(r - 1)/n^2 N v^3.

For the third derivative, we do the following

    (∂ H_n()/∂ x_ℓ    R_n()∂ H_n()/∂ x_ℓ R_n() ∂ H_n()/∂ x_ℓ R^2_n()) 
       ≤∂ H_n()/∂ x_ℓ R_n() ∂ H_n()/∂ x_ℓ_F · R_n() ∂ H_n()/∂ x_ℓ R^2_n()_F     (by Cauchy-Schwartz)
       ≤∂ H_n()/∂ x_ℓ_op·R_n() ∂ H_n()/∂ x_ℓ_F ·R_n()∂ H_n()/∂ x_ℓ R^2_n()_F 
       ≤∂ H_n()/∂ x_ℓ_op·R_n()_op·∂ H_n()/∂ x_ℓ_F ·R_n()∂ H/∂ x_ℓ R^2_F 
       ≤∂ H_n()/∂ x_ℓ_op·∂ H_n()/∂ x_ℓ_F^2 ·R_n()_op^4 
       ≤r - 1/√(N)·r(r - 1)/N·1/v^4
       ≤r(r - 1)^2/N^3/2·1/v^4.

This yields

    ∂^3 f() /∂ x^3_ℓ_∞≤6 r(r - 1)^2/n^5/2 N^3/2 v^4.

Using (<ref>), (<ref>) and (<ref>), we obtain

    λ_2(f)    ≤  2max( v^-3, v^-4) r^2(r - 1)^2/n^2N, 
    λ_3(f)    ≤ 6 max( v^-6, v^-9/2, v^-4) r^3(r - 1)^3/n^5/2N^3/2.

This completes the proof.


For the two Laplacian matrices (nr)^-1/2L_H_n and n^-1/2L̃_H_n, we have the following results. Their proofs are similar to the proof of Proposition <ref> and hence are relegated to the appendix.

Let z = u + iv ∈_+. For = (x_1, …, x_M)^⊤, consider the functions H_n() = 1/√(N)∑_ℓ = 1^M x_ℓ Q_ℓ, L_H_n() ≡ L_H_n() = (H_n() ) - H_n(), R̂_n() = (1/√(nr)L_H_n() - z I)^-1 and Ĝ_n() = 1/nR̂_n(). Let = (Y_1, Y_2, …, Y_M)^⊤ and = (Z_1, Z_2, …, Z_M)^⊤, where the Y_ℓ's are independent random variables with zero mean and unit variance satisfying Assumption <ref> and  the Z_ℓ's are i.i.d. standard Gaussians. Then, we have for any K > 0,

    |(Ĝ_n   (𝐘)) - (Ĝ_n(𝐙))| 
       ≤ 8 max(v^-3, v^-4) r^3/2/n^2 N∑_ℓ = 1^M [ [Y^2_ℓ(|Y_ℓ| > K)] + [Z^2_ℓ(|Z_ℓ| > K)] ] 
          + 16 max(v^-6, v^-9/2, v^-4) r^9/2/n^5/2 N^3/2∑_ℓ = 1^M [ [|Y_ℓ|^3(|Y_ℓ| ≤ K)] + [|Z_ℓ|^3(|Z_ℓ| ≤ K)] ].



Let z = u + iv ∈_+. For = (x_1, …, x_M)^⊤, consider the functions H_n() = 1/√(N)∑_ℓ = 1^M x_ℓ Q_ℓ, L̃_H_n() ≡L̃_H_n() = (H_n() )/r - 1 - H_n(), R̃_n() = (1/√(n)L̃_H_n() - z I)^-1 and G̃_n() = 1/nR̃_n(). Let = (Y_1, Y_2, …, Y_M)^⊤ and = (Z_1, Z_2, …, Z_M)^⊤, where the Y_ℓ's are independent random variables with zero mean and unit variance satisfying Assumption <ref> and  the Z_ℓ's are i.i.d. standard Gaussians. Then, we have for any K > 0,

    |(G̃_n   (𝐘)) - (G̃_n(𝐙))| 
       ≤ 4 max(v^-3, v^-4) r^4/n^2 N∑_ℓ = 1^M [ [Y^2_ℓ(|Y_ℓ| > K)] + [Z^2_ℓ(|Z_ℓ| > K)] ] 
          + 12 max(v^-6, v^-9/2, v^-4) r^6/n^5/2 N^3/2∑_ℓ = 1^M [ [|Y_ℓ|^3(|Y_ℓ| ≤ K)] + [|Z_ℓ|^3(|Z_ℓ| ≤ K)] ].




In the notation of Proposition <ref> we have S__n^-1/2H_n() =  G_n() and S__n^-1/2H_n() =  G_n(). We take K = ε K_n where K_n = √(nN)/r^4. Observe that

    ∑_ℓ = 1^M [ [|Y_ℓ|^3(|Y_ℓ| ≤ε K_n)]    + [|Z_ℓ|^3(|Z_ℓ| ≤ε K_n)] ] 
       ≤ε K_n ∑_ℓ = 1^M [ [|Y_ℓ|^2(|Y_ℓ| ≤ K_n)] + [|Z_ℓ|^2(|Z_ℓ| ≤ K_n)] ] 
       ≤ 2 ε K_n M.

Therefore the second term in (<ref>) is at most

    2 r^3 (r - 1)^3 ε K_n M/n^5/2N^3/2≤2 ε K_n r^4/√(n N).

Therefore, with our choice of K_n, the second term in (<ref>) is at most 2ε. Now, i.i.d standard Gaussian random variables satisfy Assumption <ref>. By Assumption <ref> on (Y_ℓ)_1 ≤ℓ≤ M, the first term in (<ref>) goes to zero.

The proof for the Laplacian matrix n^-1/2L̃_H_n follows from Proposition <ref> in an identical fashion.

To deal with (nr)^-1/2 L_H_n, it follows from Proposition <ref> via the same argument as above that we want

    lim_n →∞r^3/2/n^2 N∑_ℓ = 1^M [|Y_ℓ|^2 (|Y_ℓ| > ε K_n')] = 0,

where K_n' = √(nN)/r^5/2. This is precisely Assumption <ref>.



 §.§ Proofs of Theorems <ref> and <ref>

We first state and prove a perturbation inequality that will be used repeatedly in the proofs. For this we will use the 1-Wasserstein metric. Recall that for q ≥ 1, the q-Wasserstein distance between probability measures μ and ν on  is given by 

    d_W_q(μ, ν) := inf_π∫ |x - y|^q   dπ(x, y),

where the infimum is over all coupings π of μ and ν. By the Kantorovich-Rubinstein duality (see, e.g., <cit.>), one also has the following representation for d_W_1:

    d_W_1(μ, ν) = sup_f_≤ 1{|∫ f  dμ - ∫ f  dν|}.

From this it is evident that d_≤ d_W_1.

    Let A and B be n × n Hermitian random matrices. Then
    
    d_W_1(_A, _B) ≤A - B_F/√(n)≤[A - B_F^2/n]^1/2.



Using the Kantorovich-Rubinstein duality,

    d_W_1(_A, _B)    = sup_f_≤ 1|∫ f   d_A - ∫ f   d_B| 
       = sup_f_≤ 1|∫ f   dμ_A - ∫ f   dμ_B| 
       ≤sup_f_≤ 1|∫ f   dμ_A - ∫ f   dμ_B| 
       =  [d_W_1(μ_A, μ_B)].

The first inequality in (<ref>) follows now from the fact that d_W_1≤ d_W_2 and the Hoffman-Wielandt inequality (Lemma <ref>). The final inequality in (<ref>) is just Jensen's inequality applied to the function x ↦√(x).


Recall the Lévy distance between two probability measures μ and ν on :

    d_(μ, ν) := inf{ϵ >0 : F_μ(x - ϵ) - ϵ≤ G_ν(x) ≤  F_μ(x + ϵ) + ϵ , ∀ x ∈}.

It is well known that (see, e.g., <cit.>)

    d_≤ 2 d_≤ 2 d_.

We will make use of the inequality d_≤ 2 d_ several times below.


Consider i.i.d. standard Gaussian random variables U, (V_i)_1 ≤ i ≤ n and an independent GOE random matrix n^-1/2 Z_n (i.e. (Z_ij)_1 ≤ i < j ≤ n are i.i.d. standard Gaussians and (Z_ii)_1 ≤ i ≤ n is another independent collection of i.i.d. Gaussians with variance 2). Consider a symmetric matrix G_n with entries

    G_n,ij = α_n U + β_n (V_i + V_j) + θ_n Z_ij.

Then we may write G_n as follows:

    G_n = α_n U_n _n _n^⊤ + β_n (_n^⊤ + _n ^⊤) + θ_n Z_n,

where _n is an n × n vector of 1's, = (V_i)_1≤ℓ≤ M. We shall choose α_n, β_n, θ_n in such a way that 

    G'_n = G_n- (G_n)

yields the same covariance structure as a GHAM. To this end, note that for i ≠ j and i' ≠ j',

    (G'_n,ij, G'_n,i'j')    = α_n^2    if  |{i, j}∩{i', j'}| = 0, 
    α_n^2 + β_n^2    if  |{i, j}∩{i', j'}| = 1, 
    α_n^2 + 2 β_n^2 + θ_n^2    if  |{i, j}∩{i', j'}| = 2.

In addition, 

    (G_n,ii) = α_n^2 + 4 β_n^2 + 2θ_n^2.

To match this with our Gaussian GHAM, we must set

    α_n^2    = ρ_n, 
    α_n^2 + β_n^2    = γ_n, 
    α_n^2 + 2β_n^2 + θ_n^2    = 1,

which yields

    α_n = √(ρ_n),   β_n = √(γ_n - ρ_n),   θ_n = √(1 - 2 γ_n + ρ_n).

As r/n → c, we have γ_n → c and ρ_n → c^2. It follows that θ_n → 1 -c. With these parameter choices, the entries of G'_n and H_n have the same joint distribution. Now we write

    d_(_n^-1/2 H_n, ν_, 1 - c)    ≤ d_ (_n^-1/2 H_n, _n^-1/2 G'_n) + d_(_n^-1/2 G'_n, _n^-1/2 G_n)) 
                + d_(_n^-1/2 G_n, _n^-1/2θ_n Z_n) + d_ (_n^-1/2θ_n Z_n, _n^-1/2 (1-c) Z_n) 
                        + d_( _n^-1/2 (1-c) Z_n, ν_, 1 - c).

Now we bound each of the terms on the right hand side. The first term vanishes since the entries of H_n and G'_n have the same joint distribution.

For the second term, we use the inequality d_≤ d_W_1 and then appeal to Lemma <ref> to get

    d_(_n^-1/2 G'_n, _n^-1/2 G_n) ≤ d_W_1(_n^-1/2 G'_n, _n^-1/2 G_n) ≤((G_n)_F^2)^1/2/n  = √((G_n, 11)/n)≤√(4/n),

where the last inequality holds because (G_n, 11) = α_n^2 + 4 β_n^2 + 2 θ_n^2 = 1 + 2 β_n^2 + θ_n^2 ≤ 4.

For the third term, using the fact that (G_n - θ_n Z_n) ≤ 2, we obtain

    d_(_n^-1/2 G_n, _n^-1/2θ_n Z_n)    ≤ 
        2d_(_n^-1/2 G_n, _n^-1/2θ_n Z_n) 
       = sup_x | F_μ_n^-1/2G_n(x)- F_μ_n^-1/2θ_n Z_n(x)| 
       ≤sup_x |F_μ_n^-1/2G_n(x)- F_μ_n^-1/2θ_n Z_n(x)| 
       =  [ d_(μ_n^-1/2 G_n, μ_n^-1/2θ_n Z_n) ] 
       ≤[(n^-1/2(G_n - θ_n Z_n))/n]   (using Lemma <ref>)
       ≤2/n.

The fourth term is bounded using the same strategy as the second term:

    d_ (_n^-1/2θ_n Z_n, _n^-1/2 (1-c) Z_n) ≤ |θ_n -(1-c)| 1/n(𝔼Z_n^2_F)^1/2 = |θ_n-(1-c)|.

Since θ_n, (1-c) are bounded away form 0 and bounded above by 1, using the Lipschitzness of the function x ↦√(x) away from 0,

    |θ_n-(1-c)| =|√(1-2(r/n) +(r/n)^2 +O(1/n))-√(1-2c+c^2)| = O(max{|r/n-c|,1/n}).

Therefore

    d_ (_n^-1/2θ_n Z_n, _n^-1/2 (1-c) Z_n) ≤ O(max{|r/n-c|,1/n}).

For the final term, using Theorem 1.6 of <cit.> we get that

    d_(_n^-1/2 (1-c) Z_n, ν_, 1 - c) ≤ 2 d_( _n^-1/2 (1-c) Z_n, ν_, 1 - c) ≤C/n.

for some absolute constant C > 0. This concludes the proof.


Now we restate Theorem 2.1 of <cit.> in our notation for orthogonally invariant matrices (see the discussion on page 280 of <cit.>).
<cit.>
    Let B_n = U_n^⊤ F_1,n U_n + V_n^⊤ F_2,n V_n, where F_1,n and F_2,n are (potentially) random n × n symmetric matrices with arbitrary distributions and U_n, V_n are orthogonal matrices uniformly distributed over the orthogonal group (n) according to the Haar measure. We assume that the matrices F_1, n, F_2, n, U_n, V_n are independent. Assume that the ESDs μ_n^-1/2 F_r,n, r = 1, 2, converge weakly in probability as n →∞ to non-random probability measures μ_r, r = 1, 2, respectively and that 
    
    sup_n ∫ |λ|  _n^-1/2 F_r, n(dλ) < ∞

    for at least one value of r ∈{1, 2}. Then μ_n^-1/2 B_n converges weakly in probability to μ_1 ⊞μ_2, the free additive convolution of the measures μ_1 and μ_2.


    To prove (i), we use the low rank representation of a Gaussian GHAM. We only give the details for L̃_H_n. The stated result for L_H_n follows in a similar manner.

    First note that
    
    L̃_G_n - L̃_G_n' = -r - 2/r - 1(G_n),

    and thus
    
    d_W_1(_n^-1/2L̃_G'_n, _n^-1/2L̃_G_n)^2 ≤(r - 2)^2/n^2 (r - 1)^2(G_n)_F^2 = O(1/n).

    Therefore it is enough to consider L̃(G_n). Since the map X ↦L̃_X is linear, we have
    
    L̃_G_n = L̃_P_n + θ_n L̃_Z_n.

    where P_n = α_n U ^⊤ + β_n (^⊤ + ^⊤). Further, using the rank-inequality (Lemma <ref>), it is clear that we may focus on
    
    X_n = (P_n )/r - 1 + θL̃_Z_n.

    Now
    
    (P_n ) = (n α_n U  + nβ_n V̅ + nβ_n ).

    Consider the matrix
    
    X̃_n = nβ_n/r - 1() + θ_n L_Z_n.

    Using Lemma <ref>, we see that
    
    d_W_1(_n^-1/2X̃_n, _n^-1/2 X_n)^2 ≤1/n^2(r - 1)^2(nα_n U  + nβ_n V̅)_F^2 = n/(r - 1)^2(α_n U + β_n V̅)^2.

    Now
    
    (α_n U + β_n V̅)^2 =  (α_n U + β_n V̅) = α_n^2 + β_n^2 / n  = O(1/n^2).

    Hence
    
    d_W_1(_n^-1/2X̃_n, _n^-1/2 X_n) = O_P(1/√(n)).

    In fact, since β_n = √(r - 2)/√(n) +O(1/n) and θ_n = O(1/n), it is enough to consider (again by Hoffman-Wielandt) the matrix
    
    Ŵ_n = √(n(r - 2))/r - 1() + L̃_Z_n = √(n(r - 2))/r - 1() + (Z_n)/r - 1 - Z_n.

    By a modification of the proof of Lemma 4.12 of <cit.> one can instead consider the matrix (see Lemma <ref> for a precise statement of this replacement and its proof)
    
    W̃_n = √(n(r - 2))/r - 1() + √(n) ()/r - 1 + Z_n,

    where  is a vector of i.i.d. standard Gaussians independent of  and Z_n. Recall that n^-1/2 Z_n is a GOE random matrix which is orthogonally invariant.
    It is clear using the strong law of large numbers that the ESD of
    
    n^-1/2[√(n(r - 2))/r - 1() + √(n)()/r - 1]

    converges weakly almost surely to ν_, 1/r - 1. Now, using Theorem <ref> it follows that the ESD of
    n^-1/2[ √(n(r - 2))/r - 1() + √(n) ()/r - 1 + Z_n ] convereges weakly in probability to ν_, 1/r - 1⊞ν_. This proves (i) (the weak convergence of the EESD follows from the in-probability weak convergence of the ESD via the dominated convergence theorem).
    
    Now we prove (ii). First consider the matrix L̃_H_n. We invoke Lemma <ref>:
    
    d_W_1(_n^-1/2L̃_H_n, _n^-1/2 H_n)^2 ≤1/n(n^-1/2H_n )/r - 1_F^2 = 1/(r - 1)^2 n^2∑_i (∑_j H_n, ij)^2.

    Since
    
    ∑_i (∑_j H_n, ij)^2 = ∑_i (∑_j H_n, ij) = ∑_i (n + n(n - 1) γ_n) = O(n^2 r),

    we conclude that
    
    d_W_1(_n^-1/2L̃_H_n, _n^-1/2 H_n) = O(1/√(r)).

    Since r →∞, it follows that _n^-1/2L̃_H_n and _n^-1/2 H_n have the same weak limit, namely ν_, (1 - c)^2.

    Now we consider the usual Laplacian L_H_n. Again by Lemma <ref>,
    
    d_W_1(_(nr)^-1/2 L_G_n, _(nr)^-1/2(G_n ))    ≤1/n(nr)^-1/2 G_n_F^2 
       =1/n^2 r∑_i, j [G_n, ij^2] 
       =O(r^-1).

    Now
    
    G_n  = n α_n U  + n β_n V̅ + nβ_n  + θ_n Z_n .

    Another application of Lemma <ref> gives
    
    d_W_1(_(nr)^-1/2(G_n ), _(nr)^-1/2(nα_n U  + nβ_n ))    ≤1/n(nr)^-1/2(nβ_n V̅ + θ_n Z_n )_F^2 
       =1/n^2 r∑_i [nβ_n V̅ + θ_n ∑_j Z_ij]^2 
       =1/n r(nβ_n V̅ + θ_n ∑_j Z_1j) 
       =1/n r (n β_n^2 + n θ_n^2) 
       =O(r^-1).

    Finally note that
    
    (nr)^-1/2(n α_n U + nβ_n ) = (√(r/n) U  + ) = √(r/n) U I + ().

    Since the first matrix on the right hand side above is orthogonally invariant, using Theorem <ref> we conclude that
    
    _(nr)^-1/2(n α_n U + nβ_n )ν_, c⊞ν_, 1.

    This completes the proof.





 §.§ Proof of Theorem <ref>

Theorem <ref> follows from Lemmas <ref> and <ref> below.

We have the following.

    
  (i) The map ↦ n^-1/2H_n() is Δ_n, r-Lipschitz, where
    
    Δ_n, r^2 = 1/nN∑_s = 0^r (s^2 - s) rsn - rr - s.

    
  * (ii) The map ↦ (nr)^-1/2 L_H_n() is Γ_n,r-Lipschitz, where
    
    Γ_n,r^2 = 1/n r N∑_s = 0^r ((r^2 - 2r) s + s^2) rsn - rr - s.

    
  * (iii) The map ↦ n^-1/2L̃_H_n() is Ξ_n,r-Lipschitz, where
    
    Ξ_n,r^2 = 1/nN∑_s = 0^r s^2 rsn - rr - s.




We first prove (i). Note that

    (Q_ℓQ_ℓ')    = ((_ℓ_ℓ^⊤ - (_ℓ)) (_ℓ'_ℓ'^⊤ - (_ℓ')) 
       = (_ℓ_ℓ^⊤_ℓ'_ℓ'^⊤ - (_ℓ)_ℓ'_ℓ'^⊤ - _ℓ_ℓ^⊤(_ℓ') + (_ℓ) (_ℓ')) 
       = (_ℓ^⊤_ℓ')^2 - _ℓ^⊤_ℓ'
       = |e_ℓ∩ e_ℓ'|^2 - |e_ℓ∩ e_ℓ'|.

Therefore

    n^-1/2H_n() - n^-1/2H_n(')_F^2    = 1/nN∑_ℓ, ℓ' ( - ')_ℓ ( - ')_ℓ'  (Q_ℓQ_ℓ') 
       = 1/nN∑_ℓ, ℓ' ( - ')_ℓ ( - ')_ℓ'   (|e_ℓ∩ e_ℓ'|^2 - |e_ℓ∩ e_ℓ'|) 
       = 1/nN∑_s = 0^r (s^2 - s) ∑_ℓ, ℓ' : |e_ℓ∩ e_ℓ'|= s ( - ')_ℓ ( - ')_ℓ'.

Now two applications of Cauchy-Schwartz gives

    ∑_ℓ, ℓ' : |e_ℓ∩ e_ℓ'|= s ( - ')_ℓ ( - ')_ℓ'   = ∑_ℓ = 1^M ( - ')_ℓ∑_ℓ' : |e_ℓ∩ e_ℓ'|= s( - ')_ℓ'
       ≤(∑_ℓ = 1^M ( - ')_ℓ^2)^1/2(∑_ℓ = 1^M (∑_ℓ' : |e_ℓ∩ e_ℓ'|= s( - ')_ℓ')^2)^1/2
       ≤ - '[∑_ℓ = 1^M rsn - rr - s∑_ℓ' : |e_ℓ∩ e_ℓ'|= s( - ')_ℓ'^2]^1/2
       =  - '[rsn - rr - s∑_ℓ' = 1^M ( - ')_ℓ'^2 ∑_ℓ : |e_ℓ∩ e_ℓ'|= s 1 ]^1/2
       = rsn - rr - s - '^2.

Therefore

    n^-1/2H_n() - n^-1/2H_n(')_F^2 ≤[1/nN∑_s = 0^r (s^2 - s) rsn - rr - s]  - '^2 = Δ_n, r^2  - '^2.

This completes the proof of (i).

Let us now prove (ii). Notice that

    L_H_n()   = (H_n() ) - H_n() 
       = 1/√(N)∑_ℓ_ℓ ( Q_ℓ) - 1/√(N)∑_ℓ_ℓ Q_ℓ
       = 1/√(N)∑_ℓ (r - 1) _ℓ ( _ℓ) -  1/√(N)∑_ℓ_ℓ Q_ℓ
       = 1/√(N)∑_ℓ_ℓ ((r - 1)( _ℓ) -  Q_ℓ) 
       = 1/√(N)∑_ℓ_ℓ (r  ( _ℓ) - _ℓ_ℓ^⊤) 
       = 1/√(N)∑_ℓ_ℓQ̂_ℓ,

where Q̂_ℓ := r  ( _ℓ) - _ℓ_ℓ^⊤.
Note that 

    (Q̂_ℓQ̂_ℓ' )    = ((r  ( _ℓ) - _ℓ_ℓ^⊤) (r  ( _ℓ') - _ℓ'_ℓ'^⊤ )) 
       = (r^2  (_ℓ)(_ℓ') - r  (_ℓ) _ℓ'_ℓ'^⊤ - r ( _ℓ') _ℓ_ℓ^⊤ + _ℓ_ℓ^⊤_ℓ'_ℓ'^⊤ ) 
       = r^2  _ℓ^⊤_ℓ' - r  _ℓ^⊤_ℓ' - r  _ℓ^⊤_ℓ' + (_ℓ^⊤_ℓ')^2 
       = (r^2 - 2r) _ℓ^⊤_ℓ' + (_ℓ^⊤_ℓ')^2 
       = (r^2 - 2r) |e_ℓ∩ e_ℓ'| + |e_ℓ∩ e_ℓ'|^2.

Now using the bound (<ref>), we get

    (nr)^-1/2 L_H_n() - (nr)^-1/2 L_H_n(')_F^2    = 1/n r N∑_ℓ, ℓ' ( - ')_ℓ ( - ')_ℓ'  (Q̂_ℓQ̂_ℓ') 
       = 1/n r N∑_ℓ, ℓ' ( - ')_ℓ ( - ')_ℓ'   [(r^2 - 2r) |e_ℓ∩ e_ℓ'| + |e_ℓ∩ e_ℓ'|^2 ]  
       = 1/n r N∑_s = 0^r ((r^2 - 2r) s + s^2) ∑_ℓ, ℓ' : |e_ℓ∩ e_ℓ'|= s ( - ')_ℓ ( - ')_ℓ'
       ≤[1/n r N∑_s = 0^r ((r^2 - 2r) s + s^2) rsn - rr - s]  - '^2 
       = Γ_n,r^2  - '^2.

This proves (ii). Finally, we prove (iii). Notice that

    L̃_H_n()   = ( H_n() )/r - 1 - H_n() 
       = 1/√(N)(r - 1)∑_ℓ_ℓ ( Q_ℓ) - 1/√(N)∑_ℓ_ℓ Q_ℓ
       =  1/√(N)∑_ℓ_ℓ( _ℓ) -  1/√(N)∑_ℓ_ℓ Q_ℓ
       = 1/√(N)∑_ℓ_ℓ ( ( _ℓ) -  Q_ℓ) 
       = 1/√(N)∑_ℓ_ℓ (2  ( _ℓ) - _ℓ_ℓ^⊤) 
       = 1/√(N)∑_ℓ_ℓQ̃_ℓ,

where Q̃_ℓ := 2  ( _ℓ) - _ℓ_ℓ^⊤.
Note that 

    (Q̃_ℓQ̃_ℓ' )    = ((2  ( _ℓ) - _ℓ_ℓ^⊤) (2  ( _ℓ') - _ℓ'_ℓ'^⊤ )) 
       = (4  (_ℓ)(_ℓ') - 2  (_ℓ) _ℓ'_ℓ'^⊤ - 2 ( _ℓ') _ℓ_ℓ^⊤ + _ℓ_ℓ^⊤_ℓ'_ℓ'^⊤ ) 
       = 4  _ℓ^⊤_ℓ' - 2  _ℓ^⊤_ℓ' - 2  _ℓ^⊤_ℓ' + ( _ℓ^⊤_ℓ' )^2 
       = ( _ℓ^⊤_ℓ' )^2 
       = |e_ℓ∩ e_ℓ'|^2.

Now using the bound (<ref>), we get

    n^-1/2L̃_H_n() - n^-1/2L̃_H_n(')_F^2    = 1/nN∑_ℓ, ℓ' ( - ')_ℓ ( - ')_ℓ'  (Q̃_ℓQ̃_ℓ') 
       = 1/nN∑_ℓ, ℓ' ( - ')_ℓ ( - ')_ℓ'   |e_ℓ∩ e_ℓ'|^2  
       = 1/nN∑_s = 0^r s^2 ∑_ℓ, ℓ' : |e_ℓ∩ e_ℓ'|= s ( - ')_ℓ ( - ')_ℓ'
       ≤[1/nN∑_s = 0^r s^2 rsn - rr - s]  - '^2 
       = Ξ_n,r^2  - '^2.

This proves (iii).



    For any r ≥ 2, we have the following estimates.
    
        
  (i) Δ_n, r^2 ≤r^2/n.
        
  (ii) Γ_n,r^2 ≤ r.
        
  (iii) Ξ_n,r^2 ≤r/r - 1 + r^2/n.
    


Let X ∼(n, r, r). Then

    [X]    = r^2/n, 
    (X)    = r^2/n·n - r/n·n - r/n - 1 = r^2/n(1 - r/n)^2 (1 - 1/n)^-1≤r^2/n(1 - r/n)^2.

We note that

    1/nr∑_s = 0^r (s^2 - s) rsn - rr - s   =(X^2 - X) 
       = (X) + ([X])^2 - [X] 
       ≤r^2/n(1 - r/n)^2 + r^2/n(r^2/n - 1) 
       = r^2/n(1 - 2r/n + r^2/n^2 + r^2/n - 1) 
       = r^3/n^2(r/n + r - 2 ) 
       ≤r^3(r - 1)/n^2.

Therefore

    Δ_n, r^2 ≤nr/n N·r^3(r - 1)/n^2 = n (n-1)/nr (r - 1)·r^3(r - 1)/n^2≤r^2/n.

This proves (i). For (ii), note that

    r Ξ_n, r^2    = nr/nN∑_s = 0^r (r - 1)^2 s rsn - rr - s/nr + Δ_n, r^2 
       = nr/nN (r - 1)^2 [X] +Δ_n, r^2 
       = (n - 1)/r(r - 1) (r - 1)^2 r^2/n + Δ_n, r^2 
       ≤ (n - 1) r^2/n + r^2/n
       = r^2.

Finally, for (iii), we have

    Γ_n, r^2    = nr/nN∑_s = 0^r s rsn - rr - s/nr + Δ_n, r^2 
       = nr/nN[X] +Δ_n, r^2 
       = (n - 1)/r(r - 1)r^2/n + Δ_n, r^2 
       ≤r/r - 1 + r^2/n.

This completes the proof.


    It is clear from the proof of Lemma <ref> that in fact, Δ_n, r = Θ(r/√(n)), Γ_n, r = Θ(√(r)), and Ξ_n, r = Θ(√(r/(r - 1) + r^2/n)).

Now we will prove Corollary <ref>.
Henceforth we will use the notation ⟨ f, μ⟩ := ∫ f   dμ for brevity. The proof of the following result is standard (see <cit.>).

Suppose that all the entries of = (Y_ℓ)_1 ≤ℓ≤ M satisfy _κ for some κ > 0. There are universal constants C_j, Ĉ_j, C̃_j > 0, j = 1, 2, such that for any 1-Lipschitz function f, we have for any t > 0, 

     
  (i) (|⟨ f, μ_n^-1/2H_n()⟩ - ⟨ f, _n^-1/2H_n()⟩| > t) ≤ C_1 exp(-C_2 n^2 t^2/κ r^2);
    
  (ii) (|⟨ f, μ_(nr)^-1/2 L_H_n()⟩ - ⟨ f, _(nr)^-1/2 L_H_n()⟩| > t) ≤Ĉ_1 exp(-Ĉ_2 n t^2/κ r);
    
  (ii) (|⟨ f, μ_n^-1/2L̃_H_n()⟩ - ⟨ f, _n^-1/2L̃_H_n()⟩| > t) ≤C̃_1 exp(-C̃_2 min{n, n^2 / r^2} t^2/κ).



For any 1-Lipschitz function f,

    |⟨ f, μ_n^-1/2H_n()⟩ - ⟨ f, μ_n^-1/2H_n(')⟩| ≤1/n∑_i = 1^n |f(λ_i) - f(λ_i')|  ≤1/n∑_i = 1^n |λ_i - λ_i'|.

Using the Cauchy-Schwartz and Hoffman-Wielandt inequalities, the last quantity can be bounded by

    (1/n∑_i = 1^n (λ_i - λ_i')^2)^1/2   ≤(1/nn^-1/2 H_n() - n^-1/2 H_n(')_F^2 )^1/2
       ≤Δ_n, r/√(n) - '
       ≤r/n - '.

Thus the map ↦⟨ f, μ_n^-1/2H_n()⟩ is r/n-Lipschitz.

If all entries (Y_ℓ)_1 ≤ℓ≤ M satisfy _κ, then by the tensorization property of LSI, their joint law also satisfies _κ (see, e.g., <cit.>). Then by concentration of Lipschitz functions for measures satisfying LSI, we have

    (|⟨ f, μ_n^-1/2H_n()⟩ - ⟨ f, _n^-1/2H_n()⟩| > t)    = (|⟨ f, μ_n^-1/2H_n()⟩ - ⟨ f, μ_n^-1/2H_n()⟩| > t) 
       ≤ C_1 exp(-C_2 n^2 t^2/κ r^2).

This proves (i). 

The proofs of (ii) and (iii) are similar. For (iii), we just note that the Lipschitz constant of the map ↦⟨ f, μ_n^-1/2L̃_H_n()⟩ is

    Ξ_n, r/√(n) = √(r/n(r - 1) + r^2/n^2) = Θ(max{1/√(n), r/n}).

This completes the proof.

Similarly, using Talagrand's inequality, one can prove the following.

Suppose the entries of = (Y_ℓ)_1 ≤ℓ≤ M are uniformly bounded by K > 0. There exist absolute constants C_j, Ĉ_j, C̃_j > 0, j = 3, 4, 5, 6, such that with δ_1(n) = C_5 K/n, δ̂_1(n) = Ĉ_5 K/n, δ̃_1(n) = C̃_5 K/n and Q = C_6 K, Q̂ = Ĉ_6 K, Q̃ = C̃_6 K we have for any 1-Lipschitz function f and any t, t̂, t̃ > 0 satisfying t > (C_3 (Q + √(t)) δ_1(n))^2/5, t̂ > (Ĉ_3 (Q̂ + √(t̂))δ̂_1(n))^2/5 and t̃ > (C̃_3 (Q̃ + √(t̃))δ̃_1(n))^2/5, that

    
  (i) (|⟨ f, μ_n^-1/2H_n()⟩ - ⟨ f, _n^-1/2H_n()⟩| > t) ≤C_3 (Q + √(t))/t^3/2exp(- C_4 n^2/r^2·(t^5/2/C_3 (Q + √(t)) - δ_1(n))^2);
    
  (ii) (|⟨ f, μ_(nr)^-1/2 L_H_n()⟩ - ⟨ f, _(nr)^-1/2 L_H_n()⟩| > t̂) ≤Ĉ_3 (Q̂ + √(t̂))/t̂^3/2exp(- Ĉ_4 n/r·(t̂^5/2/Ĉ_3 (Q̂ + √(t̂)) - δ̂_1(n))^2);
    
  (iii) (|⟨ f, μ_n^-1/2L̃_H_n()⟩ - ⟨ f, _n^-1/2L̃_H_n()⟩| > t) ≤C̃_3 (Q̃ + √(t̃))/t̃^3/2exp(- C̃_4 ·min{n, n^2/r^2}·(t̃^5/2/C̃_3 (Q̃ + √(t̃)) - δ̃_1(n))^2).



Using a standard covering argument (see the proofs of Theorems 1.3 and 1.4 in <cit.>), we can obtain from Lemmas <ref> and <ref> the inequalities given in (i)-(vi). We skip the details.




 §.§ Proofs of Theorems <ref> and <ref>



    Define G_n and G'_n as in (<ref>) and (<ref>), respectively and recall that H_n and G'_n have the same distribution. Also, n^-1/2 Z_n is a GOE random matrix.
    Note that by Weyl's inequality,
    
    max_1 ≤ i ≤ n|λ_i(G_n) - λ_i(G'_n)| ≤(G_n)_ =  max_i |G_n,ii| = O_P(√(log n)).

     Write P_n = α_n U ^⊤ + β_n (^⊤ + ^⊤). Then
    
    max_1 ≤ i ≤ n|λ_i(G_n) - λ_i(P_n)| ≤θ_n Z_n_ = O_P(√(n)).

    Thus, it is enough to prove (<ref>) by replacing H_n with P_n and (<ref>) by replacing H_n with G_n. 
    
    Notice that ,  are almost surely linearly independent. Consider an ordered basis ℬ = {, , _3, _4, …, _n} of ^n, where {_3, _4, …, _n} is a linearly independent set which is orthogonal to both  and . In the basis ℬ, P_n has the following matrix representation:
    
    [  nα_n U + nβ_n V̅ nα_n UV̅  +β_n ^2                 0                 0                 ⋯                 0;              nβ_n           nβ_n V̅                 0                 0                 ⋯                 0;                 0                 0                 0                 0                 ⋯                 0;                 ⋮                 ⋮                 ⋮                 ⋮                                   ⋮;                 0                 0                 0                 0                 ⋯                 0 ].

    From this representation, one can easily compute the eigenvalues of P_n. Let s^2 := 1/n∑_i=1^n (V_i - V̅)^2. Then
    
    λ_1(P_n)/n   = α_n/2 U  + β_n V̅ + √((α_n/2U + β_n V̅)^2 + β_n^2 s^2), 
    λ_n(P_n)/n   = α_n/2U + β_n V̅ -√((α_n/2U + β_n V̅)^2 + β_n^2 s^2), 
    λ_k(P_n)    = 0   for  k = 2, 3, …, n - 1.

    Note that V̅ 0 and s^2  1. Therefore it is natural to compare λ_1(P_n) to α_n/2 U + √(α_n^2/4U^2 + β_n^2). To that end, note that
    
    √(n)|   λ_1(P_n)/n - c_n/2U - √(c_n^2/4U^2 + c_n(1-c_n))| 
       = √(n)|1/2(α_n - c_n)U +β_n V̅ + (α_n/2U +β_n V̅)^2 +β_n^2 s^2 -c_n^2/4U^2 - c_n(1-c_n)/√((α_n/2U +β_n V̅)^2 + β_n^2 s^2) + √(c_n^2/4U^2 + c_n(1-c_n))|
       ≤1/2√(n)|α_n - c_n| · |U| + β_n √(n) |V̅| + |α_n U + c_n U + 2β_n V̅| · (√(n)|α_n - c_n| |U| + 2β_n √(n) |V̅|)/4√(c_n (1-c_n))
                    + √(n)|β_n^2 s^2 -c_n(1-c_n)|/√(c_n(1-c_n)).

    Observe that √(n)|α_n - c_n| = O(1/√(n)). Also, since √(n)V̅∼ N(0, 1),
    
    β_n √(n)V̅ = O_P(√(c)_n).

    Further, since √(n)(s^2 - 1)  N(0, 2),
    
    √(n) |β_n^2 s^2 -c_n(1-c_n)| 
               ≤√(n) s^2|β_n^2 - c_n(1-c_n)| + c_n (1-c_n) √(n)|s^2 -1| 
       = O_P(1/√(n)) + O_P(c_n),

    Finally, notice that 1/√(c_n(1-c_n)) = O(1/√(c)_n). Combining these we get that
    
    √(n)(λ_1(P_n)/n - c_n/2U - √(c_n^2/4U^2 + c_n(1-c_n))) = O_P(1).

    From these the desired result follows for λ_1(P_n) and hence for λ_1(H_n). Similarly, one can tackle λ_n(H_n). This completes the proofs of (<ref>) and (<ref>).

    Now we prove (ii). Suppose that c_n → 0 and r →∞. From (<ref>) it follows that
    
    sup_1 ≤ i ≤ n|λ_i(G_n)/√(nr) - λ_i(P_n)/√(nr)| = O_P(1/√(r)).

    Further note that
    
    λ_1(P_n)/√(nr)   = 1/√(c_n)·λ_1(P_n)/n = 1/√(c_n)[c_n/2U + √(c_n^2/4U^2 + c_n(1-c_n)) +  O_P(1/√(n))] 
       = √(c_n)/2U + √(c_n/4U^2 + (1-c_n)) + O_P(1/√(r)),

    from which it follows that
    
    λ_1(P_n)/√(nr) 1,

    and similarly,
    
    λ_n(P_n)/√(nr) -1.

    
    Now we consider (iii), the regime where r is fixed. In this regime, we have to consider G_n itself. We think of G_n as a low rank deformation of a scaled GOE matrix:
    
    G_n = P_n + θ_n Z_n.

    Since r is fixed, it is clear that
    
    nα_n = O(1),   √(n)β_n →√(r-2)  and  θ_n → 1.

    Now, multiplying both sides of (<ref>) and (<ref>) by √(n) and using the facts that 0 and s^2  1, we get that
    
    λ_1(P_n)/√(n)√(r-2)  and  λ_n(P_n)/√(n) -√(r-2).

    Suppose _1 and _n are a orthonormal pair of eigenvectors corresponding to λ_1 and λ_n, respectively. Then P_n has the representation
    
    P_n = λ_1(P_n) _1 _1^⊤ + λ_n(P_n) _n _n^⊤.

    Define P̃_n = √(n(r-2))(_1 _1^⊤ - _n _n^⊤). Now, by virtue of (<ref>), we may conclude that 1/√(n)P_n - P̃_n_ 0. Therefore by Weyl's inequality, it is enough to consider 1/√(n)G̃_n instead of 1/√(n) G_n, where G̃_n is defined as 
    
    G̃_n = P̃_n + θ_n Z_n.

    Now note that P̃_n and Z_n are independent and Z_n is orthogonally invariant. Further, the LSD of θ_n Z_n is the standard semi-circle law. Hence one may apply Theorem 2.1 of <cit.> on G̃_n to conclude that
    
    λ_1(G̃_̃ñ)/√(n)   √(r-2) + 1/√(r-2)    if √(r-2) > 1,  i.e. if  r > 3, 
    
                2     if √(r-2)≤ 1,  i.e. if  r ≤ 3.

    Similarly,
    
    λ_n(G̃_n)/√(n)   
                - √(r-2) - 1/√(r-2)    if √(r-2) > 1,  i.e. if  r > 3, 
    
                -2     if √(r-2)≤ 1,  i.e. if  r ≤ 3.

    This gives us the desired result.
    
    To prove (iv), notice that for k ≥ 1, by Lemma <ref>, for any i≤ k+1, i' ≥ k+1,
    
    λ_i'(θ_n Z_n) + λ_n+k+1-i'(P_n) ≤λ_k+1(G_n) ≤λ_i(θ_n Z_n) + λ_k+2-i (P_n).

    Taking i=k and i' = k+2 and noticing that λ_2(P_n) = λ_n-1(P_n) =0, we get
    
    θ_n λ_k+2(Z_n) ≤λ_k+1 (G_n) ≤θ_n λ_k (Z_n).

    As a consequence of Tracy and Widom's  seminal result on the fluctuations of extreme eigenvalues of the GOE (see <cit.>), n^2/3(λ_k(Z_n) -2) and n^2/3 (λ_k+2(Z_n) - 2) are O_P(1), implying that n^2/3 (λ_k+1(G_n) - 2 θ_n) = O_P(1). Therefore, 
    
    n^2/3 (λ_k+1(G_n) - 2(1-c)) = O_P(1).

    This proves (<ref>). The proof of (<ref>) is similar to that of (<ref>), thus skipped.


   
    Here, we prove (<ref>), (<ref>), (<ref>),  (<ref>), (<ref>). Then, (<ref>), (<ref>), (<ref>),  (<ref>),  (<ref>) can be proved following the same line of argument with minor modifications, so we skip them. 

    First, we prove part (A). Since L_G_n = L_G'_n, it suffices to consider L_G_n. Since B ↦ L_B is a linear map,
    
    L_G_n = L_P_n + θ_n L_Z_n = D_P_n - P_n + θ_n L_Z_n.

    Using Theorem 1.2 of <cit.>, we have L_Z_n_ = O_P(√(n log n)). Note that 
    
    D_P_n = n α_n U I + n β_n ( ) + n β_n V̅ I.

    Now, 
    
    n α_n U I_ = O_P(n),   n V̅ I _ = O_P(√(n)),    and   P_n_ = O_P(n).

    Combining these, we have by Weyl's inequality, 
    
    |λ_k(L_G_n) - n β_n λ_k(())| ≤L_G_n - n β_n  ()_ = O_P(n).

     Notice that λ_k(()) is nothing but the k-th largest order statistic of n i.i.d. standard Gaussians. Thus, using Lemma <ref>, we get
     
    log n(λ_k(())/√(2 log n) - 1 +loglog n/4 log n) = O_P(1).

     Taking into account the error terms, we can conclude that
    
    √(log n)   ( λ_k(L_G_n)/n√(2  log n) -β_n )
       =λ_k(L_G_n)-n β_nλ_k(())/√(2) n + β_n √(log n)(λ_k(())/√(2 log n)-1-loglog n/4 log n) + β_n loglog n/4 √(log n)
       =O_P(1).

    which yields (<ref>).


    Now we prove parts (B) and (C). Notice that L̃_G'_n - L̃_G'_n_op = 1/rmax_i |G_n,ii| = O_P(√(log n)/r). We thus see that (<ref>), (<ref>),  (<ref>), (<ref>) hold for L̃_G_n if and only if they hold for L̃_G'_n. Thus, it is enough to work with L̃_G_n.

    Note that L̃_G_n can be expressed as
    
    L̃_G_n = 1/r-1D_P_n - P_n +θ_n/r-1 D_Z_n -θ_n Z_n.

    Using Lemma <ref>, we obtain the following estimates:
    
    D_P_n_   ≤ n α_n |U|  + n β_n ( )_ + n β_n V̅_  = O_P(n√(log n)), 
    D_Z_n_   = √(n)max_i |1/√(n)∑_j Z_n,ij| =O_P(√(n log n)).

    Therefore
    
    |λ_1(L̃_G_n) - λ_1(P_n)| 
               ≤1/r-1D_P_n_ +θ_n/r-1D_Z_n_ +θ_n Z_n_
       = O_P(n√(log n)/r) +  O_P(√(n log n)/r) + O_P(√(n))
       = O_P(n√(log n)/r) + O_P(√(n)).

    Using the proof of (<ref>),
    
    |λ_1(L̃_G_n)/n -    c_n/2U -√(c_n^2/4U +c_n(1-c_n))| 
       ≤1/n |λ_1(L̃_G_n) - λ_1(P_n)| + |λ_1(P_n)/n -c_n/2U -√(c_n^2/4U +c_n(1-c_n))|
       =O_P(√(log n)/r) + O_P(1/√(n)).

    This proves (<ref>). In order to prove (<ref>), notice that
    
    |λ_1(L̃_G_n) - 1/r-1λ_1(D_P_n)| ≤P_n_ +θ_n/r-1D_Z_n_ +θ_n Z_n_ = O_P(n),

    which, together with the proof of (<ref>), implies that
    
    |(r-1) λ_1(L̃_G_n)/n√(2 log n)   -√(c_n(1-c_n))| 
       ≤|(r-1) λ_1(L̃_G_n)- λ_1(D_P_n)/n√(2 log n)| + |λ_1(D_P_n)/n√(2 log n) - β_n| + |β_n - √(c_n(1-c_n))|
       = |-(r-1)P_n + θ_n D_Z_n - (r-1)θ_n Z_n /n √(2 log n)|+O_P(1/√(log n)) + O_P(1/n)
       = O_P(r/√(log n)) + O_P(1/√(n)) + O_P(r/√(n log n)) + O_P(1/√(log n)) + O_P(1/n)
       = O_P(r/√(log n)).

    This completes the proof of (B).
    
    For (<ref>) and (<ref>), using Weyl's inequality as in the proof of (<ref>), it is enough to consider the matrix 
    
    L̃'_G_n := L̃_G_n - P_n = 1/r-1 D_P_n +θ_n/r-1 D_Z_n + θ_n Z_n.

    Note that
    
    L̃'_G_n - 1/r-1 D_P_n_   = O_P(√(n log n)/r) +O_P(√(n)), 
    L̃'_G_n - θ_n Z_n_   = O_P(n √(log n)/r).

    Therefore if r ≪√(n log n), then
    
    |(r-1) λ_k(L̃'_G_n)/n√(2 log n) -√(c_n(1-c_n))| 
               ≤|(r-1) λ_k(L̃'_G_n)- λ_k(D_P_n)/n√(2 log n)| + |λ_k(D_P_n)/n√(2 log n) - c_n(1-c_n)|
       = O_P(1/√(log n)) + O_P(r/√(n log n)),

    which proves (<ref>).
    On the other hand, if r ≫√(n log n),
    
    |λ_k(L̃'_G_n)/√(n) -2 (1-c)| 
               ≤1/√(n)L̃'_G_n - θ_n Z_n_ + | θ_n λ_k(1/√(n)Z_n) - 2(1-c) |
       = O_P(√(n log n)/r) + O_P(1/n^2/3)
       = O_P(√(n log n)/r)

    proving (<ref>). This completes the proof of the theorem.





§ ACKNOWLEDGEMENTS

We thank Arijit Chakrabarty for helpful discussions. SSM was partially supported by the INSPIRE research grant DST/INSPIRE/04/2018/002193 from the Dept. of Science and Technology, Govt. of India, 
and a Start-Up Grant from Indian Statistical Institute.

alpha





§ AUXILIARY RESULTS

Here we collect lemmas and results borrrowed from the literature. First we define some notations.

    _n() := The set of all  n × n  matrices with complex entries.

For A ∈_n(), define the Frobenius norm of A by

    A_F := √(∑_1 ≤ i ≤ j ≤ n|A_ij|^2).

For x ∈^n, let x = √(∑_i = 1^n x^2_i). The Operator norm of A is defined as

    A_ := sup_x = 1Ax.

For a random matrix A with eigenvalues λ_1, …, λ_n, let F_A(x) := 1/n∑_i = 1^n (λ_i ≤ x) be the empirical distribution function associated with the eigenvalues.  Let _n denotes the set of all permutations of the set {1, 2, …, n}. 

  Let A,B ∈_n() are two normal matrices, with eigenvalues λ_1(A),λ_2(A), …, λ_n(A) and λ_1(B),λ_2(B), …, λ_n(B) respectively. Then we have
  
    min_σ∈_n∑_i = 1^n | λ_i(A) - λ_σ(i)(B)|^2 ≤A - B ^2_F.

  An immediate consequence of this is that
  
    d_W_2(μ_A, μ_B)^2 ≤A - B^2/n.



 Let A, B ∈_n() are two Hermitian matrices. Then,
 
    sup_x ∈ |F_A(x) - F_B(x)| ≤rank(A - B)/n.



    Let A, B ∈_n() be two Hermitian matrices with decreasing sequence of eigenvalues λ_1(A), λ_2(A), …, λ_n(A) and λ_1(B), λ_2(B), …, λ_n(B), respectively. Then, for i ∈ [n],
    
    λ_j'(A) + λ_i-j'+n(B) ≤λ_i(A+B) ≤λ_j(A) + λ_i-j+1(B)

    for any j≤ i and j' ≥ i. A consequence of this is that for any 1 ≤ i ≤ n,
    
    |λ_i(A + B) - λ_i(A)| ≤max{|λ_1(B)|, |λ_n(B)|} = B_.


The following lemma is an amalgamation of Theorems 1.5.3 and  2.2.2 from <cit.>.

    If ξ_1, ξ_2, …, ξ_n are i.i.d. standard normal variables, then for k ∈,
    
    [√(2 log n)(ξ_(k) - √(2 log n) + loglog n + log (4π)/2 √(2 log n))≤ t ] → e^-e^-x∑_j=0^k-1e^-jx/j!,

where ξ_(k) denotes the k-th largest order statistic of ξ_1, ξ_2, …, ξ_n. In particular, 

    2 log n(ξ_(k)/√(2 log n)-1 +loglog n/4 log n) = O_P(1).


Since the ξ_i's are symmetric, a similar result holds for ξ_n+1-k, modulo the obvious sign change in the centering parameter.



§ MISCELLANEOUS RESULTS AND PROOFS

We can adapt Lemma 4.12 of <cit.> to our setting. 

Let 

    Ŵ_n = √(n(r - 2))/r - 1() + (Z_n)/r - 1 - Z_n

and

    W̃_n = √(n(r - 2))/r - 1() + √(n + 1) ()/r - 1 + Z_n,

where n^-1/2 Z_n is a GOE random matrix and  and  are vectors of i.i.d. standard Gaussian random variables. Further, ,  and Z_n are independent. Then, for fixed r and every k ∈,

    lim_n →∞ n^-(k + 1) [ (Ŵ_n^2k) - (W̃_n^2k)] = 0.



Let = _n and _n + 1 = [     '_n; V_n + 1 ] where '_n is an i.i.d copy of _n and V_n + 1 is a standard Gaussian independent of '_n. Let Z_n + 1 be the matrix defined by 

    Z_n + 1 = [ Z'_n     ;   ^⊤  Z^1 ],

where Z'_n is an i.i.d copy of Z_n,  is an n × 1 vector with i.i.d. Gaussian entries and Z^1 is a mean 0 variance 2 Gaussian random variable. Now consider the matrix 

    W'_n =  √(n(r - 2))/r - 1('_n) + (Z'_n )/r - 1 - Z_n.

Then W'_n and W̃_n has same distribution. So, it is enough to prove that 

    lim_n →∞ n^-(k + 1) [ (Ŵ_n^2k) - ((W'_n)^2k)] = 0.

Now

    [(Ŵ_n^2k) - ((W'_n)^2k)] = ∑_π [Ŵ_π -  W'_π]',

where the sum is over all circuits π : {0, …, 2k }→ [n] with π(0) = π(2k) and

    Ŵ_π = ∏_i = 1^2kŴ_π(i - 1), π(i).

A word w of length k is a sequence of numbers of length k, e.g., 12234 is a word of length 5. Set each word w of length 2k to be a circuit assigning w[0] = w[2k]. We associate a word with each circuit of length 2k via the relation w[i] = π(i), 1 ≤ i ≤ 2k. Let Π(w) denote the collection of circuits π such that the distinct letters of w are in a one-to-one correspondence with the distinct values of π. Let v(w) be the number of distinct letters in the word w. We note that #Π(w) ≤ n^v(w). Define f_n(w) := Ŵ_w -  W'_w. We show that, for any word w, there exits a constant C_w > 0 such that for all n ≥ 1, 

    |f_n(w)| = |Ŵ_w - W'_w| ≤ C_w(n/r - 1 + 3)^k - v(w) + 1/2.

Let q = q(w) be the number of indices 1 ≤ i ≤ 2k for which w[i] = w[i - 1]. If q(w) = 0 then Ŵ_w is product of only off-diagonal entries of Ŵ_n and off-diagonal entries of Ŵ_n and W'_n are same. Thus f_n(w) = 0 and f_n(w) ≠ 0 only if q(w) ≥ 1. Let _w be the graph with vertex set as the distinct letters of w and edge set { (w[i - 1], w[i] ) : 1 ≤ i ≤ 2k }.  Let u = u(w) be the number of edges of _w with distinct endpoints in w, which appear exactly once along the circuit w, e.g u(12234) = 4. Then by independence of the entries of W'_n we have that W'_w = 0 as soon as u(w) ≥ 1. For u(w) > q(w), let there are b number of off-diagonal entries in Ŵ_w and ( 2k - b) diagonal entries. Then b > 2k - b. Since u(w) > 1, among these b off-diagonal entries there will be at least one entry, say Ŵ_ij such that the edge {i,j} is traversed exactly once in _w. By Wick's formula Ŵ_w = 0. Thus, to prove (<ref>) it is enough to consider q(w) ≥ u(w). 

It is easy to check that excluding the q loop-edges (each vertex connecting to itself), there are at most k + ⌊ (u - q)/2 ⌋ distinct edges in w. These distinct edges form a connected path through v(w) vertices, which for u ≥ 1 must also be a circuit. From the proof of Lemma 4.12 of <cit.>, we have

    v(w) ≤ k + ( u(w) = 0) + ⌊ (u(w) - q(w) )/2 ⌋≤ k.

Proceeding to bound |f_n(w)|, suppose first that u ≥ 1, in which case f_n(w) = Ŵ_w. To compute this expectation we employ Wick's formula. Note that if we match u off-diagonal entries with the u diagonal entries with which they are correlated, and remaining ( q - u ) diagonal entries are either self matched, or they can match among themselves, then only contribution to the expectation will be non-zero. Other matching configurations will result in 0 due to the independence of the entries, e.g for the word w = 11223333, we have Ŵ_w =  [Ŵ_11Ŵ_12]  [Ŵ_22Ŵ_23]   [Ŵ_33Ŵ_33]   [Ŵ_33Ŵ_31]. Further, observe that covariance terms, i.e  [ Ŵ_iiŴ_ij ] = 1/r - 1, [ Ŵ_ijŴ_jj] = 1/( r - 1)^2 and [Ŵ^2_ii] = n/r - 1 + 1/(r - 1)^2 + 2 - 4/r - 1 < n/r - 1 + 3, for any 1 ≤ i ≤ n. Then 

    |f_n(w)|    ≤ C^3_w(1/r - 1)^u [ C^1_w( 1/(r - 1)^2)^( q - u )/2 + C^2_w(n + r - 3/r - 1 + ( r - 2/r - 1)^2)^( q - u )/2] 
       ≤ C_w [ 1 + C'_w ( n/r - 1 + 2 )^( q - u )/2].


By our bound (<ref>) on v(w), this implies that (<ref>) holds.

Consider next words w for which u(w) = 0.  There will be some diagonal entries and some off-diagonal entries which can appear twice or more in f_n ( w). Let a_1, …, a_q be the q vertices for which { a_i , a_i } is an edge of _w. Then 

    Ŵ_w = ∏_i = 1^q Ŵ_a_i, a_iV̂_w,

where V_w is the product of ( 2k - q ) off-diagonal entries of Ŵ_n that correspond to the edges of w that are in _w. Similarly, we can write

    W'_w = ∏_i = 1^q W'_a_i , a_i V'_w.

Since off-diagonal entries of Ŵ_n are W'_n are same, we can replace V̂_w by V'_w in Ŵ_w.
Let Ŵ_ii = D̂_i + Ŝ_i and W'_ii = D'_i + S'_i, for i = 1,…, 2k, where D̂_i = √(n(r - 2))/r - 1_i + 1/r - 1∑_j = 1^2k Z_ij - Z_ii, D'_i = √(n(r - 2))/r - 1'_i + 1/r - 1∑_j = 1^2k Z'_ij - Z_ii and Ŝ_i = ∑_j = 2k + 1^n Z_ij and S'_i = ∑_j = 2k + 1^n Z'_ij. Note that we may and shall replace each Ŝ_i by S'_i without altering Ŵ_w, as Z_ij and Z'_ij have same distribution. 

    f_n(w)    = [ V'_w [ ∏_i = 1^q ( D̂_a_i + S'_a_i) - ∏_i = 1^q  (D'_a_i + S'_a_i) ]]
       = ∑_i = 1^q [ V'_w ( D_a_i - D'_a_i ) ∏_j = 1^i - 1Ŵ_a_j, a_j∏_j = i + 1^q W'_a_j, a_j] 
       ≤∑_i = 1^q ([V'^4_w])^1/4[( D_a_i - D'_a_i )^4 ]^1/4√([ ∏_j = 1^i - 1Ŵ^2_a_j, a_j∏_j = i + 1^q W'^2_a_j, a_j]).

Note that V'_w is product of some i.i.d standard Gaussians, so [V'^4_w] is constant. For each i, D_a_i - D'_a_i is a Gaussian random variable with mean 0 variance 2n(r - 2)/( r - 1)^2 + 4k/(r - 1)^2 = O(n) , so [( D_a_i - D'_a_i )^4 ]^1/4 = O( √(n)). We know [ W'^2_ii] = n/r - 1 + 1/(r - 1)^2 + 2 < n/r - 1 + 3 and [Ŵ^2_ii] = n/r - 1 + 1/(r - 1)^2 + 2 - 4/r - 1 < n/r - 1 + 3 and [ Ŵ_ii W_jj] = - 2/r - 1 + 2. By Wick's formula, we have 

    [ ∏_j = 1^i - 1Ŵ^2_a_j, a_j∏_j = i + 1^q W'^2_a_j, a_j] = O(( n/r - 1 + 3 )^q).

Hence

    f_n(w) ≤ C_w √(n)( n/r - 1 + 3 )^q/2.

It is clear that (<ref>) implies that (<ref>) holds and hence the proof of the lemma is complete.



Let g() = Ĝ_n(). As before, we have to control λ_2(g) and λ_3(g). We have the identities:

    ∂ g() /∂ x_ℓ   = - 1/n^3 / 2 r^1/2(∂ L_H_n()/∂ x_ℓR̂_n^2()), 
    ∂^2 g()/∂ x^2_ℓ   = 2/n^2 r(∂ L_H_n()/∂ x_ℓR̂_n() ∂ L_H_n()/∂ x_ℓR̂_n^2()), 
    ∂^3 g() /∂ x^3_ℓ   = - 6/n^5/2 r^3/2(∂ L_H_n()/∂ x_ℓR̂_n() ∂ L_H_n()/∂ x_ℓR̂_n() ∂ L_H_n()/∂ x_ℓR̂_n^2()).

Note that

    (H_n() ) = (1/√(N)∑_ℓ = 1^M x_ℓ Q_ℓ) = 1/√(N)∑_ℓ = 1^M x_ℓ (Q_ℓ).

Hence 

    ∂ L_H_n()/∂ x_ℓ = 1/√(N)((Q_ℓ) - Q_ℓ) = 1/√(N)[ r I_r - J_r           0;           0           0 ],

where we have assumed (after a relabeling of nodes if necessary) that

    Q_ℓ = [ J_r - I_r         0;         0         0 ].

Now

    |(∂ L_H_n()/∂ x_ℓR̂_n^2())| ≤1/v^2∑_i,j| ( ∂ L_H_n()/∂ x_ℓ)_ij| = 1/v^22 r (r - 1)/√(N)≤1/v^22 r^2/√(N),

and a fortiori,

    ∂ g() /∂ x_ℓ_∞≤2/v^2r^3/2/n^3/2√(N).

From (<ref>) we also deduce that

    ∂ L_H_n()/∂ x_ℓ^2_F = r^2(r - 1)/N≤r^3/N  and  ∂ L_H_n()/∂ x_ℓ_ = r/√(N).

Therefore

    (∂ L_H_n()/∂ x_ℓR̂_n() ∂ L_H_n()/∂ x_ℓR̂_n^2()) ≤∂ L_H_n()/∂ x_ℓ^2_F·R̂_n()^3_≤r^3/N1/v^3

and so

    ∂^2 g()/∂ x^2_ℓ_∞≤2r^2/n^2Nv^3.

Finally,

    (∂ L_H_n()/∂ x_ℓR̂_n() ∂ L_H_n()/∂ x_ℓR̂_n() ∂ L_H_n()/∂ x_ℓR̂_n^2())    ≤∂ L_H_n()/∂ x_ℓ_·∂ L_H_n()/∂ x_ℓ_F^2 ·R̂_n()_^4 
       ≤r/√(N)·r^3/N·1/v^4

and therefore

    ∂^3 g() /∂ x^3_ℓ_∞≤6 r^5 / 2/n^5/2 N^3/2 v^4.

We conclude that

    λ_2(g) ≤ 4 max( v^-4, v^-3) r^3/n^2 N

and

    λ_3(g) ≤ 8 max( v^-6, v^-9/2, v^-4) r^9/2/n^5/2 N^3/2.

Hence 

    |(Ĝ_n   (𝐘)) - (Ĝ_n(𝐙))| 
       ≤ 8 max(v^-3, v^-4) r^3/n^2 N∑_ℓ = 1^M [ [Y^2_ℓ(|Y_ℓ| > K)] + [Z^2_ℓ(|Z_ℓ| > K)] ] 
          + 16 max(v^-6, v^-9/2, v^-4) r^9/2/n^5/2 N^3/2∑_ℓ = 1^M [ [|Y_ℓ|^3(|Y_ℓ| ≤ K)] + [|Z_ℓ|^3(|Z_ℓ| ≤ K)] ].

This completes the proof.



Let g() = G̃_n(). As before, we have to control λ_2(g) and λ_3(g). We have the identities:

    ∂ g() /∂ x_ℓ   = - 1/n^3/2(∂L̃_H_n()/∂ x_ℓR̃_n^2()), 
    ∂^2 g()/∂ x^2_ℓ   = 2/n^2( ∂L̃_H_n()/∂ x_ℓR̃_n() ∂L̃_H_n()/∂ x_ℓR̃_n^2()), 
    ∂^3 g() /∂ x^3_ℓ   = - 6/n^5/2(∂L̃_H_n()/∂ x_ℓR̃_n() ∂L̃_H_n()/∂ x_ℓR̃_n() ∂L̃_H_n()/∂ x_ℓR̃_n^2()).

Note that

    (H_n() ) = (1/√(N)∑_ℓ = 1^M x_ℓ Q_ℓ) = 1/√(N)∑_ℓ = 1^M x_ℓ (Q_ℓ).

Hence 

    ∂L̃_H_n()/∂ x_ℓ = 1/√(N)( (Q_ℓ)/r - 1 - Q_ℓ) = 1/√(N)[ 2I_r - J_r          0;          0          0 ],

where we have assumed (after a relabeling of nodes if necessary) that

    Q_ℓ = [ J_r - I_r         0;         0         0 ].

Now

    |(∂L̃_H_n()/∂ x_ℓR̃_n^2())| ≤1/v^2∑_i,j| ( ∂L̃_H_n()/∂ x_ℓ)_ij| =1/v^2r^2/√(N),

and a fortiori,

    ∂ g() /∂ x_ℓ_∞≤1/v^2r^2/n^3/2√(N).

From (<ref>) we also deduce that

    ∂L̃_H_n()/∂ x_ℓ^2_F = r^2/N  and  ∂L̃_H_n()/∂ x_ℓ_ = max{2, r - 2}/√(N)≤r/√(N).

Therefore

    (∂L̃_H_n()/∂ x_ℓR̃_n() ∂L̃_H_n()/∂ x_ℓR̃_n^2()) ≤∂L̃_H_n()/∂ x_ℓ^2_F·R̃_n()^3_≤r^2/N1/v^3

and so

    ∂^2 g()/∂ x^2_ℓ_∞≤2r^2/n^2Nv^3.

Finally,

    (∂L̃_H_n()/∂ x_ℓR̃_n() ∂L̃_H_n()/∂ x_ℓR̃_n() ∂L̃_H_n()/∂ x_ℓR̃_n^2())    ≤∂L̃_H_n()/∂ x_ℓ_·∂L̃_H_n()/∂ x_ℓ_F^2 ·R̃_n()_^4 
       ≤r/√(N)·r^2/N·1/v^4

and therefore

    ∂^3 g() /∂ x^3_ℓ_∞≤6 r^3/n^5/2 N^3/2 v^4.

We conclude that

    λ_2(g) ≤ 2max( v^-4, v^-3) r^4/n^2 N

and

    λ_3(g) ≤ 6 max( v^-6, v^-9/2, v^-4) r^6/n^5/2 N^3/2.

Hence 

    |(G̃_n   (𝐘)) - (G̃_n(𝐙))| 
       ≤ 4 max(v^-3, v^-4) r^4/n^2 N∑_ℓ = 1^M [ [Y^2_ℓ(|Y_ℓ| > K)] + [Z^2_ℓ(|Z_ℓ| > K)] ] 
          + 12 max(v^-6, v^-9/2, v^-4) r^6/n^5/2 N^3/2∑_ℓ = 1^M [ [|Y_ℓ|^3(|Y_ℓ| ≤ K)] + [|Z_ℓ|^3(|Z_ℓ| ≤ K)] ].

This completes the proof.

