# Brouwer Fixed Point Theorem

The **Brouwer fixed point theorem** states that any continuous function \(f\) sending a compact convex set onto itself contains at least one fixed point, i.e. a point \(x_0\) satisfying \(f(x_0)=x_0\). For example, given two similar maps of a country of different sizes resting on top of each other, there always exists a point that represents the same place on both maps.

The simplest examples of a compact convex set are

- A closed interval in the real numbers
- A closed disk (the region enclosed by a circle)
- Any convex region in the plane; i.e. a region \(R\) such that for any two points \(X,Y\) in \(R\), the segment \(XY\) lies entirely in \(R\)

and thus Brouwer's fixed point theorem applies to all these examples.

Brouwer's fixed point theorem is useful in a surprisingly wide context, with applications ranging from topology (where it is essentially a fundamental theorem) to game theory (as in Nash equilibrium) to cake cutting.

#### Contents

## Informal illustration

There are a number of real-world examples that illustrate Brouwer's theorem, though they are somewhat counterintuitive. The most famous is the following:

Consider a map of a country. If that map is placed anywhere in that country, there will always be a point on the map that represents that exact point in the country.

Equivalently,

Given two similar maps of a country of different sizes resting on top of each other, there always exists a point that represents the same place on both maps.

This holds for *any* mapping, including ones where the region is rotated:

## Formal statement

A **compact** set is one that is both **bounded** and **closed**, meaning that

- All points lie within a fixed distance of another (intuitively, nothing gets infinitely large)
- The set contains all of its limit points; i.e. if a sequence of points in the set approaches some value \(L\), the set also contains \(L\).

For instance, \(\mathbb{R}\) is not bounded, as its elements get infinitely large; it is, however, closed. The interval \((-1,1)\) is not closed, as the limit points -1 and 1 are not part of the interval, though the interval is bounded (all points are within 2 of each other).

A **convex set** was previously defined above.

Brouwer's theorem states that if \(R\) is a compact convex set, and \(f:R \rightarrow R\) is continuous function, then there exists a point \(x_0\) such that \(f(x_0)=x_0\). Note that all of these conditions are necessary; for instance, the function

\[f:\mathbb{R} \rightarrow \mathbb{R}, f(x)=x+1\]

does indeed take the region \(\mathbb{R}\) to itself, but has no fixed points. Similarly, the function

\[f:(0,1) \rightarrow (0,1), f(x)=\frac{x+1}{2}\]

also takes the region \((0,1)\) to itself, but also has no fixed points (the function \(f:[0,1] \rightarrow [0,1], f(x)=\frac{x+1}{2}\), however, has a fixed point at 1).

## One-dimensional case

In the one-dimensional case of Brouwer's theorem, the theorem states

Given a continuous function \(f:[a,b] \rightarrow [a,b]\), there exists a \(c \in [a,b]\) such that \(f(c)=c\).

In fact, this statement is an immediate consequence of the intermediate value theorem, and also has a very intuitive graphical interpretation:

Here, the statement is equivalent to

Any continuous path (dark green in the picture) from the left side to the right side must intersect the green line at some point.

which is intuitively clear.

## Proof of Brouwer's theorem

Brouwer's theorem is notoriously difficult to prove, but there is a remarkably visual and easy-to-follow (if somewhat unmotivated) proof available based on **Sperner's lemma**.

Define the **n-simplex** to be the set of all \(n\)-dimensional points whose coordinates sum to 1. The most interesting case is \(n=2\), as higher dimensions follow via induction (and are much harder to visualize); in this case, the 2-simplex is simply a triangle. A **triangulation** of this triangle is a division into smaller triangles:

A **Sperner coloring** of this triangulation is one that satisfies:

- Each vertex is colored with one of \(n+1\) (3 in the 2-dimensional case) colors
- The vertices that lie on an \((n-1)\)-face of the simplex (the edges of the large triangle in the 2-dimensional case) are colored only with the colors on the corners of that face (the vertices of the large triangle in the 2-dimensional case).

Then Sperner's lemma states:

Sperner's Lemma:For any Sperner coloring of a triangulation of a simplex, there exists an element of the triangulation (a small triangle) whose corners all have different colors.

Indeed, the above Sperner coloring does contain such a triangle (in the lower right).

Now consider the coloring as a "house", with "doors" at every edge whose endpoints are red and green. It is necessary first to show that the boundary has an odd number of doors. But only one side of the large triangle can contain doors, since points are colored the same as one of the two main vertices, and there are clearly an odd number of them as each door denotes an alternation of colors (and at the end, the colors have alternated).

Now consider a path through the triangle starting at some point outside the triangle and walking only through doors. This path ends by either

- Walking outside the triangle or
- Entering a red-green-blue triangle (since there is nowhere to go from there)

Furthermore, once the triangle is entered, the path is completely determined, as no triangle has 3 red-blue edges. This means that no two paths meet in a single small triangle.

Now the key point: a path that ends outside the triangle determines two doors on the boundary of the large triangle, while entering a red-green-blue triangle determines only one. But there are an odd number of doors on the boundary of the large triangle, so some path must have entered a red-green-blue triangle, and so a red-green-blue triangle must exist! This proves Sperner's lemma.

Now we show that Sperner's lemma implies Broewer's theorem. For each point \(P\) in a simplex, let \(f(P)\) be its image. Consider the vector \(v=f(P)-P\), which points towards some corners of the simplex and away from some. Color \(P\) with the color of the vertex it points most away from (choosing arbitrarily in the case of a tie).

It is relatively easy to see that this satisfies the Sperner coloring constraints: any point on an edge will point most away from one of the two vertices defining that edge, and so it will be colored with one of those two colors. Thus, by Sperner's lemma there exists a small triangle whose vertices all have different colors. Repeating this process on the points inside this triangle infinitely gives a point that should be all three colors at the same time, which is possible *only* if that point is a fixed point (as the resulting vector is then not pointing towards any vertex). This demonstrates a fixed point exists for any continuous \(f\) from the simplex to the simplex, and since a simplex is homeomorphic to a closed ball, this demonstrates Brouwer's theorem.

## See Also

**Cite as:**Brouwer Fixed Point Theorem.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/brouwer-fixed-point-theorem/