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 *ascending* order.

Let $m := \binom{n}{2}$. Let $\mathrm C$ be the $m \times n$ *oriented* [incidence matrix][1] of the (undirected) [complete graph][2] $K_n$ such that $\mathrm C \mathrm z$ is a *nonnegative* difference vector if the entries of $\mathrm z \in \mathbb R^n$ are in *ascending* 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][3] 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 ascending order, i.e., there exists an $n \times n$ permutation matrix $\mathrm P$ such that the entries of $\mathrm P \mathrm x$ and $\mathrm P \mathrm y$ are in *ascending* 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, 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$$

If $n \geq 2$, then

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

  [1]: https://en.wikipedia.org/wiki/Incidence_matrix
  [2]: https://en.wikipedia.org/wiki/Complete_graph
  [3]: https://en.wikipedia.org/wiki/Laplacian_matrix