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.