2
$\begingroup$

I have 2 matrices: $A \in R^{nxn}$ is a non-singular matrix and $B \in R^{nxn}$ is a singular matrix. Here is the expression I need to prove:

$$||A - B|| \ge ||A^{-1}||^{-1}$$

I dont understand why it makes a difference to say B is singular. Is there something special about the norm of a singular matrix? I know the condition number of B = inf and its determinate is 0, thus has no inverse, but I dont know how these things can help me determine the inequality above. I feel like I am missing a key point about singular matrices or something.

Also, would it be true to say in this instance that: $$||A - B|| \ge ||A|| - ||B||$$

or should that be less than or equal to instead of greater than or equal to.

3 Answers 3

2

The first inequality is actually a direct consequence of the following lemma:

Lemma. If $\|\cdot\|$ is a matrix norm and $\|I-X\|<1$, then $X$ is invertible.

I am not going to prove the lemma here. I think it can be found in many textbooks. Essentially, by using the properties of a matrix norm, one can first show that the partial sums of $Y=\sum_{k=0}^\infty (I-X)^k$ form a Cauchy sequence. Hence $Y$ converges. Then, one can show that $XY=I$ and in turn $X$ is invertible.

Since $A^{-1}B$ is singular, by the previous lemma, we have $1\le\|I-A^{-1}B\|=\|A^{-1}(A-B)\|\le\|A^{-1}\|\|A-B\|$. Thus we get your first inequality. Note that we have used the fact that $A^{-1}B$ is singular. Should $B$ be invertible, so be $A^{-1}B$ and we cannot make use of the contraposition of the previous lemma.

Your second inequality is correct. It is just the triangle inequality in disguise: $\|A\| = \|(A-B)+B\| \le \|A-B\|+\|B\|$. Yet we can refine it by a little: by interchanging the roles of $A$ and $B$, we have also $\|B-A\|\ge\|B\|-\|A\|$. So, putting the two inequalities together, we get $\|A-B\|\ge\left\lvert\left(\|A\|-\|B\|\right)\right\rvert$.

  • 0
    Could please explain the step, "since $A^{-1}B$ is singular, $1\leq \lvert\lvert I-A^{-1}B\rvert\rvert$". Because, the lemma you used states, if $||I-X||<1$, then $X$ is invertible. Where does it say anything about singular matrices?. Did you mean if $X$ is singular, then $1\geq ||I-X||$.2012-12-05
  • 1
    @dineshdileep The lemma says "$\|I-X\|<1\Rightarrow X$ is invertible". This is equivalent to "$X$ is singular $\Rightarrow\|I-X\|\ge1$". (Statement calculus: the contraposition of $p\rightarrow q$ is $\neg q\rightarrow \neg p$.) Now put $X=A^{-1}B$. As $X$ is singular, we use the contrapositive form of the lemma rather than the original form.2012-12-05
  • 0
    oh!!, thats new to me. Thanks a lot for the explanation. Could you point to me some easy reference on contrapositive. I really like your answers.2012-12-05
  • 0
    @dineshdileep: Are you assuming $A^{-1}B$ is singular or can you deduce it is singular because B is singular?2012-12-05
  • 0
    for two matrices $P$,$Q$, we have $det(PQ)=det(P)det(Q)$, use $P=A^{-1}$,$Q=B$. If $det(C)=0$, $C$ is singular.2012-12-05
  • 0
    @dineshdileep I learnt basic propositional calculus back in high school, so I no longer have any reference at hand now, but a [Wikipedia entry](http://en.wikipedia.org/wiki/Propositional_calculus#Basic_and_derived_argument_forms) summarizes the relevant material fairly well and you may take a look at it. The contrapositive here is called "transposition" in the article.2012-12-05
0

Some constraint on $B$ is needed, or we could take $B=A$ and deduce that $$ 0 = \|A-A\| \ge \| A^{-1}\|^{-1}. $$ Your inequality $\|A-B\| \ge \|A\| - \|B\|$ is a rearrangement of the triangle inequality and so holds for any two matrices.

And you should state what norm you are using. If we use the Frobenius norm and take $A$ to be the $3\times3$ identity matrix and let $B$ be the matrix we get by setting $A_{3,3}=0$, then $\|A-B\|=1$ and $\|A^{-1}\|=3$. (In fact it is not clear to me that the inequality you want is true.)

  • 0
    how could B = A? A is nonsingular and B is singular. How can they be equal?2012-12-05
  • 0
    also, in your statement, you need to take the reciprocal of 3 to get the inequality. So 1 >= 1/3. I think it should work in any norm. Is it true to say that if its equivalent in one norm, its equivalent in all norms?2012-12-05
  • 0
    The first question was, why do we need $B$ to be nonsingular. My response shows why. For the Frobenius norm part, all I can say is that it was late.2012-12-05
0

The point is that if $A$ is nonsingular and $\|B - A\| < \|A^{-1}\|^{-1}$, then $B$ is also nonsingular. In fact, if we write $B = A - T = A (I - A^{-1} T)$, then $$B^{-1} = \sum_{j=0}^\infty (A^{-1} T)^j A^{-1}$$ where the sum converges since $\|A^{-1} T\| \le \|A^{-1}\| \|T\| < 1$.