# Extremal Laws for Laplacian Random Matrices ††thanks: Research supported by
Conacyt Grant A1-S-976

Santiago Arenas-Velilla Victor Pérez-Abreu CIMAT, Guanajuato, Mexico,
<EMAIL_ADDRESS>Politécnico Nacional, Mexico<EMAIL_ADDRESS>
###### Abstract

For an $n\times n$ Laplacian random matrix $L$ with Gaussian entries it is
proven that the fluctuations of the largest eigenvalue and the largest
diagonal entry of $L/\sqrt{n-1}$ are Gumbel. We first establish suitable non-
asymptotic estimates and bounds for the largest eigenvalue of $L$ in terms of
the largest diagonal element of $L$. An expository review of existing results
for the asymptotic spectrum of a Laplacian random matrix is also presented,
with the goal of noting the differences from the corresponding classical
results for Wigner random matrices. Extensions to Laplacian block random
matrices are indicated.

##  1 Introduction

The largest eigenvalue of a random Laplacian matrix plays an important role in
applications of complex graphs [11], analysis of algorithms for the
$\mathbb{Z}_{2}$ Synchronization, and community detection in the Stochastic
Block Model [1, 13], among other optimization problems in semidefinite
programming [4]. Its limiting behavior both almost surely and in probability
has been considered by Bryc, Dembo and Jiang [8] and Ding and Jiang [12]. The
present paper considers the limiting law of the largest eigenvalue of a random
Laplacian matrix.

The famous Tracy–Widom distribution appears in random matrix theory as the
limiting law of the largest eigenvalue for a large class of random matrices,
including classical Gaussian [25], [26], Wigner [24], Wishart [15], and sparse
matrices [17].

However, there are examples of structured random matrices constructed from a
number of independent random variables less than the one used to construct
Wigner matrices, and for which the limiting law of the largest eigenvalue is
Gumbel. This is the case for palindromic circulant random matrices, as shown
by Bryc and Sethuraman [9], and for Gaussian Hermitian circulant matrices, as
shown by Meckes [19]. The Gumbel distribution is also the limiting law of the
spectral radius of Ginibre ensembles [23].

One of the purposes of the present paper is to show that the Gumbel
distribution is also the limiting law of the largest eigenvalue of a Laplacian
matrix constructed from independent real Gaussian random variables. This kind
of random matrix appears in the $\mathbb{Z}_{2}$ Synchronization problem of
recovering binary labels with Gaussian noise [4].

More specifically, let $X=(X_{ij})$ be an $n\times n$ symmetric matrix. The
Laplacian matrix $L=L_{X}=(L_{ij})$ of $X$ is defined by

$L=D_{X}-X$ (1.1)

where $D_{X}$ is the diagonal matrix whose entries are given by

$(D_{X})_{ii}=\sum_{j=1}^{n}X_{ij}.$ (1.2)

Matrices whose row sums are zero are often called Markov matrices, so a
Laplacian matrix is an example of a Markov matrix.

Let $X=(X_{ij})$ be a Wigner random matrix, that is, an $n\times n$ symmetric
random matrix whose off-diagonal entries $\\{X_{ij},1\leq i<j\leq n\\}$ are
real-valued, independent and identically distributed random variables with
zero mean and unit variance, and the diagonal entries $\\{X_{ii},1\leq i\leq
n\\}$ are independent random variables with zero mean and variance two that
are independent of the off-diagonal entries.

We observe that for a Wigner matrix $X$, the corresponding Laplacian matrix
$L$ has $n(n-1)/2$ independent random variables and its diagonal entries are
not independent of the non-diagonal entries, while $X$ has $n(n+1)/2$
independent random variables.

Let $\lambda_{\max}(X)$ denote the largest eigenvalue of $X$ and
$\lambda_{\max}(L)$ denote that of $L$. It is well known that under suitable
moment conditions, the limiting spectral distribution of $X/\sqrt{n}$ is the
semicircle law in $[-2,2]$, that $\lambda_{\max}(X)/\sqrt{n}$ converges to $2$
almost surely as $n$ goes to infinity, and that the limiting law of
$\lambda_{\max}(X)$, after appropriate rescaling, obeys the Tracy–Widom
distribution.

In contrast, for the Laplacian matrix $L$, under suitable conditions on the
entries of $X$, the limiting spectral law of $L/\sqrt{n}$ is a distribution
with unbounded support which is the free convolution of the semicircular law
with the standard Gaussian distribution [8], [12]. Moreover,
$\lambda_{\max}(L)/\sqrt{n\log n}$ converges to $\sqrt{2}$ in probability as
$n$ goes to infinity [12]. In Section 2 we provide a brief summary of the
above results for Laplacian random matrices, and also indicate some extensions
to block matrices.

Our main result is the weak convergence of $\lambda_{\max}(L)/\sqrt{n-1}$ with
an appropriate rescaling to the Gumbel distribution, as presented in Theorem
4. In order to prove this result, we first show in Section 3 that the limiting
law of the largest entry $\max_{i}L_{ii}/\sqrt{n-1}$ of the sequence of the
triangular array $\\{L_{ii}=L_{ii}^{(n)}:i=1,\ldots,n\\}$ is a Gumbel
distribution for which we use the form of the non-stationary covariance matrix
of $\\{L_{ii}\\}$ to produce a useful approximating sequence of independent
Gaussian random variables. Then we present in Section 4 suitable non-
asymptotic estimates and bounds for the largest eigenvalue of $L$ in terms of
the largest diagonal element of $L$ for a class of Laplacian matrices, namely,
those such that $\max_{i}L_{ii}/\sqrt{n-1}$ grows faster than $\sqrt{\log n}$.
Finally, we prove in Section 5 that, after appropriate rescaling,
$\max_{i}L_{ii}/\sqrt{n-1}$ and $\lambda_{\max}(L)/\sqrt{n-1}$ have the same
limiting law under Gaussian assumptions.

##  2 On the asymptotic spectrum of the Laplacian

In this section we present a summary of two kinds of known results for the
asymptotic spectrum of a random Laplacian matrix, namely, the weak convergence
of the empirical spectral distribution of the Laplacian matrix and the almost
sure behavior of its largest eigenvalue. We remark on the differences from the
corresponding results for Wigner matrices and also indicate some new useful
extensions to block matrices.

###  2.1 Weak convergence of the empirical spectral distribution

As is by now well known, the empirical spectral distribution plays an
important role in the theory of large dimensional random matrices. For a
symmetric $n\times n$ matrix $A_{n}$, let
$\lambda_{1}(A_{n})\geq\cdot\cdot\cdot\geq\lambda_{n}(A_{n})$ denote the
eigenvalues of the matrix $A_{n}$ and let
$\tilde{F}_{n}(x)=\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}\left\\{\lambda_{i}(A_{n})\leq
x\right\\},x\in\mathbb{R}$ be the empirical distribution of its eigenvalues.
When $A_{n}$ is a random matrix, $\tilde{F}_{n}$ is a random distribution
function in $\mathbb{R}.$

In his pioneering work, Wigner [27] proved that for a Wigner matrix $X$, the
empirical spectral distribution of $\frac{1}{\sqrt{n}}X$ converges weakly to
the semicircle law $S$ in $[-2,2]$

$S(dx)=\frac{1}{2\pi}\sqrt{4-x^{2}}\mathbb{I}_{|x|\leq 2}dx.$

with probability one

In the case when $X_{n}$ is a Wigner matrix with Gaussian entries and the
sequence $(X_{n})_{n\geq 1}$ is independent of a sequence of diagonal random
matrices $(\widetilde{D}_{n})_{n\geq 1}$ also with independent Gaussian
entries of zero mean, Pastur and Vasilchuk [21] proved that with probability
one the empirical spectral distribution of
$\frac{1}{\sqrt{n}}(\widetilde{D}_{n}-X_{n})$ converges weakly to a non-random
distribution $\gamma_{M}$, which is the free convolution $S\boxplus\gamma$ of
the semicircle law $S$ in $(-2,2)$ with the standard Gaussian distribution
$\gamma$.

This result is a consequence of a pioneering result by Voiculescu, who
established that, under suitable conditions, if $A=(A_{n})_{n\geq 1}$ and
$B=(B_{n})_{n\geq 1}$ are independent sequences of $n\times n$ random matrices
with empirical spectral distributions $F_{A}$ and $F_{B}$, then $A$ and $B$
become asymptotically free and the asymptotic spectral distribution of the sum
$(A_{n}+B_{n})_{n\geq 1}$ is the free convolution $F_{A}\boxplus F_{B}.$ This
remarkable fact shows the usefulness of free probability in large dimensional
random matrices, since from a knowledge of the eigenvalues of $A_{n}$ and
$B_{n}$, it is not easy to find the eigenvalues of the sum $A_{n}+B_{n}$,
unless $A_{n}$ and $B_{n}$ commute. We refer to the books [2] and [20] for the
definition and properties of the free convolution $\boxplus$ and the
asymptotic freeness of random matrices, and to [7] for a study of
distributions that are free convolutions with the semicircle distribution.

A natural question is whether it is possible to find a corresponding spectral
asymptotic result for the Laplacian matrix $L_{n}$ given by (1.1). The
challenge is that the elements of the diagonal $D_{n}$ of $L_{n}$ are not
independent of the non-diagonal entries of $X_{n}$. However, the result in
[21] predicted that the result holds also for $L_{n}$, but the problem is
nontrivial because $D_{n}$ strongly depends on $X_{n}$. This was done by Bryc,
Dembo and Jiang [8] in the context of Markov random matrices and when the
entries $X_{ij}$ are independent and identically distributed random variables.
We summarize some of their results in what follows.

######  Theorem 1.

Let $L_{n}=L_{X_{n}}$ be the Laplacian matrix of $X_{n}=(X_{ij}^{(n)})$ where
$\left\\{X_{ij}^{(n)}:1\leq i<j\leq n\right\\}_{n\geq 1}$ is a collection of
independent identically distributed random variables of mean $m$ and finite
variance $\sigma^{2}$. Let $\tilde{F}_{n}$ be the empirical spectral
distribution of $\frac{1}{\sqrt{n}}L_{n}.$

i) If $m=0$ and $\sigma^{2}=1$, then, with probability one, as
$n\rightarrow\infty$, $\tilde{F}_{n}$ converges weakly to the free convolution
$\gamma_{M}=S\boxplus\gamma$ of the semicircle law $S$ in $[-2,2]$ with the
standard Gaussian distribution $\gamma.$

ii) The measure $\gamma_{M}$ is a nonrandom symmetric probability measure with
unbounded support which does not depend on the distribution of $X_{ij}^{(n)}$.

iii) If $m$ is not zero and $\sigma^{2}<\infty$, then $\tilde{F}_{n}$
converges weakly to the degenerate distribution $\delta_{-m}$ as
$n\rightarrow\infty$.

The above result was extended by Ding and Jiang [12] to the case when the
random variables $X_{ij}^{(n)}$ are independent but not necessarily
identically distributed. More specifically, they make the following
assumption.

######  Condition 1.

Let $X_{n}=(X_{ij}^{(n)})$ be an $n\times n$ symmetric matrix with
$\\{X_{ij}^{(n)};1\leq i<j\leq n,n\geq 2\\}$ random variables defined on the
same probability space and $\\{X_{ij}^{(n)};1\leq i<j\leq n\\}$ independent
for each $n\geq 2$ (not necessarily identically distributed) with
$X_{ij}^{(n)}=X_{ji}^{(n)}$, $\mathbb{E}(X_{ij}^{(n)})=\mu_{n}$,
$\text{Var}(X_{ij}^{(n)})=\sigma_{n}^{2}>0$ for all $1\leq i<j\leq n$ $n\geq
2$, and

$\sup_{1\leq i<j\leq n,n\geq
2}\mathbb{E}|(X_{ij}^{(n)}-\mu_{n})/\sigma_{n}|^{p}<\infty$

for some $p>0$.

Assuming this condition for some $p>4,$ it is proved in [12] that if

$\tilde{F}_{n}(x)=\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}\left\\{\frac{\lambda_{i}(L_{n})-n\mu_{n}}{\sqrt{n}\sigma_{n}}\leq
x\right\\},\qquad x\in\mathbb{R},$

then, as $n\rightarrow\infty$, with probability one, $\tilde{F}_{n}$ converges
weakly to the distribution of the free convolution
$\gamma_{M}=S\boxplus\gamma$ of the semicircle law $S$ in $[-2,2]$ with the
standard Gaussian distribution $\gamma$.

###  2.2 On the distribution of $\gamma_{M}=S\boxplus\gamma$

Several other properties of the limiting spectral distribution
$\gamma_{M}=S\boxplus\gamma$ are known. In addition to being symmetric and
with unbounded support, it is also shown in [8] that this distribution has a
smooth bounded density $f_{\gamma_{M}}$ and is determined by its moments. Some
of these properties are based on [7], where the author consider distributions
that are free convolutions with the semicircle distribution. It is also proved
in [8] that $\gamma_{M}$ has even moments given by the combinatorial formula

$m_{2k}=\sum_{\omega:\left|\omega\right|=2k}2^{h(\omega)}$

where $h(\omega)$ is the so-called height function that assigns to a pair
partition $\omega$ the number of connected blocks which are of cardinality 2.

However, an explicit expression for $\gamma_{M}$ is not known. One can easily
simulate this distribution using large dimensional random matrices and predict
the form of the empirical spectral distribution. In fact, Figure 1 presents an
example of a consistent result of a large simulation study we have done,
finding that the density $f_{\gamma_{M}}$ can be statistically approximated by
a mixture of a Gaussian distribution and a semicircle distribution, although,
in this approximation, the derivative of the density has two singularities.

More specifically, if a Laplacian matrix $L$ is constructed from independent
identically distributed random variables $\\{X_{ij}^{(n)};1\leq i<j\leq
n,n\geq 2\\},$ with zero mean and variance $\sigma^{2},$ a good approximation
$\widehat{f}_{\gamma_{M}}$ is

$\displaystyle\widehat{f}_{\gamma_{M}}(x)$
$\displaystyle=\frac{\alpha}{2\sigma\sqrt{2}}f_{S}\left(\frac{x}{\sigma\sqrt{2}}\right)+\frac{1-\alpha}{2\sigma\sqrt{2}}f_{\gamma}\left(\frac{x}{\sigma\sqrt{2}}\right)$
(2.1)
$\displaystyle=\frac{\alpha}{2\sigma\sqrt{2}}f_{S_{\sigma}}\left(x\right)+\frac{1-\alpha}{2\sigma\sqrt{2}}f_{\gamma_{\sigma}}\left(x\right),\text{
\ \ }x\in\mathbb{R},$ (2.2)

where $S_{\sigma}$ is the semicircle distribution on
$[-\sqrt{2}\sigma,\sqrt{2}\sigma]$, $\gamma_{\sigma}$ is the Gaussian
distribution of zero mean and variance $2\sigma^{2}$, and $\alpha=\sqrt{2}/2$
is the weight of the mixture.

Figure 1: Figure 1

###  2.3 Almost sure behavior of the largest eigenvalue

Bai and Yin [3] proved that the largest eigenvalue $\lambda_{\max}(X)$ of a
Wigner matrix $X$ satisfies

$\lim_{n\rightarrow\infty}\frac{1}{\sqrt{n}}\lambda_{\max}(X)=2\quad\text{a.s.}\quad\text{
as }n\rightarrow\infty.$ (2.3)

The next result from Ding and Jiang [12] gives the same almost sure
convergence for the largest eigenvalue for symmetric matrices as in the Wigner
case, but with unit variance in the diagonal $X$. The second part is the same
almost sure convergence of the maximum eigenvalue of symmetric matrices with
zero diagonal elements as is the case with adjacency matrices in random
graphs.

######  Proposition 1.

Let $\mathbf{U}_{n}=(u_{ij}^{(n)})$ be an $n\times n$ symmetric random matrix
and assume that for each $n\geq 1$, $\\{u_{ij}^{(n)}:1\leq i\leq j\leq n\\}$
are independent random variables with $\mathbb{E}u_{ij}^{(n)}=0$,
$\text{Var}(u_{ij}^{(n)})=1$ for all $1\leq i,j\leq n$, and $\sup_{1\leq
i,j,\leq n,n\geq 1}\mathbb{E}|u_{ij}^{(n)}|^{6+\delta}<\infty$ for some
$\delta>0$. Then:

  1. (i)

$\lim_{n\to\infty}\frac{\lambda_{\max}(\mathbf{U}_{n})}{\sqrt{n}}=2\quad\text{a.s.}$

  2. (ii)

The statement in (i) still holds if $\mathbf{U}_{n}$ is replaced by
$\mathbf{U}_{n}-\text{diag}(u_{ij}^{(n)})$.

However, for Laplacian matrices, the asymptotic empirical spectral
distribution has unbounded support and therefore it is not expected to have
the same type of convergence to a finite limit, if at all, with the same
normalization $1/\sqrt{n}$. A description of the asymptotic behavior of the
largest eigenvalue of Laplacian matrices is also given in [12, Theorem 1]. It
turns out that when normalized by $1/\sqrt{n\log n}$, the largest eigenvalue
of Laplacian matrices converges to a finite limit in probability.

######  Theorem 2.

Let $L_{n}=L_{X_{n}}$ be the Laplacian matrix of an $n\times n$ symmetric
matrix $X_{n}$ whose entries satisfy Condition 1 for some $p>6$. If
$\mu_{n}=0$ and $\sigma_{n}=1$ for all $n\geq 2$, then

  1. (a)

$\frac{\lambda_{\max}(L_{n})}{\sqrt{n\log n}}\to\sqrt{2}$

in probability as $n\to\infty$.

  1. (b)

Furthermore, if $\\{L_{2},L_{3},\ldots\\}$ are independent Laplacian matrices,
then

$\liminf_{n\rightarrow\infty}\frac{\lambda_{\max}(L_{n})}{\sqrt{n\log
n}}=\sqrt{2}\quad\text{a.s.}$

and

$\limsup_{n\rightarrow\infty}\frac{\lambda_{\max}(L_{n})}{\sqrt{n\log
n}}=2\quad\text{a.s.}$

and the sequence $\\{\lambda_{\max}(L_{n})/\sqrt{n\log n};n\geq 2\\}$ is dense
in $[\sqrt{2},2]\quad\text{a.s.}$

As a consequence of Theorem 2, we have the following result (which will be
used in Section 4), giving upper and lower bounds for the largest eigenvalue
of a Laplacian matrix.

We say that an event $\mathcal{C}_{n}$ occurs with high probability
($\mathrm{w.h.p}$) if for every $\eta>0$, there exists an $n_{0}\in\mathbb{N}$
such that

$\mathbb{P}(\mathcal{C}_{n})\geq 1-\eta\qquad\text{for }\quad n>n_{0}.$

######  Corollary 1.

Let $L=L_{X}$ be the Laplacian matrix of an $n\times n$ symmetric matrix $X$
whose entries satisfy Condition 1 for some $p>6$. If $\mu_{n}=0$ and
$\sigma_{n}=1$ for all $n\geq 2$, then for all $\epsilon>0$

$\lambda_{\max}(L)\leq\sqrt{(2+\epsilon)n\log n}$ (2.4)

with high probability, and

$\lambda_{\max}(L)\geq(2\sqrt{2}-\sqrt{2+\epsilon})\sqrt{n\log n}.$ (2.5)

###### Proof.

This follows from Theorem 2, which ensures that

$\mathbb{P}\left(\left|\frac{\lambda_{\max}(L)}{\sqrt{n\log
n}}-\sqrt{2}\right|>\delta\right)\to 0\qquad\text{as}\quad n\to\infty$

taking $\delta=\sqrt{2+\epsilon}-\sqrt{2}>0$. ∎

Observe that the right side of (2.5) is non-negative if $0<\epsilon<6$.

###  2.4 Block Laplacian matrices

We now indicate some extensions of Theorem 2 to certain block diagonal
Laplacian matrices

$L=\left[\begin{array}[]{cccc}L_{1}&0&\ldots&0\\\ 0&L_{2}&\ldots&0\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&L_{k}\end{array}\right],$ (2.6)

where $\\{L_{1},L_{2},\ldots,L_{k}\\}$ are independent Laplacian random square
matrices of the same size. These block matrices and the behavior of the
largest eigenvalue of $L$ are important in the optimization problems of
Stochastic Block Models: see [4].

As an application of Theorem 2, we find the asymptotic convergence of the
largest eigenvalue for block diagonal Laplacian matrices.

######  Proposition 2.

Let $L$ be a $k$-block Laplacian diagonal matrix in which each block is of
size $n/k$, and the off-diagonal entries in each block are independent.
Suppose that Condition 1 holds for some $p>6$. If whenever $L_{ij}$ is a
nonzero entry of $L$, $\mathbb{E}[L_{ij}]=0$ and $\text{Var}(L_{ij})=1$ for
all $n\geq 2$, then

$\frac{\lambda_{\max}(L)}{\sqrt{n\log n}}\to\sqrt{\frac{2}{k}}$ (2.7)

in probability as $n\to\infty$.

###### Proof.

Let $L_{1},L_{2},\ldots,L_{k}$ be the $k$ blocks of $L$. For $i=1,\ldots,k$
let

$\Omega_{i}^{(n)}=\\{\omega\in\Omega:\lambda_{\max}(L_{j})\leq\lambda_{\max}(L_{i})\text{
for all }j\\}.$

Hence

$\displaystyle\mathbb{P}\left(\left|\frac{\lambda_{\max}(L)}{\sqrt{n\log
n}}-\sqrt{\frac{2}{k}}\right|>\epsilon\right)$
$\displaystyle=\sum_{i=1}^{k}\mathbb{P}\left(\left\\{\left|\frac{\lambda_{\max}(L)}{\sqrt{n\log
n}}-\sqrt{\frac{2}{k}}\right|>\epsilon\right\\}\bigcap\Omega_{i}^{(n)}\right)$
$\displaystyle\leq\sum_{i=1}^{k}\mathbb{P}\left(\left|\frac{\lambda_{\max}(L_{i})}{\sqrt{n\log
n}}-\sqrt{\frac{2}{k}}\right|>\epsilon\right)$
$\displaystyle\leq\sum_{i=1}^{k}\mathbb{P}\left(\left|\frac{\lambda_{\max}(L_{i})}{\sqrt{\frac{n}{k}\log\frac{n}{k}}}\frac{\sqrt{\frac{n}{k}\log\frac{n}{k}}}{\sqrt{n\log
n}}-\sqrt{\frac{2}{k}}\right|>\epsilon\right)$

Note that each matrix $L_{i}$ has size $n/k\times n/k$ and satisfies the
hypotheses of Theorem 2, so, for $i=1,\ldots,k$,

$\frac{\lambda_{\max}(L_{i})}{\sqrt{\frac{n}{k}\log{\frac{n}{k}}}}\to\sqrt{2}$

in probability as $n\to\infty$ and

$\frac{\sqrt{\frac{n}{k}\log\frac{n}{k}}}{\sqrt{n\log
n}}\to\frac{1}{\sqrt{k}}\qquad\text{as}\qquad n\to\infty.$

Then, by Slutsky’s theorem, we have that for each $i=1,\ldots,k$,

$\frac{\lambda_{\max}(L_{i})}{\sqrt{\frac{n}{k}\log{\frac{n}{k}}}}\frac{\sqrt{\frac{n}{k}\log\frac{n}{k}}}{\sqrt{n\log
n}}\to\sqrt{\frac{2}{k}}$

in probability as $n\to\infty$. This guarantees that for all $\epsilon>0$,

$\mathbb{P}\left(\left|\frac{\lambda_{\max}(L)}{\sqrt{n\log
n}}-\sqrt{\frac{2}{k}}\right|>\epsilon\right)\to 0.$

∎

From Proposition 2 and following similar ideas from Corollary 1, we obtain
upper and lower bounds for the largest eigenvalue of a Laplacian block
diagonal matrix.

######  Proposition 3.

Let $L$ be a $k$-block Laplacian diagonal matrix in which each block is of
size $n/k$, where the off-diagonal entries in each block are independent.
Suppose that Condition 1 holds for some $p>6$. If $\mathbb{E}[L_{ij}]=0$ and
$\text{Var}(L_{ij})=\sigma^{2}$ for all $n\geq 2$, then, for all $\epsilon>0$,

$\lambda_{\max}(L)\leq\sigma\sqrt{\left(\frac{2}{k}+\epsilon\right)n\log n}$
(2.8)

with high probability, and

$\lambda_{\max}(L)\geq\sigma\left(2\sqrt{2}-\sqrt{\frac{2}{k}+\epsilon}\right)\sqrt{n\log
n}.$ (2.9)

###### Proof.

The proof follows from Proposition 2, which implies that

$\mathbb{P}\left(\left|\frac{\lambda_{\max}(L)}{\sqrt{n\log
n}}-\sqrt{\frac{2}{k}}\right|>\delta\right)\to 0\qquad\text{as}\qquad
n\to\infty$

taking

$\delta=\sqrt{\frac{2}{k}+\epsilon}-\sqrt{\frac{2}{k}}>0.$

∎

##  3 Limiting law for the largest diagonal entry

Let $L=\left(L_{ij}\right)$ be an $n\times n$ Laplacian matrix whose off-
diagonal entries are independent random variables with zero mean and variance
one, and let

$D^{(n)}=\frac{1}{\sqrt{n-1}}(L_{11},L_{22},\ldots,L_{nn}).$

The random variables $\\{D_{i}^{(n)}\\}_{i=1,\ldots,n}$ are not independent
but rather have the covariance matrix

$\Sigma_{D^{(n)}}=(\Sigma_{D^{(n)}})_{ij}=\left\\{\begin{array}[]{ccc}1&\text{
if }&i=j\\\ \frac{1}{n-1}&\text{ if }&i\neq j.\end{array}\right.$ (3.1)

To find the limiting law of the largest element of $D^{(n)}$ we first consider
a useful representation for $\Sigma_{D^{(n)}}$, which holds in the case of any
distribution of $L_{ij}$ with the same covariance matrix.

The eigenvalues of $\Sigma_{D^{(n)}}$ are $(n-2)/(n-1)$ with multiplicity
$n-1$ and $2$ with multiplicity $1$.

Consider the spectral decomposition of $\Sigma_{D^{(n)}}$

$\Sigma_{D^{(n)}}=U\Lambda U^{t}$

where $\Lambda=(\Lambda_{ii})$ is the diagonal matrix with the eigenvalues of
$\Sigma_{D^{(n)}}$ and $U$ is an orthogonal matrix whose first $n-1$ columns
are an orthonormal basis for the eigenvectors associated to the $n-1$ equal
eigenvalues and the last is a normalized eigenvector of the eigenvalue $2$,
namely, $(1/\sqrt{n},\ldots,1/\sqrt{n})$.

Taking

$\tilde{D}^{(n)}=\Sigma_{D^{(n)}}^{-1/2}D^{(n)}$ (3.2)

we have that the covariance matrix of $\tilde{D}^{(n)}$ is the identity
matrix, so the random variables $\\{\tilde{D}_{i}^{(n)}\\}_{i=1}^{n}$ are
uncorrelated.

Then

$\displaystyle\left(\Sigma_{D^{(n)}}^{1/2}\right)_{ij}$
$\displaystyle=\sum_{l=1}^{n}U_{il}\Lambda_{ll}^{1/2}U_{lj}^{t}$
$\displaystyle=\sum_{l=1}^{n-1}U_{il}\sqrt{\frac{n-2}{n-1}}U_{lj}^{t}+\sqrt{2}U_{in}U_{nj}^{t}$
$\displaystyle=\sqrt{\frac{n-2}{n-1}}\sum_{l=1}^{n}U_{il}U_{lj}^{t}+\left(\sqrt{2}-\sqrt{\frac{n-2}{n-1}}\right)U_{in}U_{nj}^{t},$

and since $U$ is orthogonal and $U_{in}=1/\sqrt{n}$ for $i=1,\ldots,n$, we
obtain

$\left(\Sigma_{D^{(n)}}^{1/2}\right)=\left\\{\begin{array}[]{ccc}\left(\sqrt{2}-\sqrt{\frac{n-1}{n-2}}\right)\frac{1}{\sqrt{n}}U_{nj}^{t}&\text{
if }&i\neq j\\\
\sqrt{\frac{n-2}{n-1}}+\left(\sqrt{2}-\sqrt{\frac{n-1}{n-2}}\right)\frac{1}{\sqrt{n}}U_{ni}^{t}&\text{
if }&i=j.\\\ &&\end{array}\right.$ (3.3)

Thus

$\displaystyle D_{i}^{(n)}$ $\displaystyle=\sum_{\begin{subarray}{c}j=1\\\
j\neq
i\end{subarray}}^{n}\left(\sqrt{2}-\sqrt{\frac{n-1}{n-2}}\right)\frac{1}{\sqrt{n}}U_{nj}^{t}\tilde{D}_{j}^{(n)}+\left(\sqrt{\frac{n-2}{n-1}}+\left(\sqrt{2}-\sqrt{\frac{n-2}{n-1}}\right)\frac{1}{\sqrt{n}}U_{nj}^{t}\right)\tilde{D}_{i}^{(n)}$
$\displaystyle=\left(\sqrt{2}-\sqrt{\frac{n-2}{n-1}}\right)\frac{1}{\sqrt{n}}\sum_{j=1}^{n}U_{nj}^{t}\tilde{D}_{j}{(n)}+\sqrt{\frac{n-2}{n-1}}\tilde{D}_{i}^{(n)},$
(3.4)

which is a useful explicit representation of the elements of $D^{(n)}$ in
terms of the elements of $\tilde{D}^{(n)}$, $\Lambda$, and $U$.

We now assume that the entries $L_{ij}$ of $L$ are Gaussian. The following
result shows that the Gumbel distribution is the limiting law of the largest
diagonal entry of $L/\sqrt{n-1}$.

######  Proposition 4.

Let $L=L_{X}$ be an $n\times n$ Laplacian matrix with $X=(X_{ij})$ a symmetric
matrix whose off-diagonal entries are independent standard Gaussian random
variables. Let

$a_{n}=\sqrt{2\log n}\qquad\text{and}\qquad b_{n}=\sqrt{2\log
n}-\frac{\log\log n+\log 4\pi}{2\sqrt{2\log n}}.$ (3.5)

Then

$M_{n}=a_{n}\left(\frac{\max_{i}L_{ii}}{\sqrt{n-1}}-\sqrt{\frac{n-2}{n-1}}b_{n}\right)$
(3.6)

converges in distribution when $n\rightarrow\infty$ to a Gumbel random
variable.

###### Proof.

Since we are assuming Gaussianness, the uncorrelated random variables
$\\{D_{i}^{*}\\}_{i=1}^{n}$ given by (3.2) are independent standard Gaussian
random variables. Then

$Z=Z_{n}=\sum_{j=1}^{n}U_{nj}^{t}\tilde{D}_{j}^{(n)}$

has the standard Gaussian distribution for all $n$ and by (3)

$D_{i}^{(n)}=\left(\sqrt{2}-\sqrt{\frac{n-2}{n-1}}\right)\frac{1}{\sqrt{n}}Z+\sqrt{\frac{n-2}{n-1}}\tilde{D}_{i}^{(n)}.$
(3.7)

We write

$\displaystyle a_{n}\left(\max_{1\leq i\leq
n}D_{i}^{(n)}-\sqrt{\frac{n-2}{n-1}}b_{n}\right)$
$\displaystyle=a_{n}\left(\max_{1\leq i\leq
n}\tilde{D}_{i}^{(n)}-b_{n}\right)$ $\displaystyle+a_{n}\left(\max_{1\leq
i\leq n}D_{i}^{(n)}-\max_{1\leq i\leq
n}\tilde{D}_{i}^{(n)}-\sqrt{\frac{n-2}{n-1}}b_{n}+b_{n}\right).$ (3.8)

The first term on the right side of (3) converges in distribution to the
Gumbel law by the classical extreme value result for maxima of i.i.d. Gaussian
random variables; see [16] or [22].

On the other hand, using (3.7) we obtain

$\displaystyle\max_{1\leq i\leq n}D_{i}^{(n)}$ $\displaystyle=\max_{1\leq
i\leq
n}\left(\left(\sqrt{2}-\sqrt{\frac{n-2}{n-1}}\right)\frac{1}{\sqrt{n}}Z+\sqrt{\frac{n-2}{n-1}}\tilde{D}_{i}^{(n)}\right)$
$\displaystyle=\left(\sqrt{2}-\sqrt{\frac{n-2}{n-1}}\right)\frac{1}{\sqrt{n}}Z+\sqrt{\frac{n-2}{n-1}}\max_{1\leq
i\leq n}\tilde{D}_{i}^{(n)}.$

Thus

$\displaystyle\left|\max_{1\leq i\leq n}D_{i}^{(n)}-\max_{1\leq i\leq
n}\tilde{D}_{i}^{(n)}-\left(\sqrt{\frac{n-2}{n-1}}-1\right)b_{n}\right|$
$\displaystyle\leq\left|\left(\sqrt{2}-\sqrt{\frac{n-2}{n-1}}\right)\frac{1}{\sqrt{n}}Z\right|+\left|\sqrt{\frac{n-2}{n-1}}\max_{1\leq
i\leq n}\tilde{D}_{i}^{(n)}-\max_{1\leq i\leq
n}\tilde{D}_{i}^{(n)}-\left(\sqrt{\frac{n-2}{n-1}}-1\right)b_{n}\right|$
$\displaystyle=\left(\sqrt{2}-\sqrt{\frac{n-2}{n-1}}\right)\frac{1}{\sqrt{n}}\left|Z\right|+\left(\sqrt{\frac{n-2}{n-1}}-1\right)\left|\max_{1\leq
i\leq n}\tilde{D}_{i}^{(n)}-b_{n}\right|.$

Then by Slutsky’s theorem

$a_{n}\left|\max_{1\leq i<n}D_{i}^{(n)}-\max_{1\leq
i<n}\tilde{D}_{i}^{(n)}-\left(\sqrt{\frac{n-2}{n-1}}-1\right)b_{n}\right|\to
0\qquad\text{in probability }$

as $n$ goes to infinity. Hence, the second term on the right side of (3) also
goes to zero in probability as $n$ goes to infinity.

Then, again using Slutsky’s theorem in (3), we obtain that $M_{n}$ converges
in distribution to a Gumbel random variable as $n$ goes to infinity. ∎

######  Remark.

The last result is similar to Theorem 3.1 in [6]. However, in [6], a fixed
sequence $\\{X_{n}:n=0,n=\pm 1,\ldots\\}$ of stationary random variables is
considered, while Proposition 4 deals with a triangular array
$\\{L_{ii}^{(n)}:i=1,\ldots,n\\}$, as is the case in the study of the largest
eigenvalue of ensembles of random matrices.

##  4 Non-asymptotic estimates for the largest eigenvalue

A consequence of the classical Courant–Fischer min-max Theorem [14] gives that

$\max_{i}L_{ii}\leq\lambda_{\max}(L),$ (4.1)

without more assumptions than that the matrix $L$ is symmetric. This section
establishes a converse inequality, which is valid $\mathrm{w.h.p.}$, for a
class of Laplacian matrices of symmetric Wigner matrices.

The intuition for this comparison is the following. From Theorem 2(a),
$\lambda_{\max}(L)$ grows like $\sqrt{2n\log n}$. On the other hand, the
diagonal entries of a Laplacian matrix are sums of independent random
variables, so by the Central Limit Theorem they would have an approximately
Gaussian distribution for large $n$. It can be proved that for Gaussian random
variables $\gamma_{i}$ (not necessarily independent as is the case of
$L_{ii}$) $\max_{i}\gamma_{i}$ grows like $\sqrt{n\log n}$. This and (4.1)
suggests that $\max_{i}L_{ii}$ and $\lambda_{\max}(L)$ behave similarly when
$n$ is large.

This comparison of $\max_{i}L_{ii}$ and $\lambda_{\max}(L)$ is known when the
Wigner matrix has Gaussian or bounded entries [4, 5]. Our Theorem 3 below
makes rigorous the above motivation, and is a general result under the
assumption (4.2) and uses Corollary 1, which is a consequence of Theorem 2(a).
For the sake of completeness we give a proof that this assumption is satisfied
when the Laplacian matrix $L$ is constructed from a Wigner matrix with
Gaussian entries, using concentration results for the maximum of Gaussian
random variables and Sudakov Minorization which deals with correlated Gaussian
random variables.

######  Theorem 3.

Let $L=(L_{ij})$ be the Laplacian matrix of an $n\times n$ symmetric Wigner
matrix $X=(X_{ij})$ constructed from independent random variables with zero
mean, variance $\sigma^{2}$, and finite $p$-th moment for some $p>6$. If there
exists a $c>0$ such that

$\sigma\sqrt{(n-1)\log n}\leq c\max_{i}L_{ii}\qquad\mathrm{w.h.p}.,$ (4.2)

then for all $\epsilon>0$ and

$K=c\sqrt{2+\epsilon}>0,$ (4.3) $\lambda_{\max}(L)\leq
K\left(1+\frac{1}{\sqrt{n-1}}\right)\max_{i}L_{ii}\qquad\mathrm{w.h.p}.$ (4.4)

###### Proof.

Let $\hat{L}$ be the matrix given by

$\hat{L}=\frac{1}{\sigma}L.$

We note that for all $1\leq i<j\leq n$, $\mathbb{E}\hat{L}_{ij}=0$ and
$\mathbb{E}\hat{L}_{ij}^{2}=1$.

From Corollary 1, we have that

$\lambda_{\max}(\hat{L})\leq\sqrt{(2+\epsilon)n\log n}\qquad\mathrm{w.h.p}.$

and

$\lambda_{\max}(L)\leq\sigma\sqrt{(2+\epsilon)n\log n}\qquad\mathrm{w.h.p}.$

Hence, with high probability

$\displaystyle\lambda_{\max}(L)$
$\displaystyle\leq\sigma\sqrt{(2+\epsilon)(n-1)\log
n}+\sigma\sqrt{(2+\epsilon)\log n}$ $\displaystyle\leq
c\sqrt{2+\epsilon}\max_{i}L_{ii}+\sigma\sqrt{(2+\epsilon)\log n}$
$\displaystyle=\left(c\sqrt{2+\epsilon}+\frac{1}{\max_{i}L_{ii}}\sigma\sqrt{(2+\epsilon)\log
n}\right)\max_{i}L_{ii}.$ (4.5)

From (4.2) we have that

$\frac{1}{\max_{i}L_{ii}}\sigma\sqrt{(2+\epsilon)\log
n}\leq\frac{c\sigma\sqrt{(2+\epsilon)\log n}}{\sigma\sqrt{(n-1)\log
n}}=\frac{c\sqrt{2+\epsilon}}{\sqrt{n-1}}.$

Now, replacing the last term in (4), we obtain that

$\displaystyle\lambda_{\max}(L)$
$\displaystyle\leq\left(c\sqrt{2+\epsilon}+\frac{c\sqrt{2+\epsilon}}{\sqrt{n-1}}\right)\max_{i}L_{ii}$
$\displaystyle=c\sqrt{2+\epsilon}\left(1+\frac{1}{\sqrt{n-1}}\right)\max_{i}L_{ii}.$

Hence for $\epsilon>0$, if we take $K=c\sqrt{2+\epsilon}$, it follows that

$\lambda_{\max}(L)\leq
K\left(1+\frac{1}{\sqrt{n-1}}\right)\max_{i}L_{ii}\qquad\mathrm{w.h.p}.$

∎

The inequality (4.2) is satisfied by several distributions. In particular,
under Gaussian assumptions, as we now show.

######  Proposition 5.

Let $L=(L_{ij})$ be the Laplacian matrix of an $n\times n$ symmetric Wigner
matrix $X=(X_{ij})$ constructed from i.i.d. standard Gaussian random
variables. Then (4.2) is satisfied.

###### Proof.

We note that

$\max_{i}L_{ii}=\sqrt{n-1}\max_{i}\frac{L_{ii}}{\sqrt{n-1}}=\sqrt{n-1}\max_{i}\gamma_{i},$

where $\gamma_{i}$ are standard Gaussian random variables with covariance
matrix given by (3.1).

Now, using concentration results (Theorem 3.12 in [18]) we obtain that for all
$\alpha>0$

$\max_{i}\gamma_{i}\geq\mathbb{E}\max_{i}\gamma_{i}-\sqrt{\alpha\log
n}\qquad\text{w.h.p.}.$ (4.6)

From the structure of the covariance matrix, it follows that for all $i\neq j$
and $n>3$,

$\mathbb{E}\left(\gamma_{i}-\gamma_{j}\right)^{2}=2-2\frac{1}{n-1}=2\left(\frac{n-2}{n-1}\right)\geq
1.$

So, Sudakov Minorization (Lemma A.3 in [10]) implies

$\mathbb{E}\max_{i}\gamma_{i}\geq C\sqrt{\log n},$ (4.7)

where $C$ is a positive constant independent of $n$ and the covariance of the
Gaussian random variables $\gamma_{i}$’s. Hence, combining (4.6) and (4.7),
with high probability

$\displaystyle\max_{i}L_{ii}$ $\displaystyle\geq\sqrt{n-1}\left(C\sqrt{\log
n}-\sqrt{\alpha\log n}\right)$ $\displaystyle=(C-\sqrt{\alpha})\sqrt{(n-1)\log
n}.$

Then (4.2) is satisfied with $c=(C-\sqrt{\alpha})^{-1}$. ∎

######  Remark.

  1. (a)

It is well known (see for example Lemma 2.3 in [18] or Appendix A in [10])
that the expected value of the maximum of $n$ standard Gaussian random
variables, even if they are not independent, cannot be much larger that
$\sqrt{2\log n}$. For that reason, the universal constant in the Sudakov
Minorization is less than or equal to $\sqrt{2}$. So with this, we can take
$\alpha$ such that $C\geq 1-\sqrt{\alpha}$, and taking
$\epsilon=2((C-\sqrt{\alpha})^{2}-1)\geq 0$ we obtain that in the Gaussian
case the constant $K$ can be equal to $\sqrt{2}$.

  2. (b)

The constant $K$ might not be sharp but it is useful for our weak convergence
result in Section 5.

For the non-Gaussian case, when the random variables $X_{ij}$ have bounded
support, Bandeira proved (proof of Theorem 2.1 in [4]) that condition (4.2) is
satisfied. Moreover, the following bound can be established as a consequence
of Theorem 2.1 in [4], which considers Laplacian matrices constructed from
Wigner matrices with bounded entries but not necessarily with the same
distribution.

######  Proposition 6.

Let $L=(L_{ij})$ be the Laplacian matrix of an $n\times n$ symmetric Wigner
matrix $X=(X_{ij})$ constructed from independent random variables bounded by
$M$, with zero mean and variance $\sigma^{2}.$ If there exists a $c>0$ such
that

$\sigma\sqrt{n-1}\geq cM\sqrt{\log n},$

then there exist positive constants $c_{1},C_{1},\beta$ depending only on $c,$
such that

$\lambda_{\max}(L)\leq\left(1+\frac{C_{1}}{\sqrt{\log
n}}\right)\max_{i}L_{ii}\qquad$ (4.8)

with probability at least $1-c_{1}n^{-\beta}$.

##  5 Limiting law for the largest eigenvalue

We are now ready to prove that the Gumbel distribution is the limiting law of
the largest eigenvalue of a Laplacian random matrix constructed from Gaussian
entries. We write

$a_{n}^{\prime}=\frac{a_{n}}{\sqrt{2}}=\sqrt{\log n}\qquad\text{and}\qquad
b_{n}^{\prime}=\sqrt{2}b_{n}=2\sqrt{\log n}-\frac{\log\log n+\log
4\pi}{\sqrt{2\log n}}.$ (5.1)

######  Theorem 4.

Let $L=L_{X}$ be an $n\times n$ Laplacian matrix with $X=(X_{ij})$ a symmetric
matrix whose off-diagonal entries are independent standard Gaussian random
variables. Then

$R_{n}=a_{n}^{\prime}\left(\frac{\lambda_{\max}(L)}{\sqrt{n-1}}-b_{n}^{\prime}\sqrt{\frac{n-2}{n-1}}\right)$
(5.2)

converges in distribution when $n\to\infty$ to a Gumbel random variable with
distribution $G(x)=\exp(-e^{-x})$ for all $x\in\mathbb{R}$.

We observe that the rescaling sequences $a_{n}^{\prime}$ and $b_{n}^{\prime}$
given by (5.1) have the same order as the appropriate choices for the extreme
value theorem for the maxima of a sequence of Gaussian random variables in the
i.i.d. and the stationary sequence cases; see [6], [22] respectively and [16].

###### Proof.

We first note, with the notation of Section 2,

$\displaystyle
a_{n}^{\prime}\left(\frac{\lambda_{\max}(L)}{\sqrt{n-1}}-b_{n}^{\prime}\sqrt{\frac{n-2}{n-1}}\right)$
$\displaystyle=a_{n}\left(\max_{1\leq i\leq
n}D_{i}^{(n)}-b_{n}\sqrt{\frac{n-2}{n-1}}\right)$
$\displaystyle+a_{n}^{\prime}\left(\frac{\lambda_{\max}(L)}{\sqrt{n-1}}-\sqrt{2}\max_{1\leq
i\leq n}D_{i}^{(n)}\right).$ (5.3)

From Proposition 4, the first term on the right side of (5) converges in
distribution to a Gumbel random variable. On the other hand, taking
$K=\sqrt{2}$ in Theorem 3 and Proposition 5, we have that

$\left|\frac{\lambda_{\max}(L)}{\sqrt{n-1}}-\sqrt{2}\max_{1\leq i\leq
n}D_{i}^{(n)}\right|\leq\left|\frac{\sqrt{2}}{\sqrt{n-1}}\max_{1\leq i\leq
n}D_{i}^{(n)}\right|$

and

$\displaystyle\frac{a_{n}}{\sqrt{2}}\left|\frac{\lambda_{\max}(L)}{\sqrt{n-1}}-\sqrt{2}\max_{1\leq
i\leq n}D_{i}^{(n)}\right|$
$\displaystyle\leq\frac{a_{n}}{\sqrt{2}}\left|\frac{\sqrt{2}}{\sqrt{n-1}}\max_{1\leq
i\leq n}D_{i}^{(n)}\right|$
$\displaystyle\leq\frac{a_{n}}{\sqrt{n-1}}\left|\max_{1\leq i\leq
n}D_{i}^{(n)}-b_{n}\sqrt{\frac{n-2}{n-1}}+b_{n}\sqrt{\frac{n-2}{n-1}}\right|$
$\displaystyle\leq\frac{a_{n}}{\sqrt{n-1}}\left|\max_{1\leq i\leq
n}D_{i}^{(n)}-b_{n}\sqrt{\frac{n-2}{n-1}}\right|$
$\displaystyle\quad\qquad\qquad+\frac{a_{n}b_{n}}{\sqrt{n-1}}\sqrt{\frac{n-2}{n-1}}.$
(5.4)

Now using Proposition 4 and Slutsky’s theorem, the first term in the last
inequality goes to zero in probability as $n$ goes to infinity. Hence, using
$a_{n}$ and $b_{n}$ in (3.5), we have that the second term in (5) goes to zero
as $n$ goes to infinity. Therefore

$\frac{a_{n}}{\sqrt{2}}\left|\frac{\lambda_{\max}(L)}{\sqrt{n-1}}-\sqrt{2}\max_{1\leq
i\leq n}D_{i}^{(n)}\right|\to 0\qquad\text{as}\qquad n\to\infty$

in probability. Thus, the second term of the right side of Equation (5) tends
to zero as $n$ goes to infinity, and we obtain that $R_{n}$ in (5.2) converges
in distribution to a Gumbel random variable as $n$ goes to infinity. ∎

######  Remark.

It is easy to find the asymptotic distribution of the largest eigenvalue of a
$k$-block Laplacian diagonal matrix $L$ given by (2.6) when the blocks are
independent and all the entries are Gaussian. Indeed the largest eigenvalue
$\lambda_{\max}(L)$ of $L$ satisfies

$R_{n}^{k}=a_{n}^{\prime}\left(\frac{\lambda_{\max}(L)}{\sqrt{n-1}}-b_{n}^{\prime}\sqrt{\frac{n-2}{n-1}}\right)$

converges in distribution when $n\to\infty$ to a random variable with
distribution $G_{k}(x)=\exp(-ke^{-x})$ for all $x\in\mathbb{R}$, where
$a_{n}^{\prime}$ and $b_{n}^{\prime}$ are given by (5.1).

Acknowledgments. The authors would like to thank the anonymous referee of our
manuscript for the valuable and constructive suggestions that improved the
revised version of our work.

## References

  * [1] E. Abbe, A. S. Bandeira, A. Bracher, and A. Singer, Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery, IEEE Transactions on Network Science and Engineering, 1 (2014), pp. 10–22.
  * [2] G. W. Anderson, A. Guionnet, and O. Zeitouni, An Introduction to Random Matrices, Cambridge University Press, 2010.
  * [3] Z.-D. Bai and Y.-Q. Yin, Necessary and sufficient conditions for almost sure convergence of the largest eigenvalue of a Wigner matrix, Ann. Probab., 16 (1988), pp. 1729–1741.
  * [4] A. Bandeira, Random Laplacian matrices and convex relaxations, Found. Comput. Math., 18 (2018), pp. 345–379.
  * [5] A. Bandeira, A. Singer, and T. Strohme, Mathematics of Data Science, in preparation.
  * [6] S. M. Berman, Limit theorems for the maximum term in stationary sequences, Ann. Math. Statist., 35 (1964), pp. 502–516.
  * [7] P. Biane, On the free convolution with a semi-circular distribution, Indiana Univ. Math. J., 46 (1997), pp. 705–718.
  * [8] W. Bryc, A. Dembo, and T. Jiang, Spectral measure of large random Hankel, Markov and Toeplitz matrices, Ann. Probab., 34 (2006), pp. 1–38.
  * [9] W. Bryc and S. Sethuraman, A remark on the maximum eigenvalue for circulant matrices, in High Dimensional Probability V: The Luminy Volume, Institute of Mathematical Statistics, 2009, pp. 179–184.
  * [10] S. Chatterjee, Superconcentration and Related Topics, Springer-Verlag, Berlin, 2014.
  * [11] F. Chung and L. Lu, Complex Graphs and Networks, American Mathematical Society, Providence, RI, USA, 2006.
  * [12] X. Ding and T. Jiang, Spectral distributions of adjacency and Laplacian matrices of random graphs, Ann. Appl. Probab., 20 (2010), pp. 2086–2117.
  * [13] M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42 (1995), pp. 1115–1145.
  * [14] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 2012.
  * [15] I. M. Johnstone, On the distribution of the largest eigenvalue in principal components analysis, Ann. Statist., 29 (2001), pp. 295–327.
  * [16] M. R. Leadbetter, G. Lindgren, and H. Rootzén, Extremes and Related Properties of Random Sequences and Processes, Springer-Verlag, Berlin, 1983.
  * [17] J. O. Lee and K. Schnelli, Local law and Tracy–Widom limit for sparse random matrices, Probab. Theory and Related Fields, 171 (2018), pp. 543–616.
  * [18] P. Massart, Concentration Inequalities and Model Selection. Ecole d’Eté de Probabilités de Saint-Flour XXXIII.2003, Springer-Verlag, Berlin, 2007.
  * [19] M. W. Meckes, Some results on random circulant matrices, in High Dimensional Probability V: The Luminy Volume, Institute of Mathematical Statistics, 2009, pp. 213–223.
  * [20] J. A. Mingo and R. Speicher, Free Probability and Random Matrices, Springer-Verlag, Berlin, 2017.
  * [21] L. Pastur and V. Vasilchuk, On the law of addition of random matrices, Comm. Math. Phys., 214 (2000), pp. 249–286.
  * [22] S. I. Resnick, Extreme Values, Regular Variation, and Point Processes, Springer-Verlag, Berlin, 1987.
  * [23] B. Rider and C. D. Sinclair, Extremal laws for the real Ginibre ensemble, Ann. Appl. Probab., 24 (2014), pp. 1621–1651.
  * [24] A. Soshnikov, Universality at the edge of the spectrum in Wigner random matrices, Comm. Math. Phys., 207 (1999), pp. 697–733.
  * [25] C. A. Tracy and H. Widom, Level-spacing distributions and the Airy kernel, Comm. Math. Phys., 159 (1994), pp. 151–174.
  * [26] , On orthogonal and symplectic matrix ensembles, Comm. Math. Phys., 177 (1996), pp. 727–754.
  * [27] E. P. Wigner, On the distribution of the roots of certain symmetric matrices, Ann. Math., 67(2) (1958), pp. 325–327.