## Minimum distance between two data sets

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

2
same question was posted and was answered here: math.stackexchange.com/questions/95546/… – Paul Jan 1 2012 at 11:29

## 1 Answer

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 26, "mathjax_display_tex": 3, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9400469660758972, "perplexity_flag": "head"}