Show $x_n$ converges for any $x_0$ iff spectral radiaus is less than 1

Question

Let $M$ be a $n \times n$ real matrix and $b \in \mathbb{R}^n$.

We consider the sequence $(x_k)_k$ defined by

$x_0\in\mathbb{R}^n,x_{k+1}=M x_k+b$.

Show that $(x_k)$ converges for any $x_{0}$ IFF

the spectral radius of $M$ is less than $1$.

Remark. I found $x_k=M^kx_0+(M^{k−1}+M^{k−2}+....+I)b$; how can I justify from here?

Answer 1

We assume that $\rho(M)<1$ where $\rho(.)$ is the spectral radius. We can invoke the Contraction Mapping Theorem, since the operator $$Tx := Mx+b$$ maps $\mathbb{R}^n$ to $\mathbb{R}^n$, which is a complete metric space wrt the standard Euclidean norm. To do this, it suffices to show that $T$ is a contraction for some operator norm. Indeed $$||Tx-Ty|| = ||(Mx+b)-(My+b)|| = ||M(x-y)|| \leq ||M||||x-y||.$$ Now, there exists an operator norm s.t. $||M||<\rho(M)+\epsilon$. It we choose $\epsilon=1-\rho(M)$, then $||M||<1$ and we obtain the existence of the limit.

Answer 2

$\textbf{Proposition}$. The "only if" part is valid when $1$ is not a semi simple eigenvalue of $M$.

Note that if $M=I$ and $b=0$, then, for every $x_0$, $(x_k)$ converges.

$\textbf{Proof}$. Assume that $\rho(M)\geq 1$ and that, for every $x_0$, $(x_k)$ converges. We look for a contradiction.

If $x_0=0$, then $x_k=(M^{k-1}+\cdots+I)b$ and the sequence $((M^{k-1}+\cdots+I)b)_k$ converges. Thus, for every $x_0$, the sequence $(M^kx_0)_k$ converges.

There is $\lambda\in spectrum(M)$ s.t. $|\lambda|\geq 1$.

i) If $\lambda\in\mathbb{R}$, then let $x_0$ be an eigenvector associated to $\lambda$. Since $M^kx_0=\lambda^kx_0$, we obtain a contradiction except if $\lambda=1$.

If $1\in spectrum(M)$, then it is not semi simple, that is, in the Jordan decomposition of $M$, there is a block $I_r+J_r$ where $J_r$ is the nilpotent Jordan block of dimension $r\geq 2$. To obtain the contradiction, it suffices to choose $x_0=e_2$ in this new basis.

ii) If $\lambda\notin\mathbb{R}$, then $\lambda=a+ib$ (where $b\not=0,a^2+b^2\geq 1$) is associated to an eigenvector $u$ s.t. $Au=\lambda u,A\overline{u}=\overline{\lambda}\overline{u}$. Note that $\Pi=span(u+\overline{u},i(u-\overline{u}))$ is an $M$-invariant plane; the matrix of $M_{|\Pi}$ associated to the above basis is

$\begin{pmatrix}a&-b\\b&a\end{pmatrix}=\sqrt{a^2+b^2}R_{\theta}$ where $R_{\theta}$ is in the form

$\begin{pmatrix}\cos(\theta)&-\sin(\theta)\\\sin(\theta)&\cos(\theta)\end{pmatrix}$ with $\sin(\theta)\not=0$.

If $x_0\in\Pi\setminus \{0\}$, then $M^kx_0=(a^2+b^2)^{k/2}R_{k\theta}x_0$. If $a^2+b^2=1$, then $(R_{k\theta}x_0)_k$ has a limit, a contradiction. If $a^2+b^2>1$, then $R_{k\theta}x_0$ tends to $0$, a contradiction.