# A function that is not contractive with respect to any metric

I am struggling with this homework question with is related to iterated function system and fixed point theory. The question is:

Let $\Delta \in R^2$ be a filled non-degenerate triangle with vertices $A,B,C\in R^2$. Let D be the midpoint of the side $BC$. Now define two affine transformations by $f_1(ABC)=ABD$ and $f_2(ABC)=CAD$. (We write $f(PQR)=STU$ to mean f$(P)=S,f(Q)=T,f(R)=U$). Let $\mathcal{F}$ be the iterated function system $\{\Delta;f_1,f_2\}$. Now we need to show

(1)$f_2$ is not contractive w.r.t any metric (that induces on $\Delta$ the usual topology)

(2) Prove or provide thoughts that $\mathcal{F}$ possese a unique attractor.

(3) explain how is this consistent with the fact that if $\mathcal{F}$ is an affine iterated function system on $R^M$ that possesses a unique attractor, then there is a metric w.r.t which is contractive.

For (1) , I've tried to show there is no fixed point of $f_2$. However, the picture is like shrinking the original toward somewhere along the line segment from C to the midpoint of AD and I can't see why there is no fixed point.

I don't know how to do (2) and (3) either .But for (3), I am suspecting that we have to invent a metric which makes $f_1\cup f_2$ being contractive with respect to this metric. Any ideas? Thanks for help.

-
Do the two maps take corresponding vertices to each other as written? e.g. is it $f_2(A)=C,f_2(B)=A$ etc. for both maps (so that $f_1$ fixes both of $A,B$). –  coffeemath Aug 13 '13 at 6:01
@coffeemath $f_1$ is fixed by two points. However, the question is to look at $f_2$. Moreover, I couldn't find the attractor of the system. –  tagb78 Aug 13 '13 at 6:17
On Wiki, an IFS is required to have its mappings all contractions, but in your system $f_1$ fixes two points $A,B$ and so is not a contraction. In fact $f_1$ is not a contraction in any metric because of its two fixed points. –  coffeemath Aug 13 '13 at 22:36
@coffeemath Thanks , I guess there's typo . However, if this is the case, how can we answer (2) and (3) –  tagb78 Aug 13 '13 at 22:43
It would be good if you looked again at the source of the problem, and make sure about which points are taken to which under $f_1,f_2$. I'd also suggest a look at the phrase (that induces on $\Delta$ the usual topology); is that to mean for example a homeomorphism, which is fairly wide, or a diffeomorphism, which would have to preserve vertices? –  coffeemath Aug 13 '13 at 23:22

The map $f_2$ does have a (unique) fixed point. To describe it, use barycentric coordinates based on the triangle $ABC$ taking the coordinates as $A=(1,0,0),B=(0,1,0),C=(0,0,1)$. Then every point in the plane has a unique expression as $xA+yB+zC$ where $x+y+z=1.$ (negative values are OK, they go with points outside the reference triangle $ABC.$)

The coordinates of $D$ are then $(0,\frac12,\frac12)$ since it is the midpoint of $BC$. Now since $f_2$ maps $A \to C, \ C \to B, \ B \to D$ we can represent $f_2$ as a matrix $M$ which multiplies a column vector $(x,y,z)^t$ on the left to produce the image of the point $(x,y,z)$ under $f_2.$ This matrix is $$M= \begin{matrix} 0 & 1 & 0 \\ 0 & 0 & \frac12 \\ 1 & 0 & \frac12 \end{matrix}.$$

Using this to set up for a fixed point (seting $Mv=v$ and solving) gives the unique fixed point to be at barycentric coordinates $(\frac14,\frac14,\frac12)$. Concretely this means the point $\frac14A +\frac14B +\frac12C$ is the (unique) fixed point of $f_2.$

Sidenote: This fixed point has a geometric interpretation. It may be viewed as the midpoint of the median from $C$ to side $AB$ of the triangle $ABC$. That is, bisect $BC$ at the point $X$, and then the fixed point of $f_2$ will be the midpoint of the "median" which is the segment $AX$.

-
Aww, you beat me to it. :) Not only is there a fixed point, the other two eigenvalues are complex with absolute values $<1$, so no iterate of $f_2$ has any additional fixed points. It's possibly relevant that $M$ has a singular value greater than $1$, namely $\frac12\sqrt{3+\sqrt5}\approx1.14$. So it involves some stretching, at least in these coordinates! But is this enough to conclude that $f_2$ isn't a contraction map in any metric...? –  Chris Culter Aug 13 '13 at 6:59

I confess I haven't even really looked at your particular function. But I think that in principle the answer is given by the following result.

Theorem (Bessaga): Let $X$ be a nonempty set and $f: X \rightarrow X$ a map. Denote by $f^n$ the $n$-fold composition $f \circ \ldots \circ f$. Then the following are equivalent:
(i) For every positive integer $n$, $f^n$ has at most one fixed point.
(ii) $X$ admits a metric $d$ with respect to which $f$ is a contraction: there is some $\alpha \in (0,1)$ such that for all $x,x' \in X$, $d(f(x),f(x')) \leq \alpha d(x,x')$.

See e.g. here for a proof. (I learned this result from a wonderful colloquium talk given by Keith Conrad. He has a closely related expository note.)

Anyway, the point of the above theorem is that in order to show that $f$ is not a contraction with respect to any metric (i.e., a not necessarily complete metric), you don't want to show that there are no fixed points. On the contrary, you want to find some iterate which has at least two fixed points. Maybe in your case you'll get lucky and some iterate is easier to understand?

Added: I just noticed that you are restricting to metrics which induce the standard topology on $\Delta$. Since $\Delta$ is compact in the standard topology, this forces completeness. Still you might try looking at iterates to see if that makes things easier...

On the other hand, your third question really does look to be a special case of Bessaga's Theorem (along with the observation that the fixed point being attractive forces all the iterates to have the same unique fixed point).

-
Thanks for your answere. However, I couldn't find more than one fixed points (in fact, not even for one ). –  tagb78 Aug 13 '13 at 6:25
For (2), it's also hard to figure out the attractor of the whole system –  tagb78 Aug 13 '13 at 6:26