13
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ how is is the "distance" of $\nabla f$ and $\nabla g$ defined? sum of difference of all elements squared? $\endgroup$ Apr 22, 2017 at 11:44
  • 6
    $\begingroup$ 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}$? $\endgroup$ Apr 22, 2017 at 12:35
  • 3
    $\begingroup$ 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... $\endgroup$ Apr 22, 2017 at 12:42
  • 3
    $\begingroup$ @Poloni. I have checked it for many more than 10.000 random functions. $\endgroup$
    – j.s.
    Apr 22, 2017 at 13:08
  • 2
    $\begingroup$ @Rasberry: No, entries of $\nabla{f}$ indexed by all two-element subsets of ${\{1,...,n}\}$. $\endgroup$
    – j.s.
    Apr 22, 2017 at 19:21

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Apr 26, 2017 at 16:27
  • $\begingroup$ @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$. $\endgroup$ Apr 26, 2017 at 16:33
  • $\begingroup$ @RodrigodeAzevedo I see, now I understand your reasoning. $\endgroup$ Apr 26, 2017 at 16:40
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.