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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.