Condition for a contraction mapping?

Question

Consider a mapping $F:\mathbb{R}^N \rightarrow \mathbb{R}^N$, with $F = (F_1,...,F_N)$, and with $F_i$ increasing in all its arguments for all $i$. Let $(x_{1}^{1},x_{2}^{1},...,x_{N}^{1})=(x_{1}^{0}+\Delta,x_{2}^{0}+\Delta,...,x_{N}^{0}+\Delta)$ for $\Delta > 0$. If $$||F\left(x^{1}\right)-F\left(x^{0}\right)||<\Delta$$ for any such $x^1,x^0$. If $F$ is differentiable then we can show that its Jacobian is substochastic and hence its spectral radius is lower than one, which implies that $F$ is a contraction. Is there a more direct way of showing that $F$ is a contraction without going through the Jacobian?

Answer 1

The answer mimics the proof of the Blackwell's sufficient condition for contraction (it is along the lines Andrew gave in the comments to the original post).

Suppose that all norms are infinity norms: $\left\| x \right\|_{\infty} = \max_{i} \left| x_i \right| $, so that the condition in the original post is \begin{align*} \left\| F\left(x^{1}\right) - F\left(x^{0}\right) \right\|_{\infty} \leq \lambda \Delta, \end{align*} for some $0 < \lambda < 1$. (Here I use a stronger condition than in the original post.) Observe that since $x^{1} > x^{0}$ and $F_{i}$ is monotone for each $i$, we can write the above condition as \begin{align} F_{i}\left(x^{1}\right) < F_{i}\left(x^{0}\right) + \lambda\Delta, \; i = 1, \dots, N. \quad (1) \end{align}

Now take any two vectors $x$ and $y$. Let $\Delta \equiv \left\| x - y \right\|_{\infty}$ and $\delta \equiv \left( \Delta, \dots, \Delta \right)$.

First, we have $x \leq y + \delta$. Then, for each $i = 1,\dots, N$ we have \begin{align*} F_{i} \left( x \right) \leq F_{i} \left( y + \delta \right) \leq F_{i} \left( y \right) + \lambda\Delta. \quad (2) \end{align*} The first inequality is due to monotonicity of $F_{i}$, and the second inequality uses condition $(1)$.

Similarly, we have $y \leq x + \delta$ and so for each $i = 1,\dots,N$, \begin{align*} F_{i} \left( y \right) \leq F_{i} \left( x + \delta \right) \leq F_{i} \left( x \right) + \lambda\Delta. \quad (3) \end{align*}

Combining $(2)$ and $(3)$, we get $\left| F_{i} (x) - F_{i}(y) \right| \leq \lambda\Delta$ for all $i = 1, \dots, N$. This implies that $\left\| F_{i} (x) - F_{i}(y) \right\|_{\infty} \leq \lambda \Delta = \lambda \left\| x - y \right\|_{\infty}$. Thus, $F$ is a contraction mapping.