Brouwer's Fix Point Theorem

Theorem 1   Every continuous mapping f of a closed n-ball to itself has a fixed point. Alternatively, Let $A \subset R^n$ be a non empty compact convex set and $f: A \rightarrow A$ a continuous function. Then f has a fix point, i.e. f(x)=x for some $x \in A$.

Let us define the terms which are used in the theorem:

A set $A \subset R^n$ is compact if it is bounded and closed relative to Rⁿ. A set A is bounded if there is some $x \in R$, such that ||a|| < x for all $a \in A$. Moreover, if f is a continuous function, then it maps compact sets to compact sets.

Let the sequence x^m converge to x in Rⁿ. Point x is the limit point of the sequence. Let $X \subset R$ be the domain of the function f. The function f is said to be continuous if for all $x \in R$, and every convergent sequence x^m to x, f(x^m) converges to f(x). A set is open, if for every point in the set, we can find a small neighborhood, such that all points in the neighborhood are within the set. A set is closed, if its complement is open.

Lets first look at the Brouwer's theorem in one dimension. Let f be a continuous function in the interval $f:[0,1] \rightarrow [0,1]$. We want to show that there exists $x\in [0,1]$ such that f(x)=x (see Figure 2. Assume that f(0) and f(1) are not equal to 0 and 1, respectively, otherwise we already have a fix-point. Plot this function on the x-y plane, restricted to the interval [0,1]x[0,1]. Consider the plot of this function and the line x=y. Clearly these two intersects in at least one point, since f starts above this line at x=0, and terminates below this line at x=1, and is continuous. All intersection points are fix points!

  

Figure 2: Illustration of Brouwer's Theorem in 1-dimension

Proof in two and higher dimensions uses Sperner's Lemma. (This proof is based on the survey paper of P.J.S.G. Ferreira on Fixed point problems - an introduction).

We want to show that a continuous mapping from a closed triangle T (or circle) to a closed triangle has a fixed point. Since T is convex, any point in T can be expressed using the barycentric coordinates (a₀, a₁, a₂), such that $a_i's \ge 0$ and a₀+a₁+a₂=1. The function f maps points in T to points in T, i.e., f(a₀,a₁,a₂)=(b₀,b₁,b₂) where all points are represented using the barycentric coordinates.

(What are Barycentric coordinates? For any point x inside a triangle ABC, there exists three weights w_A, w_B, and w_C such that, if placed at the corresponding vertices of the triangle, their center of gravity (barycenter) will coincide with the point x. August Ferdinand Moebius (1790-1868) defined the weights w_A, w_B, and w_C as the barycentric coordinates of x, provided w_A+w_B+w_C =1. )

Define three sets S_i of points, where i=0,1,2, such that $x=(a_0, a_1, a_2) \in S_i$ if $a_i \le b_i$. Observe that the vertex $(1,0,0) \in S_0, (0,1,0) \in S_1,$ and $(0,0,1) \in S_2$. We will show that the points belonging to the intersection of these three sets are fixed points! Suppose the intersection is non-empty and let x=(a₀, a₁, a₂) be such a point, with its image f(x)=(b₀,b₁,b₂). By definition $b_i \le a_i,$ for i=0,1,2. But a₀+a₁+a₂=1=b₀+b₁+b₂, hence x=f(x). Next we show that the intersection of these sets is non-empty! That's where the Sperner's lemma will be used.

First of all vertices of the triangle can be labeled by 0, 1 and 2, respectively because of the following. Let (1,0,0) be a vertex and let f(1,0,0)=(b₀,b₁,b₂). Clearly $b_0 \le 1$, and hence this vertex can be labeled by 0. Next consider a point x on one of the sides of T, say defined by vertices labeled 0 and 1. Barycentric coordinate of point x will be (a, 1-a, 0), where $0\le a \le 1$. Consider f(x)=y. Now y may be mapped to the same edge of the triangle or somewhere else. First consider the case that y is mapped to the same edge as x. Now barycentric coordinate of y=(b,1-b, 0) where $0\le b \le 1$. If $b\le a$, then label of point x will be 0 otherwise it will be 1. What about if point y is not on this edge? Then the third coordinate of y is non-zero, but the third coordinate of x is zero. This implies that x cannot be labeled 2. So the points along this edge of the triangle will be labeled 0 or 1, as required in Sperner's lemma.

Next we show that the sets S_i are closed. Consider a convergent sequence xⁿ of points in S_i and let x be the limit of the sequence. Why is $x \in S_i$? Let xⁿ=(a₀ⁿ, a₁ⁿ, a₂ⁿ) and the image yⁿ=f(xⁿ)=(b₀ⁿ, b₁ⁿ, b₂ⁿ). Moreover $b_i^n \le a_i^n$ by definition of S_i. Since f is a continuous function, so the coordinates a_i and b_i of the limit point a and f(x) will satisfy the similar condition and hence $x \in S_i$.

By Sperner's Lemma, if we consider a subdivision of T, then there is a baby triangle with vertices 0,1, and 2, and this baby triangle can be very very small! This implies that the points of the sets S₀, S₁ and S₂ become arbitrary close in this baby triangle of very very small diameter. But sets S_i are closed and non-empty - this implies they should eventually intersect!