# Proof of Neumann Lemma

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.

-
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$. – Norbert Jan 12 '12 at 20:28
I guess it should be Neumann? See Wikipedia: Neumann series. – Martin Sleziak Jan 12 '12 at 20:37
I think the only hint one would need is 'geometric series'. – wildildildlife Feb 11 '12 at 18:50

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$.

-
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. – Alex Youcis Jan 12 '12 at 21:22
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}$ – rookieRailer Jan 12 '12 at 21:38
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$. – Alex Youcis Jan 12 '12 at 21:41
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? – rookieRailer Jan 12 '12 at 21:55
Roughly, that's right. – Alex Youcis Jan 12 '12 at 21:57

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$.

-
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$. – Jonas Meyer Jan 12 '12 at 21:00
@JonasMeyer By "norm" I meant "matrix norm" which, at least for me, means submultiplicative. I'll edit this to make it clear. – Alex Youcis Jan 12 '12 at 21:01
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. – Jonas Meyer Jan 12 '12 at 21:04
@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! – Alex Youcis Jan 12 '12 at 21:06
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 terminology – user16299 Jan 12 '12 at 22:25