How to use fixed point theorems

Quick description

Let $X$ be a set and let $f$ be a function from $X$ to $X$ . A fixed point of $f$ is an element $x\in X$ such that $f(x)=x$ . A fixed point theorem is a theorem that asserts that every function that satisfies some given property must have a fixed point. If you have an equation and want to prove that it has a solution, and if it is hard to find that solution explicitly, then consider trying to rewrite the equation in the form $f(x)=x$ and applying a fixed point theorem. This method can be applied not just to numerical equations but also to equations involving vectors or functions. In particular, fixed point theorems are often used to prove the existence of solutions to differential equations.

Prerequisites

A knowledge of some of the main fixed point theorems (though these are also discussed in the article, and links are given to Wikipedia articles about them).

This article is incomplete. There should be several examples. In particular, there should be at least one example for each of the fixed point theorems mentioned below.

General discussion

Some of the major fixed point theorems that can be used in analysis and topology: the Brouwer fixed point theorem, the Lefschetz fixed point theorem, the contraction mapping theorem, and the Schauder fixed point theorem.

Example 1

Let $A$ be an $n\times n$ matrix with non-negative entries. A result with many applications is that $A$ must have an eigenvector with non-negative coefficients.

To prove this, let $S$ be the subset of $\R^n$ that consists of all vectors $(x_1,\dots,x_n)$ such that each $x_i$ is non-negative and $x_1+\dots+x_n=1$ . If there exists $x\in S$ such that $Ax=0$ , then we are done. Otherwise, we know that for every $x\in S$ , $Ax$ has non-negative entries, not all of them zero. Let us write $|Ax|$ for the sum of the coefficients of $Ax$ . Then the map $x\mapsto Ax/|Ax|$ is a continuous map from $S$ to $S$ .

Now geometrically $S$ is a simplex of dimension $n-1$ , and therefore it is homeomorphic to a ball of dimension $n-1$ . The Brouwer fixed point theorem implies that $\phi$ has a fixed point, so there must be some $x$ such that $Ax=|Ax|x$ . This $x$ is an eigenvector with eigenvalue $|Ax|$ , so the result is proved.

Example 2

Let $X$ be a Banach space, and let $B$ and $A$ be linear operators on $X$ . If $A$ is invertible and $\Vert B-A\Vert\cdot\Vert A^{-1}\Vert <1$ , then the Contraction Mapping Theorem can be used to show that $B$ is also invertible. Informally, this says that if $B$ closely approximates an invertible operator, then $B$ is invertible.

To show that $B$ is invertible, we will show that for each $y$ in $X$ , there is a unique $x$ such that $Bx=y$ . Let $y$ be an element of $X$ . If $Bx_0=y$ for some $x_0$ in $X$ , then we have $y=Bx_0=(B-A)x_0+Ax_0$ . Multiplying by $A^{-1}$ , we have $A^{-1}y=A^{-1}(B-A)x_0+x_0$ . To simplify notation, write $z=A^{-1}y$ and $C=A^{-1}(B-A)$ , so that $x_0=z-Cx_0$ .

Now we'll define a function $f$ on $X$ by $f(x)=z-Cx$ . If we can show that $f$ is a contraction mapping, then the fixed point of $f$ will be $x_0$ , as $f(x)=x$ gives us $x=z-Cx$ .

Let $x$ and $y$ be elements of $X$ . Then $\vert f(x)-f(y)\vert = \vert C(x-y)\vert \leq \Vert A^{-1}\Vert\cdot\Vert B-A\Vert\,\vert x-y\vert$ . By assumption, $\Vert B-A\Vert\cdot\Vert A^{-1}\Vert<1$ , so $f$ is a contraction mapping, which gives us the desired fixed point $x_0$ .

The proof of the contraction mapping theorem proceeds by iterating the contraction. In this case, since the contraction is a linear map, one can do this explicitly and see what one obtains. The first few iterates of the function $f$ above are $z-Cx$ , $z-C(z-Cx)=z-Cz+C^2x$ , $z-Cz+C^2z-C^3x$ , and we see that, because $\|C\|<1$ , this sequence is converging to the point $z-Cz+C^2z-C^3z+\dots$ .

If $A$ is the identity and $\|C\|<1$ , then this is particularly easy to see directly: the inverse of $I+C$ is $I-C+C^2-C^3+\dots$ , and one can justify it by noting that $(I+C)(I-C+C^2-\dots+(-1)^nC^n)=I-C^{n+1}$ , which converges to $I$ . One can deduce the general case from this too, since $A+(B-A)=A(I+A^{-1}(B-A))$ . Therefore, the contraction mapping theorem is not essential in this example.

This article is in need of attention. It would be nice to have an example of the contraction mapping theorem applied in a less linear context so that one can't just write down a solution anyway.

Login or register to post comments
11432 reads

Comments

An application of the contraction mapping principle

Tue, 26/05/2009 - 15:31 — lacruz

A nice application of this principle is Picard's theorem about the existence of solutions to an initial value problem for a first order, ordinary differential equation. The map involved is highly non linear and the solution cannot be written down explicitily as in example 2. The idea is to convert the differential equation into an integral equation. The solution is then a fixed point for the operator that rules the integral equation. I just realized that there is a reference to this kind of trick at the end of the quick description above.

An application of Schauder's fixed point theorem

Tue, 26/05/2009 - 16:21 — lacruz

An application of this result is Lomonosov's remarkable theorem about the existence of invariant subspaces for an operator on a Banach space that commutes with a non zero compact operator. It would be nice to write an article on this. Also, it could be linked from other articles like

analysis > Operator theory

How to prove the existence of > Invariant subspaces

Fixed point theorems for set valued maps

Tue, 26/05/2009 - 23:44 — lacruz

I would like to mention that this kind of results, in particular Kakutani's fixed point theorem, can be used to produce invariant subspaces for operators on Banach spaces. Added later: where I said Kakutani, I meant to say Ky Fan.

Universal mappings and universal morphisms

Thu, 24/06/2010 - 07:44 — wlod

There are good reasons to study not just the fixed point property (fpp) but the common generalization of fpp and the covering dimension theory, namely the universal functions, and even the universal (and couniversal) morphisms for general categories. (Since monoids are 1-object categories, one may also focus on the universal elements of monoids).