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$
1
  • $\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$ Oct 14, 2018 at 20:25

1 Answer 1

1
$\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$
3
  • $\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, 2018 at 22:05
  • $\begingroup$ No, $\sup\{\|Ax-Bx\|:\|x\|=1\}$ need not occur when $Bx=0$. $\endgroup$ Oct 14, 2018 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, 2018 at 0:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .