# Condition for linear equations to be a contraction

Let $C$ be a fixed $n\times n$ matrix of real numbers and $b \in \mathbb{R}^n$ a fixed vector. Define $T: \mathbb{R}^n \rightarrow \mathbb{R}^n$ by $y = Tx = Cx+b$. I need to show that, using the Euclidean metric $d(x,z) = \sqrt{\sum\limits_{j=1}^n (\xi_j - \zeta_j)^2}$, $T$ is a contraction mapping if $\sum\limits_{j=1}^n \sum\limits_{k=1}^n c_{jk}^2<1$.

I feel like this should be pretty simple, but I'm struggling with the double-summation. $$d(Tx,Tz) = \left[\sum\limits_{j=1}^n \left(\sum\limits_{k=1}^n c_{jk} (\xi_k-\zeta_k)\right)^2 \right]^{1/2},$$ but I can't get from here to there in a way that I'm happy with.

-

This should help:

$d(T(x),T(y))=||T(x)-T(y)||_{2}=||C(x-y)||_{2}\leq ||C||\cdot ||x-y||_{2}$

I will complete: Note that:

$\sum_{j} c_{ij}x_{j}\leq \sum_{j}|c_{ij}x_{j}|\leq \sqrt{\sum_{j}c_{ij}^2}\cdot\sqrt{\sum_{j}x_{j}^2}=\sqrt{\sum_{j}c_{ij}^2}$,

because I assume $||x||_{2}=1$ (second inequality uses Gauchy-Schwartz).

Then $\sqrt{\sum_{i}\left(\sum_{j}c_{ij}x_{j}\right)^2}\leq \sqrt{\sum_{i}\sum_{j}c_{ij}^2}<1$,

Thus $||C||<1$. Conculusion: you have to use somewhere Gauchy-Schwartz.

-

Hint: $T$ is a contraction iff $\langle C x, C x\rangle <1$ for all nonzero $x$. Note that $\langle C x, C x\rangle = x^T C^T C x$. What are the entries of $C^T C$? Does that help?

-