3
$\begingroup$

Let $X$ be an $n\times n$ symmetric random matrix whose diagonal is fixed as $1$, and every element in the upper triangle (excluding the diagonal) is drawn from Bernoulli($p$). The elements in the lower triangle is then set to ensure symmetry.

First ask a simple question, for such a random matrix, let $\lambda_1(X)$ denotes the largest eigenvalue of $X$, then

Do $\lambda_1(\frac{X}{\sqrt n})$ and $\frac{\lambda_1(X)}{\sqrt n}$ have the same distribution, as $n\to \infty$?

I think they are probably not, otherwise further discussion is meaningless. It looks like $\lambda_1(\frac{X}{\sqrt n})$ obeys semi-circle law, but if $\frac{\lambda_1(X)}{\sqrt n}$ obeys the same distribution, $\frac{\lambda_1(X)}{n}$ will simply concentrate at $0$, which is not possible.

Now let $\sigma^2$ be the variance of the distribution. In the answer of Bound for largest eigenvalue of symmetric matrices of uniform random variables over $[0,1]$ and fixed $1$s along diagonal and scattered $1$s, it states

It is a standard fact that there is a transition: if $p\leq \sigma$, then $\lambda_1(\frac{X}{\sqrt n})$ concentrates at $2\sigma$; if $p>\sigma$, then $\lambda_1(\frac{X}{\sqrt n})$ concentrates at $p+\sigma^2/p$.

The answer also indicates

The above claim holds if we replace the Bernoulli distribution by a uniform distribution, and let $p$ be its mean, and $\sigma^2$ be its variance.

I know in random matrix theory, it is standard to study the distribution of eigenvalues of $\frac{X}{\sqrt n}$, and it obeys semi-circle law. My question is, rather than the largest/smallest eigenvalue of $X/\sqrt n$,

Is there similar result for $\frac{\lambda_1(X)}{n}$; if so please help provide some explanation or reference. (sorry, there was a typo)


A simulation shows $\frac{\lambda_1(X)}{n}$ looks like Gaussian (10000 samples of $1000\times 1000$ matrices, Bernoulli distribution parameter by 0.7).

enter image description here

$\endgroup$
  • 2
    $\begingroup$ For any $c\ne 0$, $X\boldsymbol{x}=\lambda\boldsymbol{x}$ iff $(cX)\boldsymbol{x}=(c\lambda)\boldsymbol{x}$. So $\lambda_1(X)/\sqrt n$ and $\lambda_1(X/\sqrt n)$ are exactly the same. $\endgroup$ – Brendan McKay Jan 16 '18 at 3:46
  • $\begingroup$ @BrendanMcKay Here is where I am extremely confused. For finite $n$, yes. But as $n \to \infty$, I am confused. It looks like $\lambda_1(\frac{X}{\sqrt n})$ obeys semi-circle law, but if $\frac{\lambda_1(X)}{\sqrt n}$ obeys the same distribution, $\frac{\lambda_1(X)}{n}$ will simply concentrate at $0$, which is not possible. $\endgroup$ – Tony Jan 16 '18 at 4:00
  • $\begingroup$ The largest eigenvalue of a nonnegative matrix is always at least equal to the average row sum, which in your cases is about $pn$. Assuming $p$ is constant, I'd expect $\lambda_1(X)/n$ to concentrate at $p$. $\endgroup$ – Brendan McKay Jan 16 '18 at 4:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.