# Equivalent Norms on $\mathbb{R}^d$ and a contraction

Suppose we have a norm $|| \cdot ||$ on $\mathbb{R}^d$ and a linear transformation $T$ which is a contraction in regards to $c \in [0,1)$.

How can I prove that $\exists k\in \mathbb{N}$ s.t $T^k$ is also a contraction in the euclidean norm $||\cdot||_2$?

I got, by the equivalence of the two norms and by $T$ being a contraction, to:

$||x-y||_2 > \frac{b}{ac} ||Tx-Ty||_2$ using $b||x-y||_2 \leq ||x-y|| \leq a||x-y||_2$. This yields $\frac{b}{ac} \leq 1$ and I thought I'd be able to iterate on $n\in \mathbb{N}$ to get $\frac{b}{ac} \alpha||T^nx-T^ny||_2$ while $\frac{b}{ac} \alpha > 1$ but no success with that attempt.

Any hints?

• Aren't you overlooking the power of $c$ that comes with considering $T^k$ in place of just the single application of $T$? – hardmath Dec 13 '16 at 0:34
• @hardmath do you mean to next arrive at $||T^k(x-y)|| < c^k||x-y||$, then get convergence of $||T^k(x-y)||_2$ to zero? – Mariah Dec 13 '16 at 0:47
• Right, since you are assuming linearity of $T$, there is no difference in $T^k(x-y)$ and $T^k x - T^k y$. Make $k$ large enough that $c^k$ overcomes the coefficients from the equivalence of norms. – hardmath Dec 13 '16 at 0:49
• @hardmath can you hint where the linearity of $T$ comes in? Is it in a use of $||T||_{op}$? – Mariah Dec 13 '16 at 1:24
• You mentioned in the Question that $T$ is assumed to be linear. For that reason the property of being contractive is simplified (in contrast to the definition for a nonlinear mapping). However it really doesn't make a critical difference in the conclusion. It implies $T^k(x-y) = T^k x - T^k y$, as I tried to say in the previous Comment. – hardmath Dec 13 '16 at 1:49

To emphasize that linearity of the map $T$ is not necessary, let's proceed with a careful development that avoids such an assumption. At the end we can point out the minor "simplification" in notation and definition that linearity allows.

Consider $T:V\to V$, where $V$ is a normed vector space with two equivalent norms, say $||\cdot||_1$ and $||\cdot||_2$ such that for some positive constants $a,b$:

$$a ||x||_1 \le ||x||_2 \le b ||x||_1 \text{ for all }x\in V$$

We say that $T$ is a contraction map on $V$ with respect to norm $||\cdot||_1$ iff there exists a constant $c\in [0,1)$ such that for all $x,y \in V$:

$$||T(x) - T(y)||_1 \le c ||x - y||_1$$

Our challenge is to show there exists a positive integer $k$ such that $T^k$ is also a contraction with respect to the second norm $||\cdot||_2$. To begin with one shows, by induction, that for all $x,y \in V$:

$$||T^k(x) - T^k(y)||_1 \le c^k ||x - y||_1$$

The basis step $k=1$ is already in hand (as above). The induction step does not require any linearity assumption, as the following shows:

\begin{align*} ||T^{k+1}(x) - T^{k+1}(y)||_1 &= ||T^k(T(x)) - T^k(T(y))||_1 \\ &\le c^k ||T(x) - T(y)||_1 \\ &\le c^{k+1} ||x - y||_1 \end{align*}

Here we have first rewritten the operator $T^{k+1}$ as a composition, then applied the induction hypothesis to the result, and finally used the base estimate to obtain an extra factor of $c$.

Now we have the following chain of inequalities:

\begin{align*} ||T^k(x) - T^k(y)||_2 &\le b ||T^k(x) - T^k(y)||_1 \\ &\le bc^k ||x - y||_1 \\ &\le \frac{bc^k}{a} ||x - y||_2 \end{align*}

The desired contractive property for $T^k$ will follow when $k$ is chosen large enough that, since $0 \le c \lt 1$, the factor $c^k$ is small enough that:

$$0 \le \frac{bc^k}{a} \lt 1$$

In other words pick $k$ such that $c^k \lt a/b$.

Based on some feedback I got in chat, Readers may have difficulty envisioning an actual example, so let's give one.

In a finite dimensional normed vector space, it turns out that all norms are equivalent. The converse is also true.

For simplicity we will consider the two-dimensional vector space $\mathbb{R}^2$, and the linear transformation $T$ of matrix multiplication by:

$$\begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}$$

Obviously $T^2 = 0$ is a contraction with respect to the Euclidean norm (or with respect to any norm), but since:

$$T\begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix}$$

$T$ itself is not a contraction in the Euclidean norm $||\cdot||_2$. However a custom norm can be created with respect to which $T$ is contraction, such as in particular:

$$|| (x,y)^T ||_1 = \sqrt{x^2 + (y^2)/2}$$

Thus $||T(x,y)^T||_1 = || (0,x)^T ||_1 = \sqrt{0.5 x^2} \lt 0.8 || (x,y)^T ||_1$, so in this custom norm $T$ is a contraction.