1
$\begingroup$

Consider $A$, a random binary matrix of zeros and ones in $\mathbb{R}^{{M\times N}}$, and $M>N$. We assume that $P(a_{i,j}=0)=P(a_{i,j}=1)=0.5$ (although I appreciate any advice on the case of non-even probabilities). Are there any results that provide a lower bound (and maybe an interesting upper bound) on the eigenvalues of $A^TA$? The reference ring is certainly $\mathbb{R}$.

Thanks in advance!

$\endgroup$
2
  • $\begingroup$ lower bound is 0 $\endgroup$
    – guest
    Dec 27, 2013 at 10:03
  • $\begingroup$ Well, thanks for your response, but certainly we are interested in positive lower bounds and any results that hold with high probability. $\endgroup$
    – Ali
    Dec 27, 2013 at 10:21

1 Answer 1

3
$\begingroup$

The distribution of eigenvalues will follow the Marchenko-Pastur distribution, scaled appropriately.

Since the mean entry will be equal to $0.5$, then the largest eigenvalue will be (approximately) equal to $0.25MN$, and the corresponding eigenvector will be the vector of all $1$'s (again, approximately). The rest of the eigenvalues will follow Marchenko-Pastur. In this case the random variables in the matrix have variance $\sigma^2=0.25$, which means that the next largest eigenvalue will be $0.25(1+\sqrt{N/M})^2M$ and the smallest will be $0.25(1-\sqrt{N/M})^2M$. In other words, the range of eigenvalues other than the first will be $$\bigl[0.25(\sqrt{M}-\sqrt{N})^2,0.25(\sqrt{M}+\sqrt{N})^2\bigr].$$

You can similarly compute the spectrum for other probablitites besides $0.5$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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