Stuck trying to prove an inequality

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! :)

-
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? – NoChance 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
why was this two year old question closed instead of the two week old question? – robjohn Oct 9 '13 at 23:58

3 Answers

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.

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

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

-
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
Nice work. Does the same inequality and perhaps similar approach work for $x_i$ being complex or a vector? – Hans Oct 18 '14 at 23:52

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

-
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