I have a distribution $\mathcal{D}$ that spits out vectors in $\{-1, 1\}^N$. Suppose I have a sample of $H$ of these vectors which I arrange into a matrix $M$ of the form $H \times N$.
Consider the eigenvalues of $\frac{MM^T}{NH}$. Note that each row sum is at most $1$. Thus, the maximum eigenvalue is at most $1$.
Is there some way of defining a measure of complexity of $\mathcal{D}$ that lets me say with high probability the maximum eigenvalue is only $\varepsilon$ away from 1? Hopefully the lower the complexity, the closer it is to one. However, increasing $N$ should bring it closer to 1.
EDIT--------------------------------------------------- I found an interesting result. For graph matrices, the largest eigenvalue is less than $\frac{(k-1)n}{k}$ where $k$ is the chromatic number. If we divide by $N$ like in my problem, we do have a way of tying the complexity to the largest eigenvalue. This upper bound comes closer to $1$ as complexity increases. However, I want to show that with high probability, the eigenvalue comes close to one not just an upper bound.
