MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we have two sets of data, $X$ and $Y$, each of which contains $10$ positive numbers. Now let us order the data sets $X=\left\{ x_{1},\cdots,x_{10}\right\}$, $x_{1}\ge\cdots\ge x_{10}>0$ and $Y=\left\{ y_{1},\cdots,y_{10}\right\}$, $y_{1}\ge\cdots\ge y_{10}>0$ and define $d:=\sum_{k=1}^{10}\left|x_{i_{k}}-y_{j_{k}}\right|$, that is the sum of the distances of the numbers in pairs from the two data sets. Does anyone know how to prove that $d$ achieves its minimum when $i_{k}=j_{k}=k$ for $1\le k\le10$, or is there any counter example if it is not true? Thanks.

share|cite|improve this question
same question was posted and was answered here:… – Paul Jan 1 '12 at 11:29

Here is a slightly more general proof.

Let $x$ be any vector in $R^n$. Let $x^\downarrow$ denote the vector obtained from $x$ by sorting its entries in decreasing order, so that $x_1^\downarrow \ge x_2^\downarrow \ge \cdots \ge x_n^\downarrow$. Now, let $x, z \in R^n$, and consider $x+z$. Clearly, if we apply the same permutation to $x$ and $z$ separately, the entire sum $x+z$ is also permuted the same way. Hence, we may assume wlog that $x=x^\downarrow$. Now, let $x$ be as in your question above, and let $z=-y$.

Recall now the concept of majorization. A quick calculation (also see Theorem II.4.2 of Matrix Analysis by R. Bhatia) shows that $$x^\downarrow + z^\uparrow \prec x + z$$ (since we assumed wlog that $x=x^\downarrow$); also since $y=-z$ we obtain

$$x^\downarrow - y^\downarrow \prec x - y.$$

But this majorization implies that for any symmetric gauge function $G$, we have $$G(x^\downarrow-y^\downarrow) \le G(x-y).$$ This then implies the original minimization claim if we choose $G=\|\cdot\|_1$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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