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

Question

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?

Answer 1

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.

Answer 2

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.)

Answer 3

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

Answer 4

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\to 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: $x_0, x_1, \dots$ by picking $x_0$ 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$$

Answer 5

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.

Answer 6

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.

Answer 7

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

Answer 8

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.

Answer 9

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.