# Distance of vectors versus distance of their difference vectors

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.

• how is is the "distance" of $\nabla f$ and $\nabla g$ defined? sum of difference of all elements squared? – Carlo Beenakker Apr 22 '17 at 11:44
• what if you take $f=(1,-1)$ and $g=(-1,1)$? Isn't then $\nabla f = \nabla g = (2)$, and their distance 0, while $dist(f,g)=2\sqrt{2}$? – Moritz Firsching Apr 22 '17 at 12:35
• This is the kind of claims that I start believing in only after I have done at least 10.000 random experiments without finding any counterexample... – Federico Poloni Apr 22 '17 at 12:42
• @Poloni. I have checked it for many more than 10.000 random functions. – j.s. Apr 22 '17 at 13:08
• @Rasberry: No, entries of $\nabla{f}$ indexed by all two-element subsets of ${\{1,...,n}\}$. – j.s. Apr 22 '17 at 19:21

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.

• Wasn't $\mathrm x^{\top} \mathrm y \geq 0$ a condition that was necessary, since otherwise a counterexample exists? (see my comment above, after which the OP added the condition). It is weird, that it would not be used, when trying to prove the statement. – Moritz Firsching Apr 26 '17 at 16:27
• @MoritzFirsching I did not quite prove the statement. I proved that the statement holds in the extremely special case where the same permutation puts both vectors in non-decreasing order. That is not the case in the counterexample you gave. I am still working on the general case, trying to find an use for $\rm x^\top y \geq 0$. – Rodrigo de Azevedo Apr 26 '17 at 16:33
• @RodrigodeAzevedo I see, now I understand your reasoning. – Moritz Firsching Apr 26 '17 at 16:40

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