# A lower bound for the condition number matrix

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?

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