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?

$\endgroup$
6
  • 1
    $\begingroup$ Look at the series $\sum_{n=0}^\infty(-A)^n$ $\endgroup$
    – Aweygan
    Mar 13, 2017 at 18:16
  • $\begingroup$ Can you show that $I_n-A+A^2-A^3+\cdots$ converges? $\endgroup$ Mar 13, 2017 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, 2017 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$ Mar 13, 2017 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, 2017 at 19:10

3 Answers 3

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

$\endgroup$
3
  • 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$ Mar 13, 2017 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, 2017 at 19:39
  • 1
    $\begingroup$ @Mophotla see my edit. I exchanged the roles of $A$ and $A+I$ by accident $\endgroup$ Mar 13, 2017 at 19:47
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} $$

$\endgroup$
8
  • 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, 2017 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, 2017 at 19:34
  • 1
    $\begingroup$ @dantopa Okay, and how does it follow that $\lVert A\rVert>1$? $\endgroup$
    – Mophotla
    Mar 13, 2017 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, 2017 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, 2017 at 20:41
1
$\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.

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