Distance of vectors versus distance of their difference vectors

Question

For any given $x \in \mathbb{R}^n$, let $\nabla{x} \in \mathbb{R}^{n \choose 2}$ be the vector whose $\{i,j\}$-th entry is $|x_i-x_j|$. I think the following claim is true.

Claim. If $f, g \in \mathbb{R}^n$ are vectors with zero mean, i.e., $$\sum_{i=1}^n f_i = \sum_{i=1}^n g_i = 0$$ and the angle between them is at most $\frac{\pi}{2}$, then $$\operatorname{dist} (\nabla{f},\nabla{g}) \ge \operatorname{dist}(f,g).$$

If anybody has any idea about how to prove this, please share it with me. Thanks.

Answer 1

Let $\mathrm x, \mathrm y \in \mathbb R^n$. Let $\mathrm P_1$ and $\mathrm P_2$ be $n \times n$ permutation matrices such that the entries of $\mathrm P_1 \mathrm x$ and $\mathrm P_2 \mathrm y$ are in non-decreasing order. Let

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

Let $\mathrm C$ be the $m \times n$ oriented incidence matrix of the (undirected) complete graph $K_n$ such that $\mathrm C \mathrm z$ is a nonnegative difference vector if and only if the entries of $\mathrm z \in \mathbb R^n$ are in non-decreasing order.

Using the Euclidean distance, the squared distance between the difference vectors is

$$\| \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)$$

where

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

is the (symmetric, positive semidefinite) Laplacian of $K_n$. The spectrum of $\mathrm L$ contains eigenvalue $n$ with multiplicity $n-1$ and eigenvalue $0$ with multiplicity $1$. The null space of $\mathrm L$ is spanned by $1_n$.

In the fortunate case where the same permutation puts both $\mathrm x$ and $\mathrm y$ in non-decreasing order, i.e., there exists an $n \times n$ permutation matrix $\mathrm P$ such that $\mathrm P \mathrm x$ and $\mathrm P \mathrm y$ are in non-decreasing order,

$$\| \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)$$

If $1_n^{\top} \mathrm x = 0$ and $1_n^{\top} \mathrm y = 0$, then $\mathrm x$ and $\mathrm y$ are orthogonal to the null space of $\mathrm L$ and, hence, $\mathrm x - \mathrm y$ is also orthogonal to the null space of $\mathrm L$. Thus,

$$\| \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$$

Since $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}$$

Note that the condition $\mathrm x^{\top} \mathrm y \geq 0$ (i.e., the angle between $\mathrm x$ and $\mathrm y$ is at most $\frac{\pi}{2}$) was not used.

Answer 2

Too long for a comment.

We can simplify the proposed inequality as follows.

Put $F=\sum_{i=1}^n f_i^2$, $G=\sum_{i=1}^n g_i^2$, and $H=\sum_{i=1}^n f_ig_i$. Remark that $H\ge 0$ and $$\|\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.$$

Similarly,

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

Let $\operatorname{dist}$ be Euclidean distance. Then
$$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.$$

So we have to show that

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

Applying Cauchy-Schwartz inequality, we can obtain a bit weaker result. Namely, we have

$$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}.$$

On the other hand, since $H\ge 0$, by the inequality between arithmetic and geometric means,

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

We can try to improve our bound as follows. Assume that $f$ and $g$ are non-zero, $0\le\alpha\le\tfrac {\pi}2$ be the angle between vectors $f$ and $g$, and $\nabla\alpha$ be the angle between vectors $\nabla f$ and $\nabla g$. Then $H=\sqrt{FG}\cos\alpha$ and

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

So it suffices to show that

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

This inequality holds at least when $\alpha=0$, because in this case vectors $f$ and $g$ are collinear, so the vectors $\nabla f$ and $\nabla g$ are collinear too and hence $\nabla\alpha=\alpha=0$.