# Inequality involving rearrangement: $\sum_{i=1}^n |x_i - y_{\sigma(i)}| \ge \sum_{i=1}^n |x_i - y_i|.$

If $x_1 \ge x_2 \ge \cdots \ge x_n$ and $y_1 \ge y_2 \ge \cdots \ge y_n$ are real numbers, and $\sigma$ is any permutation, then $$\sum_{i=1}^n |x_i - y_{\sigma(i)}| \ge \sum_{i=1}^n |x_i - y_i|.$$ This must be a known inequality. What is it called, and how is it proven? (Just a reference is OK.)

The conditions are similar to rearrangement inequality. The inequality is a simple statement about minimizing the $\ell^1$ distance between a finite sequence and any rearrangement of another finite sequence.

I searched around and clicked through various pages but couldn't find something relevant. If it is true, perhaps a proof could be constructed by decomposing the permutation into a sequence of transpositions.

• the trivial inequality ${}{}{}$? – Jorge Fernández-Hidalgo Aug 11 '16 at 2:22
• @CarryonSmiling How is this the trivial inequality? – 6005 Aug 19 '16 at 3:01

For any convex function, such as $f(x) = |x|$,

$$\sum f(x_i - y_{\sigma(i)}) \geq \sum f(x_i - y_i)$$

because $(x_i - y_{\sigma(i)})$ majorizes $(x_i - y_i)$.

A reference is the first theorem, 6.A.1, in chapter 6 of Olkin and Marshall's book on majorization, applied to the sequences $x_i$ and $-y_i$.

They attribute the result to a 1972 article by Peter W Day on general forms of the rearrangement inequality, and give a proof for vectors of real numbers. Day's article is about more general situations with ordered abelian groups. The inequality for real vectors must have been known earlier to many people.

• Thank you -- I very much appreciate the generalization to any convex function! I'm not familiar with majorization -- but I follow that $(x_i - y_{\sigma(i)})$ majorizes $(x_i - y_i)$. Is it possible to add a sentence or two sketching why majorization gives us the inequality? – 6005 Aug 19 '16 at 2:12
• The relation to convex functions is listed under "equivalent conditions" at the Wikipedia page. Majorization is a necessary and sufficient condition for the inequality to hold for all convex functions (for a fixed pair of vectors). – zyx Aug 20 '16 at 20:40
• Very cool result. Thanks. – 6005 Aug 21 '16 at 8:06

We can prove it in a similar way as the rearangement inequality. There are only finitely many possibilities for $\sigma$, so a minimum is achieved, pick $\sigma$ so that it has the least possible number of inversions among all the permutations that minimize the expression.

Suppose by way of contradiction there is $i<j$ with $\sigma(i)>\sigma(j)$. Notice $|x_i-y_{\sigma_i}|+|x_j-y_{\sigma(j)}|\geq |x_i-y_{\sigma(j)}|+|x_j-y_{\sigma(i)}|$.

So the permutation that transposes $i$ and $j$ must also minimize the expression, and has less inversions, a contradiction.

You may be interested in the following inequality.

Let $f_1(x), f_2(x), \cdots, f_n(x): \mathbb{R} \rightarrow \mathbb{R}$ be functions such that for $\forall 1 \leq k < n$, $f_{k+1}(x) - f_k(x)$ is non-decreasing with respect to $x$. In addition, let $y_1 \geq y_2 \geq \cdots \geq y_n$. Then, $$\sum_{k}f_k(y_{n-k+1}) \geq \sum_k f_k(y_{\sigma(k)}) \geq \sum_k f_k(y_k)$$

The book "the cauchy-schwarz master class" does not give a formal name for this inequality but just call it "a non-linear rearrangement inequality". See p.81 of the book.

I show a proof based on the inequality above.

Proof. Let $$f_k(x) = |x_k - x|$$ Then $$f_{k+1}(x) - f_k(x) = \begin{cases} x_{k+1}-x_{k} &\text{if}\ x \leq x_{k+1} \\ 2x - x_{k+1} - x_k &\text{if}\ x_{k+1} < x < x_k\\ x_{k} - x_{k+1} &\text{otherwise} \end{cases}$$ is non-decreasing, thus the inequality applies. That is, $$\sum_k |x_k - y_k| \leq \sum_k |x_k - y_{\sigma(k)}| \leq \sum_k |x_k - y_{n-k+1}|$$