This question already has an answer here:

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.


marked as duplicate by Norbert, Sharkos, Dominic Michaelis, Nate Eldredge, azimut Nov 25 '13 at 9:37

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Are you not satisfied with my answer? $\endgroup$ – Siméon Oct 2 '13 at 16:39
  • 2
    $\begingroup$ Iran Team Selection Test 2006,Day 2,Problem 4 $\endgroup$ – Smy2012 Oct 6 '13 at 19:55
  • $\begingroup$ @user1551: I just noticed that, too. But why was that two year old question closed instead of this two week old question? $\endgroup$ – robjohn Oct 9 '13 at 23:49
  • $\begingroup$ @robjohn I first voted to close it, because the bounty for this newer duplicate question is still active, but the bounty for the old question we answered is not. It may be a bit strange to close the original instead of the duplicate. I am sorry for any inconvenience caused. $\endgroup$ – user1551 Oct 10 '13 at 12:05

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

  • 1
    $\begingroup$ I have been trying to prove this very same inequality for this question. Unfortunately, I don't think this approach works. A counterexample is $\{1,-1\}$. In this case, $\sum f(x_i,x_j)=0$ yet $\sum\sqrt{2|x_i|}\gt0$. $\endgroup$ – robjohn Sep 29 '13 at 22:43
  • $\begingroup$ Step 1 is true only for $x_i\in\mathbb{R}^1$, in which case, the theorem is much easier to prove. $\endgroup$ – robjohn Oct 3 '13 at 9:39
  • $\begingroup$ Ah, never mind. I see that the question states that $x_i$ are real numbers. $\endgroup$ – robjohn Oct 3 '13 at 9:53
  • $\begingroup$ @robjohn: this is precisely why I don't like this proof very much. I would be happy to know if the inequality $(\star)$ holds in $\Bbb C$ or in higher dimension. $\endgroup$ – Siméon Oct 3 '13 at 10:32
  • $\begingroup$ Yes. That was the question I was working on. I will continue to work on it since my gut feeling is that it is true in $\mathbb{R}^n$. $\endgroup$ – robjohn Oct 3 '13 at 20:37

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.

  • $\begingroup$ This is very nice (+1) $\endgroup$ – Siméon Oct 3 '13 at 8:14
  • $\begingroup$ It seems that this solution is for $\mathbb{R}^1$ only. Otherwise, $x_ix_j\ge0$ does not make sense. $\endgroup$ – robjohn Oct 3 '13 at 9:41
  • $\begingroup$ Ah, never mind. I see that the question states that $x_i$ are real numbers. $\endgroup$ – robjohn Oct 3 '13 at 9:53
  • $\begingroup$ @Ju'x: thanks. I do however prefer more conceptual proof reducing the problem to $\int_{0}^1\int_0^1|f(x)+f(y)|dxdy\ge \int_{0}^1|f(x)|dx$ and plying around with Hanh decomposition. $\endgroup$ – leshik Oct 3 '13 at 15:37
  • $\begingroup$ @leshik: could you please give a sketch of the proof using the Hanh decomposition? I don't see how it apply here. $\endgroup$ – Siméon Oct 4 '13 at 18:13

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.


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