1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Show that T is a contraction on a metric space

  1. Apr 3, 2014 #1
    1. The problem statement, all variables and given/known data

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

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

    Assume that [itex](R^{n}, d_{∞})[/itex] is complete.

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

    [itex]∑_{j}|C_{ij}| < 1[/itex], for [itex]i=1,2,3,....,n[/itex]

    show that [itex]T: R^{n} → R^{n}[/itex] is a contraction on [itex](R^{n}, d_{∞})[/itex]

    2. Relevant equations

    [itex]∑_{j}|C_{ij}| < 1[/itex], for [itex]i=1,2,3,....,n[/itex]

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

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

    3. The attempt at a solution

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

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

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

    The best that I can get from this is that [itex]∑_{j} c_{ij}x{j}[/itex] 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. jcsd
  3. Apr 3, 2014 #2


    User Avatar
    Science Advisor

    You have already said that "Therefore the sum of every row of the matrix C is less than 1." So [itex]\sum_j c_{ij}< 1[/itex]. What does that tell you about [itex]\sum_j c_{ij}x_j[/itex]?
  4. Apr 4, 2014 #3
    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

    [itex]|∑_{j} c_{ij}x_{j} - c_{ij}y_{j}| ≤ ∑_{j} |c_{ij}x_{j} - c_{ij}y_{j}|[/itex]

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

    Then everything is straight forward from there.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted