Proof of Neumann Lemma

Question

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.

Answer 1

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

Answer 2

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

Answer 3

Neumann Series:

For $A \in \mathbb{C}^{n \times n},\rho(A)<1$ Since $\rho(A)< 1.$

Then we know that:$$\lim_{k \to \infty}A^{k}=0$$

the below series converges:

$$(I-A)(I+A+A^{2}+\dots+A_{k}) = I - A^{k} =\sum _{k=0}^{\infty }A^{k},\ \text{(1)}$$

Proof :

\begin{align*} (I-A)&(I+A+A^{2}+A^{3}+\dots +A^{k-1}) \\ &=I-A+A-A^{2}+A^{2}+\dots+A^{k-1}\\ &=I-A^{k} \end{align*}

Now taking the limit as $k \to \infty$ and because of $(1)$ we have:

$$ I-\lim_{k \to \infty} A^{k} = I-0=I$$ Therefore coronary of the above,we have that:

\begin{align*} (I-A)\sum_{k=0}^{\infty}A^{k}&=I \\ \sum_{k=0}^{\infty}A^{k}&=\dfrac{I}{(I-A)} \\ \sum_{k=0}^{\infty}A^{k} &= (I-A)^{-1} \end{align*}

Since $||I|| =1$ holds we have that : $$1 = ||I|| \leq ||I-A|| \cdot||(I-A)^{-1}|| \leq (1+||A||)\cdot ||(I-A)^{-1} || $$

Noting that $$I = I-A+A$$ and multiplying both sides on the right by $(I-A)^{-1}$ one gets $$(I-A)^{-1} =I+A(I-A)^{-1}.$$

Passing to the norms, we obtain $$||(I-A)^{-1} || \leq 1+||A|| \cdot ||(I-A)^{-1} || $$ and thus $$||(I-A)^{-1} || \leq \frac{1}{1-||A||}$$