# Homework Help: Show that the linear transformation matrix is a contraction mapping

1. Apr 21, 2013

### unawareness

1. The problem statement, all variables and given/known data
Show that the following linear transformation matrix is a contraction mapping.
\begin{bmatrix}
0.5 & 0 & -1 \\
0 & 0.5 & 1 \\
0 & 0 & 1
\end{bmatrix}
I don't know how to make that into a matrix, but it is a 3x3 matrix. The first row is [.5 0 -1] the second row is [0 .5 1] and the third row is [0 0 1].

Mod note: I formatted the matrix for you. If you quote this message, you can see how it's done.

2. Relevant equations
Well, I read some definitions. A function f is a contraction mapping if given a metric space (S,d) and a real constant 1 > c ≥ 0, then c $\times$ d(x,y) ≥ d(f(x),f(y)) $\forall$ x,y $\in$ S.

and

A metric space is an ordered pair (S,d) where S is a set and d is a metric (a notion of distance) on S.
d: S$\times$S $\mapsto$ R
such that for any x,y,z $\in$ S the following holds:
1. d(x,y) ≥ 0
2. d(x,y) = 0 $\Leftrightarrow$ x = y
3. d(x,y) = d(x,y)
4. d(x,y) ≤ d(x,y) + d(y,z)

3. The attempt at a solution
Okay. I am almost certain it is a contraction mapping. The .5 makes me think that if an object is transformed with this matrix, it will shrink by a scale of 1/2 every time. I drew a little picture of an iterated mapping with a starting point (0,0) and saw that the composition of mappings converged to the point (-2,2). Each iteration got 1 + 1/2 the distance from the previous iteration to the point (-2,2). I don't know if that even means anything, though. I think that the third column of the matrix also implies a translation. I don't know how this plays into the contraction, though. I'm just lost in definitions. I might have "shown" it with my example, but I don't really know if I've shown anything because I'm clueless in general.

Also, in the definition of contraction mapping, I don't know what the "c" constant is. Like... in my specific problem would c = 1/2? If it is, why? I don't know how I could arbitrarily pull out the 1/2 in the matrix. Like... could it be a scalar 1/2 on a matrix with entries [1 0 -2] and so on for the other rows?

If c is 1/2, though, I could just pick two random points say x = 2 and y = 5 then use 1/2 for c and plug them all into the definition, and if it is satisfied, then the transformation would indeed be a contraction? The result does satisfy the definition as 1/2 $\times$ d(2,5) ≥ d(f(2),f(5)) = $\sqrt{29}$ / 2 ≥ $\sqrt{29}$ / 2, but I don't know if that process is correct in any way.

Last edited by a moderator: Apr 21, 2013
2. Apr 21, 2013

### unawareness

I've been playing with it some more. Any arbitrary vector seems to converge to the point (-2,2,1) when iterated under the transformation.

And on the last part where I chose x = 2 and y = 5, I mean x is the vector (2,0,0) and y is the vector (0,5,0). I'm not sure if I'm allowed to choose these two points or vectors or whatever they are. So I separately multiplied T$\times$(2,0,0) and T$\times$(0,5,0) and took the distance between the new values, which turned out to be equal to 1/2 the distance between x and y. Which satisfied the definition. I still don't know if this is correct or not, I was just clarifying how I calculated everything. That actually doesn't make any sense, when I look at it, because basically I didn't do anything at all. I just did the same thing two different ways.

3. Apr 21, 2013

### vela

Staff Emeritus
According to the definition you gave for a contraction mapping, the linear transformation isn't such a mapping. If
$$A = \begin{bmatrix} 0.5 & 0 & -1 \\ 0 & 0.5 & 1 \\ 0 & 0 & 1 \end{bmatrix} \\ x = \begin{bmatrix} -2 \\ 2 \\ 1 \end{bmatrix} \\ y = \begin{bmatrix} -4 \\ 4 \\ 2 \end{bmatrix},$$ then d(x,y) = d(Ax, Ay), so there's no constant $c<1$ that can satisfy the definition for all x and y in S. I'm assuming S is ℝ3 here. If it isn't, you should tell us how S is defined.

4. Apr 22, 2013

### unawareness

S isn't quite ℝ3. The uhh... 3rd dimension is always equal to one. It's like an x-y plane shifted up one unit along the 3rd dimension. I don't know what you call that.

But that method would work then? If I took two random points with the 3rd dimension equal to 1, then that would tell me if it's a contraction mapping or not?

5. Apr 22, 2013

### vela

Staff Emeritus
You need to show the relationship c[d(x,y)] ≥ d(Ax,Ay) holds for all x, y in S for some value of c between 0 and 1. You've only shown c=1/2 works for two particular choices for x and y.

Are you familiar with diagonalizing a matrix?

6. Apr 22, 2013

### unawareness

I've seen and done it, but I can't recall the method. I'm looking it up, but it's only vaguely familiar still.

If A is a 3x3 matrix with 3 different eigenvalues, then it is diagonalizable? And to diagonalize it... you take 3 eigen vectors and combine them into a matrix P. Then P-1AP = diagonalized A?

I think I remember how to find eigen values, but I don't recall how to get eigen vectors. Actually, I don't remember eigen values. I know it's det(A-λI). I just don't remember what the eigen values actually are when you do that.

I worked out the characteristic equation and got λ32+(λ/4).

Is this correct so far?

7. Apr 22, 2013

### unawareness

Then set it equal to zero to get λ=0 and λ=1/2 but there's two 1/2's, so it's still a valid diagonalizable matrix?

Also, the theories behind diagonalizing a matrix are completely unknown to me. I don't know what it means and I don't know why doing it is supposed to be a good thing.

Last edited: Apr 22, 2013
8. Apr 22, 2013

### unawareness

Yeah, I have no clue where this diagonal matrix stuff is going. I'm probably doing everything wrong. I wound up with

$$P = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}$$

I think P is singular, so I won't be able to find a P-1.

9. Apr 22, 2013

### vela

Staff Emeritus
I'm trying to figure out your background. It turns out you can express any element $\vec{x} \in S$ in the form
$$\vec{x} = \begin{bmatrix} -2 \\ 2 \\ 1 \end{bmatrix} + a\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} + b\begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}.$$ Those three vectors happen to be the eigenvectors of the matrix. So you can think of elements of S as being centered around the point (-2, 2, 1) and offset by $a$ in the x-direction and $b$ in the y-direction.

If you multiply $\vec{x}$ by the matrix, having it act on each term separately, you should be able to see the why behind what you found through experimentation earlier. Also, it might give you ideas of how to formulate a proof that the transformation is a contraction mapping.