Question

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.

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