Brouwer Fixed Point Theorem

From Math Images

Revision as of 14:13, 6 July 2010 by Rebecca (Talk | contribs)
Jump to: navigation, search

{{Image Description |ImageName=Brouwer Fixed Point Theorem |Image=mainpic134.jpg |ImageIntro=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!

Image 1
Image 1


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:scenarios2.jpg


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.

If the point P is in the same position both when the red disk is deformed, when it is being rotated, and when it has returned to its initial position, then it is a fixed point.

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. |ImageDesc=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.

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.


Image 4
Image 4


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 4. 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 4, 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

z

Personal tools