2
$\begingroup$

Prove that if $\|A\| < 1$, then $I-A$ is invertible. Here, $\|\cdot\|$ is a matrix norm induced by a vector norm.

This lemma is referred to as Neumann Lemma.

Any ideas on how to go ahead with this?

Thanks.

  • 2
    Note that $(I-A)(I+A+A^2+A^3+\ldots+A^n)=I-A^{n+1}$ and $\lim\limits_{n\to\infty}A^{n+1}=0$. Hence, $(I-A)^{-1}=I+A+A^2+\ldots$.2012-01-12
  • 0
    I guess it should be Neumann? See Wikipedia: [Neumann series](http://en.wikipedia.org/wiki/Neumann_series).2012-01-12
  • 0
    I think the only hint one would need is 'geometric series'.2012-02-11

2 Answers 2

4

Let's say that we are dealing with matrices in $\text{Mat}_n(\mathbb{C})$. Then, $\|\cdot\|$ induces a topology on $\text{Mat}_n(\mathbb{C})$ which, by the equivalence of norms, is equivalent to the usual topology and so complete (being homeomorphic to $\mathbb{C}^{n^2}$).

Now, note that since $\displaystyle \|\sum_k A^k\|\leqslant \sum_k \|A\|^k$ and $||A\|<1$ it's easy to show that $\displaystyle \left\{\sum_k A^k\right\}$ is a Cauchy sequence in $\text{Mat}_n(\mathbb{C})$ and so by previous discussion, convergent in $\text{Mat}_n(\mathbb{C})$ to some matrix $\displaystyle \sum_{k=1}^{\infty}A^k$.

Now, prove that $(I-A)\left(I+\cdots+A^k\right)=I-A^{k+1}\quad\mathbf{(1)}$ as a formal algebraic identity.

Since $\|A^k\|\leqslant \|A\|^k\to0$ you have that $\|A^k\|\to0$ and so $A^k\to0$. Thus, taking the limit of both sides of $\mathbf{(1)}$ shows that $\displaystyle \sum_{k=1}^{\infty}A^k$ is an inverse for $A$.

  • 0
    It's true in any ring. You just do it out. $(I-A)(I+A)=I-A^2$ and $(I-A)(I+\cdots+A^k+A^{k+1})=(I-A)A^{k+1}+I-A^{k+1}=I-A^{k+2}$ so everything works out by induction.2012-01-12
  • 0
    I'm a little confused about where the matrix norm comes into play in the equation $(I−A)(I+A+⋯+A^k)=I−A^{k+1}$2012-01-12
  • 0
    It doesn't. As I said, that's an equation of a purely algebraic nature. The matrix norm comes in a) in showing that we can take limits (i.e. that it even makes sense to define limits!) and b) to show that once we can take limits the left hand side coverges to $(I-A)M$ for some matrix $M$ (i.e. that $\lim_m \sum_{k=1}^m A^k$ converges) and that the right hand side goes to $I$.2012-01-12
  • 0
    So, will it suffice to say that the series $I+A+...+A_k$ will converge if the $||A|| < 1$, and hence the inverse will exist?2012-01-12
  • 0
    Roughly, that's right.2012-01-12
1

I am adding this as a second answer because it's a fundamentally different approach.

There is a neat generalization to the above which is sometimes useful:

Theorem: Let $S\in\text{GL}(\mathbb{R}^n)$ and $T\in\text{End}(\mathbb{R}^n)$ be such that $\|T-S\|_\text{op}\|S^{-1}\|<1$. Then, $T\in\text{GL}(\mathbb{R}^n)$.

It suffices to show that $\ker T$ is trivial. To this end we observe that

$$\begin{aligned}\frac{\|v\|}{\|S^{-1}\|_\text{op}} &=\frac{1}{\|S^{-1}\|_\text{op}}\|S^{-1}(S(v))\|\\ &\leqslant \frac{\|S^{-1}\|_\text{op}}{\|S^{-1}\|_\text{op}}\|S(v)\|\\ &= \|S(v)\|\\ &\leqslant \|(S-T)(v)\|+\|T(v)\|\\ &\leqslant\|S-T\|_\text{op}\|v||+\|T(v)\|\\ &=\|T-S\|_{\text{op}}\|v\|+\|T(v)\|\end{aligned}$$

And thus we obtain that

$$\left(\frac{1}{\|S^{-1}\|_\text{op}}-\|T-S\|_\text{op}\right)\|v\|\leqslant\|T(v)\|\quad\mathbf{(1)}$$

Thus, if $v\ne0$ then $\|v\|>0$ and by assumption we may then conclude that the left side of $\mathbf{(1)}$ is positive, and so $\|T(v)\|$ is positive. Thus, $T(v)\ne0$ and so $T$ has a trivial kernel.

Now, since all matrix norms enjoy all the properties used in the above proof (submultiplicativeness, etc.) the above works if we replaced $\|\cdot\|_\text{op}$ by any norm. Thus, this proves your case taking $S=I$.

  • 1
    Good answer. It is not true that you can replace $\|\cdot\|_{op}$ by any norm. You used submultiplicativity. For a concrete example consider $1$ by $1$ matrices with the norm $\|a\|=\frac{1}{2}|a|$, $S=1$, and $T=0$.2012-01-12
  • 0
    @JonasMeyer By "norm" I meant "matrix norm" which, at least for me, means submultiplicative. I'll edit this to make it clear.2012-01-12
  • 2
    So you are just pointing out that only the property of submultiplicativity is used rather than the full assumption that it is an operator norm? I agree with that, but I don't see what that has to do with equivalence of norms.2012-01-12
  • 0
    @JonasMeyer Aha! Double meaning strikes again. That was my heavy-handed way of saying "and since all matrix norms act the same". I'll edit it. It's funny too because I used the actual technical "equivalence of norms" in the previous post. Thanks for the catch!2012-01-12
  • 1
    Small note: there are other natural norms on spaces of matrices (e.g. Frobenius or Hilbert-Schmidt norm) which are not "matrix norms" in the sense of your terminology2012-01-12
  • 0
    True, but the user did say "matrix norm" instead of "norm on matrices". I don't know, good point though.2012-01-13