Brouwer fixed point theorem
From Wikipedia, the free encyclopedia
In mathematics, the Brouwer fixed point theorem is an important fixed point theorem that applies to finite-dimensional spaces and forms the basis for several more general fixed point theorems.
Contents |
[edit] Statement
The theorem states that every continuous function from the closed unit ball D n to itself has at least one fixed point. In this theorem, n is any positive integer, and the closed unit ball is the set of all points in Euclidean n-space Rn which are at distance at most 1 from the origin. A fixed point of a function f : D n → D n is a point x in D n with f(x) = x.
[edit] Notes
The function f in this theorem is not required to be bijective or even surjective.
Because the properties involved (continuity, being a fixed point) are invariant under homeomorphisms, the theorem equally applies if the domain is not the closed unit ball itself but some set homeomorphic to it (and therefore also closed, bounded, connected, without holes, etc.).
The statement of the theorem is false if formulated for the open unit disk, the set of points with distance less than 1 from the orign. Consider for example
which maps every point of the open unit disk in R2 to another point of the open unit disk slightly to the right of the given one.
[edit] Illustrations
The theorem has several "real world" illustrations. One works as follows: take two equal size sheets of graph paper with coordinate systems on them, lay one flat on the table and crumple up (but don't rip) the other one and place it any way you like on top of the first. Then there will be at least one point of the crumpled sheet that lies exactly on top of the corresponding point (i.e. the point with the same coordinates) of the flat sheet. This is a consequence of the n = 2 case of Brouwer's theorem applied to the continuous map that assigns to the coordinates of every point of the crumpled sheet the coordinates of the point of the flat sheet right beneath it.
Another example, this time of the case n=3, is given by an informational display of a map in, for example, an airport terminal. The function that sends points of the terminal to their image on the map is continuous and therefore has a fixed point, usually indicated by a cross or arrow with the text You are here. A similar display outside the terminal would violate the condition that the function is "to itself" and fails to have a fixed point.
[edit] History
The Brouwer fixed point theorem was one of the early achievements of algebraic topology, and is the basis of more general fixed point theorems which are important in functional analysis. The case n = 3 was proved by L. E. J. Brouwer in 1909. Jacques Hadamard proved the general case in 1910, and Brouwer found a different proof in 1912. Since these early proofs were all non-constructive indirect proofs, they ran contrary to Brouwer's intuitionist ideals. Methods to construct (approximations to) fixed points guaranteed by Brouwer's theorem are now known, however; see for example (Karamadian 1977) and (Istrăţescu 1981).
[edit] Proof outlines
A full proof of the theorem would be too long to reproduce here, but the following paragraph outlines a proof omitting the difficult part. It is hoped that this will at least give some idea why the theorem might be expected to be true. Note that the boundary of D n is S n-1, the (n-1)-sphere.
Suppose f : D n → D n is a continuous function that has no fixed point. The idea is to show that this leads to a contradiction. For each x in D n, consider the straight line that passes through f(x) and x. There is only one such line, because f(x) ≠ x. Following this line from f(x) through x leads to a point on S n-1. Call this point F(x). This gives us a continuous function F : D n → S n-1. This is a special type of continuous function known as a retraction: every point of the codomain (in this case S n-1) is a fixed point of the function.
Intuitively it seems unlikely that there could be a retraction of D n onto S n-1, and in the case n = 1 it is obviously impossible because S 0 (i.e., the endpoints of the closed interval D 1) isn't even connected. The case n=2 takes more thought, but can be proven by using basic arguments involving the fundamental groups: the retraction would induce an injective group homomorphism from the fundamental group of S1 to that of D 2, but the first group is isomorphic to Z while the latter group is trivial, so this is impossible. The case n=2 can also be proven by contradiction based on a theorem about nonvanishing vector field.
For n > 2, however, proving the impossibility of the retraction is considerably more difficult. One way is to make use of homology groups: it can be shown (and this is the hard part) that Hn-1(D n) is trivial while Hn-1(S n-1) is infinite cyclic. This shows that the retraction is impossible, because again the retraction would induce an injective group homomorphism from the former to the latter group.
There is also an almost elementary combinatorial proof. Its main step consists in establishing Sperner's lemma in n dimensions.
There is also a quick proof, attributed to Morris Hirsch by John Milnor, based on the impossibility of a differentiable retraction. The indirect proof starts by noting that the map f can be approximated by a smooth map retaining the property of not fixing a point; this can be done by using the Weierstrass approximation theorem, for example. One then defines a retraction as above which must now be differentiable. Such a retraction must have a non-singular value (by Sard's theorem), whose inverse image would be a 1-manifold with boundary. The boundary would have to contain at least two end points, both of which would have to lie on the boundary of the original ball--which is impossible in a retraction!
A quite different proof given by David Gale is based on the game of Hex. The basic theorem about Hex is that no game can end in a draw. This is equivalent to the Brouwer fixed point theorem for dimension 2. By considering n-dimensional versions of Hex, one can prove in general that Brouwer's theorem is equivalent to the determinacy theorem for Hex.
[edit] Generalizations
The Brouwer fixed point theorem forms the starting point of a number of more general fixed point theorems.
The straightforward generalization to infinite dimensions, i.e. using the unit ball of an arbitrary Hilbert space instead of Euclidean space, is not true. The main problem here is that the unit balls of infinite-dimensional Hilbert spaces are not compact. For example, in the Hilbert space l 2 of square-integrable real (or complex) sequences, consider the map f : l 2 → l 2 which sends a sequence x from the closed unit ball of l 2 to the sequence y defined by
It is not difficult to check that this map is continuous, has its image in the unit sphere of l 2, but does not have a fixed point.
The generalizations of the Brouwer fixed point theorem to infinite dimensional spaces therefore all include a compactness assumption of some sort, and in addition also often an assumption of convexity. See fixed point theorems in infinite-dimensional spaces for a discussion of these theorems.
The Kakutani fixed point theorem generalizes the Brouwer fixed point theorem in a different direction: it stays in Rn, but considers upper semi-continuous correspondences (functions that assign to each point of the set a subset of the set). It also requires compactness and convexity of the set.
The Lefschetz fixed-point theorem applies to (almost) arbitrary compact topological spaces, and gives a condition in terms of singular homology that guarantees the existence of fixed points; this condition is trivially satisfied for any map in the case of Dn.
[edit] External links
- Brouwer's Fixed Point Theorem for Triangles at cut-the-knot
- Brouwer theorem, from the Encyclopaedia of Mathematics
[edit] References
- Gale, D. (1979). "The Game of Hex and Brouwer Fixed-Point Theorem". The American Mathematical Monthly 86: 818-827.
- John W. Milnor, Topology from the Differentiable Viewpoint, Princeton University Press (see p.13-15 for a proof utilizing the non-existence of a differentiable retraction)
- S. Karamadian (ed.), Fixed points. Algorithms and applications, Academic Press, 1977
- V.I. Istrăţescu, Fixed point theory, Reidel, 1981
