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?

  • $\begingroup$ Aren't you overlooking the power of $c$ that comes with considering $T^k$ in place of just the single application of $T$? $\endgroup$ – hardmath Dec 13 '16 at 0:34
  • $\begingroup$ @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? $\endgroup$ – Mariah Dec 13 '16 at 0:47
  • $\begingroup$ 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. $\endgroup$ – hardmath Dec 13 '16 at 0:49
  • $\begingroup$ @hardmath can you hint where the linearity of $T$ comes in? Is it in a use of $||T||_{op}$? $\endgroup$ – Mariah Dec 13 '16 at 1:24
  • $\begingroup$ 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. $\endgroup$ – 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.


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.