MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|improve this answer
thanks very much! This is very helpful. – Ali Dec 27 '13 at 17:09

Your Answer


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.