Brouwer Fixed Point Theorem
| Brouwer Fixed Point Theorem |
|---|
 |
Brouwer Fixed Point Theorem
- Suppose two disks of the same size, one red one blue, are initially placed so that the red disk is exactly on top of the blue disk. Then, imagine that we can strech, shrink, rotate, and fold the red disk in any way as long as it is not cut or torn. Finally, we replace the red disk so that none of the disk hangs off the blue disk.
- Brouwer's theorem states that there must be at least one point, a fixed point, on the red disk that is exactly above its initial position on the blue one.
Contents
1-dimensional case
The simplest case of the fixed point theorem is the one dimensional case, which can be explained using strings.
Suppose two identical strings are placed directly on top of one another. The bottom string remains unchanged, but the top string can be folded, stretched, and reshaped as long as it is replaced so that no part of the string hangs off the bottom string.
No matter how you stretch, bend, or move the top string, there will be a point on the top string whose horizontal position has not changed!
To visualize the situation, it is useful to be able to identify an actual fixed point. In Image 1, the strings are shaded with color that gradually fades so that every point on the string is shaded with a different color. The color represents the initial horizontal position of each string. If this color is in the same horizontal place on both the deformed and un-deformed strings, then deforming the string didn't change the horizontal location of this point.
The black dots on the two strings show this point in the image. There will always be some point whose horizontal position does not change, and that point is the fixed point!
2-dimensional case
The fixed point theorem in two-dimensional space can be represented by two disks, one red and one blue. The disks are the same size and the red disk is placed on top of the blue one. The red disk is reshaped or moved and subsequently replaced on the blue disk without any part extending beyond the boundary of the blue disk.
The fixed point theorem states that it is impossible to distort (without tearing) the red disk so that every single point moves. In other words, there will be at least one point on the red disk that still lies in the same place above the blue disk.
Image 2 above show some attempts to move or distort the red disk in a way so that there is no fixed point. The Fixed Point Theorem guarantees that none of these attempts can be successful. The explanations below describe why the arrows in the pictures in fact identify the fixed points of these examples.
Notice in Image 2.1 where the disk was only rotated, it seems like all the points are moving. Nonetheless, the center point is still fixed.
In Image 2.2, the red disk was folded in half twice to make a fourfold quarter piece and slid so that it covers the center point of the blue disk. It was also placed so that the top edge of the red disk is parallel with the horizontal center line.
To see the fixed point in Image 2.2, suppose we connect the center point of the red disk to the center of the blue disk with a white line. We can mark the midpoint of this line segment with a black point. Since we folded the red disk twice before we placed it on top of the blue, there are actually 4 red points on top of 1 blue point where we marked the dot. This point is labeled P in the illustration above.
Now that we have identified all the useful points on the diagram, we can take a strategic approach to prove the existence of a fixed point.
- 1. As shown in the animation to the right, rotating the red disk around point P allows it to exactly cover the top right quarter of the blue disk.
- Rotating the red quarter around point P will not change the position of any of the four points on the red disk that are now located at point P.
- 2. Because the red disk is exactly in one quarter of the blue disk, one of the four red layers must be in its original position.
- When this layer has returned to its original position, the point P on this quarter will also be in its original position.
We have just shown that after a layer is rotated, one of the four point located at P is in its initial location. The rotation didn't actually move this point, however, so it was in its original location even before the rotation. Therefore, this point remained fixed even when the disk was deformed.
Image 2.3 shows an example of a case where the red disk is reshaped in a very complex way. Finding the actual fixed point in Image 2.3 is impossible without knowing exactly what was done to the top disk. Nonetheless, the Fixed Point Theorem guarantees that there must be "some" fixed point, even if we can't identify exactly where it is.
3-dimensional case
The three dimensional case was apparently proposed by Brouwer himself as he drank a cup of coffee, although Henri Poincaré and P. Bohl actually proved parts of the theorem before Brouwer. The consequence of the Brouwer fixed point theorem in three dimensions is that no matter how much you stir a cup of coffee, some point of the liquid will return to its original position. That is, assuming that none of the liquid was spilled.
A More Mathematical Explanation
The Brouwer Fixed Point Theorem states that a continuous mapping, f, of a '"`UNIQ--balloon-00000 [...]
The Brouwer Fixed Point Theorem states that a continuous mapping, f, of a convex, closed bounded set in Rn into itself necessarily has a point, x0, where f(x0) = x0.
1-dimensional case
The fixed point theorem can be explained intuitively in one dimension by using graphs to show that every continuous function on a closed interval has a point where f(x) = x. If we graph f and we graph the line y = x, we can see in Image 3 that any for any x where the graphs intersect, f(x) = x. We can also see that the graph of any continuous function from x = a to x = b (in this case from the green line to the purple where a=0 and b=1) is unbroken and must intersect the blue diagonal. The x-value of the intersection is the fixed point.
More formally, we can use the intermediate value theorem to prove that there is a fixed point. Define ϕ(x) by ϕ(x) = f(x) - x. First, we can assume that f(a) ≠ a and f(b) ≠ b because if f(a) = a or f(b) = b that point will already be a fixed point, and the proof is done. Thus, ϕ(a) = f(a) - a > 0 and ϕ(b) = f(b) - b < 0. Since ϕ is continuous on the interval [a, b], the intermediate value theorem states that ϕ(x) = 0 at some point x on the open interval (a, b). This is the fixed point.
Generalizing to All Dimensions
The following explanation is an intuitive approach to proving the existence of fixed points. Links to more rigorous proofs are provided at the end of this section.
To prove that the Brouwer fixed point theorem generalizes to all dimensions, we can begin by showing that it applies in two dimensions.
We will first show that the theorem is true in R2 when the closed bounded convex set W is a rectangle. Using a rectangle is advantageous because it allows us to establish clear x and y directions. After proving Brouwer's theorem for a rectangle, we will show that this implies the theorem for all closed bounded convex shapes.
The corners of W are at A=(x0, y0), B=(x0, y1), C=(x1, y1), and D=(x1, y0), as shown in Image 4. Also, let f be a function that maps W to itself. We can say that when f is applied to a point, (x, y), it will generate the point (x ', y '). Since we know that a fixed point is a point that is unmoved by f, we can say that a fixed point is where x = x ' and y = y '.
Next, it will be useful to consider the first and second coordinates separately. If we separate the x and y components of the function f, we can say that
- x' = g(x, y)
- y' = h(x, y)
where x, x ' ∈ [x0, x1] and y, y ' ∈ [y0,y1] with g and h continuous. We will argue below that there is a curve from side AD to side BC of points (x,y) at which g(x, y) = x, that is, a curve where f fixes x. Likewise, there is a curve from side AB to CD of points at which h(x, y) =y, that is, where f fixes y. As the figure shows, these two curves must cross. The theorem follows because at the point of intersection, f fixes both coordinates. That is, (x, y) is a fixed point of f.
To show that there is a curve from AD to BC where g fixes x, consider the blue line AD. This line is where y is fixed at y0. For any point (x,y0) along this line, x ' = g(x, y0). Both the values for x and x' are from the same interval from x0 to x1. This is the n = 1 case of the theorem, and we know there will be at least one fixed x value. Now, suppose we draw any other line in the rectangle parallel to the blue one. Again, there must be a fixed x value. In fact, for each horizontal line we draw from x0 to x1, there is at least one fixed x-value. Since the function g is continuous, it is plausible that these fixed points form a continuous curve. The detail of continuity is an important one, and it can be proven in a more strict proof. For the purposes of this explanation, we can say this continuous curve will connect AD to BC.
Similarly, h fixes a curve of y values from side BA to CD. The intersection of the curve that fixes x values and the curve that fixes y values is the fixed point, p.
This completes our explanation when W is a rectangle. Now let W be any closed bounded convex set, and let f map W to itself continuously. Because W is bounded, it can be enclosed in a rectangle R. We show how to extend f to a continuous function that maps R into W. This means the extended f maps R into R, so it has a fixed point. Since all the images are in W, the fixed point p must be in W. Therefore p is also a fixed point of the original f.
So it remains to show how to extend f.
Pick a random point, a in W and let b be any point in R but outside W. Draw the line segment from b to a. Let c be the point on this segment that is on the boundary of W. There can only be one such point c for each b, since W is convex.
Simply define f(b)=f(c). Since f(b) is in W, we have extended f so that all points of R map to W. Because f is constant outside of W along rays from a, f is in fact continuous.
This completes our informal proof in 2 dimensions.
The intuitive approach of the n = 2 case generalizes to any finite dimension. To examine this further, it is easiest visually to consider dimension 3.
For n=3, we hold two variables constant and graph the points where the remaining variable is fixed. For instance, for each y and z, we let x vary and consider the function x ' = g(x, y, z), for x in [x0, x1]. As before, some value of x is fixed. Since there is such an x for each pair (y, z), it is reasonable that the set of such points where f fixes x forms a surface like the blue surface in Image 5. It cuts the cube into two connected components, one containing part of the right face and one containing part of the left face. There will also be a sheet shown in green in Image 5, where f fixes y.
The intersection of the two sheets must contain a curve, depicted in yellow, at the intersection of the green and blue sheets extending from the upper face to the lower face. Along this line f fixes both x and y. Now the points where f fixes z form the red sheet. This red sheet must intersect the yellow curve. The point of intersection is the desired fixed point in all three variables.
Additional Links
http://www.math.uchicago.edu/~amwright/BFPT.pdf An Intuitive Proof of Brouwer's Fixed Point Theorem in R2. Clarence C. Morrison. http://www.jstor.org/stable/2690266?cookieSet=1
Why It's Interesting
Brouwer's Fixed Point Theorem has sparked discussion since it was first proved and can still be seen in subjects that range from maps to economics.
Conflict with Intuitionalism
The early proofs of Brouwer's theorem were met with mixed receptions from the mathematical community. The first proofs presented by Bohl, Brouwer, and Hadamard were all non-constructive, meaning that they prove the existence of fixed points, but they do not provide a means of constructing an example.
As a result, these proofs (including Brouwer's own) ran contrary to Brouwer's intuitionist ideals. The premise of intuitionalism is that the truth of a statement is taken to be equivalent to a person being able to intuit the statement. At the time of his death, Brouwer believed that fixed points existed, but he did not believe he had sufficiently proven this fact because he couldn't provide an intuitive proof.
Although a very small number of mathematicians may still debate Brouwer's Fixed Point Theorem, the debate about proving the existence of fixed points is primarily philosophical now. Brouwer's theorem is accepted widely in mathematics and is the basis for various other theorems.
Maps
The Brouwer Fixed Point Theorem manifests itself in ways that may seem entirely unrelated to mathematics, such as the existence of a You are here marker on informational maps (often found in malls). These maps are familiar in everyday life, yet few people associate them with Brouwer's theorem. In effect, the function that takes places in the mall as input and returns their image on the map as output is continuous and therefore it must have a fixed point. This point is usually indicated by a marker containing the text You are here.
If we consider the existence of similar display outside the mall, we know there would be no marker because our location cannot be accurately represented on the map. This makes sense because a map outside the mall would violate Brouwer's condition that the function is mapped "to itself," so a map outside the mall would fail to have a fixed point (or a You are here marker).
Economics and Game Theory
Classical game theory and economics rely heavily on fixed point theorems.
The celebrated result of John Nash proving the existence of equilibrium in multiplayer games is a classic example for which the only known proofs depend on fixed point theorems. Imagine a game where each player is trying to improve his results based on the current actions of his opponents. Then Nash's theorem states that there is some combination of strategies so that each player can't improve his outcome unilaterally. Thus, players have reached a set of strategies, or strategy profiles, that are “fixed” under the optimization process.
For instance, in the rock, paper, scissors game, the Nash equilibrium involves players randomly picking each choice 1/3 of the time. If a player tried to improve his strategy by favoring rock more than 1/3 of the time, then his opponent could beat him more often than not by countering with paper.
In games, the set, W, where this function is being applied is not a string, disk or cup of coffee. Instead, a point in W is a combination of strategies, one employed by each player, that the players could be using. For example, a point in W could be that one player plays rock half the time and paper half the time, while another player plays rock 1/3 of the time, paper 1/3 of the time, and scissors 1/3 of the time.
If x is a point in W, representing a combination of strategies, the f(x) is the set of strategies the players form in response to x. The Nash equilibrium of the game is a set of strategies where each players' strategy is the best response to his opponents. The fixed point theorem guarantees that there will always be a Nash equilibrium. That is, there will be some set of strategies that are ideal for both players, so applying f does not change this point in W. This set of strategies is a fixed point.
Brouwer's theorem is also used to prove that there is an intersection between supply and demand curves. The idea that markets will generally readjust to a point of equilibrium is a fundamental assumption in economics. The models that serve as the foundation for this belief are based on a model of one product. So, when the economy has multiple products, it must be asked under what circumstances such an equilibrium is possible. The essential mathematical tools used to address this question are fixed point theorems, including Brouwer's.
In the case where there are multiple products, W is the set of combinations of commodity prices. The function, f, is chosen so that f(x) is only equal to x when supply is actually equal to demand. The challenge here is to construct f so that it has this property while at the same time satisfying the conditions in Kakutani's fixed point theorem (which is a result of the more general Brouwer's theorem). If this can be done, then the function f must have a fixed point according to the theorem, and this point equates supply with demand.
Teaching Materials
- There are currently no teaching materials for this page. Add teaching materials.
References
[1] An Intuitive Proof of Brouwer's Fixed Point Theorem in R2. Clarence C. Morrison.
[2] Fixed Points. Yu A. Shashkin.
[3] Heart of Mathematics. Edward B. Burger, Michael P. Starbird.
[4] http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem
[5] http://www.sjsu.edu/faculty/watkins/fixed.htm
[6] http://www.math.uchicago.edu/~amwright/BFPT.pdf
[7] http://www.britannica.com/EBchecked/topic/81461/Brouwers-fixed-point-theorem
[8] http://mindyourdecisions.com/blog/2007/11/20/game-theory-tuesdays-a-brain-teaser-and-related-trivia/
[9] http://en.wikipedia.org/wiki/Kakutani_fixed-point_theorem
Future Directions for this Page
- A more rigorous proof
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.
[[Description::Suppose two disks of the same size, one red one blue, are initially placed so that the red disk is exactly on top of the blue disk. Then, imagine that we can strech, shrink, rotate, and fold the red disk in any way as long as it is not cut or torn. Finally, we replace the red disk so that none of the disk hangs off the blue disk.
- Brouwer's theorem states that there must be at least one point, a fixed point, on the red disk that is exactly above its initial position on the blue one.
1-dimensional case
The simplest case of the fixed point theorem is the one dimensional case, which can be explained using strings.
Suppose two identical strings are placed directly on top of one another. The bottom string remains unchanged, but the top string can be folded, stretched, and reshaped as long as it is replaced so that no part of the string hangs off the bottom string.
No matter how you stretch, bend, or move the top string, there will be a point on the top string whose horizontal position has not changed!
To visualize the situation, it is useful to be able to identify an actual fixed point. In Image 1, the strings are shaded with color that gradually fades so that every point on the string is shaded with a different color. The color represents the initial horizontal position of each string. If this color is in the same horizontal place on both the deformed and un-deformed strings, then deforming the string didn't change the horizontal location of this point.
The black dots on the two strings show this point in the image. There will always be some point whose horizontal position does not change, and that point is the fixed point!
2-dimensional case
The fixed point theorem in two-dimensional space can be represented by two disks, one red and one blue. The disks are the same size and the red disk is placed on top of the blue one. The red disk is reshaped or moved and subsequently replaced on the blue disk without any part extending beyond the boundary of the blue disk.
The fixed point theorem states that it is impossible to distort (without tearing) the red disk so that every single point moves. In other words, there will be at least one point on the red disk that still lies in the same place above the blue disk.
Image 2 above show some attempts to move or distort the red disk in a way so that there is no fixed point. The Fixed Point Theorem guarantees that none of these attempts can be successful. The explanations below describe why the arrows in the pictures in fact identify the fixed points of these examples.
Notice in Image 2.1 where the disk was only rotated, it seems like all the points are moving. Nonetheless, the center point is still fixed.
In Image 2.2, the red disk was folded in half twice to make a fourfold quarter piece and slid so that it covers the center point of the blue disk. It was also placed so that the top edge of the red disk is parallel with the horizontal center line.
To see the fixed point in Image 2.2, suppose we connect the center point of the red disk to the center of the blue disk with a white line. We can mark the midpoint of this line segment with a black point. Since we folded the red disk twice before we placed it on top of the blue, there are actually 4 red points on top of 1 blue point where we marked the dot. This point is labeled P in the illustration above.
Now that we have identified all the useful points on the diagram, we can take a strategic approach to prove the existence of a fixed point.
- 1. As shown in the animation to the right, rotating the red disk around point P allows it to exactly cover the top right quarter of the blue disk.
- Rotating the red quarter around point P will not change the position of any of the four points on the red disk that are now located at point P.
- 2. Because the red disk is exactly in one quarter of the blue disk, one of the four red layers must be in its original position.
- When this layer has returned to its original position, the point P on this quarter will also be in its original position.
We have just shown that after a layer is rotated, one of the four point located at P is in its initial location. The rotation didn't actually move this point, however, so it was in its original location even before the rotation. Therefore, this point remained fixed even when the disk was deformed.
Image 2.3 shows an example of a case where the red disk is reshaped in a very complex way. Finding the actual fixed point in Image 2.3 is impossible without knowing exactly what was done to the top disk. Nonetheless, the Fixed Point Theorem guarantees that there must be "some" fixed point, even if we can't identify exactly where it is.
3-dimensional case
The three dimensional case was apparently proposed by Brouwer himself as he drank a cup of coffee, although Henri Poincaré and P. Bohl actually proved parts of the theorem before Brouwer. The consequence of the Brouwer fixed point theorem in three dimensions is that no matter how much you stir a cup of coffee, some point of the liquid will return to its original position. That is, assuming that none of the liquid was spilled.|]]
