Desigualdad que implica cambio: $ \sum_{i=1}^n |x_i - y_{\sigma(i)}| \ge \sum_{i=1}^n |x_i - y_i|. $

Question

Si $x_1 \ge x_2 \ge \cdots \ge x_n$ $y_1 \ge y_2 \ge \cdots \ge y_n$ son números reales, y $\sigma$ es cualquier permutación, entonces $$ \sum_{i=1}^n |x_i - y_{\sigma(i)}| \ge \sum_{i=1}^n |x_i - y_i|. $$ Este debe ser un conocido de la desigualdad. Lo que se llama, y cómo es probada? (Sólo de referencia es ACEPTAR).

---

Las condiciones son similares a la reordenación de la desigualdad. La desigualdad es una simple declaración acerca de la minimización de la $\ell^1$ distancia entre una secuencia finita y cualquier reordenamiento de otra secuencia finita.

Busqué por los alrededores y hacer clic a través de varias páginas, pero no podía encontrar algo relevante. Si es cierto, tal vez una prueba podría ser construido por la descomposición de la permutación en una secuencia de transposiciones.

Answer 1

Podemos probarlo de una manera similar como la desigualdad de rearangement. Hay solamente finito muchas posibilidades para $\sigma$, por lo que se logra un mínimo, elegir $\sigma$ para que tenga el número mínimo de inversiones de entre todas las permutaciones que minimizan la expresión.

Supongamos por contradicción hay $i<j$ $\sigma(i)>\sigma(j)$. Nota $|x_i-y_{\sigma_i}|+|x_j-y_{\sigma(j)}|\geq |x_i-y_{\sigma(j)}|+|x_j-y_{\sigma(i)}|$.

Así que la permutación que transpone $i$ y $j$ también debe minimizar la expresión y tiene menos inversiones, una contradicción.

Answer 2

Para cualquier función convexa, como $f(x) = |x|$,

$$ \sum f(x_i - y_{\sigma(i)}) \geq \sum f(x_i - y_i)$$

debido a $(x_i - y_{\sigma(i)})$ majorizes $(x_i - y_i)$.

Una referencia es el primer teorema de, 6.Una.1, en el capítulo 6 de Olkin y Marshall en su libro sobre majorization, aplicada a las secuencias de $x_i$$-y_i$.

Ellos atribuyen el resultado a una 1972 artículo de Peter W Día en las formas generales de la reordenación de la desigualdad, y dar una prueba para los vectores de números reales. Día del artículo es acerca de situaciones de carácter más general con ordenó abelian grupos. La desigualdad real de los vectores debe haber sido conocido antes a muchas personas.

Answer 3

NP-duro dio una excelente respuesta, sino que la elimina. Voy a pegar aquí (en la comunidad de la wiki).

---

Usted puede estar interesado en los siguientes desigualdad.

Deje $f_1(x), f_2(x), \cdots, f_n(x): \mathbb{R} \rightarrow \mathbb{R}$ funciones tales que para $\forall 1 \leq k < n$, $f_{k+1}(x) - f_k(x)$ es no decreciente con respecto a $x$. Además, vamos a $y_1 \geq y_2 \geq \cdots \geq y_n$. A continuación, $$ \sum_{k}f_k(y_{n-k+1}) \geq \sum_k f_k(y_{\sigma(k)}) \geq \sum_k f_k(y_k) $$

El libro "el cauchy-schwarz master class" no dar un nombre formal de esta desigualdad, pero sólo tiene que llamar a "no-lineal de reordenamiento de la desigualdad". Ver p.81 del libro.

---

Me muestra una prueba basada en la desigualdad anterior.

Prueba.Vamos $$ f_k(x) = |x_k - x| $$ Entonces $$ f_{k+1}(x) - f_k(x) = \begin{cases} x_{k+1}-x_{k} &\text{if}\ x \leq x_{k+1} \\ 2x - x_{k+1} - x_k &\text{if}\ x_{k+1} < x < x_k\\ x_{k} - x_{k+1} &\text{otherwise} \end{casos} $$ es no decreciente, por lo tanto la desigualdad a la que se aplica. Es decir, $$ \sum_k |x_k - y_k| \leq \sum_k |x_k - y_{\sigma(k)}| \leq \sum_k |x_k - y_{n-k+1}| $$