# Linear map with spectrum radius $<1$ is contraction in some norm if the basis is well-chosen

Given a norm $$x\mapsto \lVert x \rVert$$ on $$\mathbb{R}^n$$, a linear map $$f$$ is contracting if $$\exists \varepsilon >0$$ such that $$\forall x \in \mathbb{R}^n,\lVert f(x) \rVert \leq (1-\varepsilon)\lVert x \rVert$$. Assume that the norm is either the sup norm $$\lVert x \rVert_{\infty}=\max\limits_{1\leq i \leq n}|x_i|$$ or the $$\ell^1$$norm $$\lVert x \rVert_{1}=|x_1|+...+|x_n|$$ or the Euclidean norm $$\lVert x \rVert_{2}=\sqrt{x_{1}^2+...+x_{n}^2}$$ and assume that $$Spec_{\mathbb{c}}(f)\subset B(0,1)$$.

Prove that after a suitable linear change of variable, $$f$$ can be assumed to be contracting for the chosen norm. Find an example where the change of variable is necessary.

In my opinion, the problem is to find a suitable basis, under which the matrix $$A$$ of $$f$$ can meet the requirement that the norm of $$A$$ $$<1$$. However, no mater in which case above, I have difficulty finding the suitable linear change of variable. I only figure out the case in which $$A$$ can be diagonalized. In this case I can use the Jordan normal form of $$f$$ to work out the Euclidean norm. But in other cases, I have difficulties.

The Jordan normal form of $$f$$ (extended to $$\Bbb C^n$$) has eigenvalues with $$|\lambda|<1$$ on the diagonal and some $$1$$'s next to the diagonal. By scaling basis vectors, we can turn those $$1$$'s into positive $$\varepsilon$$'s of our choice. We choose $$\epsilon<1-\max|\lambda|$$ and let $$q:=\max\{\max|\lambda|+\epsilon, \sqrt{\max|\lambda|^2+\epsilon^2},\max\{ \max|\lambda|,\epsilon\}\}<1$$. So now we have a complex basis $$v_1,\ldots,v_n$$ where $$f(v_k)=\lambda v_k$$ or $$f(v_k)=\lambda v_k+\epsilon v_{k-1}$$. With respect to this basis, $$\|f(v_k)\|_1\le |\lambda|+\epsilon<1,\quad \|f(v_k)\|_2\le \sqrt{|\lambda|^2+\epsilon^2}<1,\quad\|f(v_k)\|_\infty\le \max\{|\lambda|,\epsilon\}<1,$$ i.e., $$\|f(v_k)\|\le q\|v_k\|.$$ Now transfer this to general $$v=\sum c_kv_k$$, and finally use that we may assume wlog that if $$v_k$$ is in the base, then so is $$\overline{v_k}$$. Take the $$v_k+\overline{v_k}$$ and (for $$\lambda\notin \Bbb R$$) the $$i(v_k-\overline{v_k})$$ as a real basis and show that our inequaloty still holds.
• Excuse me, but how do you derive $\|f(v_k)\|_1\le |\lambda|+\epsilon$ from$f(v_k)=\lambda v_k+\epsilon v_{k-1}$?I can only see:$\|f(v_k)\|_1\le |\lambda| \|v_k\|_1+\epsilon\|v_{k-1}\|_1$ – Skyskie Jul 1 '19 at 4:09