# Bounds on the eigenvalues of a random binary matrix

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!

-
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

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$

-
thanks very much! This is very helpful. –  Ali Dec 27 '13 at 17:09