Brouwer's Fix Point Theorem

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

A set
is *compact* if it is bounded and closed
relative to *R*^{n}. A set *A* is *bounded* if there is some ,
such that ||*a*|| < *x* for all .
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*^{n}. Point *x* is the
limit point of the sequence. Let
be the domain of the
function *f*. The function *f* is said to be *continuous* if for
all ,
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
.
We
want to show that there exists
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!

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*_{0}, *a*_{1}, *a*_{2}), such that
and
*a*_{0}+*a*_{1}+*a*_{2}=1. The function *f* maps points in *T* to points in
*T*, i.e.,
*f*(*a*_{0},*a*_{1},*a*_{2})=(*b*_{0},*b*_{1},*b*_{2}) 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
if
.
Observe that the vertex
and
.
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*_{0}, *a*_{1},
*a*_{2}) be such a point, with its image
*f*(*x*)=(*b*_{0},*b*_{1},*b*_{2}). By
definition
for *i*=0,1,2. But
*a*_{0}+*a*_{1}+*a*_{2}=1=*b*_{0}+*b*_{1}+*b*_{2}, 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*_{0},*b*_{1},*b*_{2}). Clearly ,
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
.
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
.
If ,
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*^{n} of points in *S*_{i} and let *x* be the limit of the
sequence. Why is ? Let
*x*^{n}=(*a*_{0}^{n}, *a*_{1}^{n}, *a*_{2}^{n}) and
the image
*y*^{n}=*f*(*x*^{n})=(*b*_{0}^{n}, *b*_{1}^{n}, *b*_{2}^{n}). Moreover
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 .

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*_{0}, *S*_{1} and *S*_{2} 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!