Brouwer’s Fixed Point Theorem: Many in One Post

In this post I will
(1) give a simple proof of Brouwer Fixed Point Theorem
(2) fulfill the promise given here
(3) present the Wednesday Problem in the form fill in the details in the below text

Theorem (Brouwer’s Fixed Point Theorem, BFPT). Suppose that [tex]B\subset \mathbb{R}^n[/tex] is the closed n-dimensional unit ball and [tex]f\colon B\to B[/tex] is a continuous function. Then there exists a point [tex]x\in B[/tex] such that [tex]f(x)=x[/tex].

There are funny interpretations of this theorem.

The traditional proof of this theorem is rather difficult and despite I have attended courses on algebraic topology, I have never really understood it in depth. Sometimes this result is even quoted as intuitive but hard to prove and is celebrated as a triumph of algebraic topology. The hardest part of the proof is to show that [tex]\pi_n(S^n)\ne \{0\},[/tex] let alone defining homotopy groups which takes about a month in a regular homotopy theory course held in our department; and I am not even mentioning the amount of necessary group theoretical and topologican prerequisites.

Spending some time on the internet though, one is able to find simpler proofs. From now on also in this blog. The easy proof I will present here uses the Handshaking Lemma that has been as a Wednesday Problem in this blog. In addition to that, it uses the fact that any sequence in a closed unit ball has a convergent subsequence. These are fairly meagerer prerequisites than those mentioned above.

Since BFPT implies [tex]\pi_n(S^n)\ne \{0\},[/tex] this is also a way to prove that.

We will prove BFPT for a simplex instead of a ball. A simplex is a triangle in two dimensions, a tetrahedron in three and so on. Formally an n-simplex is the set

[tex]\{(x_0,\dots,x_n)\in \mathbb{R}^{n+1}\mid x_0+\cdots+x_n=1\text{ and }0\le x_i\le 1\text{ for all }i\}[/tex]

The co-ordinate vectors of [tex]\mathbb{R}^{n+1}[/tex] are the corners of the n-simplex. For a fixed k the sets

[tex]\{(x_0,\dots,x_n)\in \mathbb{R}^{n+1}\mid x_0+\cdots+x_n=1\text{, }\forall i\,0\le x_i\le 1\text{, } x_k=0\}[/tex]

are called (n-1)-faces of the n-simplex. A triangulation of a simplex is something that looks like this:

Thus we fill the simplex with small simplices such that their pairwise intersection can only be a common face. The balls on the picture, i.e. the corners of the small simplices will be called vertices here.

Sperner’s coloring.
Suppose we have a triangulation of an n-simplex with vertices colored with n+1 different colors such that
(i) the corners (of the big triangle) have different colors
(ii) the vertices that lie on an (n-1)-face of the big simplex are colored only with the colors that correspond to the corners of that particular face.
Then this is called a Sperner’s coloring of the triangulation. Note that if a simplex is triangulated, it induces a triangulation of its faces and a Sperner’s coloring of the triangulation induces a Sperner’s coloring to the induced triangulations of the faces.

Sperner’s Lemma.
For any Sperner’s coloring of a trianglulation of a simplex, there exists an element of the triangulation (a small simplex) whose corners have all distinct colors.

Example:

The pictured coloring satisfies the Sperner’s requirements: the 1-faces (the sides of the big triangle) are colored only in colors that correspond to their corners and each corner has its own color. The reader may verify that there indeed is a fullcolored small triangle (a triangle whose corners have all different colors).

Proof of Sperner’s Lemma
Suppose we have a triangulated 2-simlex and a Sperner’s coloring with three colors red, green and blue. Let us consider the set A of all small simplices of the triangulation and let [tex]G=A\cup \{u\}[/tex], where u corresponds to the area outside the triangle. Let us endow G with a graph structure: put an edge between two elements a and b of G iff the intersection [tex]a\cap b[/tex] is a line segment whose end points are colored in red and green. For the n-dimensional version we require that the intersection of a and b is an (n-1)-face whose corners are colored in all but one color agreed in advance (say all but red). The reader verifies easily in the 2-dimensional case that the degree of u in this graph is odd. By the Handshaking Lemma there must be another vertice with an odd degree. But all other vertices are the small simplices of the triangulation and a simplex can have an odd degree only if it is fully colored, i.e. has the corners colored in all colors! The details I leave to the reader.

For the n-dimensional case use the same argument. The degree of u is odd in this case by the induction hypothesis, because the (n-1)-face of a Sperner-colored n-simplex is itself Sperner colored. [tex]\square[/tex]

Proof of Brouwer Fixed Point Theorem
To respect the Handshaking lemma, the proof will be handwaving. Let f be a continuous function from an n-simplex to itself. Let us first color all points of the simplex: the corners will simply have colours [tex]c_0,\dots,c_n[/tex]. Take a point x in the simplex and see where f maps it. Consider the vector v=f(x)-x. We may think that v starts at x and ends at f(x). It may point towards some of the corners of the simplex or away from some. We color x with [tex]c_k[/tex] if v points away from the k:th corner more than from any other. If there are two or more corners such that v points equally away from them, then just choose one of the corresponding colors. Away means here not towards (the difference maybe 0).

By Sperner’s lemma, for each n find a simplex of diameter 1/n whose all corners are colored in different colors. This requires taking a triangulation for each n such that all simplices of the triangulation have diemeters <1/n. The coloring is defined such that it leads always to a Sperner coloring (check!). Thus it defines a sequence of points of color [tex]c_0[/tex] (each small triangle has a corner of this color). Our main simplex is compact, so we find a convergent subsequence. Taking the corresponding small simplices we get convergent sequences of all colors converging to the same point! By continuity of f, it follows that the limit of these sequences must be taken by f away from every corner. Which is possible only if it is a fixed point! [tex]\square[/tex]