Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have been trying to prove (the left half of) the following inequality:

$$ \underbrace{\sum_i \sum_j |x_i| \le \sum_i \sum_j |x_i + x_j|}_\textrm{?} \le 2 \sum_i \sum_j |x_i|$$

(All $x_i$s are arbitrary reals and sums are over $1, 2, \dots, n$)

The right half follows by a simple application of the triangle inequality, but the left half isn't as simple.

I tried induction, and I could reduce the above problem to proving the following statement:

$$ \sum_i |x_i + x_{n+1}| + \sum_{i=1}^{n+1} |x_i + x_{n+1}| \ge \sum_{i=1}^{n+1} |x_i| + n|x_{n+1}|$$ or more simply (replacing $x_{n+1}$ by $y$), $$ 2\sum_i |x_i + y| \ge \sum_i |x_i| + (n-1)|y|$$

However, I don't know if the above "reduction" is any simpler than the original problem itself!

Can I continue the above line of thought, or is there an easier way to solve this problem? Any help is appreciated! :)

share|improve this question
1  
Since the LHS and the RHS has no variable in $j$, you may replace $\sum_i\sum_j|x_i|$ by $n\sum_i|x_i|$. –  AD. Oct 19 '11 at 9:34
    
In the summation: $\sum_i \sum_j |x_i + x_j|$ - Do you mean that i and j have the domain $0 <=i <=n , \ $0 <=j <=n ? Or does each summation have its own lower and upper limits? –  Emmad Kareem Oct 22 '11 at 8:47
    
Can you explain to me how this works for 1,1,-1? I get: $9 \le 2+2+0+0+0+0$ –  Phira Oct 22 '11 at 12:24
    
@Phira I get $9\leq 2+0+2+2+0+2+2+0+0=10$. –  Mike Wierzbicki Oct 22 '11 at 13:44
2  
why was this two year old question closed instead of the two week old question? –  robjohn Oct 9 '13 at 23:58
show 1 more comment

3 Answers 3

up vote 32 down vote accepted

I believe that some smart tricks will solve the problem (e.g. by recasting it into the form of some known inequality), but what came to my mind first was a proof inspired by the simplex method. Although it does not look smart, it may be of some interests to the readers:

  1. Note that by scaling the inequality, we may assume, without loss of generality, that $|x_i|\le1$ for all $i$.
  2. So we want to prove the inequality for all $(x_1,\ldots,x_n)$ inside the hypercube $[-1,1]^n$.
  3. Divide the hypercube $[-1,1]^n$ into pieces by the hyperplanes $x_i=x_j$ and $x_i=0$. For instance, when $n=2$, the four "hyperplanes" (straight lines in this case) $x=y$, $x=-y$, $x=0$ and $y=0$ will divide the square $[-1,1]^2$ into eight pieces in a manner akin to the Union Jack.
  4. In mathematics, we call each of these pieces a simplex.
  5. Note that inside each simplex, each $x_i$ or $x_i+x_j$ does not change sign.
  6. Therefore, inside each simplex, the function $f(x_1,\ldots,x_n)=-\sum_i \sum_j |x_i| + \sum_i \sum_j |x_i + x_j|$ is identical to $-\sum_i \sum_j s_ix_i + \sum_i \sum_j t_{ij}(x_i + x_j)$ for some constants $s_i, t_{ij}=\pm1$.
  7. In other words, $f$ is a linear function inside each simplex.
  8. In linear programming, it is well known that the extremum of a linear function can be attained at the corners of the simplex. You can imagine that when you move a plane closer and closer to a simplex, it will touch the simplex at a corner first (or it touches the whole face, with the corners of the face included).
  9. The corners of our simplices, however, are those points such that $x_i\in\{-1,0,1\}$.
  10. So, we only need to prove the inequality for these corner points.
  11. Let $a$ of the $x_i$s are equal to 1, $b$ of them are equal to $-1$ and $n-a-b$ of them are equal to zero. Then $$ \begin{align} &-\sum_i \sum_j |x_i| + \sum_i \sum_j |x_i + x_j|\\ =&-n(a+b) + 2a^2+2b^2+2a(n-a-b)+2b(n-a-b)\\ =&2a^2+2b^2 - 2(a+b)^2 + n(a+b)\\ \ge&2a^2+2b^2 - 2(a+b)^2 + (a+b)^2\\ =&(a-b)^2\\ \ge&0. \end{align} $$
  12. Hence the result.

In step 11 of the above, equality holds iff $a-b=0$ and $a+b\in\{0,n\}$. In other words, equality holds iff $a=b=0$ or $a=b=n/2$, that is, iff all $x_i$s are zero, or when $n$ is even, exactly half of the $x_i$s (before scaling) are identical to some $x$ and the other half are $-x$s. However, this condition for equality is derived using the corner points. The above proof does not indicate whether equality can hold in other cases.

share|improve this answer
1  
Wow. That was really slick! I wish I could upvote your answer several times more (need some help here!) for not just solving the above problem, but also for showing a very novel method. Is this part of some standard repertoire for solving inequalities? Where did you come across this? –  quantumelixir Oct 19 '11 at 15:19
3  
The technique itself (i.e. narrowing the domain to corner points) is not new. It is standard material in textbooks on linear programming or operations research. I use it here merely because I am not clever enough to think of a straightforward solution. As I said in the answer, my proof is actually a bit problematic -- although it proves the inequality, it fails to identify all cases where equality holds. –  user1551 Oct 19 '11 at 18:52
add comment

Let $p$ be the number of $x_i\ge0$, $m$ be the number of $x_i<0$, and $n=p+m$. $$ \small\begin{array}{} &\sum_i\;\:\sum_j|x_i+x_j|\\ &=\sum_{x_i\ge0}\;\:\sum_{x_j\ge0}|x_i+x_j| &+\sum_{x_i\ge0}\;\:\sum_{x_j<0}|x_i+x_j| &+\sum_{x_i<0}\;\:\sum_{x_j\ge0}|x_i+x_j| &+\sum_{x_i<0}\;\:\sum_{x_j<0}|x_i+x_j|\\ &\ge\sum_{x_i\ge0}\;\:\sum_{x_j\ge0}|x_i|+|x_j| &+\left|\sum_{x_i\ge0}\;\:\sum_{x_j<0}|x_i|-|x_j|\right| &+\left|\sum_{x_i<0}\;\:\sum_{x_j\ge0}|x_j|-|x_i|\right| &+\sum_{x_i<0}\;\:\sum_{x_j<0}|x_i|+|x_j|\\ &=2p\sum_{x_i\ge0}|x_i| &+2\left|m\sum_{x_i\ge0}|x_i|-p\sum_{x_i<0}|x_i|\right| &&+2m\sum_{x_i<0}|x_i| \end{array} $$

Subtracting $\displaystyle\sum_i\;\:\sum_j|x_i|=n\sum_i\;|x_i|$ from the inequality above yields $$ \small\begin{align}{} &\sum_i\;\:\sum_j|x_i+x_j|-\sum_i\;\:\sum_j|x_i|\\ &\ge(p-m)\sum_{x_i\ge0}|x_i| +\left|2m\sum_{x_i\ge0}|x_i|-2p\sum_{x_i<0}|x_i|\right| +(m-p)\sum_{x_i<0}|x_i|\\ &=(p-m)\sum_{i}x_i +\left|(m-p)\sum_{i}|x_i|+n\sum_ix_i\right|\\ &\ge0\tag{1} \end{align} $$ In the last inequality, if $p-m$ and $\sum\limits_ix_i$ have the same sign, we can ignore the quantity in absolute values. If $p-m$ and $\sum\limits_ix_i$ have different signs, then the quantities in the absolute values have the same sign and $|m-p|\sum\limits_i|x_i|\ge(m-p)\sum\limits_ix_i$.

Therefore, $(1)$ says that $$ \sum_i\;\:\sum_j|x_i|\le\sum_i\;\:\sum_j|x_i+x_j| $$

share|improve this answer
1  
This follows exactly the same approach suggested in my answer. An acknowledgement is in order perhaps? –  quantumelixir Oct 22 '11 at 20:16
    
@quantumelixir: I'm sorry, I hadn't read your answer before starting in on mine. I will read it and upvote appropriately. –  robjohn Oct 22 '11 at 20:54
add comment

Assume an ordering of the $x_i$ such that $x_1 \le x_2 \le \dots \le x_k < 0 \le x_{k+1} \le x_{k+2} \le \dots \le x_n$. Let's call $T_1 = \sum_{i=1}^k |x_i|$, $T_2 = \sum_{i=k+1}^n |x_i|$, and $T=\sum_i |x_i|=T_1+T_2$ so that $T, T_1, T_2 \ge 0$.

Since we only require a lower bound on the sum $\sum_{i \neq j} |x_i + x_j|$, we only consider $2\binom{k}{2} + 2\binom{n-k}{2}$ terms of the $2\binom{n}{2}$ total terms that the sum contains i.e. we only pick terms where both $x_i$ and $x_j$ have the same sign. This solves the inequality in many cases. For the other cases, we include the cross terms too later.

$$ \begin{align*} \sum_{i \neq j} |x_i + x_j| &\ge \sum_{i=1}^k \sum_{j=1,j\neq i}^k |x_i+x_j| + \sum_{i=k+1}^n \sum_{j=k+1,j\neq i}^n |x_i+x_j|\\ &= \sum_{i=1}^k \sum_{j=1,j\neq i}^k (|x_i|+|x_j|) + \sum_{i=k+1}^n \sum_{j=k+1,j\neq i}^n (|x_i|+|x_j|)\\ &= \sum_{i=1}^k ((k-1)|x_i|+T_1-|x_i|) + \sum_{i=k+1}^n ((n-k-1)|x_i|+T_2-|x_i|)\\ &= \sum_{i=1}^k ((k-2)|x_i|+T_1) + \sum_{i=k+1}^n ((n-k-2)|x_i|+T_2)\\ &= ((k-2)T_1+kT_1) + ((n-k-2)T_2+(n-k)T_2)\\ &= 2\{(k-1)T_1 + (n-k-1)T_2\}\\ \end{align*} $$

Now, the last expression is a function of $T_1$ and $T_2$. Since we require a lower bound in terms of $T=T_1+T_2$, we can get two equivalent expressions in terms of either $T_1$ and $T$ or in terms of $T_2$ and $T$. Thus,

$$\sum_{i \neq j} |x_i + x_j| \ge 2(2k-n)T_1+2(n-k-1)T$$ $$\sum_{i \neq j} |x_i + x_j| \ge 2(n-2k)T_2+2(k-1)T$$

Adding both, we get:

$$2\sum_{i \neq j} |x_i + x_j| \ge 2\left\{(2k-n)T_1+(n-2k)T_2+(n-2)T\right\}$$ $$\implies \sum_{i \neq j} |x_i + x_j| \ge (2k-n)(T_1-T_2)+(n-2)T \ge (n-2)\sum_i |x_i|$$ $$ \text{whenever,} \; (2k-n)(T_1-T_2) \ge 0$$

For the cases when the above inequality doesn't hold, we need to consider the cross terms too. Computing the cross terms alone:

$$ \begin{align*} \sum_{i \neq j} |x_i + x_j| &\ge \sum_{i=1}^k \sum_{j=k+1}^n |x_i+x_j| + \sum_{i=k+1}^n \sum_{j=1}^k |x_i+x_j|\\ &\ge 2\sum_{i=1}^k \sum_{j=k+1}^n |x_i+x_j|\\ &\ge 2\sum_{i=1}^k \sum_{j=k+1}^n \max\{|x_i|-|x_j|,|x_j|-|x_i|\}\\ &\ge 2 \max\{(n-k)T_1-kT_2, kT_2-(n-k)T_1\}\\ \end{align*} $$

Including the cross terms along with the terms from the previous case, we have:

$$ \begin{align*} \sum_{i \neq j} |x_i + x_j| &\ge 2 \max\{(n-k)T_1-kT_2, kT_2-(n-k)T_1\} + 2\{(k-1)T_1 + (n-k-1)T_2\}\\ &\ge 2 \max\{(n-1)T_1+(n-2k-1)T_2, (2k-n-1)T_1+(n-1)T_2\} \; (*)\\ \end{align*} $$

The $\max$ term can go one of two ways. Using the first term we get: $$ \sum_{i \neq j} |x_i + x_j| \ge 2 \{(n-1)T_1+(n-2k-1)T_2\} $$

We can again write the above in terms of either $T,T_1$ or $T,T_2$ giving two inequalities:

$$ \begin{align} \sum_{i \neq j} |x_i+x_j| &\ge (n-2k-1)T+2kT_1\\ \sum_{i \neq j} |x_i+x_j| &\ge (n-1)T-2kT_2 \end{align} $$

Summing the above two inequalities,

$$ \begin{align*} \sum_{i \neq j} |x_i + x_j| &\ge (2n-2k-2)T+2k(T_1-T_2)\\ &\ge (n-2)T+(n-2k)T+2k(T_1-T_2)\\ &\ge (n-2)T \quad \text{for the case} \quad (2k-n) \le 0, (T_1-T_2) \ge 0\\ \end{align*} $$

Similarly, for the other case, when $(2k-n) \ge 0, (T_1-T_2) \le 0$, we use the other $\max$ term from $(*)$ and follow the above steps routinely to prove the inequality.

Q.E.D

share|improve this answer
    
Well done. (more characters) –  Jonas Teuwen Oct 22 '11 at 16:36
    
Thanks Jonas! Please correct any errors if you spot them. –  quantumelixir Oct 22 '11 at 16:54
    
The above presentation can be greatly simplified, but it's rather long because of it's long edit history. –  quantumelixir Oct 22 '11 at 20:17
    
One simplification: $\max\{(n-k)T_1-kT_2, kT_2-(n-k)T_1\}=|(n-k)T_1-kT_2|$. At least it is easier to read. –  robjohn Oct 22 '11 at 21:31
    
As I commented before, it helps to use $2|(n-k)T_1-kT_2|$ instead of $2\max\{(n-k)T_1-kT_2,kT_2-(n-k)T_1\}$. Then, use $2T_1=(T+(T_1-T_2))$ and $2T_2=(T-(T_1-T_2))$ to convert $$ \sum_{i\not=j}|x_i+x_j|\ge2|(n-k)T_1-kT_2|+2\{(k-1)T_1+(n-k-1)T_2\} $$ into $$ \sum_{i\not=j}|x_i+x_j|\ge|(n-2k)T+n(T_1-T_2)|+(n-2)T+(2k-n)(T_1-T_2) $$ If $(2k-n)(T_1-T_2)\ge0$, ignore the stuff in the absolute values. If $(2k-n)(T_1-T_2)<0$, then $(n-2k)$ and $(T_1-T_2)$ inside the absolute values have the same sign and $|n-2k|T\ge(n-2k)(T_1-T_2)$ which cancels $(2k-n)(T_1-T_2)$. –  robjohn Oct 23 '11 at 8:13
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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