I have the following proposition:

Theorem: For every invertible matrix $A\in\mathbb{R}^{n\times n}$ and every matrix norm $\|\cdot\|$, then the condition number $\mathcal{K}(A):=\|A\|\cdot\|A^{-1}\|$ satisfies, $$\frac1{\mathcal{K}(A)}\leq\min\left\{\frac{\|A-B\|}{\|A\|}\ |\ \det(B)=0\right\}$$

Proving this is equivalent to proving that $\|A^{-1}\|\cdot\|A-B\|\geq1$ for every singular matrix $B\in\mathbb{R}^{n\times n}$.

But honestly, I have no idea how to proceed becuase the matrix norm is arbitrary and not necessarily satisfies the sub-multiplicative property. Any hint?

Edit: I know that if $\|\cdot\|_*$ is and induced norm, then it's sub-multiplicative and compatible: $$\|AB\|_*\leq\|A\|_*\cdot\|B\|_*,\quad\text{for every $A,B\in\mathbb{R}^{n\times n}$}$$ $$\|A\boldsymbol{x}\|_*\leq\|A\|_*\cdot\|\boldsymbol{x}\|_*,\quad\text{for every $A\in\mathbb{R}^{n\times n}$ and every $\boldsymbol{x}\in\mathbb{R}^n$}$$ With these properties the proof is simple.

Proof (for induced norms): Let $A\in\mathbb{R}^{n\times n}$ invertible and $B\in\mathbb{R}^{n\times n}$ singular. Then, there is $\boldsymbol{x}\in\mathbb{R}^n\setminus\{\boldsymbol{0}\}$ such that $B\boldsymbol{x}=\boldsymbol{0}$. Therefore, $B\boldsymbol{x}=(A+B-A)\boldsymbol{x}=A\boldsymbol{x}-(A-B)\boldsymbol{x}=\boldsymbol{0}$. Then, $A\boldsymbol{x}=(A-B)\boldsymbol{x}$ and since $A$ is invertible, $\boldsymbol{x}=A^{-1}(A-B)\boldsymbol{x}$.

Using the previously mentioned properties, then: $$ \begin{array}{rcl} \|\boldsymbol{x}\|_*&=&\|A^{-1}(A-B)\boldsymbol{x}\|_*\\ &\leq&\|A^{-1}(A-B)\|_*\cdot\|\boldsymbol{x}\|_*\\ &\leq&\|A^{-1}\|_*\cdot\|A-B\|_*\cdot\|\boldsymbol{x}\|_* \end{array} $$ Since $\boldsymbol{x}\neq\boldsymbol{0}$, then $\|\boldsymbol{x}\|_*\neq\boldsymbol{0}$. Simplifying we get $\|A^{-1}\|_*\cdot\|A-B\|_*\geq1$ and since $B$ is an arbitrary singular matrix, the proof is done. $\blacksquare$

So, I think using the fact that all norms in $\mathbb{R}^{n\times n}$ are equivalent we have that there are $r,s\in\mathbb{R}^+$ such that $r\|A\|\leq\|A\|_*\leq s\|A\|$ for every $A\in\mathbb{R}^{n\times n}$. Therefore, $$1\leq\|A^{-1}\|_*\cdot\|A-B\|_*\leq s^2\|A^{-1}\|\cdot\|A-B\|$$ However, we don't know if $s\leq1$, in fact it's not always the case. This theorem may only apply for sub-multiplicative and compatible norms, I'm trying to figure out a counterexample. I am going on the right way?

  • $\begingroup$ $B$ must be singular, $B=\frac1{2}I$ it's not. $\endgroup$ – CrisPaint Sep 24 '18 at 2:39
  • $\begingroup$ Thanks, sorry about that $\endgroup$ – angryavian Sep 24 '18 at 2:40

Your Answer

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

Browse other questions tagged or ask your own question.