# Bound for the solution of Non homogeneous equations

I have the following set of equations

$x_1^2+x_2^2+x_3^2+....+x_n^2=1$

$x_1+x_2+x_3+....+x_n=1$

$-1 \leq x_i \leq 1$

Then what is the bound for the |$x_1|+|x_2|+|x_3|+....+|x_n$|

The trivial bound is $n$ as each variable value is less than $1$. But I know this is a very bad bound. So can we get better than this..? Thank You.

Does $1 \le \sum |x_i| \le \sqrt{n}$ suffice?

The lower bound can be obtained by noting that $f(x) = |x|$ is convex in the interval and applying Jensen's inequality, or using extending triangle inequality.

The upper bound using Cauchy-Schwarz with $a_i = |x_i|$ and $b_i = 1$. Then we have:
$\sum a_i b_i \le (\sum a_i^2)^{1/2}(\sum b_i^2)^{1/2}$

$\implies \sum \lvert x_i \rvert \cdot 1 \le (\sum \lvert x_i \rvert ^2)^{1/2}(\sum 1)^{1/2}$

$\implies \sum \lvert x_i \rvert \le (\sum x_i^2)^{1/2}(n)^{1/2} = 1 \cdot \sqrt{n}$

The lower bound can be achieved by $x_1 = 1$ and all other $x_i = 0$, so that's tight. The upper bound however is not tight, hence there is possibility of improving it, using the fact that $\sum x_i = 1$.

• The lower bound is clear for me. But for the upper bound if we apply cauchy-schwarz then I think we will get the bound $n$. I couldn't understand the last line i.e., using the fact that $\sum |x_i| = 1$ – Kumar Mar 4 '13 at 6:20
• I have clarified the Cauchy-Schwarz application in the edit above. As mentioned, the upper bound is loose, but I meant $\sum x_i = 1$ should prove helpful in tightening it. – Macavity Mar 4 '13 at 6:39
• @Macavity as my answer shows, the upper bound of $\sqrt{n}$ is actually quite tight, and is attainable whenever $n=m^2$ is a perfect square, via $x_1=x_2= \ldots =x_{\frac{m^2+m}{2}}=\frac{1}{m}, x_{\frac{m^2+m}{2}+1}=x_{\frac{m^2+m}{2}+2}= \ldots =x_{m^2}=-\frac{1}{m}$ – Ivan Loh Mar 4 '13 at 15:47
• @IvanLoh: Yes - did not specifically consider case of n being perfect square, where its tight. Even otherwise it looks good! – Macavity Mar 5 '13 at 8:49

Overview: I shall prove the bounds

$$1 \leq \sum\limits_{i=1}^{n}{|x_i|} \leq \frac{2(k+\sqrt{(n-k)k(n-1)})}{n}-1$$

, where $k=\lceil \frac{n-1+\sqrt{n}}{2} \rceil$

Equality is achievable for both bounds, so they are the best possible bounds.

Some numbers for illustration: Let's take for example $n=2013$. Then $k=\lceil \frac{2013-1+\sqrt{2013}}{2} \rceil=1029$, and we get $$\sum\limits_{i=1}^{2013}{|x_i|} \leq \frac{2(1029+\sqrt{(984)(1029)(2012)})}{2013}-1 \approx 44.86646844<44.86646854=\sqrt{2013}$$.

Thus the simple upper bound $\sqrt{n}$ is actually quite tight. In fact, my upper bound agrees with $\sqrt{n}$ whenever $n$ is a perfect square.

Lower bound: Note that $x_i^2 \leq |x_i|$, so $1=\sum\limits_{i=1}^{n}{x_i^2} \leq \sum\limits_{i=1}^{n}{|x_i|}$, with equality when 1 of $x_i$ is $1$ and the others are $0$.

Proof of upper bound: It is easy to check $n=1, 2$. Take $n \geq 3$.

Let $a$ be the number of positive $x_i$. Since $\sum\limits_{i=1}^{n}{x_i}=1$, clearly $a \not =0$. Also if $a=n$ then $0<\sum\limits_{symm}{x_ix_j}=\left(\sum\limits_{i=1}^{n}{x_i}\right)^2-\sum\limits_{i=1}^{n}{x_i^2}=0$, a contradiction. Thus $1 \leq a \leq n-1$.

Since the conditions and the expression to be maximised are symmetric, we may safely assume $x_1, x_2, \ldots , x_a>0$ and $x_{a+1}, x_{a+2}, \ldots , x_n \leq 0$. Thus $\sum\limits_{i=1}^{a}{|x_i|}=\sum\limits_{i=a+1}^{n}{|x_i|}+1$, so $\sum\limits_{i=1}^{n}{|x_i|}=2\sum\limits_{i=1}^{a}{|x_i|}-1$.

$$1=\sum\limits_{i=1}^{a}{x_i^2}+\sum\limits_{i=a+1}^{n}{x_i^2} \geq \frac{\left(\sum\limits_{i=1}^{a}{|x_i|}\right)^2}{a}+\frac{\left(\sum\limits_{i=a+1}^{n}{|x_i|}\right)^2}{n-a}=\frac{\left(\sum\limits_{i=1}^{a}{|x_i|}\right)^2}{a}+\frac{\left(\sum\limits_{i=1}^{a}{|x_i|}-1\right)^2}{n-a}$$

Here we have used Cauchy Schwarz inequality.

We can rewrite this as $$n\left(\sum\limits_{i=1}^{a}{|x_i|}\right)^2-2a\left(\sum\limits_{i=1}^{a}{|x_i|}\right)-a(n-a-1) \leq 0$$

Thus $$\sum\limits_{i=1}^{a}{|x_i|} \leq \frac{2a+\sqrt{4a^2+4a(n-a-1)n}}{2n}=\frac{a+\sqrt{(n-a)a(n-1)}}{n}$$.

This gives an upper bound of $$\sum\limits_{i=1}^{n}{|x_i|}=2\sum\limits_{i=1}^{a}{|x_i|}-1 \leq \frac{2(a+\sqrt{(n-a)a(n-1)})}{n}-1$$

Note that equality is attainable at $x_1=x_2= \ldots =x_a=\frac{a+\sqrt{(n-a)a(n-1)}}{an}$ and $x_{a+1}=x_{a+2}= \ldots =x_n=\frac{1-\frac{a+\sqrt{(n-a)a(n-1)}}{n}}{n-a}$.

It thus suffices to maximise $$\sum\limits_{i=1}^{n}{|x_i|}=2\sum\limits_{i=1}^{a}{|x_i|}-1 \leq \frac{2(a+\sqrt{(n-a)a(n-1)})}{n}-1$$

over $1 \leq a \leq n$. Let $k$ be the value of $a$ which maximises this expression (if there is more than 1 such $a$, pick the smallest such one.)

First note that if $a<\frac{n}{2}$, then $a+\sqrt{(n-a)a(n-1)}<n-a+\sqrt{(n-(n-a))(n-a)(n-1)}$. Thus we must have $k \geq \frac{n}{2}$.

Clearly, $k$ must be a positive integer solution of the inequality $x+\sqrt{(n-x)x(n-1)}\geq x+1+\sqrt{(n-x-1)(x+1)(n-1)}$, and $k-1$ must not satisfy that inequality.

Manipulating, $$(n-x)x(n-1) \geq 1+(n-x-1)(x+1)(n-1)+2\sqrt{(n-x-1)(x+1)(n-1)}$$

$$(2x+1-n)(n-1)-1 \geq 2\sqrt{(n-x-1)(x+1)(n-1)}$$

We have already determined $k \geq \frac{n}{2}$, so $(2k+1-n)(n-1)-1 \geq n-2>0$, so we don't lose any information by squaring.

$$(2x+1-n)^2(n-1)^2-2(2x+1-n)(n-1)+1 \geq 4(n-x-1)(x+1)(n-1)$$

$$(2x+1-n)^2(n-1)-2(2x+1-n)+\frac{1}{n-1} \geq 4(n-x-1)(x+1)$$

Before we continue, note the following trivial lemma. If $a, b$ are integers and $0<c<1$ then $a+c \geq b \Leftrightarrow a \geq b$.

Proof: If $a \geq b$, then $a+c \geq b+c \geq b$. If $a+c \geq b$ then $a \geq b-c$ so $a\geq \lceil b-c \rceil=b$.

Note that we want integer solutions, so by the lemma we have $$(2x+1-n)^2(n-1)-2(2x+1-n) \geq 4(n-x-1)(x+1)$$

$$4nx^2-4n(n-1)x+n^3-3n^2+n+1 \geq 0$$ $$4x^2-4(n-1)x+n^2-3n+1+\frac{1}{n} \geq 0$$ By lemma, $$4x^2-4(n-1)x+n^2-3n+1 \geq 0$$ $$x^2-(n-1)x+\frac{n^2-3n+1}{4} \geq 0$$. We have $k \geq \frac{n}{2} > \frac{n-1-\sqrt{(n-1)^2-(n^2-3n+1)}}{2}$, so $x$ is larger than the smaller root of the quadratic, and must thus be $\geq$ the larger root.

Thus $x \geq \frac{n-1+\sqrt{(n-1)^2-(n^2-3n+1)}}{2}=\frac{n-1+\sqrt{n}}{2}$, so $k \geq \frac{n-1+\sqrt{n}}{2}$, so $k \geq \lceil \frac{n-1+\sqrt{n}}{2} \rceil$.

Assume on the contrary that $k \geq \lceil \frac{n-1+\sqrt{n}}{2} \rceil+1$, then $k-1 \geq \lceil \frac{n-1+\sqrt{n}}{2} \rceil \geq \frac{n}{2}$, so we could use $k-1$ in place of $x$ in the inequality throughout the whole manipulation, and $k-1$ satisfies the last inequality $\geq \lceil \frac{n-1+\sqrt{n}}{2} \rceil$, so $k-1$ is a solution of the original inequality, a contradiction.

Thus $k=\lceil \frac{n-1+\sqrt{n}}{2} \rceil$, and we are done.

• Perhaps a simpler approach could be to note the convexity of the function and the set involved - the maxima then has to be achieved on the boundary, which would mean some $k$ number of $x_i$ are identical to $x$ for some $x$, and remaining $n-k$ variables are identical to $-x$. Then it would reduce to solving for $k$ and $x$ using the boundary equations $\sum x_i^2 = 1$ and $\sum x_i = 1$. In the perfect square case it directly leads to the result, for the other case need to work out. – Macavity Mar 5 '13 at 8:54
• Isn't that what I did (except that I used CS)? By CS inequality, I get $\frac{2(a+\sqrt{(n-a)a(n-1)})}{n}-1$, which I then need to maximise over $a$. From your comment, solving for $k, x$ using the boundary equations, as you say, would just give an expression in terms of $k$, equivalent to what I got. (except that I used $a$ as the variable) This is because there is a solution for $x$ for each $k$. This is the easy part. The harder part is to find the value of $k$ (as referenced from your comment, equivalent to my "$a$") which gives you the maximum, which is actually the bulk of my answer. – Ivan Loh Mar 5 '13 at 9:22
• I see you mean that the negative variables have same absolute value as the positive variables, in order to maximise the expression. That is, in fact, incorrect. Take $n=3$, the maximum is achieved at $\frac{5}{3}$, with $x_1=x_2=\frac{2}{3}, x_3=-\frac{1}{3}$. – Ivan Loh Mar 5 '13 at 9:26
• Ah - you are correct. Somehow I assumed there would be a convex feasible region of interval form $[-x, x]$ for each $x_i$, which is not true. – Macavity Mar 5 '13 at 9:43