How prove this inequality: $\sum_{i,j=1}^{n}|x_{i}+x_{j}|\ge n\sum_{i=1}^{n}|x_{i}|$? Let $x_{1},x_{2},\cdots,x_{n}$ be real numbers. Show that

$$\sum_{i,j=1}^{n}|x_{i}+x_{j}|\ge n\sum_{i=1}^{n}|x_{i}|.$$

I think this problem may be solved using nice methods, but I can't find them yet; I know this may be of use:
$$|a|+|b|\ge |a+b|.$$
But I can't make it work. Thank you everyone.
 A: 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.
A: 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.
$$
A: 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.
