A proof about minimum singular values

Question

Let $A \in \mathbb{R}^{n \times n}$ be an arbitrary square matrix and $I$ be the identity matrix. I am trying to prove that $$ \sigma_{\min}(A+I) \geq 1- \sigma_{\max}(A)=1-\|A\|. $$ Any hints on how to proceed? My attempt is the following:

It suffices to prove that $(A+I)^\top (A+I) \succcurlyeq (1-\|A\|)^2 I $ which is equivalent to proving $A^\top+A+2\|A\|+ A^\top A -\|A\|^2 I \succcurlyeq 0$. However I am stuck here.

Answer 1

If $\|A\|\ge1$, the inequality is trivial, because a singular value must be nonnegative.

If $\|A\|<1$, then $I+A$ is nonsingular. Rewrite the inequality as $$ (1-\|A\|)^{-1}\ge\frac1{\sigma_\min(I+A)}=\|(I+A)^{-1}\|. $$ Now, try to make use of the series expansion $(1-x)^{-1}=1+x+x^2+\ldots$.

Answer 2

We have $$ \|x\|_2=\|[(A+I)-A]x\|_2\leq\|(A+I)x\|_2+\|Ax\|_2, $$ so $$ \|(A+I)x\|_2\geq\|x\|_2-\|Ax\|_2 $$ and $$ \sigma_\min(A+I)=\min_{\|x\|_2=1}\|(A+I)x\|_2\geq\min_{\|x\|_2=1}\left(\|x\|_2-\|Ax\|_2\right)=1-\max_{\|x\|_2=1}\|Ax\|_2=1-\sigma_\max(A). $$