$\text{det}(A+E) = 0 \implies \Vert E\Vert_{2} \geq \sigma_n$?

Question

Suppose $A,E$ are $n\times n$ matrices and $A$ has singular values $\sigma_1\geq \sigma_2 \geq \cdots \geq \sigma_n >0$.

Please help me to prove that $\Vert E \Vert_2 \geq \sigma_n$ if $A+E$ is singular.

Is there any singular matrix $E$ such that $\Vert E \Vert_2 = \sigma_n$ ?

Answer 1

If $A+E$ is singular, then $(A+E)x=0$ for some nonzero $x$. Hence $$ x=-A^{-1}Ex\quad\Rightarrow\quad \|x\|_2\leq\underbrace{\|A^{-1}\|_2}_{=\sigma_n^{-1}}\|E\|_2\|x\|_2\quad\Rightarrow\quad\sigma_n\leq\|E\|_2. $$ The matrix $E$ of the minimum norm which makes $E$ singular is (assuming $\sigma_n<\sigma_{n-1}$) $$ E=-\sigma_n u_n v_n^*, $$ where $u_n$ and $v_n$ are left and right singular vectors associated with $\sigma_n$. Clearly, $\|E\|_2=\sigma_n$ and using the SVD of $A$, you can verify that $$A+E=\sum_{i=1}^{n-1}\sigma_i u_iv_i^*$$ is singular.

Answer 2

Hint. For your first question, if $M$ is a complex matrix, then $\|M\|_2=\sigma_1(M)=\max_{\|x\|_2=1}\|Mx\|_2$ and $\sigma_n(M)=\min_{\|x\|_2=1}\|Mx\|_2$ (Courant-Fischer minimax principle). Now, if $A+E$ is singular, $(A+E)x=0$ for some unit vector $x$.

The answer to your second question should be trivial.

Answer 3

For the first question: following where the other answer left off, suppose that we can find an $x$ such that $(A+E)x = 0$ and $\|x\| = 1$. It follows that $$ Ax = -Ex \implies \|Ax\|_2 = \|Ex\|_2 $$ What does this tell us about $\min_{\|x\| = 1} \|Ax\|_2$ and $\max_{\|x\| = 1} \|Ex \|_2$?