# Fixed point problem with a monotone vector as a fixed point?

Suppose $F : [0,1]^n \to [0,1]^n$ is continuously differentiable and $0 < \frac{\partial F_1}{\partial x_i} \leq \dots \leq \frac{\partial F_n}{\partial x_i} < \beta < 1$ for all $i =1,\dots,n$. Conjecture: there exists unique $x^* = F(x^*)$, and moreover, $x_1^* \leq \dots \leq x_n^*$.

Proof of the first part is quite straightforward: one can easily verify that $F$ is a contraction mapping and then apply the contraction mapping theorem. I would need some help with the second claim.

-
What order do you endow $[0,1]^n$ with? Note also that when $n=1$, there are continuous monotonic functions with several fixed points (e.g. identity map!) – Benoît Kloeckner Apr 21 '14 at 11:36
I am not sure what you have in mind. It is a standard Euclidean space, with all the standard properties. Perhaps I should clarify that I am looking for properties that $F$ needs to satisfy that would guarantee that the fixed point would be such that $x_1^* \leq x_2^* \leq \dots \leq x_n^*$ (all are elements of $[0,1]$ of course). Thanks a lot for pointing out that continuity and monotonicity are not enough for uniqueness. Of course, you're right. For uniqueness I use additionally that $0 < \frac{\partial F_i}{x_i} < 1$. – TomH Apr 21 '14 at 13:23
If you don't have a condition on $F$ that "favors some coordinates over others", then for any $F$ that might have your property, there should be a function $G = \pi^{-1}\circ F \circ \pi$ where $\pi$ is effectively a permutation matrix that shuffles the coordinates of the input vector, and may induce a different fixed point without the desired order. Gerhard "Feels Like Something Is Missing" Paseman, 2014.04.21 – Gerhard Paseman Apr 21 '14 at 17:15
You're absolutely right that $F$ has to satisfy some additional property and I think it does. Where I'm stuck is what particular property guarantees this. Please see my answer to Aaron Meyerowitz below for one possible example. – TomH Apr 21 '14 at 22:01
I have rephrased the question now, using conjecture proposed by Aaron Meyerowitz. It should be a well-formed problem now and it would solve my initial problem as well. – TomH Apr 23 '14 at 21:10

Here is the question by @TomH (exact quote from the above):

Suppose $F : [0,1]^n \to [0,1]^n$ is continuously differentiable and $0 < \frac{\partial F_1}{\partial x_i} \leq \dots \leq \frac{\partial F_n}{\partial x_i} < \beta < 1$ for all $i =1,\dots,n$. Conjecture: there exists unique $x^* = F(x^*)$, and moreover, $x_1^* \leq \dots \leq x_n^*$.

Proof of the first part is quite straightforward: one can easily verify that $F$ is a contraction mapping and then apply the contraction mapping theorem. I would need some help with the second claim.`

Let me provide a counter-example $\ F : [0;1]^2\rightarrow [0;1]^2\$ in dim 2 (it can be written in $n$ variables too):

Let an auxiliary function $\ g:[0;1]^2\rightarrow \mathbb R\$ be given as follows:

$$g(x\ y)\,\ :=\,\ \frac14\cdot(x-\frac12)\ +\ \frac12\cdot(y-\frac14)$$

Then $\ -\frac14\le g(x\ y) \le \frac12\$ for every $\ (x\ y)\in [0;1]^2;\$ and $\ g(\frac12\ \frac14)\ =\ 0.\$ Consider $\ F:[0;1]^2\rightarrow [0;1]^2\$ defined by:

$$F(x\ y)\ :=\ \left(\frac12 + g\left(x\ y\right),\ \frac14 + g\left(x\ y\right)\right)$$

Indeed, the values of the first coordinate of $F$ belong to the interval $\ \left[\frac14;1\right],\$ and of the second coordinate to $\ \left[0;\frac34\right].\$ Thus the range of $F$ is in $\ [0;1]^2\$. Also, the partial derivatives, with respect to $x$, of the two coordinate functions are the same; and the same is true about $y$. Of course both derivatives (constants) belong to a proper closed subinterval of $\ [0;1].\$ Finally

$$F(\frac12\ \frac14)\ =\ (\frac12\ \frac14)$$

where $\ \frac12 > \frac14.\$ That's it.

-
I guess he meant that the map $F$ is surjective. Otherwise there – bartgol Aug 29 '14 at 0:13
Really?! I don't think it'd make any sense. A function increasing in all axial directions, when surjective, would have to satisfy $\ F(0\ldots 0) = (0\ldots 0)\$ and $\ F(1\ldots 1) = (1\ldots 1)\$. Next, surjections cannot be (proper) contractions; etc. – Włodzimierz Holsztyński Aug 29 '14 at 1:03
Whoops. I stop writing in the middle of it and I thought I didn't hit "add comment", since that was clearly wrong. =P – bartgol Aug 29 '14 at 15:22
Indeed, your comment stopped in a middle of a sentence. (And there are not too many comments here :-) – Włodzimierz Holsztyński Aug 29 '14 at 17:04

So I see that you are assuming that the $n^2$ first order partial derivatives are all strictly between $0$ and $1$. The fixed point can be found by repeatedly applying $F$ starting (almost?) anywhere. It would be sufficient then that the property $x_1 \le x_2 \le \cdots \le x_n$ is preserved by application of $F$. On way to have that happen is to have conditions such as $\frac{\partial F_i}{x_j} \le \frac{\partial F_{i+1}}{x_{j}}$ although that is more than is needed. Indeed, if any subset of the set of points with ordered coordinates( such as the line $x_1=x_2=x_3=\cdots=x_n$ or the curve ($t^n,t^{n-1},\cdots,t^1)$) is mapped to itself, that suffices. So all the $F_i$ equal would be enough.

In a way that is trivial since the minimal condition is that there is a $1$ point set mapped into itself and that point is ordered. So what is your function or at least what flavor of properties are you considering?

-
Thanks a lot. This is quite close to answering my question. What I learned (thanks to your answer) is that my $F$ is actually a contraction mapping, since the derivatives are bounded in $(0,k)$ for some $k<1$. So, you're right that it suffices to show that the property $x_1 \leq \dots \leq x_n$ is preserved by $F$. You said that having $\frac{\partial F_i}{\partial x_j} \leq \frac{\partial F_{i+1}}{\partial x_j}$ for all $i,j$ would be sufficient for this. Do you have a simple argument why? I am not sure yet, but I think that my function may actually satisfy this. – TomH Apr 21 '14 at 21:57
Wlodzimierz's counterexample shows that those conditions on the partial derivatives are not sufficient. What would be sufficient would be those conditions plus $F_i({\bf 0}) \le F_{i+1}({\bf 0})$. – Robert Israel Aug 29 '14 at 20:05