5
$\begingroup$

I am recently self-learning random matrix theory and made some simulations about the spectrum of Erdős–Renyi random graph $G(n,p)$ when $np\to\infty$,

Dense ER graph

and $np\to c=2,3$.

Sparse ER 2Sparse ER 3

The plots above are already normalized such that the $y$-axis is about the frenquency and the $x$-axis is the eigenvalues divided by $\sqrt{np(1-p)}$.

Now it turns out that, although the spectrum itself is not symmetric (like the largest eigenvalue is far away from the bulk), the limiting shape is asymptotically symmetric. I wonder whether we can read this property out from the ER graph or its adjacency matrix directly, before we show that e.g. in the dense case the limiting distribution is the semi-circle law.

I kind of get why the atoms in sparse case are symmetric, because they come from small components of the graph which are trees, thus bipartite and bipartite graphs have symmetric spectrum.

But why is the continuous part in the sparse case, as well as the dense one, still symmetric?

For the sparse one I probably can explain it like, the contiuous part should be the contribution of the giant component which is also locally tree-like, but still not very promising (like, why is locally tree-like enough to guarantee symmetry?). And for the dense case I have no clue—the graph does not seem bipartite to me.

$\endgroup$
1
  • 4
    $\begingroup$ Why is locally tree-like enough to guarantee symmetry: The trace of $A^k$, $A$ the adjacency matrix, counts self-returning walks on the graph. For $k$ odd, these walks must pass through an odd cycle. If the graph is locally tree-like, there are very few small cycles, so $A^k$ must be small for $k$ odd, meaning the pdf of the eigenvalue distribution has small odd moments and thus is approximately symmetric. $\endgroup$
    – Will Sawin
    Commented Apr 11, 2022 at 16:21

2 Answers 2

4
$\begingroup$

The Erdős–Renyi random matrix $G$ is a rank-one perturbation of a matrix $H$ with zero mean, $$G=H+pv^\top v,\;\;v=(1,1,\ldots 1)^\top.$$ The spectrum of $H$ is symmetric, while the eigenvalues $\lambda_k(G)$ of $G$ (numbered in ascending order) are interlaced with those of $H$, $$\lambda_k(H)\leq\lambda_{k+1}(G)\leq\lambda_{k+2}(H),\;\;1\leq k\leq n-2.$$ So except for the largest eigenvalue $\lambda_n(G)$, which is an outlier, the spectrum of $G$ will be approximately symmetric.

$\endgroup$
5
  • $\begingroup$ Is it obvious why the spectrum of $H$ is symmetric? $\endgroup$
    – Will Sawin
    Commented Apr 11, 2022 at 15:30
  • $\begingroup$ not directly obvious, but the eigenvalue density of large random matrices with i.i.d. matrix elements depends only on their mean and variance, and since $H$ and $-H$ have the same mean and variance the eigenvalue density will be symmetric for large dimensionality $n$; this refers to the smoothed density, the spectrum for any given $H$ will not be precisely symmetric around 0. $\endgroup$ Commented Apr 11, 2022 at 15:51
  • 1
    $\begingroup$ Why then is the apparent density different in the $c=2$ case? Does the result really hold if the probability distribution of the individual entries varies with $n$? $\endgroup$
    – Will Sawin
    Commented Apr 11, 2022 at 15:57
  • $\begingroup$ good point, thanks, this argument only applies to the smooth density, the semicircle in the plots above; the spikes require separate consideration. $\endgroup$ Commented Apr 11, 2022 at 16:03
  • $\begingroup$ But isn't that "density of large random matrices with i.i.d. matrix elements depends only on their mean and variance" fact depends on the proof eg. Wigner's matrices converge to semi-circle law? Is there a "intuitive" way of seeing that? (Sorry maybe I am asking too much out of this). $\endgroup$
    – MikeG
    Commented Apr 11, 2022 at 19:29
1
$\begingroup$

For $np\rightarrow\infty$ it is a very classical result that it converges to the semi-circle law. If you just want the symmetry in a general case I suppose one should just estimate $$\frac{1}{n}\mathbb{E}(\text{Tr}H^k)=o(1)$$ for any $k\in 2\mathbb{N}+1$.

In the sparce case, I think I can propose another sketch for a proof:

  1. Let $x\in \mathbb{R}$, the number of eigenvalues close to $x$ (in a neighborhood of typical size $\eta$) can be estimate using the resolvent $$\sum_{\lambda_i\in\sigma(H)}\frac{\eta}{(\lambda_i-x)^2+\eta^2} = \Im m\text{Tr}((H-x-i\eta)^{-1})=\sum_{i\leq n} \Im m \langle i,(H-x-i\eta)^{-1}i \rangle $$
  2. For $\eta>0$, the resolvent decays exponentially by Combes-Thomas estimate and we have $$\langle i,(H-x-i\eta)^{-1}i \rangle \approx \langle i,(H|_{B_r(i)}-x-i\eta)^{-1}i \rangle $$ where $H|_{B_r(i)}$ is the matrix restricted on $B_r(i)$ a large ball (for the graph distance) around the vertex $i$ .
  3. Localy (on the balls), the Erdos-Renyi graph is a tree and therefore a bipartite graph so its spectrum is symmetric. In particular
    $$ \langle i,(H|_{B_r(i)}-x-i\eta)^{-1}i \rangle = \langle i,(H|_{B_r(i)}+x-i\eta)^{-1}i \rangle$$
$\endgroup$
3
  • $\begingroup$ Thanks for the answer! Actually I am quite comfortable with the proof, but just get curious whether we can read from some intuition that it should be symmetric. Of course the semi-circle law might be beyond the intuition, but I am thinking the symmetry itself might be reachable. Although this may also be asking too much lol. $\endgroup$
    – MikeG
    Commented Apr 11, 2022 at 20:40
  • $\begingroup$ I mean the proof for semi-circle law. Could you please give a reference for especially part 1-2 in your answer? They look very powerful! $\endgroup$
    – MikeG
    Commented Apr 11, 2022 at 20:47
  • 1
    $\begingroup$ 1- is just a dirac approximation with a Cauchy function. A good reference of the Combe-Thomas estimate is the book Random Operators: Disorder Effects on Quantum Spectra and Dynamics . Indeed if you just want symmetry it is should be much simpler than the semi-circle law. $\endgroup$
    – RaphaelB4
    Commented Apr 16, 2022 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.