1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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!) $\endgroup$ Apr 21, 2014 at 11:36
  • $\begingroup$ 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$. $\endgroup$
    – TomH
    Apr 21, 2014 at 13:23
  • 1
    $\begingroup$ 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 $\endgroup$ Apr 21, 2014 at 17:15
  • $\begingroup$ 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. $\endgroup$
    – TomH
    Apr 21, 2014 at 22:01
  • $\begingroup$ 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. $\endgroup$
    – TomH
    Apr 23, 2014 at 21:10

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I guess he meant that the map $F$ is surjective. Otherwise there $\endgroup$
    – bartgol
    Aug 29, 2014 at 0:13
  • $\begingroup$ 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. $\endgroup$ Aug 29, 2014 at 1:03
  • $\begingroup$ Whoops. I stop writing in the middle of it and I thought I didn't hit "add comment", since that was clearly wrong. =P $\endgroup$
    – bartgol
    Aug 29, 2014 at 15:22
  • $\begingroup$ Indeed, your comment stopped in a middle of a sentence. (And there are not too many comments here :-) $\endgroup$ Aug 29, 2014 at 17:04
0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – TomH
    Apr 21, 2014 at 21:57
  • $\begingroup$ 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})$. $\endgroup$ Aug 29, 2014 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.