2
$\begingroup$

$\|\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.

$\endgroup$
  • $\begingroup$ 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)$) $\endgroup$ – user10354138 Oct 14 '18 at 20:25
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – S.Dragon Oct 14 '18 at 22:05
  • $\begingroup$ No, $\sup\{\|Ax-Bx\|:\|x\|=1\}$ need not occur when $Bx=0$. $\endgroup$ – user10354138 Oct 14 '18 at 23:00
  • $\begingroup$ 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. $\endgroup$ – S.Dragon Oct 15 '18 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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