Deje que $x_1,\ldots ,x_n$ sea $n$ puntos distintos en $\mathbb{R}^3$ . Considere la $n\times n$ matriz simétrica real $A$ definida por $A_{ij}:=|x_i-x_j|$ . Me gustaría mostrar que
PS
Gracias por cualquier sugerencia.
Respuesta
¿Demasiados anuncios?
Chris Benard
Puntos
1430
$\def\RR{\mathbb{R}}$Experimentos numéricos sugieren que esta matriz es negativo semidefinite en el avión $\sum v_i=0$. Específicamente, se generó un 20 conjuntos de 10 puntos cada uno, dibujado de manera uniforme desde la unidad de cubo, y esto era cierto, cada vez. Repetí el experimento con los puntos 2, 4 y 5 dimensiones, y lo mismo.
Yo me acordé de esta respuesta por Noam Elkies , pero no puede hacerse una precisión de la conexión.
Cambio de la respuesta a la CW para escribir darij la prueba de los comentarios. Vamos a mostrar que:
Si $x_i$ cualquier $n$ puntos en $\RR^d$ e $v_i$ son cualquier escalares con $\sum v_i=0$, a continuación, $\sum v_i v_j |x_i-x_j| \leq 0$ y
Si el $x_i$ son distintos y el $v_i$ no son todos los $0$, hemos de desigualdad estricta.
La última muestra que la matriz de $\left[ |x_i-x_j| \right]$ veces el vector $\left[ v_i \right]$ es distinto de cero. Empecemos, sin embargo, en la prueba de los ex. Nos dirigimos a la cuestión de cuándo cero se produce después de que la línea horizontal.
Empezamos con el promedio truco: Por rotación y el escalado de la invariancia, podemos ver que hay algunos positivos $c$ tales que $$\int_{|w|=1} \left| \langle w \cdot x \rangle \right| = c |x|.$$ Así $$\sum v_i v_j |x_i-x_j| = c^{-1} \int_{|w|=1} \sum v_i v_j \left| \langle w \cdot (x_i-x_j) \rangle \right|$$ y por lo tanto es suficiente para mostrar $\sum v_i v_j \left| \langle w \cdot (x_i-x_j) \rangle \right|\leq 0$ para un determinado vector de $w$. Ahora, $w \cdot (x_i-x_j)$ sólo depende de las proyecciones ortogonales de a$x_i$ e $x_j$ sobre la línea de $\RR w$, por lo que podemos (y hacer) asumir todas las $x_i$ se encuentran en una recta. Nuestro objetivo ahora es mostrar, por cualquier $n$ valores $x_i \in \RR$que $\sum v_i v_j |x_i-x_j| \leq 0$.
Tenemos $|z| = \max(z,0) + \max(-z,0)$, lo $\sum v_i v_j |x_i-x_j|=2 \sum v_i v_j \max(x_i-x_j,0)$. Usamos la notación $\left[ \mbox{statement} \right]$ a la media de $1$ si la afirmación es verdadera y $0$ si es falso. Así $$\max(x_i-x_j,0) = \int_{t \in \RR} \left[x_j < t < x_i \right] dt$$ y $$\sum_{i,j} v_i v_j \max(x_i-x_j,0) = \int_{t \in \RR} \sum_{i,j} v_i v_j \left[x_j < t < x_i \right] dt.$$ So it is enough to show that, for any $t$, tenemos $$\sum_{x_i < t < x_j} v_i v_j \leq 0 . $$ Deje $I = \{ i : x_i < t \}$ e $J = \{ i : x_j > t \}$. (Para casi todos los $t$, ninguno de los $x_i$ igual $t$, por lo que podemos ignorar el límite de caso). Entonces $$\sum_{x_i < t < x_j} v_i v_j = \sum_{i \in I,\ j \in J} v_i v_j = \left( \sum_{i \in I} v_i \right) \left( \sum_{j \in J} v_j \right) = - \left(\sum_{i \in I} v_i \right)^2 \leq 0 .$$ En la última igualdad, por fin hemos utilizado la hipótesis de $\sum v_k=0$.
Ahora, vamos a considerar lo que sucede para los distintos $x_i$. Mientras la $x_i$ como distinto, casi como $w$, las proyecciones ortogonales de la $x_i$ a $\RR w$ permanecerá distintas. Con el fin de obtener $0$, debemos obtener la $0$ a partir de todas estas opciones de $w$. Digamos que las proyecciones ortogonales son ordenados como $x_1 < x_2 < \cdots < x_n$. Una vez más, debemos obtener la $0$ de cada elección de $t$. Así que debemos tener $\left( \sum_{i=1}^k v_i \right)^2 =0$ para todos los $k$, y esto significa que todos los $v_i$ son cero.
