Let $x_1 < x_2 < \cdots < x_q$ and $y_1 < y_2 < \cdots < y_q$ be two monotonic sequences of real numbers. Then, I want to show
\begin{align}
\max_k |x_k – y_{\sigma(k)}| \geq \max_k |x_k – y_k|, ~~~~~~~~~~~~~~~~~~~~~~~~~(1)
\end{align}where $\{y_{\sigma(1)}, y_{\sigma(2)}, \ldots, y_{\sigma(q)}\}$ is a permutation of $\{y_1, y_2, \ldots, y_q\}$.
I found out this solution, using which I can show \begin{align*}
\left(\sum_{k=1}^q |x_k – y_{\sigma(k)}|^r\right)^{1/r} \geq \left(\sum_{k=1}^q |x_k – y_k|^r \right)^{1/r} ~~~~~~~~~~~~~~~~~~~~~~~~~(2)
\end{align*} for all $r$. I cannot apply the mazorization theory to prove (1) directly as the maximum-absolute function is not convex. However, if I apply $r\to \infty$ on both the sides of (2), I can obtain (1).
My question: I am wondering if there is a way to directly prove (1) (without using r-norm and, possibly, mazorization theory)?
Best Answer
The idea is the same as in the proof of the rearrangement inequality or in Inequality involving rearrangement: $ \sum_{i=1}^n |x_i - y_{\sigma(i)}| \ge \sum_{i=1}^n |x_i - y_i|. $: Show that if there are $i< j$ with $\sigma(i) > \sigma(j)$ then the left-hand side of $(1)$ does not increase if $\sigma(i)$ and $\sigma(j)$ are exchanged.
It then follows that the permutation which minimizes the left-hand side of $(1)$ and has the last possible number of inversions is necessarily the identity permutation.
In other words, it suffices to prove the inequality for $q=2$ and the permutation which exchanges indices $1$ and $2$. Actually we can prove strict inequality for $q=2$, but not for $q \ge 3$.
Case 1: $x_1 + x_2 \le y_1 + y_2$. Then $$ x_1 < \frac 12 (x_1+x_2) \le \frac 12 (y_1 + y_2) \implies |x_1 - y_1| < |x_1 - y_2| $$ and $$ \frac 12 (x_1+x_2) \le \frac 12 (y_1 + y_2) < y_2 \implies |y_2 - x_2| < |y_2 - x_1| \, . $$ It follows that $$ \max( |x_1 - y_1|, |x_2 - y_2|) < |x_1 - y_2| $$ and that implies $(*)$.
Case 2: $x_1 + x_2 > y_1 + y_2$ works similarly, now we get $$ \max( |x_1 - y_1|, |x_2 - y_2|) < |x_2 - y_1| $$ which again implies $(*)$.
Remark: The rearrangement inequality is strict if the $x_i$ and $y_i$ are distinct and $\sigma$ is not the identity permutation. That is not the case here if $q \ge 3$. An example is $$ (x_1, x_2, x_3) = (1, 2, 3) \\ (y_1, y_2, y_3) = (1, 2, 5) $$ with $$ \max(|x_1-y_2|, |x_2-y_1, |x_3-y_3|) = 2 = \max(|x_1-y_1|, |x_2-y_2, |x_3-y_3|) \, . $$