# Suppose ||.|| is an induced matrix norm, A is non-singular, and B is singular. Prove $\frac{1}{\kappa(A)}\leq\frac{||A-B||}{||A||}$.

$$\|\cdot\|$$ is the induced norm for $$n\times n$$ matrices in $$\mathbb{C}$$, with respect to some vector norm ($$\mathbb{C}^n\to\mathbb{R}$$). $$A$$ and $$B$$ are $$n\times n$$ matrices where $$A$$ is non-singular (invertible) and $$B$$ is singular. $$\kappa(A)$$ is the condition number of a non-singular matrix defined by $$\kappa(A)=||A||\cdot||A^{-1}||$$

Prove: $$\dfrac{1}{\kappa(A)}\leq\dfrac{||A-B||}{||A||}$$

Work so far:

I know that $$1=\|I\|=\|AA^{-1}\|\leq\|A\|\cdot\|A^{-1}\|$$ from the sub-multiplicative property of norms so that $$\frac{1}{\kappa(A)}\leq1$$

We know that $$\|A\|>0, \|B\|\geq0$$

$$\|B\|=0$$ iff $$B$$ is the zero matrix in which case the property holds. Assuming B is not the zero matrix, then $$\|B\|>0$$. So I just need to show $$\|A\|\leq\|A-B\|$$ for a singular B.

$$\|A\|-\|B\|<\|A\|=\|A-B+B\|\leq\|A-B\|+\|B\|$$

This is where I get stuck. I think I'm missing some property of induced norms or I've made an incorrect assumption somewhere.

• The bound $\kappa(A)\geq 1$ is too crude, and in general you don't have $\|A\|\leq\|A-B\|$ (e.g. consider $A=I$ and $B=\operatorname{diag}(-1,0)$) – user10354138 Oct 14 '18 at 20:25

## 1 Answer

Your bound $$\kappa(A)\geq 1$$ is too crude. Instead, appeal directly to the definition of $$\kappa(A)$$ to get $$\dfrac{1}{\kappa(A)}\leq\dfrac{\|A-B\|}{\|A\|} \iff \|A-B\|\cdot\|A^{-1}\|\geq 1.$$ Now look at the effect of $$(A-B)A^{-1}$$ (or $$A^{-1}(A-B)$$) on a suitable vector to conclude $$\|A-B\|\cdot\|A^{-1}\|\geq 1$$.

• Ok, I'm not sure if this is correct, but I think I'm getting closer. So using the definition of an induced norm the sup||Ax-Bx|| occurs when Bx=0, which must be true since B is singular and has a 0 eigenvalue. So sup||Ax-Bx||=sup||Ax||=||A||. Thus ||A-B|||A^-1||=||A||||A^-1||>=||AA^-1||=1 and since A is invertable we can say that last part. I'm still not sure I understand why that last part is a crude bound. Sorry I was still writing when I pressed enter. – S.Dragon Oct 14 '18 at 22:05
• No, $\sup\{\|Ax-Bx\|:\|x\|=1\}$ need not occur when $Bx=0$. – user10354138 Oct 14 '18 at 23:00
• How about if I separate it using the reverse triangle inequality? Edit: Never mind, I'm using a single vector at a time so I guess that still isn't necessarily true. – S.Dragon Oct 15 '18 at 0:53