# Prove that $A+I_n$ is invertible, where $\left\lVert A\right\rVert<1$

Let $\left\lVert\cdot\right\rVert:\mathbb R^{n\times n}\to\mathbb R$ be a submultiplicative matrix norm and $A\in\mathbb R^{n\times n}$ such that $\lVert A\rVert<1$. Prove that $A+I_n$ is invertible, where $I_n$ is the identity matrix in $\mathbb R^{n\times n}$.

I tried coming up with something like $$\lVert A+I_n\rVert=\lVert A(I_n+A^{-1})\rVert\leq\lVert A\rVert\cdot\lVert(I_n+A^{-1})\rVert<\lVert I_n+A^{-1}\rVert,$$ but that doesn't seem to get me anywhere. In the end, I think I should have some (in)equality with the determinant of $I_n+A^{-1}$ in it (and conclude that it is not $0$), but I don't know how to get there. How could I proceed?

• Look at the series $\sum_{n=0}^\infty(-A)^n$ – Aweygan Mar 13 '17 at 18:16
• Can you show that $I_n-A+A^2-A^3+\cdots$ converges? – Jyrki Lahtonen Mar 13 '17 at 18:16
• I guess I can: $$\forall n>m \in\mathbb N:\left\lVert\sum_{i=0}^{n}(-A)^i-\sum_{i=0}^{m}(-A)^i\right\rVert=\left\lVert\sum_{i=m+1}^{n}(-A)^i\right\rVert\leq\sum_{i=m+1}^{n}\left\lVert(-A)^i\right\rVert\leq\sum_{i=m+1}^n\left\lVert-A\right\rVert^i,$$which can be smaller than any desired $\epsilon$ if you choose $m,n$ large enough, because $\left\lVert A\right\rVert<1$. – Mophotla Mar 13 '17 at 18:28
• @Mophotla great! Now, show that this sum satisfies the properties of an inverse. That is, show that $AB = I$ (where $B$ is the sum). – Omnomnomnom Mar 13 '17 at 18:51
• @Omnomnomnom I suppose you mean "show that $(A+I)B=I$? Then I guess I have it. Is my proof of $(s_n)_n=\sum_{i=0}^n(-A)^i$ being a Cauchy sequence formally correct? – Mophotla Mar 13 '17 at 19:10

Given a matrix such that $\lVert \mathbf{A} \rVert < 1$, the matrix $\mathbf{I} \color{red}{-} \mathbf{A}$ is nonsingular with $$\left( \mathbf{I} - \mathbf{A} \right)^{-1} = \sum_{k=0}^{\infty}\mathbf{A}^{k},$$ and $$\lVert \left( \mathbf{I} \color{red}{-} \mathbf{A} \right)^{-1} \rVert \le \frac{1}{1-\lVert \mathbf{A}\rVert}.$$

Let $\mathbf{I} - \mathbf{A}$ be singular. $\exists$ a nonzero $x$ such that $\left( \mathbf{I} - \mathbf{A} \right)x = 0.$ Then we have $$\lVert x \rVert = \lVert \mathbf{A} x \rVert$$ which implies $\lVert \mathbf{A} \rVert \ge 1.$ $\color{red}{\Rightarrow \Leftarrow}$

Derivation

Start with the telescopic identity $$\left( \sum_{k=0}^{N}\mathbf{A}^{k} \right) % \left( \mathbf{I} - \mathbf{A} \right) % = % \mathbf{I} - \mathbf{A}^{N+1} %$$ Knowing the property of submultiplicative norms $\lVert \mathbf{A}^{k} \rVert \le \lVert \mathbf{A} \rVert^{k}$ and given $\lVert \mathbf{A} \rVert < 1$ we see $\lim_{k\to\infty}\mathbf{A}^{k} = 0$. This implies $$\left( \lim_{N\to \infty} \sum_{k=0}^{N}\mathbf{A}^{k} \right) % \left( \mathbf{I} - \mathbf{A} \right) % = % \mathbf{I}, %$$ and $$\left( \mathbf{I} - \mathbf{A} \right)^{-1} = \left( \lim_{N\to \infty} \sum_{k=0}^{N}\mathbf{A}^{k} \right).$$ At last, $$\lVert \left( \mathbf{I} - \mathbf{A} \right)^{-1} \rVert \le \sum_{k=0}^{\infty}\lVert \mathbf{A} \rVert^{k} = \frac{1}{1-\lVert \mathbf{A}\rVert}$$

• You actually proved that $I-A$ is invertible, but I seems that the proof is pretty analogous for $I+A$ by using the series mentioned in the comments: It's just $$\left(\sum_{k=0}^N (-A)^k\right)(I+A)=I+(-A)^NA$$ instead. Could you please elaborate on your proof by contradiction? I don't quite understand why there has to be a nonzero vector $x$ so that $(I+A)(x)=0$ and why it implies $\lVert A\rVert>1$ in the end. – Mophotla Mar 13 '17 at 19:29
• If $I+A$ is singular, it has nontrivial kernel, so there is a nonzero vector $x$ such that $(I+A)x = 0$. – Integral Mar 13 '17 at 19:34
• @dantopa Okay, and how does it follow that $\lVert A\rVert>1$? – Mophotla Mar 13 '17 at 19:42
• My question actually is about the following part: "Then we have $\lVert x\rVert=\lVert Ax\rVert$ which implies $∥A∥>1$." I don't understand why this implication holds (it is clear when applying submultiplicativity, but here, this is only given for the matrix norm, not necessarily for the vector norm). – Mophotla Mar 13 '17 at 20:05
• Neat thorough answer. A typographic error: $||x|| = ||Ax||$ for a non zero $x$ should imply $||A|| \geq 1$. – Olivier Mar 13 '17 at 20:41

Note that for any matrix $M$: if $\lambda$ is an eigenvalue, then $|\lambda| < \|M\|$. Thus, all eigenvalues of $A$ satisfy $|\lambda| < 1$.

Now, if $\mu$ is an eigenvalue of $A + I$, then $(\mu - 1)$ is an eigenvalue of $A + I$, which tells us that $|\mu - 1| < 1$. We can conclude that $A + I$ does not have zero as an eigenvalue. It follows that $A+I$ is invertible.

• The approach in the comments also works (and is, in a sense, a more general approach than mine). Nevertheless, I've given an alternative answer. – Omnomnomnom Mar 13 '17 at 18:56
• "Thus, all eigenvalues of $A+I$ satisfy $|\lambda|<1$." How do you conclude this, when it is only known that $\lVert A\rVert<1$, but not $\lVert A+I\rVert<1$? – Mophotla Mar 13 '17 at 19:39
• @Mophotla see my edit. I exchanged the roles of $A$ and $A+I$ by accident – Omnomnomnom Mar 13 '17 at 19:47

A bit of a more straightforward proof, similar to @dantopa.

Let $$K = -A$$, then $$I + A = I - K$$ and $$\lVert K \rVert = \lVert A \rVert < 1$$. Suppose for the sake of contradiction that $$(I-K)$$ is not invertible, then there exists $$x\in\mathbb{R}^n\setminus\{0\}$$, such that $$\lVert(I-K)x\rVert = 0, \lVert x \rVert \neq 0.$$ But $$\lVert(I-K)x\rVert\geq \lVert x \rVert - \lVert Kx\rVert \geq \lVert x\rVert(1 - \lVert K \rVert) > 0,$$ a contradiction, so $$(I-K)$$ is invertible.

Now let $$S = (I-K)^{-1}$$ and $$S_n = I + K + \cdots + K^n,$$ for some $$n\in\mathbb{N}$$, then \begin{align*} KS_n = K + K^2 + \cdots + K^{n+1} = S_n + K^{n+1} - I,\\ S_n= (I - K)^{-1}(I - K^{n+1}) = S(I-K^{n+1}), \end{align*} and so $$\lVert S_n - S\rVert = \lVert S(I - K^{n+1})-S\rVert = \lVert-SK^{n+1}\rVert \leq\lVert S\rVert\lVert{K\rVert}^{n+1} \xrightarrow{n\to\infty} 0.$$ Q.E.D.