Skip to main content
2 of 3
added 130 characters in body
Tony
  • 272
  • 2
  • 11

Largest eigenvalue of two types of slightly different random matrices

Consider two types of slightly different $n \times n$ symmetric random matrices $X$. The diagonal elements of $X$ are fixed as $1$. Suppose $\frac{k}{n} \to \alpha$ for some constant $\alpha\in(0,1)$.

Type I: Randomly sample $k$ distinct numbers $i_1,...,i_k$ from $1,...,n$. Let $X(i,j)=X(j,i) = 1$. All other elements above the diagonal are i.i.d. uniform random variables, and the elements in the lower triangle are set accordingly.

Type II: Randomly sample $k^2 - k$ distinct cell above the diagonal and set them as $1$, then all other elements above the diagonal are i.i.d. uniform random variables. The elements in the lower triangle are set accordingly. Type II is more random than type I and every element above the diagonal can still be viewed as i.i.d. with mean $0.5+0.5\alpha^2$.

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 has explained the largest eigenvalue of the Type II will concentrate around $(0.5n+0.5\alpha^2n+O(\sqrt n))$. The question is,

In Type I, the elements above the diagonal seems not i.i.d., will Type I still has a similar result for the largest eigenvalue?

I also guess the largest eigenvalue of the first type is larger than the second type with high probability when $n$ is large.

Any explanation or reference is very much appreciated!

Tony
  • 272
  • 2
  • 11