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}$)?
1
-
1$\begingroup$ You can get reasonable bounds using standard root separation techniques. See e.g., the answers here: mathoverflow.net/questions/198645/… $\endgroup$– ShaullSep 1, 2021 at 6:31
Add a comment
|