3
$\begingroup$

I'd appreciate any hint for the following problem: Given a vector $a=(a_1, a_2,\ldots,a_n)$, how can I find a vector $b=(b_1, b_2,\ldots,b_n)$ such that $b_1 \leq b_2 \leq \cdots \leq b_n$ and the infinitive norm of the vector $a-b$ is smallest. Thank you.

  • 0
    'Supremum' is exactly what I meant, 'infinitive' is what my teacher introduced it to me. :)2012-06-05

1 Answers 1

3

As @benmachine has pointed out, it is not entirely clear what the infinitive norm is; I'll assume you have been talking about the supremum norm.

A constructive proof

You can find such a function with induction. When $n=1$, take $b_1=a_1$. Suppose, as the induction hypothesis, that for all $k\leq n$ we can find such a sequence $(b_1,\ldots,b_k)$ for any vector $(a_1,\ldots,a_k)$ and let $(a_1,\ldots,a_{n+1})\in\mathbb{R}^{n+1}$. We construct $(b_1,\ldots,b_{n+1})$ in several steps (take pen and paper with you, because it will be easier to follow when you draw what's going on):

  1. First find $n_0$ such that $a_{n_0}$ is maximal among the $a_1,\ldots,a_{n+1}$.
    • If $n_0=n+1$, define $b_{n+1}:=a_{n_0}$ and construct $(b_1,\ldots, b_n)$ with the induction hypothesis.
    • If $n_0, find $n_0< n_1\leq n+1$ such that $a_{n_1}$ is minimal among $a_{n_0+1},\ldots,a_{n+1}$. Also, find $n_2:=\min\{1\leq i\leq n_0:\forall j\geq i,\ a_{n_1}\leq a_j\},$ Then define $b_{n_2},\ldots,b_{n+1}:=\frac{1}{2}(a_{n_0}+a_{n_1})$. This is clearly the best one can go for.

      For the remaining part $1,\ldots,n_2-1$ apply the induction hypothesis to find $b_1,\ldots,b_{n_2-1}$. By the way of construction, it will follow easily that $b_{n_2-1}\leq b_{n_2}$.

You can test your understanding of the above construction by proving that this sequence indeed matches your requirements (that's a good homework too, I guess).


A non-constructive existence proof

To show only existence is easier. For $a\in\mathbb{R}^n$, define the set $ D:=\{\|a-b\|_{\infty}:\min\{a_i\}\leq b_1\leq\cdots\leq b_n\leq\max\{a_i\}\}. $ This is the image of a continuous function of a compact set, hence it is compact. In particular, it has a minimum. It is not so hard to verify that this minimum is also the infimum of the set $ \{\|a-b\|_{\infty}: b_1\leq\cdots\leq b_n\}. $


Note that the result can be extended: for every continuous function $a:[0,1]\to\mathbb{R}$ there exists an increasing continuous function $b:[0,1]\to\mathbb{R}$ with the property that $\|a-b\|_\infty$ is minimal.

  • 0
    I'm confused here... the claim I `came up with' is the claim you asked us to help you with, isn't it?2012-06-05