# 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. Sep 24, 2018 at 2:39
• Thanks, sorry about that Sep 24, 2018 at 2:40

The statement is false. Consider the max norm, like here. So the counterexample is:

$$A := \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$$ is invertible and $$B := \begin{pmatrix} 1/4 & 1/2 \\ 1/2 & 1 \end{pmatrix}$$ is singular.

$$\|A^{-1}\| \cdot \|A-B\| = 1 \cdot \left\|\begin{pmatrix} 3/4 & -1/2 \\ -1/2 & 0 \end{pmatrix} \right\| = \frac{3}{4} < 1$$

The problem is indeed the absence of sub-multiplicative property. But if a matrix norm have this property then, the statement become true by the following lemma.

Lemma: Let $$\|\cdot\|$$ be a matrix norm on $$\mathbb{R}^{n \times n}$$. If $$\|\cdot\|$$ is sub-multiplicative, then there is a vector norm $$\|\cdot\|_*$$ on $$\mathbb{R}^n$$ such that both norms are compatible.

Proof: Fix $$\boldsymbol{0} \neq \boldsymbol{y} \in \mathbb{R}^n$$. Define $$\|\cdot\|_* : \mathbb{R}^n \to [0,\infty)$$ such that $$\|\boldsymbol{x}\|_* := \|\boldsymbol{x}\boldsymbol{y}^T\|$$ for every $$\boldsymbol{x} \in \mathbb{R}^n$$.

It's easy to check that $$\|\cdot\|_*$$ is a well defined vector norm because $$\boldsymbol{y} \neq \boldsymbol{0}$$ and the propierties of $$\|\cdot\|$$ for being, by hyphothesis, a sub-multiplicative matrix norm. So let's just check compatibility.

Let $$A \in \mathbb{R}^{n \times n}$$ and $$\boldsymbol{x} \in \mathbb{R}^n$$. Then by sub-multiplicative property of $$\|\cdot\|$$ we have $$\|A\boldsymbol{x}\|_* = \|(A\boldsymbol{x})\boldsymbol{y}^T\| = \|A(\boldsymbol{x}\boldsymbol{y}^T)\| \leq \|A\| \cdot \|\boldsymbol{x}\boldsymbol{y}^T\| = \|A\| \cdot \|\boldsymbol{x}\|_*$$

Hence $$\|\cdot\|$$ is compatible with $$\|\cdot\|_*$$. $$\blacksquare$$

Then we are done since in the edited part of my post I had already demonstrated the result when we have sub-multiplicative and compatibility properties.