Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
lower bound is 0 –  guest Dec 27 '13 at 10:03
    
Well, thanks for your response, but certainly we are interested in positive lower bounds and any results that hold with high probability. –  Ali Dec 27 '13 at 10:21

1 Answer 1

up vote 2 down vote accepted

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$

share|improve this answer
    
thanks very much! This is very helpful. –  Ali Dec 27 '13 at 17:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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