Suponga que [math] X = \ {x_1, x_2, \ ldots, x_n \} [/ math] y [math] Y = \ {y_1, y_2, \ ldots, y_n \} [/ math] son ​​tales que [math] x_1 \ leq x_2 \ leq \ ldots \ leq x_n [/ math] y [math] y_1 \ geq y_2 \ geq \ ldots \ geq y_n [/ math]. Deje que [math] Z = \ {z_1, z_2, \ ldots, z_n \} [/ math] sea cualquier permutación de los elementos de [math] Y [/ math]. ¿Por qué es [math] \ sum_i (x_i-y_i) ^ 2 \ geq \ sum_i (x_i-z_i) ^ 2 [/ math]?

Answer 1

Prueba de boceto:

Como mostró Narendra, tenemos que demostrar que

[matemáticas] \ sum_i x_iy_i \ leq \ sum_i x_iz_i [/ ​​matemáticas].

Primero, suponga que [math] z_i [/ ​​math] es lo mismo que [math] y_i [/ ​​math] excepto que se intercambian dos valores. Más precisamente, hay dos índices [matemática] a, b \ in \ {1, \ ldots, n \} [/ matemática] de manera que [matemática] a <b [/ matemática], [matemática] z_a = y_b [/ matemática], [matemática] z_b = y_a [/ matemática] y [matemática] z_i = y_i [/ ​​matemática] para todos [matemática] a \ neq i \ neq b [/ matemática].

Así que ahora [math] x_iy_i [/ ​​math] y [math] x_iz_i [/ ​​math] también son lo mismo de todos [math] a \ neq i \ neq b [/ math], y solo tenemos que demostrar que

[matemáticas] x_ay_a + x_by_b \ leq x_az_a + x_bz_b = x_ay_b + x_by_a [/ math]

pero esto es equivalente a

[matemáticas] x_a (y_a-y_b) \ leq x_b (y_a-y_b) [/ matemáticas]

lo cual es claramente cierto ya que [math] y_a-y_b [/ math] no es negativo y [math] x_a \ leq x_b [/ math].

Una vez que tengamos eso, podemos proceder a hacer más y más de esas transposiciones (intercambiando dos elementos) siempre que intercambiemos pares decrecientes, como en el cálculo que acabamos de hacer, y la desigualdad deseada continúa siendo cierta. Finalmente, dado que cualquier permutación puede lograrse mediante una secuencia de tales intercambios, se sigue la conclusión de una permutación arbitraria. (Cada permutación es un producto de transposiciones, y los métodos como la ordenación de burbujas son tales que solo intercambia elementos en el orden correcto).

Answer 2

Necesitamos probar
[matemáticas] \ sum_ {i = 1} ^ {n} (x_i – y_i) ^ 2 \ geq \ sum_ {i = 1} ^ {n} {(x_i – z_i) ^ 2} [/ matemáticas]
= {expandir los cuadrados}
[matemáticas] \ sum_ {i = 1} ^ {n} {x_i ^ 2 + y_i ^ 2 – 2x_iy_i} \ geq \ sum_ {i = 1} ^ {n} {x_i ^ 2 + z_i ^ 2 – 2x_iz_i} [ /matemáticas]
= {las sumas de cuadrados de [math] y_i [/ ​​math] y [math] z_i [/ ​​math] son ​​iguales ya que uno se obtiene reorganizando el otro}
[matemáticas] \ sum_ {i = 1} ^ {n} {x_iy_i} \ leq \ sum_ {i = 1} ^ {n} {x_iz_i} [/ matemáticas]

Tenga en cuenta que el signo de la desigualdad cambió en el último paso porque multipliqué ambos lados por -1. Si imagina x e y como vectores con x fijo en el espacio e y con una magnitud constante pero un ángulo variable con el eje principal. Luego, para obtener el producto de punto más grande, estos vectores deben alinearse entre sí, es decir, los componentes más pequeños de x se multiplican por componentes más pequeños de y y lo mismo ocurre con los componentes más grandes. Para obtener el valor más bajo del producto punto, los dos vectores deben apuntar en direcciones opuestas. El vector z simplemente está más alineado con el vector x que el vector y .

Realmente agradecería si alguien puede probar formalmente las declaraciones sobre los vectores. No sé cómo hacerlo formalmente.

Answer 3

Sea [math] x, y \ in \ mathbf {R} ^ n [/ math] como arriba y [math] P: \ mathbf {R} ^ n \ to \ mathbf {R} ^ n [/ math] una permutación .

Suponga primero que [matemáticas] x_1 \ lt x_2 \ lt \ ldots \ lt x_n [/ matemáticas] y [matemáticas] y_1 \ gt y_2 \ gt \ ldots \ gt y_n [/ matemáticas].

Como se mostró antes (por Narendra Joshi), es suficiente demostrar que si [math] (x, Py) \ leq (x, y) [/ math] luego [math] P = id [/ math], donde [math] id [/ math] es la permutación de identidad (no permuta nada) y [math] (\ cdot, \ cdot) [/ math] es el producto punto.

Deje que [math] (x, Py) [/ math] sea mínimo en todas las permutaciones [math] P [/ math]. Denote [math] z: = Py [/ math].

Ahora suponga que [matemáticas] P [/ matemáticas] no es la identidad. Luego hay un par con la propiedad [math] z_i> z_j [/ math] y [math] i> j [/ math]. También sabemos que [math] x_i> x_j [/ math]. Denote con [math] T [/ math] un intercambio de transposición [math] z_i [/ ​​math] y [math] z_j [/ math].
Entonces [matemáticas] (x, Tz) – (x, z) = x_i z_j + x_j z_i – x_i z_i – x_j z_j [/ matemáticas].

Entonces tenemos [math] (x, Tz) – (x, z) = (x_i -x_j) (z_j- z_i) <0 [/ math]
Esto es una contradicción con la minimidad de [math] (x, Py) [/ math] ya que [math] (x, (T \ circ P) y) [/ math] es más pequeño.
Entonces concluimos [matemáticas] P = id [/ matemáticas] y [matemáticas] (x, Qy)> (x, y) [/ matemáticas] para cada permutación [matemáticas] Q \ neq id [/ matemáticas].

Ahora suponga que [math] x, y \ in \ mathbf {R} ^ n [/ math] son ​​como en el problema, es decir, sus componentes no necesariamente aumentan estrictamente resp. decreciente.
Luego, elija números reales arbitrarios [math] a_1 \ lt a_2 \ lt \ ldots \ lt a_n [/ math] y [math] k \ in \ mathbf {N}. [/ Math]
Establezca [matemáticas] \ tilde {x_i}: = x_i + \ dfrac {a_i} {k} [/ matemáticas] y [matemáticas] \ tilde {y_i}: = y_i – \ dfrac {a_i} {k} [/ matemáticas] . Ahora los componentes de [math] \ tilde {x} [/ math] y [math] \ tilde {y} [/ math] están aumentando estrictamente resp. decreciente.
De acuerdo con eso, acabamos de demostrar [matemáticas] (\ tilde {x} – \ tilde {y}, \ tilde {x} – \ tilde {y})> (\ tilde {x} -Q \ tilde {y} , \ tilde {x} -Q \ tilde {y}) [/ math] para cada permutación [math] Q \ neq id [/ math].
Ahora deje que [math] k \ to \ infty [/ math]. Los productos de puntos y los operadores lineales (acotados) (permutaciones en este caso) son continuos, y [matemática] \ tilde {x} \ to x [/ matemática] y [matemática] \ tilde {y} \ a y [/ matemática] si [matemáticas] k \ a \ infty [/ matemáticas]. Por lo tanto, al pasar a los límites obtenemos la declaración requerida.