Brouwer’s Fixed Point Theorem

The Brouwer’s Fixed Point Theorem is a fundamental theorem in topology. In fact, when I took algebraic topology, it seemed like we proved it differently every few weeks. Indeed, the proofs using homotopy, homology, and degree theory are all elegant, but I will not present them in this post. Instead I will present a proof due to Emanuel Sperner that I find brilliant. The proof is based on Sperner’s Lemma, which I proved last time.

Let n\ge 1. For each 1\le k\le n+1, let e_k denote the k-th standard basis vector of \mathbb{R}^{n+1}. The standard n-simplex, denoted \Delta^{n}, is the set

\Delta^n=\{\sum_{i=1}^{n+1}t_ie_i: \sum_{i=1}^{n+1}t_{i}=1\text{ and }t_{i}\ge 0\text{ for all }i\}

You should verify that \Delta^0 is the point \{1\}, that \Delta^1 is the line segment from (0,1) to (1,0), that \Delta^2 is the standard triangle in \mathbb{R}^3, and so on.

Before we proceed, let’s fix some notation. Each point x in \Delta^n admits a unique expression in barycentric coordinates: x=\sum_{i=1}^{n+1}t_{i}e_{i} with each t_i\ge 0 and \sum_{i=1}^{n+1}t_i=1. So we’ll put x^i=t_i. So, for example, if x=(1/3,1/4,5/12), then x^1=1/3, x^2=1/4, and x^3=5/12. Admittedly, this is not my favorite notation, but it’ll do.

Theorem. (Brouwer’s Fixed Point Theorem for Simplexes) If f: \Delta^n\to \Delta^n is a continuous function, then there exists x\in \Delta^n for which f(x)=x.

Assume that f has no fixed points. Let {T}^k be a sequence of simplicial subdivisions of \Delta^n whose mesh tends to zero. Define a labeling \lambda on the vertices of T^k by

\lambda(v)=\min\{i: f(v)^i<v^i\}.

First, note that \lambda is a valid labeling since \sum_{i=1}^{n+1}v^i=1 and f has no fixed points (the coordinates have to change somewhere, and so any increase in a coordinate forces a decrease in another coordinate). Moreover, since barycentric coordinates are unique, the labeling is well-defined. I claim that \lambda is a Sperner labeling.

  1. First, notice that \lambda(e_i)=i (write it out).
  2. Secondly, if v is a vertex that lies on the facet spanned by \{e_k: 1\le k\le n+1, k\ne j\}, then the j-th coordinate of v is zero and so \lambda(v)\ne j.

Hence \lambda is a Sperner labeling.┬áBy Sperner’s Lemma, there exists a completely labeled subsimplex, call it \mathcal{T}^k and denote its n+1 vertices by v_1^k,\dots,v_{n+1}^k so that \lambda(v_i^k)=i. Since \Delta^n is compact, for each 1\le i\le n+1 the sequence \{v_k^i\}_{k=1}^{\infty} admits a convergence subsequence. However, so that we don’t have to bother with the notation, we we can either reindex or assume without loss of generality that each \{v_k^i\}_{k=1}^{\infty} converges. Since the mesh of T^k tends to zero, we see that the sequences all share a common limit point, call it x. But then by the continuity of f, since \lambda(v_k^i)=i for each 1\le i\le n+1, it follows that

f(x)^i=f(\lim_{k\to \infty}v_{k}^i)^i=\lim_{k\to \infty}f(v_k^i)^i\le \lim_{k\to \infty}(v_k^i)^i =(\lim_{k\to \infty}v_k^i)^i=x^i

Thus f(x)^i\le x^i for all 1\le i\le n+1. Since f(x) admits no fixed point, it must be the case that f(x)^i<x^i for some i. But then we see that

1=\sum_{i=1}^{n+1}f(x)^i<\sum_{i=1}^{n+1}x^i=1

a contradiction. So f admits a fixed point, as claimed.

The preceding proof should remind you of my proof of the intermediate value theorem. These two examples should better illustrate how one may exploit compactness to turn Sperner’s Lemma from a discrete tool to a continuous one. The familiar reader will have noticed that I haven’t really proven the Brouwer fixed point theorem, at least not directly. So let us recall that D^n is the n-dimensional unit disc. Proving the original Brouwer Fixed Point Theorem is just two hand waves away!

Theorem (Brouwer’s Fixed Point Theorem) If f:D^n\to D^n is a continuous function, then there exists x\in D^n for which f(x)=x.

It is clear that D^n is homeomorphic to \Delta^{n-1}, so let \phi: D^n\to \Delta^{n-1} be such a homeomorphism. Then \phi\circ f \circ \phi^{-1}: \Delta^{n-1}\to \Delta^{n-1} is continuous and so, by the previous theorem, there exists x\in \Delta^{n-1} for which \phi\circ f\circ \phi^{-1}(x)=x. But then f(\phi^{-1}(x))=\phi^{-1}(x). So f admits a fixed point, as desired.

I really like this proof of the Brouwer’s Fixed Point Theorem because it really doesn’t require as much as the other standard proofs. Now that I have given at least one precise proof, I won’t feel bad asserting an obscene amount of algebraic topology in my next few posts as I present some alternate proofs. Thanks for reading.

About these ads

2 thoughts on “Brouwer’s Fixed Point Theorem

  1. Pingback: A second proof of Brouwer’s Theorem. | Alexander Adam Azzam

  2. Pingback: Kakutani’s Fixed Point Theorem | Alexander Adam Azzam

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s