6
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – 6005 Aug 19 '16 at 2:12
  • 1
    $\begingroup$ 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). $\endgroup$ – zyx Aug 20 '16 at 20:40
  • $\begingroup$ Very cool result. Thanks. $\endgroup$ – 6005 Aug 21 '16 at 8:06
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}| $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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