# Minimum distance between two data sets

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.

-
How are $i_k$ and $j_k$ defined? Do you already have some ordering for $X$ and $Y$ and then assign a new one to them? –  Alex Becker Jan 1 '12 at 8:27
@Alex. ${i_1,\cdots,i_{10}}$ is a permutation of ${1, 2, \cdots, 10}$, similarly for ${j_1,\cdots,j_{10}}$. –  098 Jan 1 '12 at 8:34
Have you tried applying the triangle inequality ($|a+b|\leq |a|+|b|$)? –  Alex Becker Jan 1 '12 at 8:38
@Alex. Yes, I have tried that. But I couldn't prove or disprove it. –  098 Jan 1 '12 at 8:56
Lets consider the example of two sets, $X_2$ and $Y_2$, each of which have two elements which satisfy $x_1\geq x_2\geq 0, y_1\geq y_2\geq 0$. Then $$d=\sum_{k=1}^{2}\left|x_{i_{k}}-y_{j_{k}}\right| = |x_{i_1}-y_{j_1}|+|x_{i_2}-y_{j_2}|$$ and to determine all possible values we have only two cases to check, one where $i_k=j_k, k\in \{1,2\}$ and the other in which $i_k\neq j_k, k\in \{1,2\}$. In the first case, $d = |x_1 - y_1| + |x_2 - y_2|$, and in the second case $d = |x_1 - y_2| + |x_2 - y_1|$, which we break down into two further cases: $x_1 \geq y_1$ and $x_1\leq y_1$. In the first case $$|x_1 - y_2| + |x_2 - y_1| = |x_1 - y_1| + |y_1-y_2| + |x_2 - y_1|\geq |x_1 - y_1|+|x_2-y_2|$$ while in the second we have $x_2\leq x_1\leq y_1$ so $$|x_1 - y_2| + |x_2 - y_1| = |x_1 - y_2| + |x_1 - y_1| + |x_2 - x_1|\geq |x_1 - y_1|+|x_2-y_2|$$ with the inequality in both cases coming from the triangle inequality. Certainly, this method of case-by-case analysis is too laborious to use directly for your problem. However, the case of two elements turns out to be the crucial one in order to apply induction, which proves the theorem for any number of elements. The key observation is that the above proof can be modified to show that $$d=\sum_{k=1}^{n}\left|x_{i_{k}}-y_{j_{k}}\right| = |x_{i_1}-y_{j_1}|+\sum_{k=2}^{n}\left|x_{i_k}-y_{j_k}\right|$$ is at least the result of using some permutation such that $i_1=j_1$. I leave the details of this to you.
This works fine for the case where there are two elements in the set. But, the induction step is not straight-forward. Only 2 possible cases here are $x_1\le y_1$ and vice versa. But as the number of elements increases, this breakdown alone will not be sufficient in my opinion. –  Nikhil Bellarykar Jan 1 '12 at 9:38
@NikhilBellarykar Inductive case: In the case where $x_{i_k}=y_{j_k}$ for some $k$, we are done. Otherwise, we have some permutation $x_{i_k'}$ such that $x_{i_k'}=x_{i_k}$ for all but two values of $k$ and for one of these values of $k$, $x_{i_k'}=y_{j_k}$. –  Alex Becker Jan 1 '12 at 9:45
@Alex. Did you mean $i_k=j_k$ in your comment? How would you do by induction about the case $|x_1-y_2|+\cdots+|x_9-y_{10}|+|x_{10}-y_1|$? Thanks! –  098 Jan 2 '12 at 8:24
@098 Yes I did, sorry. In that case I would switch $y_2$ and $y_1$ to get $|x_1-y_1|+9$ terms, which cannot increase the value of $d$ by a similar proof as the one I gave for the $n=2$ case, with $x_{10}$ substituted for $x_2$. –  Alex Becker Jan 2 '12 at 8:28