$2\sum_{i,j} |x_i-y_j| \geq \sum_{i,j} (|x_i-x_j| + |y_i-y_j|)$?

Question

Let $x_1, \ldots, x_n$ and $y_1, \ldots, y_n$ be real numbers.

Question: Is $$2\sum_{i,j=1}^n |x_i-y_j| \geq \sum_{i,j=1}^n (|x_i-x_j| + |y_i-y_j|)$$ true?

Motivation: This is motivated from a physical problem. If the above inequality holds, then one can obtain that certain terms are suppressed exponentially.

My trial:

1. For small $n$, I randomly generated $x_i, y_i$ many times and checked that the inequality holds.

2. If the prefactor in LHS is 4, then I can prove the inequality as follows. For $k=1, \ldots, n$, we have $$|x_i-x_j| \leq |x_i-y_k| + |y_k-x_j|$$ and analogously $$|y_i-y_j| \leq |y_i-x_k| + |x_k - y_j|.$$ Averaging the above inequalities over all $k$ and summing over $i,j$ gives $$\sum_{i,j=1}^n (|x_i-x_j| + |y_i-y_j|) \leq 4 \sum_{i,j=1}^n |x_i-y_j|.$$

Answer 1

We can rewrite the RHS as follows:

$$2 \sum_{0<i<j\leq n}(|x_i-x_j|+|y_i-y_j|) $$

Now without loss of generality we can reorder each vector such that all the differences are non-negative (i.e in descending order)

$$2 \sum_{0<i<j\leq n}(x_i-x_j+y_i-y_j) = 2\sum_{0<i<j\leq n}((x_i-y_j)-(x_j-y_i))\\ =\sum_{i,j=1\leq n}(x_i-y_j)-\sum_{i,j=1\leq n}(x_j-y_i)$$

$$\sum_{i,j=1\leq n}(x_i-y_j)-\sum_{i,j=1\leq n}(x_j-y_i) \leq \sum_{i,j=1\leq n}|x_i-y_j| +\sum_{i,j=1\leq n}|x_j-y_i| = 2\sum_{i,j=1\leq n}|x_j-y_i|$$