6
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Look at the series $\sum_{n=0}^\infty(-A)^n$ $\endgroup$ – Aweygan Mar 13 '17 at 18:16
  • $\begingroup$ Can you show that $I_n-A+A^2-A^3+\cdots$ converges? $\endgroup$ – Jyrki Lahtonen Mar 13 '17 at 18:16
  • $\begingroup$ 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$. $\endgroup$ – Mophotla Mar 13 '17 at 18:28
  • 1
    $\begingroup$ @Mophotla great! Now, show that this sum satisfies the properties of an inverse. That is, show that $AB = I$ (where $B$ is the sum). $\endgroup$ – Omnomnomnom Mar 13 '17 at 18:51
  • $\begingroup$ @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? $\endgroup$ – Mophotla Mar 13 '17 at 19:10
3
$\begingroup$

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

Proof by contradiction

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Mophotla Mar 13 '17 at 19:29
  • $\begingroup$ If $I+A$ is singular, it has nontrivial kernel, so there is a nonzero vector $x$ such that $(I+A)x = 0$. $\endgroup$ – Integral Mar 13 '17 at 19:34
  • 1
    $\begingroup$ @dantopa Okay, and how does it follow that $\lVert A\rVert>1$? $\endgroup$ – Mophotla Mar 13 '17 at 19:42
  • 1
    $\begingroup$ 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). $\endgroup$ – Mophotla Mar 13 '17 at 20:05
  • 1
    $\begingroup$ Neat thorough answer. A typographic error: $ ||x|| = ||Ax||$ for a non zero $x$ should imply $||A|| \geq 1$. $\endgroup$ – Olivier Mar 13 '17 at 20:41
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Omnomnomnom Mar 13 '17 at 18:56
  • $\begingroup$ "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$? $\endgroup$ – Mophotla Mar 13 '17 at 19:39
  • 1
    $\begingroup$ @Mophotla see my edit. I exchanged the roles of $A$ and $A+I$ by accident $\endgroup$ – Omnomnomnom Mar 13 '17 at 19:47
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.