Show that T is a contraction on a metric space

[phosgene]

Homework Statement

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_{∞})$

Homework 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$

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.

 

[HallsofIvy]

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$?

 

[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.