VII. Completeness & Fixed Points #

Problems on uniform continuity and Cauchy sequences, and on contraction maps and the existence of fixed points.

Problem 1 #

Prove that every uniformly continuous function $f:S_1 \to S_2$ is continuous at every point $x_0 \in S_1$.

Solutions: Hint · Solution · Long solution

Problem 2 #

Consider a function $f:S_1 \to S_2$. If $f$ is uniformly continuous and $\{s_n\}$ is a Cauchy sequence of points in $S_1$, then the sequence $\{f(s_n)\}$ in $S_2$ is Cauchy as well. Show that this result is not true in general if $f$ is only assumed to be continuous.

Solutions: Hint · Solution · Long solution

Problem 3 #

Recall the following definition from class:

Definition. Suppose that $(S,\rho)$ is a metric space. A function $f: S \to S$ is a contraction map if there is a constant $0 < \alpha < 1$ such that
$$\rho(f(x), f(y)) \leq \alpha \, \rho(x,y).$$

Intuitively, a contraction map shrinks the distance between points of our metric space by at least a factor of $\alpha$. One of the more important theorems we prove in the course shows that for every contraction map $f$ on a complete metric space, there is a point $x \in S$ such that $f(x)=x$.

However, if we relax the restriction on $f$ and require only that

$$\rho(f(x),f(y)) < \rho(x,y)$$

for all distinct $x,y \in S$, then a fixed point may not exist. Find an example of such a function $f$ on a complete metric space which does not have a fixed point and make sure to verify your assertions.

Solutions: Hint · Solution · Long solution

Problem 4 #

Let $A$ be an $n\times n$ matrix and $\vec{b} \in \mathbb{R}^n$. Define a function $T: \mathbb{R}^n \to \mathbb{R}^n$ by

$$T(\vec{x}) = A\vec{x} + \vec{b}.$$

We can think of points in $\mathbb{R}^n$ as states in a physical system, each entry representing one of its parameters. For example, $\vec{x}$ can represent the present state of the economy and each entry one of the leading economic indicators. One can model how this system evolves over time by forming a sequence $\vec{x}_0 = \vec{x}$ and defining the successive states recursively by

$$\vec{x}_{i+1} = T(\vec{x}_i).$$

A recurrent question in a number of disciplines is the following:

Question: Does the physical system described by the iterations of the transformation $T$ reach an equilibrium? That is, is there a vector $\vec{x}$ so that $T(\vec{x}) = \vec{x}$, or in other words, does $T$ have a fixed point?

The Contraction Mapping Theorem hints at one possible answer. The object of this exercise is to find out under what circumstances the transformation $T$ is a contraction map.

(a) Consider the metric space $(\mathbb{R}^n, \rho_\infty)$. Write $A = (a_{ij})$ for a matrix in $\mathbb{R}^n$ and let $\vec{b} = (b_1, b_2, \ldots, b_n)$. Show that the map $T$ defined above is a contraction map if there exists an $\alpha \in [0,1)$ such that

$$\sum_j |a_{ij}| \leq \alpha$$

for every value of $i$. In other words, $T$ is a contraction map if for every row of $A$, the sum of the absolute values of its entries is less than one.

Hint: Let $\vec{y} = T(\vec{x})$ and write the coordinates of $\vec{y}$ in terms of the $a_{ij}$, $x_i$, and $b_i$.

(b) Now consider the metric space $(\mathbb{R}^n, \rho_2)$. Again write $A = (a_{ij})$ for a matrix in $\mathbb{R}^n$ and let $\vec{b} = (b_1, b_2, \ldots, b_n)$. Show that the map $T$ defined above is a contraction map if there exists an $\alpha \in [0,1)$ such that

$$\sum_{i,j} a_{ij}^2 \leq \alpha.$$

That is, $T$ is a contraction map if the sum of squares of the entries of $A$ is less than one.

Hint: Use the Cauchy–Schwarz inequality.

(c) Find a matrix $A$ that satisfies the condition derived in (a) but not the one derived in (b); and vice-versa.

(d) The restrictions derived in (a) and (b) are satisfied by two different sets of matrices. Nevertheless, the map $T$ associated with a matrix $A$ in either set will have a fixed point! How could you use the ideas in (a) and (b) to expand the set of transformations $T$ that have a fixed point even further?

Solutions: Hint · Solution · Long solution