# Why must every data scientist be a Platonist

Collin Joseph Van Cuyk∗ Liang Hong111Department of Mathematical Sciences, The
University of Texas at Dallas, 800 West Campbell Road, Richardson, TX 75080,
USA.

###### Abstract

Data scientists are not mathematicians, but they make heavy use of mathematics
in their daily work. While mathematicians can study a mathematical object
which is inaccessible to our five senses, data scientists must deal with real-
world data which are observable to us. This fine line suggests that a data
scientist’s philosophical position on mathematics might have a nontrivial
impact on their work. By examining how different philosophical views of
mathematics affect the interpretation of the basic model assumption in data
science, we arrive at the conclusion that a data scientist, who uses modern
probabilistic and statistical tools, must be a Platonist.

_Keywords and phrases:_ Philosophy of mathematics; data science; Platonism;
finitism; formalism.

##  1 Introduction

Mathematics is an indispensable tool for every data scientist. While most data
scientists barely examine their own philosophical positions on mathematics,
various philosophical outlooks challenge the basic assumptions made by data
scientists. In the current literature, there are three dominating schools of
thought concerning mathematical philosophy: (i) Platonism, (ii) Finitism, and
(iii) Formalism. The names of these three schools vary slightly in the
literature; see, for example, Benacerraf and Putnam (1983), George and
Vellenman (2002), Henle (1992), Kleene (1950), and Kunen (1980, 2011, 2012).
In this article, we will follow the terminologies of Chapter III of Kunen
(2012). Specifically, we will consider a Platonist to be the one who considers
all of mathematics literally real. Apparently, there is a good portion of
modern mathematics which is not observable in our real world, such as many
well-founded sets. A Platonist believes this part of mathematics exists in a
world that is inaccessible to our five senses. Next, let a finitist be one who
works with only those mathematical entities which are finite. Finitists reject
the notion of a definite infinity, although they will allow for the concept of
a potential infinite, but clarify that this process will never actually be
completable. In short, a finitist believes only in finitary mathematics.
Finally, we take a formalist be one who accepts as real only those things
which a finitist accepts, but recognizes the intellectual intrigue of infinite
mathematics. That is, they only recognize the things accepted within finitism
as meaningful, but they consider any infinite mathematics as an intellectual
game. While none of these three philosophical positions is considered to be
the “correct” position, we will show that each has a nontrivial impact on the
basic model assuption in data science. In particular, we will draw the
conclusion that an honest data scientist must be a Platonist. Throughout, by a
data scientist, we mean a person whose profession is to analyze data using
usual tools in modern probability and statistics.

##  2 The basic model assumption in data science

The most fundamental assumption of data science is that there is an underlying
unobservable probability law that governs all observable data. Depending on
the problem at hand, the data scientist chooses his assumption about this law.
Examples include but are not limited to a density model, a linear model, or a
time series model. To illustrate our point, it suffices to consider the
parametric density model. Most data science textbooks describe such a model as
follows. Assume that data $X_{1},\ldots,X_{n}$ are independently and
identically distributed (iid) according to a true (but unobservable)
probability density function $f^{\star}$. Since $f^{\star}$ is unobservable, a
data scientist posits a parametric model

$\mathcal{M}=\\{f_{\theta}\mid\theta\in\Theta\\},$

where $\Theta$, called the parameter space, is a subset of a finite-
dimensional Euclidean space. For example, if we consider a gamma model with
shape parameter $\alpha>0$ and rate parameter $\lambda>0$ where both $\alpha$
and $\lambda$ are unknown, then

$\mathcal{M}=\\{f_{(\alpha,\lambda)}\mid(\alpha,\lambda)\in\mathbb{R}_{+}\times\mathbb{R}_{+}\\},$

where $\mathbb{R}_{+}=(0,\infty)$ and

$f_{(\alpha,\lambda)}(x)=\frac{\lambda^{\alpha}}{\Gamma(\alpha)}x^{\alpha-1}e^{-\lambda
x},x>0,$

and $\Gamma$ is the gamma function.

If a data scientist is a Platonist, then this gamma model $\mathcal{M}$ makes
perfect sense, every ingredient used in the model description is well-defined,
and $\mathcal{M}$ is essentially an uncountable family of gamma distributions.
That is, a Platonist’s interpretation of this model is the same as what is in
a data science textbook (e.g. Lehmann 1983 and Schervish 1995).

However, to a finitist, the above model description cannot be interpreted as
the textbook intends. What’s even worse, this model makes no sense to a
finitist. First, since a finitist rejects any definite infinity, the parameter
space of the gamma model, i.e. $\mathbb{R}_{+}\times\mathbb{R}_{+}$, cannot be
an uncountable set. A finitist can only allow the parameter space $\Theta$ to
be a finite set. This evidently differs from what is described in a data
science textbook; see, for example, Lehmann (1983) and Schervish (1995). A
moment of reflection reveals that there is a more serious issue a finitist
will take exception to. In modern probability theory, a probability density
function $f$ is an almost surely nonnegative Borel-meausrable function such
that $\int_{\infty}^{-\infty}f(t)dt=1$, and

$F(x)=\int_{-\infty}^{x}f(t)dt,$

where $F$ is the corresponding cumulative distribution function. Since a
definite integral is the limit of a Riemann sum which is not an acceptable
concept to a finitist, the notion of a probability density function does not
make sense to a finitist. Therefore, the description of a gamma model using
gamma densities make no sense to a finitist, either. Similarly, a finitist
will reject the nice relationship between of a probability density function
and its corresponding distribution function $F^{\prime}(x)=f(x)$. Therefore, a
data scientist cannot be a finitist.

How about a formalist? Can a data scientist be a formalst? A formalist is a
“diplomatic” person; he takes a position to avoid being confrontational with
either a Platonist or a finitist. Though his position is beyond reproach in
mathematics, the story is different when it comes to data science. A formalist
only believes finitary mathematics to be real. Therefore, the above gamma
model makes no sense to him either. Can he simply consider this model as an
intellectual model (which might be meaningless in the real-world) as he always
does for the infinitary mathematics? The answer is negative. Since a data
scientist deals with real-world data which are observable to us, his job is to
propose a “best” model to describe these real-world data. Therefore, an honest
data scientist cannot posit a model he does not believe exists.

##  3 What about Bayesian analysis?

In the previous section, we evidently took the frequentist approach. However,
if a data scientist options for the Bayesian approach, he will face the same
issue. To see that, we recall that the parametric Bayesian model treats data
$X_{1},\ldots,X_{n}$ to be iid conditioning on the parameter $\theta$ and puts
a prior distribution $\Pi_{0}$ on $\theta$. That is, a parametric Bayesian
model is specified hierarchically as

$\theta\sim\Pi_{0}\text{ and
$X_{1},\ldots,X_{n}\mid\theta\overset{iid}{\sim}f_{\theta}$},$

where $f_{\theta}$ is the probability density function on the $X$-space
indexed by $\theta\in\Theta$. Then the prior distribution $\Pi_{0}$ is updated
to the posterior distribution $\Pi_{n}$ via the Bayes formula:

$\Pi_{n}(A)=\frac{\int_{A}L(\theta)d\Pi_{0}(\theta)}{\int_{\Theta}L(\theta)d\Pi_{0}(\theta)},\quad
A\subset\Theta,$

where $L(\theta)=\prod_{i=1}^{n}f(X_{i})$ is the likelihood function and $A$
is a $\Pi_{0}$-measurable set. For a detailed treatment of Bayesian analysis,
we refer to Chapter 1 of Schervish (1995) and Chapter 4 of Berger (2006).
Because integration and probability density functions (hence the likelihood
function) are both involved in a Bayesian model, the same argument we used in
the previous section shows that a data scientist can be neither a finitist nor
a formalist. Thus a data scientist must be a Platonist.

##  4 Concluding remarks

If a data scientist hopes to be consistent with their own philosophy, there is
little they, as a finitist, could accomplish. Most if not all practical
applications of statistical inference fail to function within absolutely
defined domains or purely discrete, purely finite models. It is not our
purpose to suggest which philosophy has more merit, however for all practical
or applied purposes the data scientist cannot restrict themselves so
significantly as required by finitism. What of the formalist? Believing to be
real only mathematics accepted by the finitist, the formalist will struggle
with the same contradictions and problems between their work and their
philosophy. The formalist could not ethically present findings which they
considered to be only “a game”. We are forced, then, to conclude that the
modern data scientist must hold the philosophy of Platonism if they wish to
complete their work satisfied that it is both real and meaningful.

## References

Berger, J.O. (2006). _Statistical Decision Theory and Bayesian Analysis_.
Springer: New York.

Benacerraf, P. and Putnam, H. (1983). _Philosophy of mathematics,_ Second
Edition. Cambridge University Press: Cambridge, UK.

George, A. and Velleman, D. J. (2002). _Philosophies of Mathematics._.
Blackwell Publishers Inc.

Henle, J.M. (1991). The happy formalist. _Mathematical Intelligencer_ 13(1),
12–18.

Kleene, S.C. (1950). _Introduction to MetaMathematics_. North-Holland:
Amsterdam.

Kunen, K. (1980). _Set Theory: An Introduction to Independence Proofs_.
Elsevier: Amsterdam

Kunen, K. (2011). _Set Theory_. College Publications: London, UK.

Kunen, K. (2012). _The Foundations of Mathematics_ , Revised Edition. College
Publications: London, UK.

Lehmann, E.L. (1983). _Theory of Point Estimation_. Wiley: New York.

Schervish, M.J. (1995). _Theory of Statistics_. Springer: New York.


# Limiting Distributions of Sums with Random Spectral Weights

Ángel Chávez  Department of Mathematics and Statistics, Pomona College, 610 N.
College Ave., Claremont, CA 91711<EMAIL_ADDRESS>and  Jacob Waldor
<EMAIL_ADDRESS>
###### Abstract.

This paper studies the asymptotic properties of weighted sums of the form
$Z_{n}=\sum_{i=1}^{n}a_{i}X_{i}$, in which $X_{1},X_{2},\ldots,X_{n}$ are
i.i.d. random variables and $a_{1},a_{2},\ldots,a_{n}$ correspond to either
eigenvalues or singular values in the classic Erdős-Rényi-Gilbert model. In
particular, we prove central limit-type theorems for the sequences
$n^{-1}Z_{n}$ with varying conditions imposed on $X_{1},X_{2},\ldots,X_{n}$.

###### Key words and phrases:

random matrix, random graph, eigenvalue, singular value, central limit
theorem, graph energy, Schatten norm, sub-gaussian, convolution, method of
moments

###### 2020 Mathematics Subject Classification:

60B20, 60F05, 05C80

##  1\. Introduction

Suppose $X_{1},X_{2},\ldots$ is a sequence of random variables. A classic
problem in probability is to understand the limiting behavior of the sum

$\displaystyle Y_{n}=X_{1}+X_{2}+\cdots+X_{n}.$

Early versions of this problem, which consider the case when
$X_{1},X_{2},\ldots$ are independent Bernoulli trials, are rooted in the work
of de Moivre [10] and Laplace [22] pertaining to normal approximations to the
binomial distribution. These classic results mark the beginnings of a long
standing problem of approximating laws of sums of random variables by normal
distributions. This two-hundred year problem ultimately culminated with what
is today known as the central limit theorem. Major contributions towards our
modern understanding of the central limit theorem are attributed, in
particular, to Lévy [23], Lindeberg [24] and Lyapunov [25], among several
others.

Suppose $X_{1},X_{2},\ldots$ are independent and identically distributed
(i.i.d.) random variables with mean $\mu$ and finite positive variance
$\sigma^{2}$. The version of the central limit theorem attributed to Lévy and
Lindeberg [5, Thm. 27.1] asserts that the sequence of random variables
$(Y_{n}-n\mu)/(\sigma\sqrt{n})$ converge in distribution to a standard normal.
A theorem attributed to Lyapunov [5, Thm. 27.3] shows the assumption that the
variables $X_{1},X_{2},\ldots$ be identically distributed can even be relaxed
as long as the absolute moments of the $X_{i}$ satisfy a certain (Lyapunov)
growth condition.

The present focus is to study the limiting behavior of sequences of the form

$\displaystyle Z_{n}(\boldsymbol{a})=a_{1}X_{1}+a_{2}X_{2}+\cdots+a_{n}X_{n},$
(1.1)

in which $X_{1},X_{2},\ldots$ are i.i.d. random variables and the weights
$a_{1},a_{2},\ldots$ correspond to either the eigenvalues or the singular
values of a random symmetric matrix. Specifically, we take eigenvalues and
singular values corresponding to the Erdős-Rényi-Gilbert random graph model. A
random graph in this model, which was developed independently by Erdős-Rényi
[14, 15] and Gilbert [18], is constructed by attaching edges among a set of
labeled vertices independently with probability $p$. The random variables
$a_{i}X_{i}$ in this case are neither independent nor indentically
distributed, and there is no general method available to handle this
situation. However, adjacency matrices of Erdős-Rényi-Gilbert graphs have
bounded entries which, modulo the constraints imposed by symmetry, are
independent. This simple fact, together, with the almost sure convergence of
their empirical spectral distributions to the semicircular law, allow us to
establish central limit-type theorems for the sequences
$n^{-1}Z_{n}(\boldsymbol{a})$.

###  1.1. Notation and Terminology

Graph theoretic terminology may be found in [6]. A _graph $G$ of order $n$_ is
an ordered pair $(V,E)$ consisting of a set $E=E(G)$ of _edges_ and a set
$V=V(G)$ of _vertices_ such that $|V|=n$. We adopt standard notation and let
$m=|E(G)|$ denote the number of edges in a graph $G$. A graph is _simple_ if
it contains no loops or multiple edges and it is _connected_ if it contains no
isolated vertices. If $G$ is a graph of order $n$, then its _adjacency matrix_
is the $n\times n$ real symmetric matrix $A(G)$ whose entries are defined by
setting $[A(G)]_{ij}=1$ if vertices $i$ and $j$ are connected by an edge and
$[A(G)]_{ij}=0$ otherwise. The _spectrum_ of $G$ is the spectrum of its
adjacency matrix $A(G)$, and is therefore real since $A(G)$ is Hermitian. We
adopt a standard convention and write the spectrum of $G$ in non-increasing
order,

$\displaystyle\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}.$

Moreover, the _singular spectrum_ of $G$ consists of the singular values of
$A(G)$. We remark that the singular values of the Hermitian matrix $A(G)$
correspond to the moduli of its eigenvalues. Again, we adopt a standard
convention and write the singular spectrum of $G$ in non-increasing order,

$\displaystyle s_{1}\geq s_{2}\geq\cdots\geq s_{n}.$

For $q\geq 1$, we let $L^{q}(\Omega,\mathcal{F},\mathbb{P}_{\Omega})$ denote
the vector space of random variables defined on the probability space
$(\Omega,\mathcal{F},\mathbb{P}_{\Omega})$ with finite $L^{q}$-norm defined by

$\displaystyle\|X\|_{q}=\Big{(}\mathbb{E}|X|^{q}\Big{)}^{1/q}.$

A random variable $X$ defined on a probability space
$(\Omega,\mathcal{F},\mathbb{P}_{\Omega})$ is called _sub-gaussian_ if
$\|X\|_{q}\leq\|X\|_{\psi_{2}}\sqrt{q}$ for all $q\geq 1$, where

$\displaystyle\|X\|_{\psi_{2}}=\sup_{q\geq
1}\Big{\\{}q^{-1/2}\|X\|_{q}\Big{\\}}$

is called the _sub-gaussian norm of_ $X$ [32, Def. 2.5.6]. Gaussian, Bernoulli
and bounded random variables are typical examples of sub-gaussian random
variables [32, Ex. 2.5.8].

###  1.2. Statement of Results

This paper establishes central limit-type theorems for the sequences of
weighted sums

$\displaystyle W_{n}(\boldsymbol{a})=\frac{1}{n}\sum_{j=1}^{n}a_{j}X_{j},$
(1.2)

in which $X_{1},X_{2},\ldots,X_{n}$ are i.i.d. random variables and
$a_{1},a_{2},\ldots,a_{n}$ correspond to either the eigenvalues or the
singular values of Erdős-Rényi-Gilbert graphs. Graphs in the _Erdős-Rényi-
Gilbert $\mathcal{G}(n,p)$ model_ are constructed by attaching edges between
each vertex pair from a set of $n$ labeled vertices independently with
probability $p\in[0,1]$. Here and henceforth we assume $p\neq 0,1$.

The first two theorems illustrate the relatively simple limiting distributions
of $W_{n}(\boldsymbol{\lambda})$ in the case when certain symmetry conditions
are imposed on $X_{1},X_{2},\ldots$. The third theorem illustrates the simple
limiting distributions of $W_{n}(\boldsymbol{s})$ in the case when
$X_{1},X_{2},\ldots$ are sub-gaussian with mean zero but not necessarily
symmetric.

######  Theorem 1.1.

Suppose $X$ is a normal random variable with mean $\mu$ and variance
$\sigma^{2}$. If $X_{1},X_{2},\ldots,X_{n}\sim X$ are i.i.d. random variables,
then $W_{n}(\boldsymbol{\lambda})/(\sigma\sqrt{p})$ converges in distribution
to a standard normal.

######  Theorem 1.2.

Suppose $X$ is a symmetric sub-gaussian random variable with variance
$\sigma^{2}$. If $X_{1},X_{2},\ldots,X_{n}\sim X$ are i.i.d. random variables,
then

$\displaystyle W_{n}(\boldsymbol{\lambda})\to pX+N_{p}$

in distribution, where $N_{p}$ is a normal random variable, independent of
$pX$, with mean zero and variance $p(1-p)\sigma^{2}$.

######  Theorem 1.3.

Suppose $X$ is a sub-gaussian random variable with mean zero and variance
$\sigma^{2}$. If $X_{1},X_{2},\ldots,X_{n}\sim X$ are i.i.d. random variables,
then

$\displaystyle W_{n}(\boldsymbol{s})\to pX+N_{p}$

in distribution, where $N_{p}$ is a normal random variable, independent of
$pX$, with mean zero and variance $p(1-p)\sigma^{2}$.

The final theorem illustrates, in particular, how sensitive the sequences
$W_{n}(\boldsymbol{s})$ are with respect to the conditions imposed on
$X_{1},X_{2},\ldots,X_{n}$. Very distinct behavior emerges by simply choosing
random variables with non-zero mean. Ultimately, this distinction is rooted in
the asymptotic behavior of the _Schatten $q$ norm_ of a graph, which is
defined for $q\geq 1$ by

$\displaystyle\|G\|_{S_{q}}=\Big{(}s_{1}^{q}+s_{2}^{q}+\cdots+s_{n}^{q}\Big{)}^{1/q}.$

In particular, the large $n$ behavior of $\|G\|_{S_{q}}$ is very different for
the cases $q=1$ and $q>1$ [27, Thm. 5]. Note the sub-gaussian condition is
also removed in the following theorem.

######  Theorem 1.4.

Suppose $X$ is any random variable with non-zero mean $\mu$ which admits a
moment generating function. If $X_{1},X_{2},\ldots,X_{n}\sim X$ are i.i.d.
random variables, then $W_{n}(\boldsymbol{s})/(\mu\sqrt{n})$ converges in
distribution to a point mass at $\frac{8}{3\pi}\sqrt{p(1-p)}$.

There exist various central limit-type theorems in the literature pertaining
to sums of eigenvalues of random matrices e.g. [8, 21, 26, 28]. Among the
earliest results in this direction are due to Johansson [21]. These specific
results concern random Hermitian matrices distributed according to the
probability measure

$\displaystyle
d\mu_{n,\tau}(A)\propto\exp\big{(}-\tau\operatorname{tr}V(A)\big{)}\,dA,$
(1.3)

in which $\tau>0$, $V(x)$ is a polynomial with positive even degree and a
positive leading coefficient and $dA$ denotes Lebesgue measure on the space of
$n\times n$ complex Hermitian matrices. It bears worth mentioning that setting
$\tau=n/2$ and $V(x)=x^{2}$ gives rise to the Gaussian unitary ensemble
introduced by Dyson [12, 13]. The main result of [21] establishes that the
linear eigenvalue statistic $\sum_{k}f(\lambda_{k})$ converges in distribution
to a normal random variable with mean zero. The sums we consider in this paper
can be thought of as randomized graph-theoretic versions of the sums
originally considered by Johansson.

###  1.3. Examples and Simulations

The following examples and simulations illustrate a few of the main theorems.
All code used to generate these plots is made available by contacting the
authors.

######  Example 1.5.

Suppose $X$ is a normal random variable with mean $\mu$ and variance
$\sigma^{2}$. Theorem 1.1 ensures that
$W_{n}(\boldsymbol{\lambda})/(\sigma\sqrt{p})$ converges in distribution to a
standard normal. The simulation in Figure 1 is performed with
$\mu=\sigma^{2}=1$.

Figure 1. Histogram plot for $W_{n}(\boldsymbol{\lambda})/(\sigma\sqrt{p})$
using 750 trials taken with $n=1000$ and $p=1/2$.

######  Example 1.6.

Suppose $X$ is a Rademacher random variable. In particular, one has
$\mathbb{P}(X=1)=\mathbb{P}(X=-1)=1/2$. The random variable $X$ is sub-
gaussian and Theorem 1.2 ensures that $W_{n}(\boldsymbol{\lambda})$ converges
in distribution to the sum of $pX$ with an independent normal random variable
with mean zero and variance $\sigma_{p}^{2}=p(1-p)$. The probability density
of this sum is given by the convolution of the gaussian
$f(x)=(\sigma_{p}\sqrt{2\pi})^{-1}\exp\big{[}-x^{2}/(2\sigma_{p}^{2})\big{]}$
with $\big{[}\delta(x+p)+\delta(x-p)\big{]}/2$. Interestingly, this density
corresponds to the gaussian mixture $\big{[}f(x+p)+f(x-p)\big{]}/2$, which is
bimodal in the case $p>1/2$. Figure 2 shows histogram plots for
$W_{n}(\boldsymbol{\lambda})$ in the cases $p=1/2$ and $p=3/4$.

Figure 2. Histogram plots for $W_{n}(\boldsymbol{\lambda})$ using 750 trials
taken with $n=1000$ and $p=1/2$ (left) and $p=3/4$ (right).

######  Example 1.7.

Suppose $X$ is a normal random variable with non-zero mean $\mu$ and variance
$\sigma^{2}$. Theorem 1.4 ensures that $W_{n}(\boldsymbol{s})/(\mu\sqrt{n})$
converges in distribution to a point mass at $\frac{8}{3\pi}\sqrt{p(1-p)}$.
The simulation in Figure 3 is performed with $\mu=\sigma^{2}=1$.

Figure 3. Histogram plot for $W_{n}(\boldsymbol{s})/(\mu\sqrt{n})$ using 750
trials with $n=1000$ and $p=3/4$.

###  1.4. Outline of the Paper

This paper, which is intended for a wide probabilistic audience, takes us on a
short journey through the spectral analysis of large random matrices and is
organized as follows. Section 2 highlights a few classic results in random
matrix theory which serve as prerequisites for later sections. No background
in random matrices is assumed. Section 3 provides a computational lemma that
we use to expand the partial moments of $W_{n}(\boldsymbol{a})$ in terms of
power sum symmetric functions. Section 4 establishes the asymptotics for the
partial moments of $W_{n}(\boldsymbol{a})$ by analyzing the limiting behavior
of the power sum symmetric functions. Theorems 1.1 and 1.2 are proved in
Section 5. Theorem 1.3 is proved in Section 6 and Theorem 1.4 is proved in
Section 7. Finally, we conclude with possible directions for future work and
closing remarks.

##  2\. Random Matrix Prerequisites

The limiting spectral analysis for large random matrices has become a widely
studied topic in probability since the pioneering work of Eugene Wigner who
proved that the expected empirical spectral distribution of a normalized
$n\times n$ (Wigner) matrix tends to the semicircular law
$\mu_{\operatorname{sc}}$. To begin, suppose $A$ is an $n\times n$ Hermitian
matrix with complex entries. The eigenvalues
$\lambda_{1},\lambda_{2},\ldots,\lambda_{n}$ of $A$ are real and we can define
the one-dimensional distribution function

$\displaystyle\mu_{A}(x)=\frac{1}{n}\Big{|}\\{i\leq n\,:\,\lambda_{i}\leq
x\\}\Big{|}$

called the _empircal spectral distribution (ESD)_ of $A$. The relation [3,
Sec. 1.3.1]

$\displaystyle\frac{1}{n}\operatorname{tr}(A^{k})=\int_{-\infty}^{\infty}x^{k}\,d\mu_{A}(x)$
(2.1)

plays a fundamental role in random matrix theory. Specifically, it turns the
problem of establishing convergence, in whatever sense, for the ESD of a
sequence $\\{A_{n}\\}$ of random matrices into the problem of establishing
convergence of the sequence $\\{\frac{1}{n}\operatorname{tr}(A_{n}^{k})\\}$
for each fixed $k$.

An _$n\times n$ symmetric Wigner matrix_ is an $n\times n$ real symmetric
matrix whose entries, modulo the symmetry condition $\xi_{ij}=\xi_{ji}$, are
independent. Specifically, we permit i.i.d. mean zero entries $\xi_{ij}$ above
the main diagonal and i.i.d. mean zero entries $\xi_{ii}$ on the main
diagonal. These two families need not share the same distribution, however.
Moreover, we impose the condition that all entries have bounded moments and
share a common second moment. If $B_{n}$ is an $n\times n$ symmetric Wigner
matrix, then we denote $A_{n}=B_{n}/\sqrt{n}$. The pioneering work of Wigner
[33, 34] establishes

$\displaystyle\lim_{n\to\infty}\frac{1}{n}\mathbb{E}\operatorname{tr}(A_{n}^{k})=\int_{-\infty}^{\infty}x^{k}\,d\mu_{\operatorname{sc}}(x)$
(2.2)

for all integers $k\geq 1$. In particular, the expected ESD of a normalized
$n\times n$ symmetric Wigner matrix tends to the semicircular law whose
density is given by

$\displaystyle
f_{\operatorname{sc}}(x)=\frac{1}{2\pi}\sqrt{4-x^{2}}\,\mathbb{1}_{[-2,2]}.$

This original result due to Wigner has been extended in several aspects.
Grenander [20] proved the empirical spectral distribution converges to
$\mu_{\operatorname{sc}}$ in probability. Arnold [1, 2] further improved this
result by showing the empirical spectral distribution converges to the
semicircular law almost surely. We remark that the matrix ensembles underlying
(2.2) can be generalized beyond those originally considered by Wigner and
refer the reader to [3] and [31] for excellent surveys on the rich and rapidly
developing field of spectral analysis of large random matrices.

###  2.1. Almost Sure Convergence of the ESD

The form of (2.2) that we need for later sections is due to Arnold. In
particular, suppose $B_{n}$ is an $n\times n$ real symmetric matrix whose
entries, modulo the symmetry condition $\xi_{ij}=\xi_{ji}$, are independent.
Assume the upper-triangular entries share a common distribution with finite
positive variance $\sigma^{2}$. In addition, we assume the diagonal entries
also share a common distribution. Furthermore, assume the entries $\xi_{ij}$
have finite fourth and sixth moments for $i>j$ and the diagonal entries
$\xi_{ii}$ have finite second and fourth moments. Define the normalized matrix
$A_{n}=B_{n}/(\sigma\sqrt{n})$. Arnold proves that
$\mu_{A_{n}}\to\mu_{\operatorname{sc}}$ almost surely in the sense that

$\displaystyle\int_{\mathbb{R}}\phi(x)\,d\mu_{A_{n}}(x)\to\int_{\mathbb{R}}\phi(x)\,d\mu_{\operatorname{sc}}(x)$
(2.3)

for all continuous and compactly supported test functions
$\phi:\mathbb{R}\to\mathbb{R}$ [2, Thm. 2].

###  2.2. Real Symmetric Matrices with Independent Bounded Entries

Here and throughout we adopt standard asymptotic notation. In particular, we
write $f(n)=O\big{(}g(n)\big{)}$ if there exists a constant $C$ such that
$|f(n)|\leq Cg(n)$ for all $n$ sufficiently large. Moreover, we write
$f(n)=o\big{(}g(n)\big{)}$ whenever $f(n)/g(n)\to 0$ as $n\to\infty$.

A result due to Füredi and Komlós allows us to analyze the limiting behavior
of polynomials in $a_{1},a_{2},\ldots,a_{n}$. Suppose $A_{n}$ is an $n\times
n$ real symmetric matrix with bounded entries. Moreover, we assume the entries
of $A_{n}$, modulo the constraint $\xi_{ij}=\xi_{ji}$, are independent. Let
$\mu=\mathbb{E}\xi_{ij}>0$ denote the common mean of the upper-triangular
entries and let $\sigma^{2}=\mathbb{E}(\xi_{ij}-\mu)^{2}$ denote their common
variance. Furthermore, suppose the diagonal entries share a common mean,
$\nu=\mathbb{E}\xi_{ii}$. Füredi and Komlós [17, Thm. 1] show that the
distribution of the largest eigenvalue $\lambda_{1}$ of $A_{n}$ can be
approximated in order $n^{-1/2}$ by a normal distribution with mean
$(n-1)\mu+\nu+\sigma^{2}/\mu$ and variance $2\sigma^{2}$. Moreover, with high
probability (w.h.p.) we have

$\displaystyle|\lambda_{i}|<\sigma\sqrt{n}+O(n^{1/3}\log n)$

whenever $i\neq 1$.

##  3\. A Computational Lemma for the Partial Moments of
$W_{n}(\boldsymbol{a})$

Suppose $j\geq 1$ and $X_{1},X_{2},\ldots,X_{n}$ are i.i.d. random variables
defined on the probability space $(\Omega,\mathcal{F},\mathbb{P}_{\Omega})$.
The lemma we present is a simple, albeit useful, computational tool for
evaluating the moments

$\displaystyle
f_{j}(\boldsymbol{a})=f_{j}^{(n)}(\boldsymbol{a})=\mathbb{E}_{\Omega}\big{(}a_{1}X_{1}+a_{2}X_{2}+\cdots+a_{n}X_{n})^{j},$

in which $\mathbb{E}_{\Omega}$ denotes expectation with respect to
$X_{1},X_{2},\ldots,X_{n}$. This lemma expresses $f_{j}(\boldsymbol{a})$ as a
sum taken over all partitions of $j$ and involves power sum symmetric
polynomials in the variables $a_{1},a_{2},\ldots,a_{n}$. We recall these
definitions below and refer the reader to [29, Sec. 1.7] and [30, Sec. 7.7]
for in depth discussions.

A _partition_ of an integer $j\geq 1$ is a non-increasing sequence
$\boldsymbol{\pi}=(j_{1},j_{2},\ldots,j_{r})$ of positive integers such that
$j_{1}+j_{2}+\cdots+j_{r}=j$. If $j\geq 2$ is an even integer, then a
partition $\boldsymbol{\pi}=(j_{1},j_{2},\ldots,j_{r})$ is a partition into
even parts if $j_{1},j_{2},\ldots,j_{r}$ are even integers. We let $P(j)$ and
$E(j)$ denote the set of all partitions of $j$ and the set of all partitions
of $j$ into even parts, respectively. We define

$\displaystyle y_{\boldsymbol{\pi}}=\prod_{i\geq 1}(i!)^{m_{i}}m_{i}!,$

in which $m_{i}=m_{i}(\boldsymbol{\pi})$ denotes the multiplicity of $i$
appearing in a partition $\boldsymbol{\pi}$. Lastly, the _power sum symmetric
polynomial of degree $j$_ in the variables $a_{1},a_{2},\ldots,a_{n}$ is the
homogeneous polynomial defined by setting

$\displaystyle\mathpzc{p}_{j}(\boldsymbol{a})=\mathpzc{p}_{j}^{(n)}(\boldsymbol{a})=a_{1}^{j}+a_{2}^{j}+\cdots+a_{n}^{j}.$

We often denote $\mathpzc{p}_{j}=\mathpzc{p}_{j}(\boldsymbol{a})$ for brevity
when there is no risk of confusion.

######  Lemma 3.1.

Let $j\geq 1$ be any integer and suppose $X_{1},X_{2},\ldots,X_{n}$ are i.i.d.
random variables which admit a moment generating function. If
$\kappa_{1},\kappa_{2},\ldots$ denotes the cumulants of the $X_{i}$, then

$\displaystyle f_{j}(\boldsymbol{a})=j!\sum_{\boldsymbol{\pi}\in
P(j)}\frac{\kappa_{\boldsymbol{\pi}}}{y_{\boldsymbol{\pi}}}\mathpzc{p}_{\boldsymbol{\pi}},$

where
$\kappa_{\boldsymbol{\pi}}=\kappa_{j_{1}}\kappa_{j_{2}}\cdots\kappa_{j_{r}}$
and
$\mathpzc{p}_{\boldsymbol{\pi}}=\mathpzc{p}_{j_{1}}\mathpzc{p}_{j_{2}}\cdots\mathpzc{p}_{j_{r}}$
given $\boldsymbol{\pi}=(j_{1},j_{2},\ldots,j_{r})$.

###### Proof.

The random variables $X_{1},X_{2},\ldots,X_{n}$ are i.i.d. which implies that
the moment generating function of $\sum_{k=1}^{n}a_{k}X_{k}$ takes the form
$\prod_{k=1}^{n}M(a_{k}t)$, where $M(t)$ denotes the moment generating
function of the $X_{i}$ [5, Sec. 9]. Therefore,

$\displaystyle\sum_{j=0}^{\infty}f_{j}(\boldsymbol{a})\frac{t^{j}}{j!}$
$\displaystyle=\prod_{k=1}^{n}M(a_{k}t)=\exp\Big{(}K(a_{1}t)+K(a_{2}t)+\cdots+K(a_{n}t)\Big{)},$

in which $K(t)=\log M(t)$ denotes the cumulant generating function of the
$X_{i}$. The identity
$K(t)=\sum_{\ell=1}^{\infty}\kappa_{\ell}t^{\ell}/\ell!$, which defines the
cumulant sequence $\kappa_{1},\kappa_{2},\ldots$, implies

$\displaystyle\sum_{j=0}^{\infty}f_{j}(\boldsymbol{a})\frac{t^{j}}{j!}=\exp\Big{(}\sum_{\ell=1}^{\infty}\kappa_{\ell}\mathpzc{p}_{\ell}\frac{t^{\ell}}{\ell!}\Big{)}=\sum_{j=0}^{\infty}B_{j}(\kappa_{1}\mathpzc{p}_{1},\kappa_{2}\mathpzc{p}_{2},\ldots,\kappa_{j}\mathpzc{p}_{j})\frac{t^{j}}{j!},$
(3.1)

where $B_{j}(x_{1},\ldots,x_{j})$ denotes the _complete Bell polynomial_ of
degree $j$ in the variables $x_{1},x_{2},\ldots,x_{j}$ [4, Sec. II] defined
via the generating function

$\displaystyle\sum_{j=0}^{\infty}B_{j}(x_{1},x_{2},\ldots,x_{j})\frac{t^{j}}{j!}=\exp\Big{(}\sum_{\ell=1}^{\infty}x_{\ell}\frac{t^{\ell}}{\ell!}\Big{)}.$
(3.2)

Comparing coefficients in the above expression and applying the identity

$\displaystyle
B_{j}(x_{1},x_{2},\ldots,x_{j})=j!\sum_{\begin{subarray}{c}i_{1},i_{2},\ldots,i_{j}\geq
0\\\
i_{1}+2i_{2}+\cdots+ji_{j}=j\end{subarray}}\prod_{s=1}^{j}\frac{x_{s}^{i_{s}}}{(s!)^{i_{s}}i_{s}!}=j!\sum_{\boldsymbol{\pi}\in
P(j)}\frac{x_{\boldsymbol{\pi}}}{y_{\boldsymbol{\pi}}}$ (3.3)

completes the proof. ∎

######  Remark 3.2.

$X$ admits a moment generating function, which implies that its cumulant
generating function $K(t)$ converges in a neighborhood of $t=0$ [5, Sec. 9].
Relation (3.1) therefore holds in a neighborhood of $t=0$. We use this fact
repeatedly throughout the rest of the paper.

##  4\. Asymptotics for Erdős-Rényi-Gilbert Graphs

Here and throughout we let
$\mathbb{E}_{\mathcal{G}}=\mathbb{E}_{\mathcal{G}(n,p)}$ and
$\mathbb{P}_{\mathcal{G}}=\mathbb{P}_{\mathcal{G}(n,p)}$ denote expectation
and probability, respectively, with respect to $\mathcal{G}(n,p)$. A
fundamental fact is that the number of edges in a random graph of order $n$
follow a binomial distribution,

$\displaystyle\mathbb{P}_{\mathcal{G}}\big{(}|E(G)|=m\big{)}={N\choose
m}p^{m}(1-p)^{N-m},$

where $N={n\choose 2}$. Moreover, the adjacency matrix $A_{n}$ of random graph
of order $n$ is a random $n\times n$ real symmetric matrix whose upper-
triangular entries $\xi_{ij}$ are bounded independent random variables which
have mean $\mu=p$ and variance $\sigma_{p}^{2}=p(1-p)$. The diagonal elements
of $A_{n}$ satisfy $\nu=\mathbb{E}_{\mathcal{G}}[\xi_{ii}]=0$ since loops are
not permitted. The result by Füredi and Komlós [17, Thm. 1], which we outline
in Section 2.2, implies that w.h.p.,

$\displaystyle|\lambda_{1}|=(n-1)p+1-p+O(n^{-1/2})=\big{(}p+o(1)\big{)}n$
(4.1)

and

$\displaystyle|\lambda_{2}|<2\sigma_{p}\sqrt{n}+O(n^{1/3}\log
n)=\Big{(}2\sigma_{p}+o(1)\Big{)}\sqrt{n}.$ (4.2)

###  4.1. The Eigenvalue Case

We now establish the limiting behavior for the partial moments
$f_{j}(\boldsymbol{\lambda})=\mathbb{E}_{\Omega}(\lambda_{1}X_{1}+\lambda_{2}X_{2}+\cdots+\lambda_{n}X_{n})^{j}$
in which $X_{1},X_{2},\ldots,X_{n}$ are i.i.d. random variables defined on
$(\Omega,\mathcal{F},\mathbb{P}_{\Omega})$ and
$\lambda_{1},\lambda_{2},\ldots,\lambda_{n}$ correspond to eigenvalues in the
Erdős-Rényi-Gilbert model. We recall $\mathpzc{p}_{k}(\boldsymbol{\lambda})$
denotes the power sum symmetric polynomial of degree $k$ in the variables
$\lambda_{1},\lambda_{2},\ldots,\lambda_{n}$.

######  Lemma 4.1.

Let $k\geq 1$ be an odd integer. If
$\lambda_{1},\lambda_{2},\ldots,\lambda_{n}$ correspond to eigenvalues in the
Erdős-Rényi-Gilbert $\mathcal{G}(n,p)$ model, then we have
$\mathpzc{p}_{k}(\boldsymbol{\lambda})=o(n^{1+k/2})$ almost surely.

###### Proof.

Let $B_{n}$ be the adjacency matrix of a random graph of order $n$. This
matrix satisfies the hypotheses in Section 2.1. Moreover, the variance of the
upper-triangular entries is given by $\sigma_{p}^{2}=p(1-p)$. The ESD of the
normalized matrix $A_{n}=B_{n}/(\sqrt{n}\sigma_{p})$ converges almost surely
to the semicircular law by [2, Thm. 2] as seen in Section 2.1. Therefore, we
can use (2.1) and the identity
$\operatorname{tr}(B_{n}^{k})=\mathpzc{p}_{k}(\boldsymbol{\lambda})$ to
conclude

$\displaystyle\frac{\mathpzc{p}_{k}(\boldsymbol{\lambda})}{n(\sqrt{n}\sigma_{p})^{k}}=\frac{1}{n}\operatorname{tr}(A_{n}^{k})\to\int_{-\infty}^{\infty}x^{k}\,d\mu_{\operatorname{sc}}(x)$
(4.3)

almost surely. The symmetry of the the semicircular density and the fact that
$k$ is odd imply that
$\frac{\mathpzc{p}_{k}(\boldsymbol{\lambda})}{n(\sqrt{n}\sigma_{p})^{k}}\to 0$
almost surely. The claim follows. ∎

######  Proposition 4.2.

Let $j\geq 1$ be any integer and let $X_{1},X_{2},\ldots,X_{n}$ be i.i.d.
random variables with cumulant sequence $\kappa_{1},\kappa_{2},\ldots$. Define

$\displaystyle c_{j}(p)=j!\sum_{\boldsymbol{\pi}\in
E(j)}\frac{\kappa_{\boldsymbol{\pi}}}{y_{\boldsymbol{\pi}}}p^{j-m_{2}},$

where $\kappa_{\boldsymbol{\pi}}$ and $y_{\boldsymbol{\pi}}$ are defined as in
Lemma 3.1 and $E(j)$ denotes the set of partitions of $j$ into even parts. The
partial moments $f_{j}(\boldsymbol{\lambda})$ satisfy the following, where
$o(1)$ denotes a term tending to zero as $n\to\infty$ with $j$ fixed.

(a) If $j$ is odd, then $n^{-j}f_{j}(\boldsymbol{\lambda})=o(1)$ w.h.p.

(b) If $j$ is even, then $n^{-j}f_{j}(\boldsymbol{\lambda})=c_{j}(p)+o(1)$
w.h.p.

###### Proof.

Denote $\mathpzc{p}_{i}=\mathpzc{p}_{i}(\boldsymbol{\lambda})$ for brevity.
The number of edges in a random graph $G_{n}$ of order $n$ is a binomial
random variable with parameters $N={n\choose 2}$ and $p$. The expected number
of edges in $G_{n}$ is therefore given by $\mathbb{E}_{\mathcal{G}}[m]=pN$.
The weak law of large numbers implies that $m$ is tightly concentrated around
its mean for large $n$. Therefore, we have $m=\big{(}p/2+o(1)\big{)}n^{2}$
w.h.p. If $A_{n}$ denotes the adjaceny matrix of $G_{n}$, then
$\mathpzc{p}_{2}=\operatorname{tr}(A_{n}^{2})=2m$ [9, Thm. 3.1.1], which
implies that w.h.p.,

$\displaystyle\mathpzc{p}_{2}=\big{(}p+o(1)\big{)}n^{2}.$ (4.4)

If $i>2$ is even, then consider the bound
$|\lambda_{1}|^{i}\leq\mathpzc{p}_{i}\leq|\lambda_{1}|^{i}+n|\lambda_{2}|^{i}.$
Inequalities (4.1) and (4.2) imply that w.h.p.,

$\displaystyle\big{(}p^{i}+o(1)\big{)}n^{i}\leq\mathpzc{p}_{i}<\big{(}p^{i}+o(1)\big{)}n^{i}+O(n^{1+i/2}).$

Observe that $n^{1-i/2}\to 0$ as $n\to\infty$ since $i>2$. We conclude that
w.h.p.,

$\displaystyle\mathpzc{p}_{i}=\big{(}p^{i}+o(1)\big{)}n^{i}.$ (4.5)

Let $\boldsymbol{\pi}=(j_{1},j_{2},\ldots,j_{r})$ be a partition of $j$. Lemma
4.1 together with relations (4.4) and (4.5) imply that w.h.p,

$\displaystyle\mathpzc{p}_{j_{1}}\mathpzc{p}_{j_{2}}\cdots\mathpzc{p}_{j_{r}}=o(n^{j})$
(4.6)

whenever $\boldsymbol{\pi}$ contains an odd integer larger than one. If
$m_{1}(\boldsymbol{\pi})\neq 0$, then (4.6) still holds since
$\mathpzc{p}_{1}=\operatorname{tr}(A_{n})=0$ for simple graphs. Any partition
of an odd integer must contain an odd part. Lemma 3.1 implies that w.h.p.,

$\displaystyle f_{j}(\boldsymbol{\lambda})=o(n^{j})$

whenever $j$ is odd. This proves (a). If $j$ is even, then
$\mathpzc{p}_{j_{1}}\mathpzc{p}_{j_{2}}\cdots\mathpzc{p}_{j_{r}}=o(n^{j})$
w.h.p. unless $\boldsymbol{\pi}$ is a partition of $j$ into even parts. Lemma
3.1, together with relations (4.4) and (4.5), imply that w.h.p.,

$\displaystyle f_{j}(\boldsymbol{\lambda})=\Bigg{(}j!\sum_{\boldsymbol{\pi}\in
E(d)}\frac{\kappa_{\boldsymbol{\pi}}}{y_{\boldsymbol{\pi}}}p^{j-m_{2}}+o(1)\Bigg{)}n^{j},$

which proves (b). We remark that the $m_{2}$ term appearing in the last
expression occurs because of the discrepency in the power of $p$ occuring in
(4.4) and (4.5). ∎

###  4.2. The Singular Value Case

We now establish the limiting behavior for the partial moments
$f_{j}(\boldsymbol{s})=\mathbb{E}_{\Omega}(s_{1}X_{1}+s_{2}X_{2}+\cdots+s_{n}X_{n})^{j}$
in which $X_{1},X_{2},\ldots,X_{n}$ are i.i.d. random variables defined on
$(\Omega,\mathcal{F},\mathbb{P}_{\Omega})$ and $s_{1},s_{2},\ldots,s_{n}$
correspond to singular values in the Erdős-Rényi-Gilbert model.

######  Proposition 4.3.

Let $j\geq 1$ be any integer and let $X_{1},X_{2},\ldots,X_{n}$ be i.i.d. mean
zero random variables with cumulant sequence $\kappa_{1},\kappa_{2},\ldots$.
The partial moments $f_{j}(\boldsymbol{s})$ satisfy

$\displaystyle n^{-j}f_{j}(\boldsymbol{s})=j!\sum_{\boldsymbol{\pi}\in
P_{0}(j)}\frac{\kappa_{\boldsymbol{\pi}}}{y_{\boldsymbol{\pi}}}p^{j-m_{2}}+o(1)$

w.h.p., where $\kappa_{\boldsymbol{\pi}}$ and $y_{\boldsymbol{\pi}}$ are
defined as in Lemma 3.1 and $P_{0}(j)$ denotes the set of all partitions of
$j$ for which $m_{1}=0$.

###### Proof.

The singular values of a random graph correspond to the moduli of its
eigenvalues. Therefore, (4.4) and (4.5) hold for
$\mathpzc{p}_{i}=\mathpzc{p}_{i}(\boldsymbol{s})$ when $i$ is even. The same
exact reasoning behind (4.5) implies
$\mathpzc{p}_{i}=\big{(}p^{i}+o(1)\big{)}n^{i}$ when $i\neq 1$ is odd.
Finally, $\kappa_{1}=0$ since $X_{1},X_{2},\ldots,X_{n}$ have mean zero. Lemma
3.1 implies the claim. ∎

######  Proposition 4.4.

Let $j\geq 1$ be any integer and let $X_{1},X_{2},\ldots,X_{n}\sim X$ be
i.i.d. random variables in which $X$ admits a moment generating function and
has non-zero mean $\mu$. The partial moments $f_{j}(\boldsymbol{s})$ satisfy

$\displaystyle\frac{f_{j}(\boldsymbol{s})}{(\mu
n^{3/2})^{j}}=\Big{(}\frac{8\sigma_{p}}{3\pi}\Big{)}^{j}+o(1)$

w.h.p., in which $\sigma_{p}^{2}=p(1-p)$.

###### Proof.

The quantity $\mathpzc{p}_{1}=\mathpzc{p}_{1}(\mathbf{s})$ is called the graph
energy [19] and [11, Thm. 1] establishes that w.h.p.,

$\displaystyle\frac{\mathpzc{p}_{1}}{n^{3/2}}=\frac{8\sigma_{p}}{3\pi}+o(1).$

Lemma 3.1 asserts

$\displaystyle f_{j}(\boldsymbol{s})=j!\sum_{\boldsymbol{\pi}\in
P(j)}\frac{\kappa_{\boldsymbol{\pi}}}{y_{\boldsymbol{\pi}}}\mathpzc{p}_{\boldsymbol{\pi}}=\mu^{j}\mathpzc{p}_{1}^{j}+j!\sum_{\boldsymbol{\pi}\neq(1,1,\ldots,1)}\frac{\kappa_{\boldsymbol{\pi}}}{y_{\boldsymbol{\pi}}}\mathpzc{p}_{\boldsymbol{\pi}}$
(4.7)

since $\kappa_{1}=\mu$ and $y_{\boldsymbol{\pi}}=m_{1}!=j!$ when
$\boldsymbol{\pi}=(1,1,\ldots,1)\in P(j).$ We have so far established that
$\mathpzc{p}_{2}=\big{(}p+o(1)\big{)}n^{2}$ and
$\mathpzc{p}_{i}=\big{(}p^{i}+o(1)\big{)}n^{i}$ for integers $i\geq 3$.
Dividing both sides of (4.7) by $(\mu n^{3/2})^{j}$ implies the claim since
$\mathpzc{p}_{\boldsymbol{\pi}}/(n^{3/2})^{j}=o(1)$ w.h.p. whenever
$\boldsymbol{\pi}\neq(1,1,\ldots,1)$. ∎

##  5\. Proof of Theorems 1.1 and 1.2

The following general form of the Hoeffding inequality [32, Thm. 2.6.3] plays
an important role in our proof. Suppose $\xi_{1},\xi_{2},\ldots,\xi_{n}$ are
independent mean zero sub-gaussian random variables. There exists an absolute
constant $c_{1}>0$ such that

$\displaystyle\mathbb{P}\Bigg{(}\Big{|}\sum_{j=1}^{n}a_{i}\xi_{i}\Big{|}\geq
t\Bigg{)}\leq
2\exp\Big{(}-\frac{c_{1}t^{2}}{K^{2}\mathpzc{p}_{2}(\boldsymbol{a})}\Big{)}$

for all $a_{1},a_{2},\ldots,a_{n}\in\mathbb{R}$, in which
$\mathpzc{p}_{2}(\boldsymbol{a})=\sum_{i}a_{i}^{2}$ and
$K=\max_{i}\|\xi_{i}\|_{\psi_{2}}.$ If in addition
$\xi_{1},\xi_{2},\ldots,\xi_{n}$ have unit variances, then

$\displaystyle\|\sum_{k=1}^{n}a_{i}X_{i}\|_{1}\leq\sqrt{\mathpzc{p}_{2}(\boldsymbol{a})}.$
(5.1)

Moreover, there exists an absolute constant $c_{2}>0$ such that for all $q\geq
2$,

$\displaystyle\|\sum_{k=1}^{n}a_{i}X_{i}\|_{q}\leq
c_{2}K\sqrt{q}\sqrt{\mathpzc{p}_{2}(\boldsymbol{a})}.$ (5.2)

###  5.1. Proof of Theorem 1.1

Suppose $X_{1},X_{2},\ldots,X_{n}\sim X$ are i.i.d. random variables defined
on a probability space $(\Omega,\mathcal{F}_{\Omega},\mathbb{P}_{\Omega})$ in
which $X$ is a sub-gaussian random variable with mean $\mu$ and variance
$\sigma^{2}$. Define the auxiliary variables $\xi_{i}=\sigma^{-2}(X_{i}-\mu)$
and let $j\geq 1$ be any integer. The sum $W_{n}(\boldsymbol{\lambda})$
satisfies

$\displaystyle\mathbb{E}_{\Omega}|W_{n}(\boldsymbol{\lambda})|^{j}$
$\displaystyle=\|W_{n}(\boldsymbol{\lambda})\|_{j}^{j}$
$\displaystyle=n^{-j}\|\sum_{k=1}^{n}\lambda_{k}X_{k}\|_{j}^{j}$
$\displaystyle=n^{-j}\|\sum_{k=1}^{n}\lambda_{k}(X_{k}-\mu)+\mu\sum_{k=1}^{n}\lambda_{k}\|_{j}^{j}$
$\displaystyle=n^{-j}\sigma^{2j}\|\sum_{k=1}^{n}\lambda_{k}\xi_{k}\|_{j}^{j}$

since simple graphs are traceless. The random variables
$\xi_{1},\xi_{2},\ldots\xi_{n}$ are mean zero sub-gaussian random variables
with unit variances. Relations (5.1) and (5.2), together with the inequality
$2m\leq n(n-1)$, imply that there exists a constant $c>0$, which is
independent of $n$, such that

$\displaystyle\mathbb{E}_{\Omega}|W_{n}(\boldsymbol{\lambda})|^{j}\leq
cn^{-j}\big{[}\mathpzc{p}_{2}(\boldsymbol{\lambda})\big{]}^{j/2}=cn^{-j}(2m)^{j/2}\leq
cn^{-j}[n(n-1)]^{j/2}\leq c$ (5.3)

Therefore,
$\mathbb{E}_{\mathcal{G}}\mathbb{E}_{\Omega}|W_{n}(\boldsymbol{\lambda})|^{j}$
is finite and the Fubini-Tonelli theorem [16, Thm. 2.16] ensures

$\displaystyle\mathbb{E}\big{[}W_{n}(\boldsymbol{\lambda})\big{]}^{j}=\mathbb{E}_{\mathcal{G}}\mathbb{E}_{\Omega}\big{[}W_{n}(\boldsymbol{\lambda})\big{]}^{j},$
(5.4)

in which $\mathbb{E}[\cdot]$ denotes expectation with respect to the product
measure $\mathbb{P}_{\mathcal{G}}\otimes\mathbb{P}_{\Omega}$.

Proposition 4.2 and the uniform boundedness of the variables
$\mathbb{E}_{\Omega}|W_{n}(\boldsymbol{\lambda})|^{j}$ allow us to compute the
limit for the total expectation of $[W_{n}(\boldsymbol{\lambda})]^{j}$, which
we now highlight. Define
$E_{j}=\\{G\,:\,n^{-j}f_{j}(\boldsymbol{\lambda})=\alpha_{j}\\}$, where
$\alpha_{j}=\alpha_{j}(n)$ is a real number to be chosen momentarily. Relation
(5.4) implies

$\displaystyle\mathbb{E}[W_{n}(\boldsymbol{\lambda})]^{j}$
$\displaystyle=\mathbb{E}_{\mathcal{G}}[n^{-j}f_{j}(\boldsymbol{\lambda})]$
$\displaystyle=\int_{\mathcal{G}}n^{-j}f_{j}(\boldsymbol{\lambda})\,d\mathbb{P}_{\mathcal{G}}$
$\displaystyle=\alpha_{j}\mathbb{P}_{\mathcal{G}}(E_{j})+\int_{E_{j}^{c}}n^{-j}f_{j}(\boldsymbol{\lambda})\,d\mathbb{P}_{\mathcal{G}}.$

The inequality
$n^{-j}|f_{j}(\boldsymbol{\lambda})|\leq\mathbb{E}_{\Omega}|W_{n}(\boldsymbol{\lambda})|^{j},$
together with (5.3), implies that

$\displaystyle\Big{|}\int_{E_{j}^{c}}n^{-j}f_{j}(\boldsymbol{\lambda})\,d\mathbb{P}_{\mathcal{G}}\Big{|}\leq\int_{E_{j}^{c}}\mathbb{E}_{\Omega}|W_{n}(\boldsymbol{\lambda})|^{j}\,d\mathbb{P}_{\mathcal{G}}\leq
c\mathbb{P}_{\mathcal{G}}(E_{j}^{c}).$

Therefore,

$\displaystyle\lim_{n\to\infty}\mathbb{E}[W_{n}(\boldsymbol{\lambda})]^{j}=\lim_{n\to\infty}\Big{(}\alpha_{j}\mathbb{P}_{\mathcal{G}}(E_{j})\Big{)}$

provided $\mathbb{P}_{\mathcal{G}}(E_{j})\to 1$ as $n\to\infty$ so that
$\mathbb{P}_{\mathcal{G}}(E_{j}^{c})\to 0$ as $n\to\infty$. We now choose
$\alpha_{j}$ according to Proposition 4.2 to conclude

$\displaystyle\lim_{n\to\infty}\mathbb{E}\big{[}W_{n}(\boldsymbol{\lambda})\big{]}^{j}=\begin{cases}0&\mbox{for
}j\mbox{ odd},\\\ c_{j}(p)&\mbox{for }j\mbox{ even}.\end{cases}$ (5.5)

A useful criteria for determing when a distribution is determined by its
moments is that it admits a moment generating function [5, Thm. 30.1]. Suppose
that the distribution of a random variable $W$ is determined by its moments.
The method of moments [5, Thm. 30.2] ensures that
$W_{n}(\boldsymbol{\lambda})$ converges in distribution to $W$ provided
$W_{n}(\boldsymbol{\lambda})$ has moments of all orders and for all $j\geq 1$,

$\displaystyle\lim_{n\to\infty}\mathbb{E}\big{[}W_{n}(\boldsymbol{\lambda})\big{]}^{j}=\mathbb{E}[W^{j}].$

Recall identity (3.3) to conclude, for $j\geq 1$,

$\displaystyle(2j)!\sum_{\boldsymbol{\pi}\in
E(2j)}\frac{\kappa_{\boldsymbol{\pi}}}{y_{\boldsymbol{\pi}}}p^{2j-m_{2}}$
$\displaystyle=(2j)!p^{2j}\sum_{\boldsymbol{\pi}\in
E(2j)}\frac{1}{y_{\boldsymbol{\pi}}}\kappa_{2}^{m_{2}}\kappa_{4}^{m_{4}}\cdots\kappa_{2k}^{m_{2k}}p^{-m_{2}}$
(5.6) $\displaystyle=(2j)!p^{2j}\sum_{\boldsymbol{\pi}\in
E(2j)}\frac{1}{y_{\boldsymbol{\pi}}}\kappa^{m_{2}}\kappa_{4}^{m_{4}}\cdots\kappa_{2k}^{m_{2k}}$
(5.7)
$\displaystyle=p^{2j}B_{2j}(0,\kappa,0,\kappa_{4},0,\ldots,0,\kappa_{2j}),$
(5.8)

where $\kappa=\kappa_{2}/p$. The generating function (3.2) for the complete
Bell polynomials implies

$\displaystyle\exp\Big{(}\sum_{\ell=1}^{\infty}x_{\ell}\frac{t^{\ell}}{\ell!}\Big{)}+\exp\Big{(}\sum_{\ell=1}^{\infty}x_{\ell}\frac{(-t)^{\ell}}{\ell!}\Big{)}=2\sum_{j=0}^{\infty}B_{2j}(x_{1},x_{2},\ldots,x_{2j})\frac{t^{2j}}{(2j)!}$

Setting $x_{1}=x_{2}=\cdots=x_{2j-1}=0$ in the above expression and then
simplifying yields the identity

$\displaystyle\sum_{j=0}^{\infty}B_{2j}(0,x_{2},0,\ldots,0,x_{2j})\frac{(pt)^{2j}}{(2j)!}=\exp\Big{(}\sum_{\ell=1}^{\infty}x_{2\ell}\frac{(pt)^{2\ell}}{(2\ell)!}\Big{)}.$

Setting $x_{2}=\kappa$ and $x_{i}=\kappa_{i}$ for $i>2$ in the above
expression and then appealing to (5.8) implies

$\displaystyle\sum_{j=0}^{\infty}c_{2j}(p)\frac{t^{2j}}{(2j)!}$
$\displaystyle=\sum_{j=0}^{\infty}B_{2j}(0,\kappa,0,\ldots,0,\kappa_{2j})\frac{(pt)^{2j}}{(2j)!}$
$\displaystyle=\exp\Big{(}\frac{\kappa
p^{2}t^{2}}{2}+\sum_{\ell=2}^{\infty}\kappa_{2\ell}\frac{(pt)^{2\ell}}{(2\ell)!}\Big{)}$
$\displaystyle=\exp\Big{(}\frac{\kappa
p^{2}t^{2}}{2}-\frac{\kappa_{2}p^{2}t^{2}}{2}+\sum_{\ell=1}^{\infty}\kappa_{2\ell}\frac{(pt)^{2\ell}}{(2\ell)!}\Big{)}$
$\displaystyle=\exp\Big{(}\frac{\alpha
p^{2}t^{2}}{2}-\frac{\kappa_{2}p^{2}t^{2}}{2}\Big{)}\exp\Bigg{(}\frac{K(pt)+K(-pt)}{2}\Bigg{)}$
$\displaystyle=\exp\Big{(}\frac{1}{2}p(1-p)\sigma^{2}t^{2}\Big{)}\sqrt{M(pt)M(-pt)}$
(5.9)

in a neighborhood of $t=0$, where $M(t)$ and $K(t)$ denote the moment and
cumulant generating functions of $X$, respectively. If $X$ is a normal random
variable with mean $\mu$ and variance $\sigma^{2}$, then the moment generating
function of $X$ is given by $M(t)=\exp\big{(}\mu
t+\frac{1}{2}\sigma^{2}t^{2}\big{)}$ and (5.9) implies that

$\displaystyle\sum_{j=0}^{\infty}c_{2j}(p)\frac{t^{2j}}{(2j)!}=\exp\Bigg{(}\frac{1}{2}p\sigma^{2}t^{2}\Bigg{)}$

in a neighborhood of $t=0$. The method of moments and (5.5) imply Theorem 1.1
since the moment generating function for the sum of two independent random
variables is given by the product of their moment generating functions.

###  5.2. Proof of Theorem 1.2

If $X$ is a symmetric sub-gaussian random variable, then $M(t)=M(-t)$ and
(5.9) implies

$\displaystyle\sum_{j=0}^{\infty}c_{2j}(p)\frac{t^{2j}}{(2j)!}=\exp\Bigg{(}\frac{1}{2}p(1-p)\sigma^{2}t^{2}\Bigg{)}M(pt).$

The moment generating function of $pX$ converges for all $t\in\mathbb{R}$
since $pX$ is a sub-gaussian random variable with mean zero [32, Prop. 2.5.2].
The right hand side is the moment generating function for the sum of $pX$ with
an independent normal with mean zero and variance $p(1-p)\sigma^{2}$. The
corresponding distribution is therefore determined by its moments. The method
of moments and (5.5) now conclude the proof of Theorem 1.2.

##  6\. Proof of Theorem 1.3

Suppose $X_{1},X_{2},\ldots,X_{n}\sim X$ are i.i.d. random variables defined
on $(\Omega,\mathcal{F},\mathbb{P}_{\Omega})$ in which $X$ is a sub-gaussian
random variable with mean zero and variance $\sigma^{2}$. The same reasoning
of Section 5 implies that for all $j\geq 1$,

$\displaystyle\lim_{n\to\infty}\mathbb{E}[W_{n}(\boldsymbol{s})]^{j}=j!\sum_{\boldsymbol{\pi}\in
P_{0}(j)}\frac{\kappa_{\boldsymbol{\pi}}}{y_{\boldsymbol{\pi}}}p^{j-m_{2}}.$

Set $\kappa=\kappa_{2}/p$ and apply (3.3) to conclude, for $j\geq 1$,

$\displaystyle j!\sum_{\boldsymbol{\pi}\in
P_{0}(j)}\frac{\kappa_{\boldsymbol{\pi}}}{y_{\boldsymbol{\pi}}}p^{j-m_{2}}$
$\displaystyle=j!p^{j}\sum_{\boldsymbol{\pi}\in
P_{0}(j)}\frac{1}{y_{\boldsymbol{\pi}}}\kappa_{2}^{m_{2}}\kappa_{3}^{m_{3}}\cdots\kappa_{j}^{m_{j}}p^{-m_{2}}$
$\displaystyle=j!p^{j}\sum_{\boldsymbol{\pi}\in
P_{0}(j)}\frac{1}{y_{\boldsymbol{\pi}}}\kappa^{m_{2}}\kappa_{3}^{m_{3}}\cdots\kappa_{j}^{m_{j}}$
$\displaystyle=p^{j}B_{j}(0,\kappa,\kappa_{3},\ldots,\kappa_{j}).$

The generating function (3.2) for the complete Bell polynomials implies

$\displaystyle\sum_{j=0}^{\infty}B_{j}(0,\kappa,\kappa_{3},\ldots,\kappa_{j})\frac{(pt)^{j}}{j!}$
$\displaystyle=\exp\Big{(}\frac{1}{2}\kappa
p^{2}t^{2}+\sum_{\ell=3}^{\infty}\kappa_{\ell}\frac{(pt)^{\ell}}{\ell!}\Big{)}$
$\displaystyle=\exp\Big{(}\frac{1}{2}\kappa
p^{2}t^{2}-\frac{1}{2}\kappa_{2}p^{2}t^{2}+\sum_{\ell=2}^{\infty}\kappa_{\ell}\frac{(pt)^{\ell}}{\ell!}\Big{)}$
$\displaystyle=\exp\Big{(}\frac{1}{2}\kappa
p^{2}t^{2}-\frac{1}{2}\kappa_{2}p^{2}t^{2}\Big{)}\exp\Big{(}K(pt)\Big{)}$
$\displaystyle=\exp\Big{(}\frac{1}{2}p(1-p)\sigma^{2}t^{2}\Big{)}M(pt)$

in a neighborhood of $t=0$, where $M(t)$ and $K(t)$ denote the moment and
cumulant generating functions of $X$, respectively. The method of moments
concludes the proof of Theorem 1.3.

##  7\. Proof of Theorem 1.4

Suppose $X$ is a random variable defined on
$(\Omega,\mathcal{F},\mathbb{P}_{\Omega})$ which has a non-zero mean and
admits a moment generating function. Let $X_{1},X_{2},\ldots,X_{n}\sim X$ be
i.i.d. random variables. Denote
$V_{n}(\boldsymbol{s})=W_{n}(\boldsymbol{s})/(\mu\sqrt{n})$ for brevity.
Minkowski’s inequality [5, p. 242] and the fact that
$X_{1},X_{2},\ldots,X_{n}\sim X$ are identically distributed imply

$\displaystyle\Big{(}\mathbb{E}_{\Omega}|V_{n}(\boldsymbol{s})|^{j}\Big{)}^{1/j}$
$\displaystyle=\mu^{-1}n^{-3/2}\Big{(}\mathbb{E}_{\Omega}|\sigma_{1}X_{1}+\sigma_{2}X_{2}+\cdots+\sigma_{n}X_{n}|^{j}\Big{)}^{1/j}$
$\displaystyle=\mu^{-1}n^{-3/2}\|\sigma_{1}X_{1}+\sigma_{2}X_{2}+\cdots+\sigma_{n}X_{n}\|_{j}$
$\displaystyle\leq\mu^{-1}n^{-3/2}\|X\|_{j}\sum_{k=1}^{n}\sigma_{k}.$

The Cauchy-Schwarz inequality yields the inequality

$\displaystyle\Big{(}\sum_{k=1}^{n}\sigma_{k}\Big{)}^{2}=\Big{(}\sum_{k=1}^{n}1\cdot\sigma_{k}\Big{)}^{2}\leq
n\sum_{k=1}^{n}\sigma_{k}^{2}=n\mathpzc{p}_{2}(\boldsymbol{s}).$

Appealing to the inequality
$\mathpzc{p}_{2}(\boldsymbol{s})=\mathpzc{p}_{2}(\boldsymbol{\lambda})=2m\leq
n(n-1)$ now implies that there exists a constant $c$, which is independent of
$n$, for which

$\displaystyle\mathbb{E}_{\Omega}|V_{n}(\boldsymbol{s})|^{j}\leq\big{(}\mu^{-1}n^{-3/2}\big{)}^{j}\|X\|_{j}^{j}\big{(}\sqrt{2nm}\big{)}^{j}\leq
c.$ (7.1)

Therefore,
$\mathbb{E}_{\mathcal{G}}\mathbb{E}_{\Omega}|V_{n}(\boldsymbol{\lambda})|^{j}$
is finite and the Fubini-Tonelli theorem ensures

$\displaystyle\mathbb{E}\big{[}V_{n}(\boldsymbol{\lambda})\big{]}^{j}=\mathbb{E}_{\mathcal{G}}\mathbb{E}_{\Omega}\big{[}V_{n}(\boldsymbol{\lambda})\big{]}^{j},$
(7.2)

in which $\mathbb{E}[\cdot]$ denotes expectation with respect to the product
measure $\mathbb{P}_{\mathcal{G}}\otimes\mathbb{P}_{\Omega}$.

Proposition 4.4 and the uniform boundedness of the variables
$\mathbb{E}_{\Omega}|V_{n}(\boldsymbol{s})|^{j}$ now allow us to compute the
limit for the total expectation of $[V_{n}(\boldsymbol{s})]^{j}$, which we now
highlight. Define
$E_{j}=\\{G\,:\,\big{(}\mu^{-1}n^{-3/2}\big{)}^{j}f_{j}(\boldsymbol{s})=\alpha_{j}\\}$,
where $\alpha_{j}=\alpha_{j}(n)$ is a real number to be chosen momentarily.
Relation (7.2) implies

$\displaystyle\mathbb{E}[V_{n}(\boldsymbol{s})]^{j}$
$\displaystyle=\mathbb{E}_{\mathcal{G}}\big{[}\big{(}\mu^{-1}n^{-3/2}\big{)}^{j}f_{j}(\boldsymbol{s})\big{]}$
$\displaystyle=\int_{\mathcal{G}}\big{(}\mu^{-1}n^{-3/2}\big{)}^{j}f_{j}(\boldsymbol{s})\,d\mathbb{P}_{\mathcal{G}}$
$\displaystyle=\alpha_{j}\mathbb{P}_{\mathcal{G}}(E_{j})+\int_{E_{j}^{c}}\big{(}\mu^{-1}n^{-3/2}\big{)}^{j}f_{j}(\boldsymbol{s})\,d\mathbb{P}_{\mathcal{G}}.$

The inequality
$\big{(}\mu^{-1}n^{-3/2}\big{)}^{j}|f_{j}(\boldsymbol{s})|\leq\mathbb{E}_{\Omega}|V_{n}(\boldsymbol{s})|^{j},$
together with (7.1), implies that

$\displaystyle\Big{|}\int_{E_{j}^{c}}\big{(}\mu^{-1}n^{-3/2}\big{)}^{j}f_{j}(\boldsymbol{s})\,d\mathbb{P}_{\mathcal{G}}\Big{|}\leq\int_{E_{j}^{c}}\mathbb{E}_{\Omega}|V_{n}(\boldsymbol{s})|^{j}\,d\mathbb{P}_{\mathcal{G}}\leq
c\mathbb{P}_{\mathcal{G}}(E_{j}^{c}).$

Therefore,

$\displaystyle\lim_{n\to\infty}\mathbb{E}[V_{n}(\boldsymbol{s})]^{j}=\lim_{n\to\infty}\Big{(}\alpha_{j}\mathbb{P}_{\mathcal{G}}(E_{j})\Big{)}$

provided $\mathbb{P}_{\mathcal{G}}(E_{j})\to 1$ as $n\to\infty$ so that
$\mathbb{P}_{\mathcal{G}}(E_{j}^{c})\to 0$ as $n\to\infty$. We now choose
$\alpha_{j}$ according to Proposition 4.4 to conclude

$\displaystyle\lim_{n\to\infty}\mathbb{E}\big{[}V_{n}(\boldsymbol{s})\big{]}^{j}=\Big{(}\frac{8\sigma_{p}}{3\pi}\Big{)}^{j}.$
(7.3)

Finally, the series

$\displaystyle\sum_{j=0}^{\infty}\Big{(}\frac{8\sigma_{p}}{3\pi}\Big{)}^{j}\frac{t^{j}}{j!}=\exp\Big{(}\frac{8\sigma_{p}}{3\pi}t\Big{)}$

corresponds to the moment generating function of a point mass at
$8\sigma_{p}/(3\pi)$. The method of moments concludes the proof of Theorem
1.4.

##  8\. Closing Remarks and Open Questions

There are several possible paths to take with this project. However, none of
these paths appear to be particularly easy. We argue, without the intention of
undermining its potentital for difficulty, that a natural step forward is to
replace the weights appearing in (1.2) with the eigenvalues for the Laplacian
and signless Laplacian of a random graph [9, Ch. 7]. We recall that the
_Laplacian_ of a simple graph $G$ of order $n$ is the symmetric $n\times n$
matrix $L(G)$ defined by

$\displaystyle L(G)=D(G)-A(G),$

where $D(G)$ denotes the _degree matrix of $G$_ defined by setting
$[D(G)]_{ii}$ equal to the degree of vertex $i$ and $[D(G)]_{ij}=0$ when
$i\neq j$. The _signless Laplacian_ of a simple graph $G$ of order $n$ is the
symmetric $n\times n$ matrix $Q(G)$ defined by

$\displaystyle Q(G)=D(G)+A(G).$

If $G$ is a random graph, then the upper-triangular entries of $L(G)$ and
$Q(G)$ satisfy the hypotheses of the theorems in Section 3. Unfortunately, the
vertex degrees of a random graph, while not highly correlated, are not
independent. The theorems of Section 3, therefore, do not apply. A result due
to Bryc, Dembo and Jiang on spectral measures of large Markov matrices [7,
Thm. 1.3], however, can likely be adapted to handle this new situation.
Lastly, we remark that the Laplacian and signless Laplacian matrices are
positive semi-definite and therefore have non-negative eigenvalues. This
motivates the following.

######  Problem 8.1.

Find analogs of Theorems 1.3 and 1.4 for the Laplacian and signless Laplacian
spectra of Erdős-Rényi-Gilbert graphs.

Perhaps the most natural question to consider pertains to the assumptions
imposed on $X_{1},X_{2},\ldots,X_{n}$. Ultimately, the sub-gaussian assumption
in Theorems 1.2 and 1.3 is needed to ensure the partial moments of
$W_{n}(\boldsymbol{a})$ are uniformly bounded over all graphs. This uniform
boundedness is crucial for evaluating the limit of
$\mathbb{E}[W_{n}(\boldsymbol{a})]^{j}$. The authors leave it as an
interesting task to try and drop the sub-gaussian assumption in these
theorems.

######  Problem 8.2.

Can we relax the sub-gaussian condition imposed on the random variables
$X_{1},X_{2},\ldots,X_{n}$ appearing in Theorems 1.2 and 1.3?

Acknowledgments. The authors thank Stephan Ramon Garcia and Ken McLaughlin for
useful comments and suggestions in the preparation of this manuscript.

## References

  * [1] L. Arnold, _On the asymptotic distribution of the eigenvalues of random matrices_ , J. Math. Anal. Appl. 20 (1967), 262-268.
  * [2] L. Arnold, _On Wigner’s semicircle law for the eigenvalues of random matrices_ , Z. Wahrsh. Verw. Gebiete. 19 ( 1971), 191-198.
  * [3] Z. Bai and J. Silverstein, _Spectral Analysis of Large Dimensional Random Matrices_ , Springer-Verlag, New York, 2010.
  * [4] E. Bell, _Exponential Polynomials_ , Ann. Math. 35 (1934), 258-277.
  * [5] P. Billingsley, _Probability and Measure, Third Edition,_ John Wiley and Sons, New York, 1995.
  * [6] B. Bollobás, _Modern Graph Theory, Graduate Texts in Mathematics_ , Springer, New York, 1998.
  * [7] W. Bryc, A. Dembo, T. Jiang, _Spectral Measure of Large Random Hankel, Markov and Toeplitz Matrices_ , Ann. Probab. 34 (2006), no. 1, 1-38.
  * [8] G. Cipolloni, L. Erdős, D. Schröder, _Central limit theorem for linear eigenvalue statistics of non-Hermitian random matrices_ , Comm. Pure Appl. Math. (2021) https://doi.org/10.1002/cpa.22028
  * [9] D. Cvetković, P. Rowlinson and S. Simić, _An Introduction to the Theory of Graph Spectra_ , Cambridge University Press, Cambridge, 2009.
  * [10] A. de Moivre, _The Doctrine of Chances: or, a Method of Calculating the Probability of Events in Play_ , W. Pearson, London, 1718.
  * [11] W. Du, X. Li, Y. Li, _The Laplacian energy of random graphs_ , J. Math. Anal. Appl. 368 (2010), no. 1, 311-319.
  * [12] F. Dyson, _Statistical Theory of the Energy Levels of Complex Systems. I_ , J. Math. Phys. 3, 140 (1962).
  * [13] F. Dyson, _The Threefold Way. Algebraic Structure of Symmetry Groups and Ensembles in Quantum Mechanics_ , J. Math. Phys. 3, 1199 (1962).
  * [14] P. Erdős, A. Rényi, _On random graphs I_ , Publ. Math. 6 (1959), 290-297.
  * [15] P. Erdős, A. Rényi, _On the evolution of random graphs_ , Magyar Tud. Akad. Mat. Kutató Int. Kőzl. 5 (1960), 17-61.
  * [16] G. Folland, _A Guide to Advanceed Real Analysis,_ Mathematical Association of America, 2009.
  * [17] Z. Füredi, J. Komlós, _The eigenvalues of random symmetric matrices_ , Combinatorica. 1 (1981), no. 3, 233-241.
  * [18] E. Gilbert, _Random Graphs_ , Ann. Math. Stat. 30 (1959), no. 4, 1141–1144.
  * [19] I. Gutman, _The energy of a graph_ , Ber. Math. Stat. Sekt. Forschungszent. Graz. 103 (1978), 1-22.
  * [20] U. Grenander, _Probabilities on Algebraic Structures_ , John Wiley and Sons, New York, 1963.
  * [21] K. Johansson, _On fluctuations of eigenvalues of random Hermitian matrices_ , Duke Math. J. 91 (1998), no. 1, 151-204.
  * [22] P. Laplace, _Théorie Analytiques Probabilités_ , Imprimerie Royale, Paris, 1847.
  * [23] P. Lévy, _Théorie de l’Addition des Variables Aléatoires_ , Gauthier-Villars, Paris, 1937.
  * [24] J. Lindeberg, _Eine neue Herleitung des Exponentialgesetzes in der Wahrscheinlichkeitsrechnung_ , Math. Z. 15 (1922), 211-225.
  * [25] A. Lyapunov, _Une proposition générale du calcul de probabilités_ , Comp. Ren. Heb. de l’Académie des Sci. de Paris. 132 (1901), 814.
  * [26] A. Lytova, L. Pastur, _Central limit theorem for linear eigenvalue statistics of random matrices with independent entries_ , Ann. Probab. 37 (2009), no. 5, 1778-1840.
  * [27] V. Nikiforov, _Extremal norms of graphs and matrices_ , J. Math. Sci. 182 (2012), 164-174.
  * [28] M. Shcherbina, B. Tirozzi, _Central limit theorem for fluctuations of linear eigenvalue statistics of large random graphs_ , J. Math. Phys. 51 (2010)
  * [29] R. Stanley, _Enumerative Combinatorics, Volume 1, 2nd Edition_ , Cambridge University Press, New York, 2012.
  * [30] R. Stanley, _Enumerative Combinatorics, Volume 2_ , Cambridge University Press, New York, 1999.
  * [31] T. Tao, _Topics in Random Matrix Theory, Graduate Studies in Mathematics Volume 132,_ American Mathematical Society, 2012.
  * [32] R. Vershynin, _High-Dimensional Probability: An Introduction with Applications to Data Science_ , Cambridge University Press, Cambridge, 2018.
  * [33] E. Wigner, _Characteristic vectors bordered matrices with infinite dimensions_ , Ann. Math. 62 (1955), 548-564.
  * [34] E. Wigner, _On the distributions of the roots of certain symmetric matrices_ , Ann. Math. 67 (1958), 325-327.


# Vertex electrical model:
lagrangian and non-negative properties

D. Talalaev  D. T.: Lomonosov Moscow State University, Moscow, Russia; and
Centre of Integrable Systems, P. G. Demidov Yaroslavl State University,
Sovetskaya 14, 150003, Yaroslavl, Russia<EMAIL_ADDRESS>
###### Abstract.

This note is a modest addition to the work [1]. Here we construct an embedding
of the space of electrical networks to the totally non-negative Lagrangian
Grassmannian in a generic situation with the help of the technique of vertex
integrable models of statistical mechanics.

###### Contents

  1. 1 Introduction
  2. 2 Vertex model
    1. 2.1 Lagrangian property
    2. 2.2 Nonnegativity

##  1\. Introduction

The question of embedding the space of electrical networks to a Lagrangian
non-negative Grassmannian already has a rather rich history and should be
perceived in the context of other archetypal models on weighted graphs. The
latter include the dimer model and the Ising model. For the first of them,
there is an embedding of the model space into a non-negative Grassmannian [2],
for the second - into a non-negative orthogonal Grassmannian [3]. The
electrical network model is related to the Lagrangian version of the non-
negative Grassmannian. This statement has been proven with the help of various
techniques in the works [4], [5], [6] and [1]. Here we apply the technique of
integrable vertex models of statistical physics to the Grassmannian embedding
problem. The actual idea of the vertex representation is to express the
observables in a factorized form, each of whose multipliers satisfies local
controllable properties. These are usually versions of the Yang-Baxter
equation, the local Yang-Baxter equation. The vertex representation of
electrical networks involves the solution of the local Yang-Baxter equation
encoding Ohm’s law. This solution is related to the so-called electrical
solution of the Zamolodchikov tetrahedron equation [7]. This representation
was found in Sergeyev’s work [8] and led to the modern understanding of
electrical manifolds proposed in the work [9].

By an electrical network $e$, we mean a connected graph $\Gamma$ without loops
with a function of weights on the edges $c:E\to\mathbb{R}^{+}$ (the
conductivity function) and a subset of boundary vertices
$V_{B}=\\{1,\ldots,n\\}\subset V=\\{1,\ldots,N\\}.$ Let $c_{ij}$ be the
conductivity of an edge connecting vertices $i$-th and $j$-th which is zero if
the vertices are not connected.

######  Definition 1.1.

The Kirchhoff matrix of a network is a matrix

(3) $\displaystyle T_{ij}=\left\\{\begin{array}[]{ccc}-c_{ij}&\mbox{if}&i\neq
j\\\ \sum_{k\neq i}c_{ik}&\mbox{if}&i=j\end{array}\right.$

The network response matrix $M_{R}(e)$ relates the currents and potentials at
the boundary points of the network

$\displaystyle I=M_{R}U,$

where $I:V_{B}\to\mathbb{R}$ are the currents and $U:V_{B}\to\mathbb{R}$ are
the potentials in boundary points. Let us present the Kirchhoff matrix in a
block form where the $n\times n$ block $A$ corresponds to the subset of
boundary points:

(6) $\displaystyle T=\left(\begin{array}[]{cc}A&B\\\
B^{T}&C\end{array}\right)$

then the response matrix is given by an expression

$\displaystyle M_{R}=A-BC^{-1}B^{T},$

which is just the Schur complement of $C.$ We denote by $E_{n}$ the variety of
electrical networks with $n$ boundary points. The main statements of this note
are the theorem 2.4 where we construct an embedding of the subvariety of
electrical networks on standart graphs $\subset E_{n}$ to the lagrangian
grassmanian $LG(n-1)$ and the theorem 2.10 which demonstrate the total non-
negativity of this embedding in the case of odd $n.$

##  2\. Vertex model

The set of standard graphs is a subset of the set of critical graphs (see
[10], [11]). They are defined inductively. The first few examples of standard
graphs are presented on Figure 1.

Figure 1. Standard graphs

In this paper we deal only with standard graphs. In the problem of
parametrization of electrical networks, they represent, in a certain sense, a
point of generic position.

For $e\in E_{n}$ on a standard graph the authors of [9] defined the boundary
partition function $M_{B}(e)$. It is a matrix which depends on at most
$n(n-1)/2$ parameters, these parameters are the conductivities of the edges of
the network. According to [9] such a matrix belongs to the symplectic group
$Sp(n)$.

Let us introduce the notations

(19) $\displaystyle
T_{2n}=\left(\begin{array}[]{ccccccc}1&0&0&\cdots&0&0&\cdots\\\
0&0&0&\cdots&1&0&\cdots\\\ 0&1&0&\cdots&0&0&\cdots\\\
0&0&0&\cdots&0&1&\cdots\\\ 0&0&1&\cdots&0&0&\cdots\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\\
0&0&0&\cdots&0&0&\ddots\end{array}\right);\qquad
S_{n}=\left(\begin{array}[]{ccccc}1&0&0&\cdots&-1\\\ -1&1&0&\cdots&0\\\
0&-1&1&\cdots&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
0&0&0&\cdots&1\end{array}\right).$

One of the main results from [9] is the following

######  Lemma 2.1.

For an electrical network $e\in E_{n}$ on the standard critical graph
$\Sigma_{n}$ the row spaces of the matrices

$\displaystyle W_{1}=(S_{n},M_{R})\quad\mbox{and}\quad
W_{2}=(M_{B},Id_{n})S_{2n}T_{2n}$

define the same point in $\mathrm{Gr}(n-1,2n)$.

###  2.1. Lagrangian property

The modified boundary measurement matrix $\check{M}_{B}(e)$ for the standard
graph is given by

$\displaystyle\check{M}_{B}=\prod_{i<j}\check{\phi}_{j-i,j-i+1}\left((-1)^{i+j}r_{ij}^{(-1)^{i+j}}\right).$

Here $E_{ij}$ are just elementary matrices with $1$ on the $i,j$-th place and
the multipiers in the product are given by

$\displaystyle\check{\phi}_{ii+1}(s)=1-s(E_{ii}+E_{i,i+1}-E_{i+1,i}-E_{i+1,i+1})\in
Mat_{n},$

the parameters $r_{ij}=1/c_{ij}$ are the resistances of the corresponding
edges. Then

$\displaystyle M_{B}=\omega_{0}\check{M}_{B},$

where $\omega_{0}$ represents the longest element in the Weil group

(25) $\displaystyle\omega_{0}=\left(\begin{array}[]{ccccc}0&0&\cdots&0&1\\\
0&0&\cdots&1&0\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&1&\cdots&0&0\\\
1&0&\cdots&0&0\end{array}\right),$

######  Lemma 2.2.

The row space of the matrix

$\displaystyle W_{0}=(M_{B},Id_{n})$

is an isotropic subspace with respect to the bilinear form

(28) $\displaystyle\eta=\left(\begin{array}[]{cc}g&0\\\
0&g\end{array}\right);$

where

(34) $\displaystyle g=\left(\begin{array}[]{ccccc}0&-1&1&\cdots&(-1)^{n-1}\\\
1&0&-1&\cdots&(-1)^{n}\\\ -1&1&0&\cdots&(-1)^{n-1}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
(-1)^{n}&(-1)^{n-1}&\cdots&\cdots&0\end{array}\right).$

###### Proof.

We want to show that

$\displaystyle W_{0}\eta W_{0}^{t}=0$

which is equivalent to the following

$\displaystyle M_{B}gM_{B}^{t}+g=0.$

By Theorem 4.11 of [9] the modified boundary measurement matrix
$\check{M}_{B}(e)$ preserves the skew-symmetric form $g$

(35) $\displaystyle\check{M}_{B}g\check{M}_{B}^{t}=g.$

This equality follows from the same one for each generator
$\check{\phi}_{i,i+1}(s).$

Therefore

$\displaystyle
M_{B}gM_{B}^{t}=\omega_{0}\check{M}_{B}g\check{M}_{B}^{t}\omega_{0}=\omega_{0}g\omega_{0}=-g.$

∎

The row space of $W_{0}$ contains the vector
$\xi=(1,\ldots,1)\in\mathbb{R}^{2n}$ which generates the left kernel of
$S_{2n}.$

######  Lemma 2.3.

The row space of the matrix $W_{2}$ lies in a subspace
$\widetilde{V}\in\mathbb{R}^{2n}$ of dimension $2n-2,$ i.e.
$W_{2}\in\mathrm{Gr}(n-1,\widetilde{V}).$

###### Proof.

Let $\mu=(1,-1,1,\ldots,(-1)^{n+1})\in\mathbb{R}^{n}$, then

$\displaystyle\check{\phi}_{i,i+1}\mu=\mu.$

Hence

$\displaystyle\check{M}_{B}\mu=\mu;\qquad M_{B}\mu=\omega_{0}\mu=\pm\mu;$

with $+$ for odd $n$ and $-$ for even $n$. Hence the row space of $W_{0}$ lies
in the orthogonal complement to the $2n$-vector

$w=\left(\begin{array}[]{c}\mu\\\
\mp\mu\end{array}\right)=(1,-1,1,-1,\ldots,1,-1).$

The kernel of $S_{2n}$ lies in this complement. Hence the image of $w^{\perp}$
under the action of $S_{2n}T_{2n}$ is a $(2n-2)$-dimensional space which we
denoted by $\widetilde{V}$. ∎

Note that $\xi^{t}\eta=w^{t}$ for even $n$ and $\xi^{t}\eta=0$ for $n$ odd.
Therefore $\xi^{t}\eta v=0$ $\forall v\in w^{\perp}$ and

$\displaystyle\xi\in Ann(\eta|_{w^{\perp}}),$

therefore the form $\eta$ can be projected to the quotient
$w^{\perp}/\langle\xi\rangle$.

From now on we will work inside $w^{\perp}/\langle\xi\rangle$. It is
convenient to prove Lagrangian and nonnegativity properties in the appropriate
bases of this space. Summarizing the above arguments we obtain

######  Theorem 2.4.

The projection of the row space of $W_{0}$ to the space
$w^{\perp}/\langle\xi\rangle$ is a lagrangian subspace with respect to the
reduction of $\eta.$

###  2.2. Nonnegativity

In this subsection we present a demonstration of the total nonnegative
property of the subspace corresponding to an electrical network. Strictly
speaking, this method works only for standard graphs moreover only for the
case of odd $n$. But the arguments seem to allow generalization.

Choose a basis in $w^{\perp}$

$\displaystyle f_{i}=e_{i}+e_{i+1},\qquad i=1,\ldots,2n-1.$

The matrix

(38)
$\displaystyle(\check{M}_{B},Id_{n})=\omega_{0}(M_{B},Id_{n})\left(\begin{array}[]{c}Id_{n}\\\
\omega_{0}\end{array}\right)$

represents the same point in $\mathrm{Gr}(n,2n)$ as $(M_{B},Id_{n})$ after an
appropriate change of basis in $\mathbb{R}^{2n}.$

######  Remark 2.5.

The representation (38) is important for us, it provides an explicit
expression for the point of $\mathrm{Gr}(n,2n)$ in terms of the vertex
representation of boundary measurements matrix. (38) is suitable to relate the
nonegativity property of the whole matrix with its nontrivial block. In what
follows we adapt this strategy making a reduction to
$w^{\perp}/\langle\xi\rangle.$

Note that $\check{M}_{B}$ preserves $\mu$ on the right and the vector
$\zeta=(1,1,1,\ldots)\in\mathbb{R}^{n}$ on the left:

$\displaystyle\zeta^{t}\check{M}_{B}=\zeta^{t};\qquad\check{M}_{B}\mu=\mu.$

Hence its left action preserves the subspace $V_{\mu}=\mu^{\perp}.$ Let us
choose the following basis in $V_{\mu}$

$\displaystyle f_{i}=e_{i}+e_{i+1},\qquad i=1,\ldots,n-1.$

The operators $\chi_{ii+1}(t)=\check{\phi}_{ii+1}(t)|_{V_{\mu}}$ in this basis
(let us make attention that we act on vectors on the left) takes the form

$\displaystyle\chi_{ii+1}(t)=1+t(E_{i+1i}-E_{i-1i})$

with the exceptions:

$\displaystyle\chi_{12}(t)=1+tE_{21}$

and

$\displaystyle\chi_{n-1,n}(t)=1-tE_{n-2,n-1}.$

Also let us define the matrix

$\displaystyle\Delta=Diag(1,-1,-1,1,1,-1,\ldots)\in Mat_{n-1}.$

Let us introduce the next notation:

$\displaystyle u_{ii+1}(t)=1+t(E_{ii-1}+E_{ii+1})$

with the appropriate exceptions for $i=1$ and $n-1.$ This matrix is totally
nonnegative for $t\geq 0$ for obvious reasons.

######  Lemma 2.6.

The matrix

$\displaystyle\Delta\chi_{i,i+1}(t)\Delta$

takes the form

$\displaystyle\Delta\chi_{ii+1}(t)\Delta=u_{ii+1}((-1)^{i}t).$

######  Remark 2.7.

The similar formulas for the generators of the symplectic group was obtained
in [12] in their exploring of the positivity properties of the electrical
group.

######  Lemma 2.8.

The matrix

$\displaystyle\mathcal{M}_{B}=\Delta\check{M}_{B}|_{V_{\mu}}\Delta$

in the basis $\\{f_{i}\\}$ is totally nonnegative.

###### Proof.

The proof is a consequence of the Binet-Cauchy formula and of the observation
that this matrix is a product of totally nonegative factors from Lemma 2.6.
The subspace $V_{\mu}$ is invariant with respect to the action of all factors
of the decomposition

(39) $\displaystyle\mathcal{M}_{B}=\Delta\check{M}_{B}|_{V_{\mu}}\Delta$
$\displaystyle=$
$\displaystyle\Delta\left(\prod_{i<j}\check{\phi}_{j-i,j-i+1}\left((-1)^{i+j}r_{ij}^{(-1)^{i+j}}\right)\right)|_{V_{\mu}}\Delta$
$\displaystyle=$
$\displaystyle\Delta\prod_{i<j}\chi_{j-i,j-i+1}\left((-1)^{i+j}r_{ij}^{(-1)^{i+j}}\right)\Delta$
$\displaystyle=$
$\displaystyle\prod_{i<j}u_{j-i,j-i+1}\left(r_{ij}^{(-1)^{i+j}}\right).$

Lemma 2.6 provides that all factors are totally nonnegative. ∎

Here we need a version of the lemma 3.9 from [2].

######  Lemma 2.9.

Let $A$ be a totally nonnegative matrix $n\times n$ than the matrix $n\times
2n$

$\displaystyle\psi(A)=(Id_{n},\omega_{0}D_{n}A)$

gives a point in the nonnegative Grassmannian.

An $n=4$ example of $\psi(A)$ is given by

(45)
$\displaystyle\psi(A)=\left(\begin{array}[]{cccccccc}1&0&0&0&-a_{41}&-a_{42}&-a_{43}&-a_{44}\\\
0&1&0&0&a_{31}&a_{32}&a_{33}&a_{34}\\\
0&0&1&0&-a_{21}&-a_{22}&-a_{23}&-a_{24}\\\
0&0&0&1&a_{11}&a_{12}&a_{13}&a_{14}\end{array}\right).$

###### Proof.

In fact we can demonstrate a stronger statement which identifies some minors
of $A$ with principal minors of $\psi(A).$ Let $I=\\{i_{1},\ldots,i_{k}\\}$ be
a subset in $[n].$ We denote by $Inv(I)\subset[n]$ the subset

$\displaystyle Inv(I)=\\{n-i_{k}+1,\ldots,n-i_{1}+1\\},$

and by $\widetilde{I}$ the shifted subset in $[2n]$

$\displaystyle\widetilde{I}=\\{i_{1}+n,\ldots,i_{k}+n\\}.$

Then the following is true

(46) $\displaystyle\Delta_{[n]\backslash
I\cup\widetilde{J}}\psi(A)=\Delta_{Inv(I)}^{J}A.$

Let us demonstrate this by two steps. The first step considers the set $I$
concentrated at the end of $[n]$, that is of the type
$I=\\{n-k+1,\ldots,n-1,n\\}.$ In this case the principal minor
$\Delta_{[n]\backslash I\cup\widetilde{J}}\psi(A)$ coincides with the minor
$\Delta_{I}^{\widetilde{J}}\psi(A)$. The last one coincide up to the sign with
the minor $\Delta_{I}^{J}A.$ Let us show that the sign is the same. The lower
$k$ rows of $\omega_{0}D_{n}A$ are just the first $k$ rows of $A$ in altered
order with some rows with altered signs. The length of the longest element in
$S_{k}$ is $\frac{k(k-1)}{2}$. The number of rows with altered signs is
$\left[\frac{k}{2}\right].$ They coinside and hence the signs of minors
coincide.

Now let us demonstrate the statement for minors for generic $I$ by induction
with respect to the lexicographic order. Let $I=\\{i_{1},\ldots,i_{k}\\}$ be
such that for all $I^{\prime}>I$ the formula 46 is true. For examle the
statement is true for the $I^{\prime}=\\{i_{1},\ldots,i_{s}+1,\ldots,i_{k}\\}$
(with the shift in only one index). We have

$\displaystyle\Delta_{[n]\backslash
I^{\prime}\cup\widetilde{J}}\psi(A)=\Delta_{Inv(I^{\prime})}^{J}A.$

We know that $\Delta_{[n]\backslash I\cup\widetilde{J}}\psi(A)$ and
$\Delta_{Inv(I)}^{J}A$ coincide up to a sign. Let us remark the passing from
$I^{\prime}$ to $I$ the sign of the left side expression changes twice, the
first one due to the fact that the neighboring rows of right block of
$\psi(A)$ have different signs, and the secondly: the change of the
neighboring columns in the left block of $\psi(A)$ also changes the sign. ∎

######  Theorem 2.10.

Let us consider the subspace $V_{0}\in\mathbb{R}^{2n}$ generated by

$\displaystyle\\{\pm
f_{2n-1},\ldots,f_{n+5},-f_{n+4},-f_{n+3},f_{n+2},f_{n+1},f_{1},-f_{2},-f_{3},f_{4},f_{5},-f_{6},\ldots,\pm
f_{n-1}\\}$

For $n$ odd the projection of the space $w^{\perp}/\langle\xi\rangle$ to
$V_{0}$ is an isomorphism. The image of the row space of
$(\check{M}_{B},Id_{n})$ after this projection is represented by the matrix

$\displaystyle\psi(\Delta\check{M}_{B}|_{V_{\mu}}\Delta).$

which corresponds to a nonnegative point of the Grassmannian.

###### Proof.

The vector $\xi\in w^{\perp}$ has a representation
$\xi=\sum_{i=1}^{n}f_{2i-1}.$ The projection of $w^{\perp}$ to the subspace
generated by $\\{f_{i}\\}$ except $f_{n}$ induces an isomorphism on
$w^{\perp}/\langle\xi\rangle.$ This projection could be described by the
action of the blocks of the matrix $(\check{M}_{B},Id_{n})$ on the basis on
the left. This action after the sign change given by the matrix $\Delta$ is
represented by the matrix

$\displaystyle(\Delta\check{M}_{B}|_{V_{\mu}}\Delta,Id_{n-1})=(\mathcal{M}_{B},Id_{n-1}).$

The following matrix multiplication

(49)
$\displaystyle\omega_{0}D_{n-1}\times(\mathcal{M}_{B},Id_{n-1})\times\left(\begin{array}[]{cc}0&Id_{n-1}\\\
\omega_{0}D_{n-1}&0\end{array}\right)=(Id_{n-1},\omega_{0}D_{n-1}\mathcal{M}_{B})$

transforms the matrix $(\mathcal{M}_{B},Id_{n-1})$ to the form
$\psi(\mathcal{M}_{B}).$ Let us comment that the left multiplication does not
change the point of the Grassmannian and the right multiplication is just the
change of the basis in $V_{0},$ it transforms the matrix of the symplectic
form and the subspace remains Lagrangian. ∎

## Acknowledgements

I am grateful to B. Bychkov, V. Gorbunov and A. Kazakov for numerous
discussions and especially to B. Bychkov for a careful reading of the text.

The work was partially supported by the Basis foundation, the grant Leader
(Math) 20-7-1-21-1.

## References

  * [1] Boris Bychkov, Vassily Gorbounov, Anton Kazakov, Dmitry Talalaev, Electrical networks, Lagrangian Grassmannians and symplectic groups, arXiv:2109.13952
  * [2] A. Postnikov, Total positivity, Grassmannians, and networks, arXiv:math/0609764.
  * [3] P. Galashin, P. Pilyavskyy, Ising model and the positive orthogonal Grassmannian, Duke Math. J. 169(10): 1877-1942 (2020)
  * [4] T. Lam and P. Pilyavskyy, Electrical networks and Lie theory, Algebra Number Theory 9(6), P.1401-1418 (2015)
  * [5] T. Lam, Electroid varieties and a compactification of the space of electrical networks, Advances in Mathematics, V.338, P.549-600 (2018)
  * [6] S.Chepuri, T. George, D. Speyer, Electrical networks and Lagrangian Grassmannians. arXiv:2106.15418
  * [7] Zamolodchikov A.B., Tetrahedra equations and integrable systems in three-dimensional space, Soviet Phys. JETP 52 (1980), 325–336.
  * [8] S. Sergeev, Mathematics of quantum integrable systems in multidimensional discrete space-time, Preprint.
  * [9] V. Gorbounov, D. Talalaev, Electrical varieties as vertex integrable statistical models, J. Phys. A: Math. Theor. V.53, 454001 (2020)
  * [10] E. B. Curtis, D. Ingerman, J. A. Morrow, Circular planar graphs and resistor networks. Linear algebra and its applications. Vol.283. No. 1-3. p.115-150 (1998)
  * [11] E. B. Curtis, D. Ingerman, J. A. Morrow, Inverse problems for electrical networks. World Scientific. Vol.13 (2000)
  * [12] A. Berenstein, A. Gainutdinov, V. Gorbounov, Total positivity in the electrical Lie groups, work in progress.