Suppose we have two sets of real numbers $x$ and $y$ each with $n$ elements. Suppose I order the sets such that $x_{(1)} \geq x_{(2)} \geq x_{(3)} \geq ... \geq x_{(n)}$ and $y_{(1)} \geq y_{(2)} \geq y_{(3)} \geq ... \geq y_{(n)}$. I have been struggling to show that:
$|x_{(k)} - y_{(k)}| \leq ||x-y||_2$
In other words:
$|x_{(k)} - y_{(k)}| \leq \sqrt{\sum_{i=1}^n(x_i-y_i)^2}$
Does anyone have any ideas?
In fact, you can prove a much stronger inequality: $$ ||\tilde{x} - \tilde{y}||^2\le ||{x} - {y}||^2, $$ where $\tilde x$ and $\tilde y$ are the order statistics vectors. Just expand the squares and use the rearrangement inequality.