Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
2  
same question was posted and was answered here: math.stackexchange.com/questions/95546/… –  Paul Jan 1 '12 at 11:29
add comment

1 Answer 1

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|improve this answer
add comment

Your Answer

 
discard

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.