Distancia de los vectores frente a la distancia de sus vectores diferenciales

Question

Para cualquier $x \in \mathbb{R}^n$ , dejemos que $\nabla{x} \in \mathbb{R}^{n \choose 2}$ sea el vector cuyo $\{i,j\}$ -la quinta entrada es $|x_i-x_j|$ . Creo que la siguiente afirmación es cierta.

Reclamación. Si $f, g \in \mathbb{R}^n$ son vectores con media cero, es decir, $$\sum_{i=1}^n f_i = \sum_{i=1}^n g_i = 0$$ y el ángulo entre ellos es como máximo $\frac{\pi}{2}$ entonces $$\operatorname{dist} (\nabla{f},\nabla{g}) \ge \operatorname{dist}(f,g).$$

Si alguien tiene alguna idea sobre cómo probar esto, por favor compártala conmigo. Gracias.

Answer 1

Dejemos que $\mathrm x, \mathrm y \in \mathbb R^n$ . Sea $\mathrm P_1$ y $\mathrm P_2$ sea $n \times n$ matrices de permutación tales que las entradas de $\mathrm P_1 \mathrm x$ y $\mathrm P_2 \mathrm y$ están en no decreciente orden. Sea

$$m := \binom{n}{2}$$

Dejemos que $\mathrm C$ sea el $m \times n$ orientado matriz de incidencia del (no dirigido) gráfico completo $K_n$ tal que $\mathrm C \mathrm z$ es un no negativo si y sólo si las entradas de $\mathrm z \in \mathbb R^n$ están en no decreciente orden.

Utilizando la distancia euclidiana, la distancia al cuadrado entre los vectores de diferencia es

$$\| \mathrm C \mathrm P_1 \mathrm x - \mathrm C \mathrm P_2 \mathrm y \|_2^2 = \| \mathrm C \left( \mathrm P_1 \mathrm x - \mathrm P_2 \mathrm y \right) \|_2^2 = \left( \mathrm P_1 \mathrm x - \mathrm P_2 \mathrm y \right)^{\top} \mathrm C^{\top} \mathrm C \left( \mathrm P_1 \mathrm x - \mathrm P_2 \mathrm y \right)$$

donde

$$\mathrm C^{\top} \mathrm C = n \mathrm I_n - 1_n 1_n^{\top} =: \mathrm L$$

es la (simétrica, semidefinida positiva) Laplaciano de $K_n$ . El espectro de $\mathrm L$ contiene el valor propio $n$ con multiplicidad $n-1$ y el valor propio $0$ con multiplicidad $1$ . El espacio nulo de $\mathrm L$ está atravesado por $1_n$ .

En el afortunado caso de que el mismo La permutación pone a ambos $\mathrm x$ y $\mathrm y$ en orden no decreciente, es decir, existe un $n \times n$ matriz de permutación $\mathrm P$ tal que $\mathrm P \mathrm x$ y $\mathrm P \mathrm y$ están en no decreciente orden,

$$\| \mathrm C \mathrm P \mathrm x - \mathrm C \mathrm P \mathrm y \|_2^2 = \left( \mathrm x - \mathrm y \right)^{\top} \underbrace{\mathrm P^{\top} \mathrm L \, \mathrm P}_{= \mathrm L} \left( \mathrm x - \mathrm y \right) = \left( \mathrm x - \mathrm y \right)^{\top} \mathrm L \left( \mathrm x - \mathrm y \right)$$

Si $1_n^{\top} \mathrm x = 0$ y $1_n^{\top} \mathrm y = 0$ entonces $\mathrm x$ y $\mathrm y$ son ortogonal al espacio nulo de $\mathrm L$ y, por lo tanto, $\mathrm x - \mathrm y$ también es ortogonal al espacio nulo de $\mathrm L$ . Así,

$$\| \mathrm C \mathrm P \mathrm x - \mathrm C \mathrm P \mathrm y \|_2^2 = \left( \mathrm x - \mathrm y \right)^{\top} \mathrm L \left( \mathrm x - \mathrm y \right) \geq \lambda_{n-1} (\mathrm L) \| \mathrm x - \mathrm y \|_2^2 = n \, \| \mathrm x - \mathrm y \|_2^2$$

Desde $n \geq 1$ ,

$$\boxed{\| \mathrm C \mathrm P \mathrm x - \mathrm C \mathrm P \mathrm y \|_2 \geq \sqrt{n} \, \| \mathrm x - \mathrm y \|_2 \geq \| \mathrm x - \mathrm y \|_2}$$

Tenga en cuenta que la condición $\mathrm x^{\top} \mathrm y \geq 0$ (es decir, el ángulo entre $\mathrm x$ y $\mathrm y$ es como máximo $\frac{\pi}{2}$ ) no se utilizó.

Answer 2

Demasiado largo para un comentario.

Podemos simplificar la desigualdad propuesta como sigue.

Poner $F=\sum_{i=1}^n f_i^2$ , $G=\sum_{i=1}^n g_i^2$ y $H=\sum_{i=1}^n f_ig_i$ . Obsérvese que $H\ge 0$ y $$\|\nabla f\|^2_2=\sum_{i,j=1}^n (f_i-f_j)^2=\sum_{i,j=1}^n f_i^2+f_j^2-2f_if_j=$$ $$2nF-2\sum_{i=1}^n f_i\sum_{j=1}^n f_j=2nF-2\sum_{i=1}^n f_i\cdot 0=2nF.$$

De la misma manera,

$$\|\nabla g\|^2_2=\sum_{i,j=1}^n (g_i-g_j)^2=2nG.$$

Dejemos que $\operatorname{dist}$ es la distancia euclidiana. Entonces
$$2(\operatorname{dist}(\nabla{f},\nabla{g}))^2-2(\operatorname{dist}(f,g))^2=$$ $$\sum_{i,j=1}^n \left(|f_i-f_j|-|g_i-g_j|\right)^2-2\sum_{i=1}^n (f_i-g_i)^2=$$ $$\sum_{i,j=1}^n (f_i-f_j)^2+(g_i-g_j)^2-2|f_i-f_j|\cdot|g_i-g_j|-2\sum_{i=1}^n f_i^2+g_i^2-2f_ig_i=$$ $$(2n-2)(F+G)-2\sum_{i,j=1}^n |f_i-f_j|\cdot|g_i-g_j|+4H.$$

Así que tenemos que demostrar que

$$(n-1)(F+G)+2H\ge\sum_{i,j=1}^n |f_i-f_j|\cdot|g_i-g_j|=S.$$

Aplicando la desigualdad de Cauchy-Schwartz, podemos obtener un resultado un poco más débil. A saber, tenemos

$$S=\sum_{i,j=1}^n |f_i-f_j|\cdot|g_i-g_j|\le \left(\sum_{i,j=1}^n (f_i-f_j)^2\right)^{1/2}\left(\sum_{i,j=1}^n (f_i-f_j)^2\right)^{1/2}=2n\sqrt{FG}.$$

Por otra parte, dado que $H\ge 0$ por la desigualdad entre las medias aritméticas y geométricas,

$$(n-1)(F+G)+2H\ge 2(n-1)\sqrt{FG}.$$

Podemos intentar mejorar nuestro atado de la siguiente manera. Supongamos que $f$ y $g$ son distintos de cero, $0\le\alpha\le\tfrac {\pi}2$ sea el ángulo entre los vectores $f$ y $g$ y $\nabla\alpha$ sea el ángulo entre los vectores $\nabla f$ y $\nabla g$ . Entonces $H=\sqrt{FG}\cos\alpha$ y

$$S=\sqrt{\|\nabla f\|^2_2\|\nabla g\|^2_2}\cos\nabla\alpha=2n\sqrt{FG}\cos\nabla\alpha.$$

Por lo tanto, basta con demostrar que

$$2(n-1)+2\cos\alpha\ge 2n\cos\nabla\alpha.$$

Esta desigualdad se mantiene al menos cuando $\alpha=0$ porque en este caso los vectores $f$ y $g$ son colineales, por lo que los vectores $\nabla f$ y $\nabla g$ son también colineales y, por tanto, $\nabla\alpha=\alpha=0$ .