¿la clasificación minimiza la distancia?

Question

Supongamos $x,y \in \mathbb{R}^n$ . Supongamos que tenemos un algoritmo de ordenación que ordena $x \to X: \{ x_i \}_{i=1}^n = \{ X_i \}_{i=1}^n $

y para cada $1 \leq i \leq j \leq n$ , $X_i \leq X_j$ .

Lo mismo ocurre con $Y$ .

¿Es cierto que $||X-Y||_2^2 \leq ||x-y||_2^2$ ? Si la respuesta es afirmativa, demuéstrelo. Si no, dé un contraejemplo.

Muchas gracias.

p/s: esto es lo que he conseguido hasta ahora: transformación equivalente

$\sum_{i=1}^n (X_i -Y_i)^2 \leq \sum_{i=1}^n (x_i -y_i)^2$

Answer 1

Tenemos $\sum_{i=1}^{n}(X_i - Y_i)^2 \leq \sum_{i=1}^{n}(x_i - y_i)^2 \iff X_1Y_1 + ... + X_nY_n \geq X_1Y_{\sigma(1)} + ... + X_nY_{\sigma(n)}$ tras cierta expansión y reordenación, donde $\sigma$ representa la permutación de $[n]$ correspondientes a las listas sin clasificar. Más concretamente, dejamos que $\sigma$ sea tal que $\forall k \in [n]$ , $(X_k, Y_{\sigma(k)})$ es equivalente a un par único $(x_i,y_i)$ . $X_1Y_1 + ... + X_nY_n \geq X_1Y_{\sigma(1)} + ... + X_nY_{\sigma(n)}$ se deduce inmediatamente de la desigualdad de reordenación (véase: https://en.wikipedia.org/wiki/Rearrangement_inequality ), ya que $X_1 \leq ... \leq X_n$ y $Y_1 \leq ... \leq Y_n$ .