Let $A, E \in M_n(\mathbb C)$ be as in this question On invertibility of $A+E$ where $||E||_2<$ smallest singular value of $A$ and $||A^{-1}E||_2<1$ .

How to prove that $\dfrac {||A^{-1}b-(A+E)^{-1}b||_2}{||A^{-1}b||_2}\le \dfrac {||E||_2||A^{-1}||_2}{1-\frac {||E||_2}{\sigma_\min}}$ ?

  • $\begingroup$ I don't have a whole lot of time to figure it out, but have you tried anything using the geometric series representation of the inverse when the spectral radius is less than one? The right hand side looks oddly reminiscent of the value obtained when summing up such a series. $\endgroup$ – OldGodzilla Jan 16 at 16:32

I assume that $b\in Bbb C^n$ is an arbitrary non-zero vector and $$\sigma_\min(M)=\inf \{\|Mx\|_2: x\in\Bbb C^n\mbox{ and }\|x\|_2=1\}$$ for each $M\in\Bbb M_n(\Bbb C)$. Put $c=(A+E)^{-1}b$. Then $A^{-1}b=A^{-1}(A+E)c=c+A^{-1}Ec$. Now we have to prove that

$$\dfrac {\|A^{-1}Ec \|_2}{\| c+A^{-1}Ec \|_2}\le \dfrac {||E||_2||A^{-1}||_2}{1-\frac {||E||_2}{\sigma_\min}}.$$

Put $d=\frac{c}{\|c\|_2}$. It suffices to prove that

$$\dfrac {\|A^{-1}Ed \|_2}{\| d+A^{-1}Ed \|_2}\le \dfrac {||E||_2||A^{-1}||_2}{1-\frac {||E||_2}{\sigma_\min}}.$$

Since $\|A^{-1}Ed \|_2\le ||E||_2||A^{-1}||_2$, it suffices to prove that

$$1-\frac {||E||_2}{\sigma_\min}\le \| d+A^{-1}Ed \|_2.$$

Since $\| d+A^{-1}Ed \|_2\ge \| d\|_2- \|A^{-1}Ed \|_2=1-\| A^{-1}Ed \|_2$, it suffices to prove that

$${\sigma_\min}\| A^{-1}Ed \|_2\le ||E||_2.$$

Since $$\| A^{-1}Ed \|_2\le \| A^{-1} \|_2\|Ed \|_2\le \| A^{-1} \|_2\|E \|_2\|d\|_2=\| A^{-1} \|_2\|E \|_2,$$

It suffices to check that $${\sigma_\min}\| A^{-1}\|_2\le 1.$$


$$\sigma_\min\| A^{-1}\|_2=\sigma_\min\sup \{\|A^{-1}x\|_2: x\in\Bbb C^n\mbox{ and }\|x\|_2=1\}.$$

Let $x\in\Bbb C^n$ and $\|x\|_2=1$. We have $$1=\|x\|_2=\|AA^{-1}x\|_2\ge \sigma_{\min} \|A^{-1}x\|_2,$$ so $\sigma_\min\| A^{-1}\|_2\le 1$.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.