Theorem: Let $M$ be a square matrix. $M$ is convergent when its spectral radius $\rho(M)$ is less than 1.
Proof:
Suppose $\rho(M) < 1$. We know that there exists a matrix norm $ \lvert\lvert . \rvert\rvert_{\epsilon}$ such that $|\lvert M \rvert|_{\epsilon} < \rho(M) + \epsilon$.
Choose $\epsilon>0$ such that $|\lvert M|\rvert_{\epsilon}<1$. By the following calculation:
\begin{align*}
|\lvert \lim_{k \to \infty} M^k|\rvert_{\epsilon} &\leq \lim_{k \to \infty} |\lvert M^k |\rvert_{\epsilon} \tag{1}\\
&\leq \lim_{k \to \infty} |\lvert M|\rvert_{\epsilon}^k \tag{2}\\
&=0 \tag{3}(qed)
\end{align*}
I don't understand $(1), (2)$ and $(3)$. Questions:
-
In $(1)$, how do we know that $\lim_{k \to \infty} M^k$ exists?
-
Also in $(1)$, how is that inequality true?
-
In $(2)$, how is that inequality true?
-
Finally, in $(3)$, why can we conclude that $M^k \to 0$ when its norm goes to $0$?
Best Answer
As you suspect, in the context of this theorem $\lim_{k\to\infty} M^k$ is a priori not meaningful at the place it is used; indeed the claim we are trying to prove is that $\lim_{k\to\infty} M^k$ indeed does make sense (independently of the norm chosen), and it is equal to the square matrix all of whose entries are $0$.
On that note, as dan_fulea noted, what needs to be proven is just that $\lim_{k\to\infty} \Vert M^k\Vert=0$ w/r/t some (hence any) norm $\Vert\cdot\Vert$ on the space of $d\times d$ matrices $\mathcal{M}_d$. To use the fact that the spectral radius of $A$ is less than $1$ one chooses the norm to use as the $\epsilon$ norm (which depends on $M$ too, as it's cooked up using $M$'s Jordan normal form). Thus the inequality in (1) is not necessary; one could start writing the chain of inequalities from its RHS. That said, any norm, when considered as a function $\mathcal{M}_d\to\mathbb{R}_{\geq0}$, is (Lipschitz, hence uniformly) continuous w/r/t the topology it defines, so the given inequality is in fact an equality (when the limit exists of course; see 1.).
The $\epsilon$ norm is a matrix norm as dan_fulea states (though for that one needs to know the actual construction of it). The point is that when a norm on $\mathcal{M}_d$ is a matrix norm (as opposed to merely a so-called vector norm) $\Vert AB\Vert \leq \Vert A \Vert\; \Vert B\Vert$, so that matrix multiplication becomes continuous when considered as a map $\mathcal{M}_d\times \mathcal{M}_d\to \mathcal{M}_d$. For a general vector norm on $\mathcal{M}_d$ addition and scalar multiplication are continuous but not necessarily matrix multiplication.
As a vector space $\mathcal{M}_d$ is finite dimensional, hence any norm on it (vector - or matrix - ) is comparable to any other norm; in particular to the so-called maximum norm $\Vert A\Vert_\max=\max_{i,j} |A_{i,j}|$. Thus all entries of $M^k$ shrink to $0$ as $k$ goes to $\infty$ (as your argument shows). This precisely means $M^k\to0$ as $k\to\infty$. Observe that this step too is redundant: by finite dimensionality convergence w/r/t one norm is the same think as convergence w/r/t any norm.