I'm trying to prove that $\left \| A^{-1} \right \|\geq 1/\epsilon$ iff $0\in\sigma_{\epsilon}(A)=\left\{ \lambda:\lambda\in \sigma(A+E),\left \| E \right \|\leq \epsilon\right\}$ with $A\in\mathbb{C}^{n\times n}$.
I proved $\Rightarrow$ direction of this proposition but I'm struggling with the opposite.
My idea is to take a non-zero eigenvector $u$ and prove that $(A+E)u=0$, but in what way are we supposed to use $\left \| A^{-1} \right \|\geq 1/\epsilon$?
I presume that $\lVert \cdot \rVert$ means a matrix norm, that is, a norm such that $\lVert B C \rVert \le \lVert B \rVert \lVert C \rVert$ for any $B, C \in \mathbb{C}^{n \times n}$.
First of all, the equivalence should be formulated in the following way:
($A$ is not invertible or $\lVert A^{-1}\rVert \ge 1/\epsilon$) if and only if $0 \in \sigma_{\epsilon}(A) = \{ \lambda: $ there exists $E$ with $\lVert E \rVert \le \epsilon$ such that $\lambda \in \sigma(A + E) \}$.
Assume that $A$ is not invertible. Then $0 \in \sigma(A) \subset \sigma_{\epsilon}(A)$.
Assume that $\lVert A^{-1} \rVert < 1/\epsilon$. For any $E$ with $\lVert E \rVert \le \epsilon$ we have $\lVert - E A^{-1} \rVert < 1$, so the Neumann series $$ \sum\limits_{k = 0}^{\infty} (-E A^{-1})^k $$ converges to some $D \in \mathbb{C}^{n \times n}$. But $(A + E) (A^{-1}D) = I$, hence $A + E$ is invertible, consequently $0 \not\in \sigma_{\epsilon}(A)$.
Finally, assume that $\lVert A^{-1} \rVert \ge 1/\epsilon$. Then there exist a non-zero $u \in \mathbb{C}^n$ and $\lambda \in \mathbb{C}$ with $\lvert \lambda \rvert \ge 1/\epsilon$ such that $A^{-1} u = {\lambda}u$. Consequently, $Au = \frac{1}{\lambda}u$, where $\lvert \frac{1}{\lambda} \rvert \le \epsilon$. It suffices now to take $E = -\frac{1}{\lambda} I$ to conclude that $0 \in \sigma_{\epsilon}(A)$.
Incidentally, the eigenvector is non-zero by definition.
