Let $\mathbf{A} \in \mathbb{C}^{n \times n}$ be a non-zero matrix with Schur decomposition $\mathbf{A}=\mathbf{U}(\boldsymbol{\Lambda}+\mathbf{N}) \mathbf{U}^*$ where $\mathbf{U}$ is unitary, $\mathbf{N}$ is strictly upper triangular, and $\boldsymbol{\Lambda}=\operatorname{diag}\left(\begin{array}{lll}\lambda_1 & \cdots & \lambda_n\end{array}\right)$. Prove that if $\mathbf{A}$ is nonsingular with
$$
2\|\mathbf{N}\|_2 \leq \min _{1 \leq j \leq n}\left|\lambda_j\right|,
$$
then $\kappa_2(\mathbf{A}) \leq 3 \kappa_2(\mathbf{\Lambda})$.
My understandng is that we can write down the Schur decomposition of $\mathbf{A}^{-1} = \mathbf{U} (\mathbf{\Lambda}^{-1} + \mathbf{M}) \mathbf{U}^*$. Then,
$$
\begin{aligned}
\kappa_2(\mathbf{A}) & = \|\mathbf{\Lambda} + \mathbf{N}\|_2 \|\mathbf{\Lambda}^{-1} + \mathbf{M}\|_2 \\
& \leqslant \left(\max |\lambda_j| + \frac{1}{2} \min |\lambda_j|\right) \left(\frac{1}{\min |\lambda_j|} + \|\mathbf{M}\|_2\right).
\end{aligned}
$$
However, I am not sure how to move forward. Should I seek for a different direction. Any suggestions?
Best Answer
Using part of your reasoning above, we have $$ \begin{align*} \|\mathbf{A}\|_2 &\le \|\mathbf{\Lambda}\|_2 + \|\mathbf{N}\|_2 \le \frac{3}{2} \|\mathbf{\Lambda}\|_2. \end{align*} $$ Thus, we'll be done if we can show $$\|\mathbf{A}^{-1}\|_2 \le 2 \|\mathbf\Lambda^{-1}\|_2$$ because then we'd have $$\kappa_2(\mathbf{A}) = \|\mathbf{A}\|_2 \|\mathbf{A}^{-1}\|_2 \le \left( \frac 3 2 \|\mathbf{\Lambda}\|\right) \left( 2 \| \mathbf{\Lambda}^{-1}\|_2\right) = 3 \kappa_2(\mathbf \Lambda).$$
Now to fill in that missing step above. Choose $\mathbf{v} \in \mathbb{C}^n$ with $\|\mathbf{v}\|_2 = 1$ and let $\mathbf{w} = \mathbf{A}^{-1} \mathbf{v}$. Then we have $$\begin{align*} 1 = \|\mathbf{v}\|_2 &= \|\mathbf{\Lambda} \mathbf{w} + \mathbf{N} \mathbf w \|_2 \\ &\ge \|\mathbf{\Lambda w}\|_2 - \| \mathbf{Nw}\|_2 \\ &\ge \big (\min |\lambda_j| - \|\mathbf{N}\|_2 \big ) \|\mathbf{w}\|_2 \\ &\ge \left(\frac 1 2 \min|\lambda_j|\right) \|\mathbf{w}\|_2 \\ \end{align*}$$
and rearranging gives $$\|\mathbf{w}\|_2 \le \frac{2}{\min |\lambda_j|} = 2 \|\mathbf{\Lambda}^{-1}\|_2$$
so we conclude $\|\mathbf{A}^{-1}\|_2 \le 2 \|\mathbf\Lambda^{-1}\|_2$ which completes the proof.