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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

You may be interested in the following inequality.

Let $f_1, \dots, f_n: \mathbb{R} \rightarrow \mathbb{R}$ be functions such that for all $1 \leq k < n$ the function $f_{k+1} - f_k$ is non-decreasing. In addition, let $y_1 \geq y_2 \geq \dots \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}| $$

Answer 4

Here is a proof that reduces the problem to a state where we can apply the rearrangement inequality directly:

Let $s$ be any permutation. We want to pick $s$ such that it minimizes the following sum:

$S = \sum_{i=1}^N|x_i - y_{s(i)}|$

Note that any permutation $s$ that minimizes $S$ is also a permutation that minimizes the sum of the squares:

$S_2 =\sum_{i=1}^N|x_i - y_{s(i)}|^2$

(To prove this last point, we can apply this identity: $(\sum_i\alpha_i)^2 = \sum_i\alpha_i^2 + 2\sum_{i<j}\alpha_i\alpha_j$

So we have:

$S_2 = S^2 - 2\sum_{i < j}|x_i - y_{s(i)}||x_j - y_{s(j)}|$

The term $2\sum_{i < j}|x_i - y_{s(i)}||x_j - y_{s(j)}|$ is constant with respect to $s$, so the only way to minimize $S_2$ is by minimizing $S^2$ which is attained by minimizing $S$, given that $S$ is positive.)

Now we can analyze the sum of the squares:

$$\begin{aligned} S_2 &= \sum_{i=1}^N|x_i - y_{s(i)}|^2 \\ &= \sum_{i=1}^N(x_i - y_{s(i)})^2 \\ &= \sum_{i=1}^N(x_i^2 + y_{s(i)}^2 - 2x_iy_{s(i)}) \\ &= \sum_{i=1}^N(x_i^2 + y_{s(i)}^2) - 2\sum_{i=1}^Nx_iy_{s(i)} \end{aligned} $$

the sum $\sum_{i=1}^N(x_i^2 + y_{s(i)}^2)$ is always the same, regardless of the permutation $s$. So, in order to minimize $S_2$, we have to maximize the sum of the products: $S_p = \sum_{i=1}^Nx_iy_{s(i)}$

Because the arrays are sorted we have $x_i \leq x_j, y_i \leq y_j$ for $i < j$. By the Rearrangement Inequality we can maximize $S_p$ by choosing $s(i) = i$.