Simplicity of singular value spectrum of random matrices and two-point quantitative invertibility

Abstract

Let $A$ be an $n\times n$ random matrix with independent, identically distributed mean 0, variance 1 subgaussian entries. We prove that $$\mathbb{P}(A\text{ has distinct singular values})\ge 1-e^{-cn}$$ for some $c>0$, confirming a conjecture of Vu. This result is then generalized to singular values of rectangular random matrices with i.i.d. entries. We also prove that for two fixed real numbers $\hat{I}{»}_1,\hat{I}{»}_2$ with a sufficient lower bound on $|\hat{I}{»}_1-\hat{I}{»}_2|$, we have a joint singular value small ball estimate for any $\hat{I}\mu >0$ $$\mathbb{P}(\ddot{I}{ƒ}_{min}(A-\hat{I}{»}_1{I}_n)\le \hat{I}\mu n^{-1/2},\ddot{I}{ƒ}_{min}(A-\hat{I}{»}_2{I}_n)\le \hat{I}\mu n^{-1/2})\le C\hat{I}{\mu }^2+e^{-cn},$$ where $\ddot{I}{ƒ}_{min}(A)$ is the minimal singular value of a square matrix $A$ and $I_n$ is the identity matrix. For much smaller $|\hat{I}{»}_1-\hat{I}{»}_2|$ we derive a similar estimate with $C$ replaced by $C\sqrt{n}/|\hat{I}{»}_1-\hat{I}{»}_2|$. This generalizes the one-point estimate of Rudelson and Vershynin, which proves $\mathbb{P}(\ddot{I}{ƒ}_{min}(A)\le \hat{I}\mu n^{-1/2})\le C\hat{I}\mu +e^{-cn}$. Analogous two-point bounds are proven when $A$ has i.i.d. real and complex parts, with $\hat{I}{\mu }^4$ in place of $\hat{I}{\mu }^2$ on the right hand side of the estimate and for any complex numbers $\hat{I}{»}_1,\hat{I}{»}_2$. These two point estimates can be used to derive strong anticoncentration bounds for an arbitrary linear combination of two eigenvalues of $A$.

68 pages. Updated references