# Show that T is a contraction on a metric space

1. Apr 3, 2014

### phosgene

1. The problem statement, all variables and given/known data

Consider the metric space $(R^{n}, d_{∞})$, where if $\underline{x}=(x_{1}, x_{2}, x_{3},...,x_{n})$ and $\underline{y}=(y_{1}, y_{2}, y_{3},...,y_{n})$ we define

$d_{∞}(\underline{x},\underline{y}) = max_{i=1,2,3...,n} |x_{i} - y_{i}|$

Assume that $(R^{n}, d_{∞})$ is complete.

Let $T: R^{n} → R^{n}$ be the mapping given by $T\underline{x}=C\underline{x} + \underline{b}$. If C has the following property

$∑_{j}|C_{ij}| < 1$, for $i=1,2,3,....,n$

show that $T: R^{n} → R^{n}$ is a contraction on $(R^{n}, d_{∞})$

2. Relevant equations

$∑_{j}|C_{ij}| < 1$, for $i=1,2,3,....,n$

Therefore the sum of every row of the matrix C is less than 1.

T is a contraction on $(R^{n}, d_{∞})$ if
$d_{∞}(T(\underline{x}),T(\underline{y}) )≤ Kd_{∞}(\underline{x}, \underline{y}), 0≤K<1$

3. The attempt at a solution

For d(T(y), T(x)) I get

$max_{i=1,2,3,...,n} |C\underline{x} + \underline{b} - C\underline{y} - \underline{b}|$

$=max_{i=1,2,3,...,n} |∑_{j} c_{ij}x{j} - c_{ij}y_{j}|$

The best that I can get from this is that $∑_{j} c_{ij}x{j}$ is less than the maximum value of x. But I don't think that's particularly useful and I'm not sure what else to do.

2. Apr 3, 2014

### HallsofIvy

Staff Emeritus
You have already said that "Therefore the sum of every row of the matrix C is less than 1." So $\sum_j c_{ij}< 1$. What does that tell you about $\sum_j c_{ij}x_j$?

3. Apr 4, 2014

### phosgene

Thanks for the reply, but I have the solution now. The key step was (for anyone else who might be having trouble with a question similar to this) to recognize that

$|∑_{j} c_{ij}x_{j} - c_{ij}y_{j}| ≤ ∑_{j} |c_{ij}x_{j} - c_{ij}y_{j}|$

and then to note how $|x_{j} - y_{j}| ≤ max_{i=1,2,3,...,n} |x_{i} - y_{i}|$

Then everything is straight forward from there.