7
$\begingroup$

Given a $n\times n$ symmetric random matrix whose diagonal elements are all fixed as $1$. In addition, there are $k$ $1$s will be randomly scattered in upper triangular (of course, the corresponding places in the lower-triangle will be filled with $1$, and $2k < n^2-n$). All other elements are independent uniform random variables over $[0,1]$.

Is there known bound (lower and upper) for the largest eigenvalue of such random matrices?

If there is not, any suggestion of possible method (I can think of using Gershgorin circle) or reference to related materials is very much appreciated.

Gershgorin circle could help with the upper bound. For example, if we assume all those $1$s are in the same row, then we should be able to find the probabilistic bound for this case with Irwin–Hall distribution; but I currently have trouble dealing with the "randomly scattered" $1$s.

I am not familiar with the random matrix theory. I am not sure if there is anything from it can help this.

$\endgroup$
3
$\begingroup$

The diagonal elements just shift the spectrum (and the top eigenvalue) by $1$. So we may assume they are $0$.

You are essentially dealing with a symmetric matrix whose entries above the diagonal are iid, sum of a Bernoulli $\{0,1\}$ of parameter (=mean) $q=2k/n^2$ and of a uniform random variable on $[0,1]$. The mean is therefore $p=q+(1-q)/2$ and the variance is $\sigma^2=q+(1-q)/3-p^2$. Since, for any value of q, the mean is bounded below and so is the variance, you are dealing with the perturbation by $\sqrt{n}$ times a Wigner matrix of a matrix of rank $1$ and norm $pn$. Thus, your top eigenvalue will concentrate around $pn$ ($\pm O(\sqrt{n}))$ by estimates on the top eigenvalue of a Wigner matrix and Weyl's inequalities.

I earlier referred to https://arxiv.org/pdf/math/0605624v1.pdf, but this is a very different scaling, so I scraped that answer.

$\endgroup$
  • $\begingroup$ I think you have misunderstood the question. The elements that are not fixed as 1 are not 0, but rather uniformly distributed between 0 and 1. So the actual mean and variance are different, and the empty rows and columns case does not happen. $\endgroup$ – Will Sawin Jan 13 '18 at 9:37
  • $\begingroup$ @Will Sawin Even simpler..... OK, this is what happens when one reads only the first few lines. I added the changes needed for the OP. $\endgroup$ – ofer zeitouni Jan 13 '18 at 9:50
  • $\begingroup$ @oferzeitouni You mentioned "It is a standard fact that there is a transition: if $p\leq \sigma$, then the largest eigenvalue of $Z$ concentrates at $2σ$. If $p> \sigma$ ... ". Could you help provide a reference to this theorem, like a textbook? Thanks! $\endgroup$ – Tony Jan 16 '18 at 0:51
  • $\begingroup$ I gave it, in the next sentence. It gives not only the location of the transition but also fluctuation results, which are beyond what you need. $\endgroup$ – ofer zeitouni Jan 16 '18 at 6:35
  • $\begingroup$ @Tony note that my earlier answer was wrong (scaling error). See the corrected post. $\endgroup$ – ofer zeitouni Jan 16 '18 at 10:14

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.

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