Suppose we have a $k\times k$ matrix $A = \sum_{i=1}^{n} a_i a_i^T$ where $n \leq \mathrm{poly}(k)$ and each $a_i\in\{-1,1\}^{k}$. It is easy to prove that the largest eigenvalue of $A$ is at most $\mathrm{poly}(k)$ as $\mathrm{Tr}(A) = nk$. But how small can the smallest nonzero eigenvalue of $A$ be? For example, can it be exponentially small (e.g. $2^{-k}$)?



Your Answer

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