Let $A$ be a PSD random matrix, which has $0$ as one of its eigenvalues. The second smallest eigenvalue of the expectation of $A$ writes as $\lambda\_2(\mathbb{E}(A))>0$.


Why the following statement holds?


If $\|A-\mathbb{E}(A)\|<\lambda\_2(\mathbb{E}(A))$, then $\lambda\_2(A)>0.$


Note that $\|\cdot\|$ denotes the operator norm.



Deviation of random matrix from its expectation informs the positiveness of its second smallest eigenvalue
The random-matrix connection is a bit of a red herring: Since the weight of $A$ in the statistical average can be arbitrarily small, we might as well replace $\mathbb{E}(A)$ by an arbitrary PSD matrix $B$ with $\lambda\_2(B)>0$.  

The statement in the OP



> 
> If $\|A-B\|<\lambda\_2(B)$, then $\lambda\_2(A)>0,$
> 
> 
> 


is a consequence of the "eigenvalue stability" inequality
$$|\lambda\_i(A)-\lambda\_i(B)|\leq \|A-B\|,$$
which is proven, for example, in [Tao's notes](https://terrytao.wordpress.com/2010/01/12/254a-notes-3a-eigenvalues-and-sums-of-hermitian-matrices/) (equation 13).


