1
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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