How prove this inequality: $\sum_{i,j=1}^{n}|x_{i}+x_{j}|\ge n\sum_{i=1}^{n}|x_{i}|$?

The following solution has been presented by one of the participants of Romanian team selection test. Essentially, the problem boils down to the following completing the square. Note that $|x_i|+|x_j|-|x_i+x_j|=0$ when $x_ix_j\ge 0$ and $=2\min{(|x_i|,|x_j|)}$ when $x_ix_j< 0.$ With this in hands, we can estimate \begin{align} &\phantom{=}\sum_{1\leq i,j\leq n}(|x_i|+|x_j|-|x_i+x_j|) \le \sum_{x_ix_j< 0}2\min\{|x_i|,|x_j|\}\\ &=4\sum_{x_i>0>x_j}\min\{x_i,-x_j\} \leq 4\sum_{x_i>0>x_j}\sqrt{-x_ix_j}\\ &\le 4\sum_{x_i>0}\sqrt{x_i}\sum_{0>x_j}\sqrt{-x_j} \leq \left (\sum_{x_i>0}\sqrt{x_i}+\sum_{0>x_j}\sqrt{-x_j}\right )^2\\ &= \left (\sum_{1\leq k\leq n}\sqrt{|x_k|}\right )^2 \leq n\sum_{1\leq k\leq n}|x_k|. \end{align} And the result follows.

The inequality asked is a consequence of $$ \sum_{i,j} |x_i + x_j| \geq \sum_{i,j} |x_i-x_j|, \quad(\star) $$ a proof of which can be found below, or there (in a more general case).

Indeed, because of the convexity of $|\cdot|$ we have $$ \forall (i,j),\qquad |x_i| \leq \frac{|x_i+x_j|+|x_i-x_j|}{2}, $$ so that, when summing over $i,j$ the inequality $(\star)$ yields $$ n\sum_{i} |x_i| \leq \frac{1}{2}\sum_{i,j} |x_i+x_j| + \frac{1}{2}\sum_{i,j} |x_i-x_j| \leq \sum_{i,j} |x_i+x_j|. $$

---

For the sake of completness, I give a proof of $(\star)$ in this particular case.

Step 1. notice that $|x_i+x_j|-|x_i-x_j| = 2\min(|x_i|,|x_j|)\times \begin{cases}1 & \text{if } x_i x_j > 0\\ -1 & \text{if } x_i x_j < 0\end{cases}$.

Step 2. let $A_t = \{i : x_i > t\}$ and $B_t = \{i : x_i < -t\}$. Using step 1, we have \begin{align} \frac{1}{2} \sum_{i,j} (|x_i + x_j| -|x_i-x_j|) = \sum_{i,j \in A_0} \min(|x_i|,|x_j|) &+\sum_{i,j \in B_0} \min(|x_i|,|x_j|)\\ & -2 \sum_{i\in A_0,j\in B_0} \min(|x_i|,|x_j|) \end{align}

Step 3. We use the trick $\min(|x_i|,|x_j|) = \int_0^\infty 1_{t < |x_i|}1_{t < |x_j|}dt$ and the fact that $\sum_{i} 1_{t < x_i} = \sum_{i \in A_t} 1 = |A_t|$.

\begin{gather} \sum_{i,j \in A_0} \min(|x_i|,|x_j|) = \int_0^\infty |A_t|\cdot |A_t|\,dt\\ \sum_{i,j \in B_0} \min(|x_i|,|x_j|) = \int_0^\infty |B_t|\cdot |B_t|\,dt\\ \sum_{i\in A_0, j\in B_0} \min(|x_i|,|x_j|) = \int_0^\infty |A_t|\cdot |B_t|\,dt\\ \end{gather}

Step 4. Putting things together, we proved that $$ \frac{1}{2} \sum_{i,j} (|x_i + x_j| -|x_i-x_j|) = \int_0^\infty (|A_t|-|B_t|)^2\,dt \geq 0. $$

For real $x_i$, I just found that I had given this answer to a similar question. That answer shows that $$ \sum_{i,j=1}^n|x_i|\le\sum_{i,j=1}^n|x_i+x_j| $$ Which is the same as this question.