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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Jan 13, 2018 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
    Commented Jan 13, 2018 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
    Commented Jan 16, 2018 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
    Commented Jan 16, 2018 at 6:35
  • $\begingroup$ @Tony note that my earlier answer was wrong (scaling error). See the corrected post. $\endgroup$
    – ofer zeitouni
    Commented Jan 16, 2018 at 10:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .