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.


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

| cite | improve this answer | |

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.