Esta es una respuesta que falta un argumento de necesidad o suficiencia (ver abajo) - ¡por favor añade si lo tienes!
Motivación:
Como buscamos un mínimo de $\sum_{i=1}^n\sum_{j=1}^n{(|x_{i}-x_{j}|-|y_{i}-y_{j}|)^2}$, el objetivo podría ser hacer que la suma sea cero, lo que exigiría que todos los términos fueran cero. Tenemos que $|x_{i}-x_{j}|=|y_{i}-y_{j}|$ para todos $\{i,j\}$, si, para todos $\{i\}$, se cumple: $y_i = x_i + d$ con alguna distancia fija $d$. Del mismo modo, se podría elegir la condición $y_i = - x_i + d$.
Intentando cumplir las condiciones, vemos que este intento falla: Necesitamos garantizar que $0 = \sum_{i=1}^{n}{y_{i}}=\sum_{i=1}^{n}{(d + x_i)}= n d + \sum_{i=1}^{n}{x_i} = nd$ lo cual da como resultado $d=0$ y por lo tanto $x_i = y_i$. Además, necesitamos $ 0 = \sum_{i=1}^{n}{x_{i} y_i}=\sum_{i=1}^{n}{x_{i}^2}$ pero este último es $1$ así que tenemos una contradicción y nuestro objetivo falla.
Sin embargo, esta motivación aún podría funcionar si se modifica. Como muestran las observaciones de @Hans Engler (ver comentarios), en el mínimo, todas menos un punto $(x_i, y_i)$ están en una línea recta. Así que tomemos esto como la única condición en lo que sigue.
Respuesta:
Como se expuso anteriormente en la motivación, supongamos que, en el mínimo, para todos $\{i = 1 \cdots n-1\}$ se cumple: $y_i = x_i + d$ con alguna distancia fija $d$. Esto es en realidad todo lo que se está suponiendo.
Definimos una media $m$ de los primeros $(n-1)$ valores $x_i$, es decir, $\sum_{i=1}^{n-1}x_i = (n-1)m$. Entonces la condición $0 = \sum_{i=1}^{n}x_i$ da como resultado $x_n = -(n-1)m$. Del mismo modo, la condición $0 = \sum_{i=1}^{n}y_i = \sum_{i=1}^{n-1}(x_i + d) + y_n= (n-1)(m+d) + y_n$ da como resultado $y_n = -(n-1)(m+d)$.
Ahora consideramos las condiciones $\sum_{i=1}^{n}{x_{i}^2}=\sum_{i=1}^{n}{y_i}^2=1$. Evaluamos $$ 1 = \sum_{i=1}^{n}{y_i}^2 = \sum_{i=1}^{n-1}(x_i + d)^2 + y_n^2\\ = (n-1)d^2 + 2 d (n-1)m + \sum_{i=1}^{n-1}{x_i}^2 + y_n^2 \\ = (n-1)d^2 + 2 d (n-1)m + 1 - x_n^2 + y_n^2 \\ = 1 - n(n-1)d(d+2m) $$ lo que implica que $d = -2m$ y por lo tanto $y_n = (n-1)m = -x_n$.
La última condición es $$ 0 = \sum_{i=1}^{n}{x_{i}y_i}=\sum_{i=1}^{n-1}(x_i + d)x_i + x_n y_n\\ = 1 - x_n^2 + d(n-1)m + x_n y_n = 1 - (n-1)^2 m^2 - 2(n-1)m^2 - (n-1)^2 m^2 \\ = 1 - 2 n(n-1)m^2 $$ lo que da como resultado $m = \sqrt{\frac{1}{2 n (n-1)}}$ (o el negativo). Así que todas las condiciones se pueden cumplir con las elecciones dadas de $d$ y $m$.
Ahora calculemos la suma objetivo $S = \sum_{i=1}^n\sum_{j=1}^n{(|x_{i}-x_{j}|-|y_{i}-y_{j}|)^2}$. Con nuestra condición supuesta tenemos, en el mínimo, $S_{min} = 2 \sum_{i=1}^{n-1}{(|x_{i}-x_{n}|-|x_{i}+d-y_{n}|)^2} = 2 \sum_{i=1}^{n-1}{(|x_{i} - m +nm|-|x_{i}- m - nm|)^2} \; . $ Ahora observamos la suma de varianza $\sum_{i=1}^{n-1} (x_i - m)^2 = 1 - x_n^2 - (n-1)m^2 = 1 - n(n-1)m^2 = \frac12 \; .$ A partir de esto, tenemos que $|x_i - m| \le \frac{1}{\sqrt{2}} = \sqrt{n(n-1)} m < nm $ lo cual nos permite calcular, utilizando de nuevo la suma de varianza,
$$ S_{min} = 2 \sum_{i=1}^{n-1}(|x_{i} - m +nm|-|x_{i}- m - nm|)^2 \\ = 2 \sum_{i=1}^{n-1}{(x_{i} - m +nm - (nm + m - x_i))^2}\\ = 2 \sum_{i=1}^{n-1}{(2 x_i- 2 m)^2} = 8 \sum_{i=1}^{n-1}{(x_i-m)^2} = 8 \cdot \frac 12 = 4$$ Esto establece la afirmación.
Trabajo restante
Todavía queda por demostrar que la única suposición usada, es decir, que, en el mínimo, para todos $\{i = 1 \cdots n-1\}$ se cumple: $y_i = x_i + d$ con alguna distancia fija $d$, es realmente una condición necesaria o suficiente para el mínimo. Como se dijo al principio - ¡por favor añade argumentos si los tienes!
