# Help me with this proof: Drop a printed map of the land on the land and there must be some common point.

Hi, I have a minor in math and this is not a homework problem - my prof mentioned it 5 years ago and I could not even begin to tackle it until I took a good intro to linear algebra (after work). Please try to adjust the answer to my level.

A map is a smaller version of the land: rotated and scaled down. The prerequisite is that the map (say of USA) lands entirely inside the land (and not partly in Canada or in the ocean). Another prerequisite might be that the map has no holes (is that really necessary?) and perhaps that it must be a convex region (however I doubt that this is needed.) Please help me eliminate these doubts and prove that $p \in M, p \in L$. Correct my notation if needed by editing this post.

Here is the notation that I came up with (let's see if LaTex likes me):

• $L$ = land (region in $R^2$)
• $M$ = map (region in $R^2$)
• $T$ = transformation in $R^2$ (scalar times a rotation matrix)
• $\vec{s}$ = shift vector (since the overall transformation is generally non-linear)
• $\vec{p}$ = "pivot" - the point that does not change.

Now, I can solve for p uniquely by picking a non-trivial triangle on the land denoted by vectors $\vec{l_1}, \vec{l_2}, \vec{l_3}$, locating the corresponding vectors $\vec{m_1}, \vec{m_2}, \vec{m_3}$ on the map and writing out:

$\vec{m_1} = T \vec{l_1} + \vec{s}$, $\vec{m_2} = T \vec{l_2} + \vec{s}$, $\vec{m_3} = T \vec{l_3} + \vec{s}$

I solve for T: $T = [ m_1 - m_2 \; \; \; m_1 - m_3 ] [ l_1 - l_2 \;\;\; l_1 - l_3 ]^{-1}$ Because we picked a non-trivial triangle, it's area will be non-zero and the matrix on the right will be invertible. So, we can always solve for T. We can also solve for s: $\vec{s} = \vec{m_1} - T \vec{l_1}$, and finally for the pivot p: $\vec{p} = (I - T)^{-1} \vec{s}$. Since T = c * rotation matrix, where $c \leq 1$, the only time when (I - T) does not have an inverse is when I = T (details omitted).

So, it seems that I can solve for a unique p.

• Now, how do I prove that pivot $\vec{p}$ will be inside both shapes/regions L and M?
• Finally, what assumptions must I make about convexity of M, absence of holes, etc ?

P.S. Which undergraduate classes might have this as a homework problem?

-
You could read about the Brouwer fixed point theorem (en.wikipedia.org/wiki/Brouwer_fixed_point_theorem), the Banach fixed point theorem (en.wikipedia.org/wiki/Banach_fixed_point_theorem) or the Schauder fixed point theorem (en.wikipedia.org/wiki/Schauder_fixed_point_theorem)... –  Mariano Suárez-Alvarez Dec 26 '09 at 19:03
As Mariano points out, there are at least three famous theorems that will do it for you. –  Theo Johnson-Freyd Dec 26 '09 at 19:46
I would have expected someone to come up with a specific construction for the fixed point using geometry---I imagine the fixed point of an affine map from a rectangle into itself must be very constructible! –  Mariano Suárez-Alvarez Dec 27 '09 at 23:51
Comment: this question currently has 0 upvotes and 11 answers. So...nobody especially likes the question, but lots of people want to answer it?? –  Pete L. Clark Aug 12 '10 at 9:34

This is usually quoted as an "application" of Brouwer's fixed point theorem: http://en.wikipedia.org/wiki/Brouwer%27s_fixed_point_theorem

which says that a continuous map from a closed ball (in any number of dimensions) to itself must have a fixed point.

You definitely need it to not have holes, because otherwise you could just rotate around the center of the hole and no fixed points will exist. However, convexity is not relevant. The main point is that the United States (minus Alaska and Hawaii and whatever holes it might have) is homeomorphic to the closed disk, so we can apply the homeomorphism, find the fixed point for the closed disk, and then reverse the homeomorphism (apply its inverse) to get the fixed point of the original function (which is your laying of the land on itself).

I'm not really sure how to finish your proof, but I would think this would appear in an algebraic topology course.

-
By using Brouwer's fixed point theorem you can get rid of the linear (scaling, translation, rotation) aspect of the problem. Just wad up the whole map into a lump and toss it over your shoulder; there will still be a point on the map sitting over "itself". –  Matt Noonan Dec 26 '09 at 21:46

The simplest case - where you only need the Banach fixed point theorem - is quite beautiful if you think about it the right way: your map lands somewhere on the land it marks, so somewhere on the map must be an (extremely small) picture of the map. That picture of the map, in turn, has a picture of the map in it, and this sequence of pictures converges to the fixed point.

(This explanation is from Lawvere and Schanuel's Conceptual Mathematics, which has a great chapter on fixed point theorems where the topology is abstracted and only the categorical content is discussed.)

-
You see... maps aren't really that accurate as to have pictures of themselves. :) –  john mangual Dec 27 '09 at 5:03
In mathematics they are, that's the difference with physicists :) –  Ilya Nikokoshev Dec 28 '09 at 0:09
Wow, that is really beautiful. –  Dinakar Muthiah Dec 28 '09 at 8:35

This sounds to me like a variant of Banach's fixed point theorem. I'm just a first year undergrad, but that's what it sounds like to me.

http://en.wikipedia.org/wiki/Banach_fixed_point_theorem

-
I think the dude over me is more on the money. –  Eivind Dahl Dec 26 '09 at 18:55
Your are answer is absolutely appropriate. The proof of Banach's fixed point theorem even tells you how to find the point. As a first approximation it must be on that part of the map which depicts the region where the map is placed. But this part is essentially a smaller map, so repeat the argument... –  Carsten Schultz Dec 26 '09 at 20:38
I've never thought about this as an application of Banach fixed point theorem, but it's absolutely correct. In this scenario we aren't stretching the map out, so the distances must be getting smaller. We would only need Brouwer's fixed point theorem if some parts of the map are allowed to be blown up. –  Steven Sam Dec 26 '09 at 21:11
Nice to know that my first post on math overflow wasn't completely off mark ... ^^ –  Eivind Dahl Dec 26 '09 at 21:23

The Brouwer Fixed Point Theorem is a bit of overkill in this circumstance.

There's a general theorem for complete metric spaces. If X is a metric space, f: X->X, and there is a p<1 such that:

d(f(x),f(y)) < p * d(x,y)


Then f has a fixed point. You can find this fixed point by defining a sequence:

x0, x1, ...


by picking x0 at random and defining x(n+1) = f(x(n))

Then you can show this sequence is Cauchy, and hence that it must be have a limit, x. But since f is continuous, you have:

f(x) = f(lim x(n)) = lim f(x(n)) = lim x(n+1) = x

-

There is a proof of the Brower Fixed point theorem using Sperner's Lemma. Starting with triangle ABC, you color A red, B blue and C green. Then you triangulate ABC such that

• any point on AB is either red or blue
• any point on BC is either blue or green
• any point on AC is either red or green

Point in the interior can be any color. Sperner's lemma states there must be a small triangle with all three colors.

The 3-colored triangle ensured by Sperner's lemma can itself be triangulated. This process leads to a fixed point. See page 5 of this article by Alex Wright.

-

I wanted to emphasize that you really need the region to include its boundary! The mapping $h(z) = z+ 1$ has no (finite) fixed point in the upper half plane $z = x + i y, \; \; y > 0.$ Take a linear fractional transformation to the open unit disc, $\Phi(z) = \frac{i z + 1}{z + i},$ with inverse mapping $\Phi^{-1}(v) = \frac{i v - 1}{-v + i}.$ Then we have a mapping from the open unit disc to itself, $\Phi^{-1} \circ h \circ \Phi .$ Just as $h$ has only a fixed point at $\infty,$ the only fixed point of this map will need to be at the image of $\infty$ in the boundary of the disc, that being $i.$ That is, no interior fixed point.

Another aspect is applications. Given a three by three matrix $A$ with positive real entries, we will show that there is at least one real positive eigenvalue. Let $\vec{w}$ be a column vector with entries $x,y,z.$ Consider $\vec{w}$ in the "positive octant" of the unit sphere, so $x^2 + y^2 + z^2 = 1$ and $x \geq 0, y \geq 0, z \geq 0.$ We define a mapping $g$ that takes the positive octant to itself, $g(\vec{w}) = ( A \vec{w} ) / | A \vec{w} |.$ The important point here is that $g$ is continuous, although it might not be continuous over the entire sphere as there could be some $\vec{u}$ with $A \vec{u} = \vec{0}$ and $g(\vec{u})$ undefined.

Finally, the positive octant is homeomorphic to the closed unit disc and to your Land.'' The Brouwer fixed point theorem applies, so there is some $\vec{w}$ in the positive octant such that $g(\vec{w}) = \vec{w},$ that is $| A \vec{w} |$ is a real positive eigenvalue because $A \vec{w} = | A \vec{w} | \cdot \vec{w}.$ I am pretty sure that I was taught this by Joel Spencer, an undergraduate course in topology.

-

This is a special case of Brouwer's fixed point theorem.

-

they sort of did this in that game Diablo, where your character occupies a position on both the floating minimap and the main screen

-

I want to comment on your last question: the classes.

The theorems mentioned rightly belong to the area of algebraic topology (the deep ideas behind them are of topological nature and are usually expressed and proven in an algebraic way), but may also appear in the undergraduate course in a seminar on geometry, in a course on complex variables or some type of analysis, especially functional analysis (a big subject which sounded dull to me until I learned about the abovementioned examples). This largely depends on the professor's preferences.

One could also note that you asked a simpler question, just about affine maps. Those will be studied in geometry and that could come with different adjectives, e.g. affine geometry.

The courses on algebraic topology can be taught on different levels, the standard way is to start quite technical. I think you might benefit from building more motivation up front. There are other nice topology facts explained in books or you could ask a question here.

-
But the Banach theorem will most probably show up in a class on Analysis (to prove existence of solutions of something, for example) and Schauder's in a class about function analysis. –  Mariano Suárez-Alvarez Dec 27 '09 at 23:48
Yes indeed, I stand expanded! –  Ilya Nikokoshev Dec 28 '09 at 0:05

While it does not do any harm to point to Brouwer's or Banach's theorem here one should note that in the problem at hand the existence of the fixed point $p$ has been established by elementary means, so we only have to prove $p\in L$. For this to hold it suffices that the "country" $L$ is closed: Choose any point $x_0\in L$. Then the sequence of iterates $x_n:=T^n(x_0)$ $(n\ge 0)$ is on the one hand contained in $L$ and on the other hand converges to $p$, as the distances $d(x_n,p)$ decrease to 0 exponentially.

-