11
$\begingroup$

Let $e=(1,1,\ldots,1)$ be the $n$-dimensional vector consisting only of ones.

Let $r=\sqrt{\dfrac{n}{n-1}}$ and $\alpha \in (0,1)$ fixed.

Given a vector $x=(x_1,x_2,\ldots,x_n) \in \mathbb R^n$, with all $x_i$ positive, and such that $\langle x, e\rangle =n$ and $\left\|x-e\right\|_2=\alpha r$, how do you show without using Lagrange multipliers that $$x_1 \cdot x_2 \cdots x_n \ge \left(1-\alpha\right)\left(1+\frac{\alpha}{n-1}\right)^{n-1}?$$

EDIT: When one tries Lagrange multipliers, one is left with this inequality which doesn't look pretty nice. Any idea how to proceed there?

$\endgroup$
4
  • $\begingroup$ Which norm are you indicating with $\left| \cdot \right|$? $\endgroup$
    – AdamO
    Jun 12, 2013 at 17:12
  • 3
    $\begingroup$ the equality condition seems to be when 1 coordinate it $(1-\alpha)$ and all of the others are $ 1 + \frac{\alpha} { n-1}$, so I'm presuming that it's the $l_2$ norm, since $\alpha^2 + \frac{\alpha^2 (n-1)} { (n-1)^2} = \alpha^2 \frac {n}{n-1}$. $\endgroup$
    – Calvin Lin
    Jun 12, 2013 at 17:14
  • $\begingroup$ @ashkan: The euclidean norm. $\endgroup$
    – Dominik
    Jun 12, 2013 at 17:15
  • $\begingroup$ we consider $x$ as a point in $\mathbb{R}^n$ with the property that $x_1+x_2+...+x_n=n$ and also we have $x_1,...,x_n\ge 0$ from our hypothesis,now we use AM-GM inequality for $x_1,...,x_n$ and also for $(1+\frac{\alpha}{n-1})^{n-1}$=$(\frac{n-1+{\alpha}}{n-1})^{n-1}$. $\endgroup$
    – R Salimi
    Jun 12, 2013 at 18:00

1 Answer 1

1
$\begingroup$

Here's a proof which does not require Lagrangian multipliers. It requires some basic insights from multidimensional / differential geometry. In the following, I first illustrate the idea before formalizing it.

I find it easier to think of the given task in its logically equivalent contrapositive, exchanging and negating the product and the Euclidian norm (the scalar product $\langle x, e\rangle =n$ is left unchanged). This reads, defining, for better reading, $P$ and $q$:

Given that $\langle x, e\rangle =n$ and that $x_1 \cdot x_2 \cdots x_n = \left(1-\alpha\right)\left(1+\frac{\alpha}{n-1}\right)^{n-1} = P$, show that $\left\|x-e\right\|_2 \geq \alpha r = q$.

In this formulation, the task is to show that the Euclidian distance, measured on the hyperplane $\langle x, e\rangle =n$ from $e$ to a point on a hyperbolic surface given by $x_1 \cdot x_2 \cdots x_n = P$, is at least $q$ (the minimum distance).

We can ask where are those points on the hyperbolic surface, with minimum distance to $e$? As an example for visualization, I took the function $x\; y \; z = 1$ and plotted (by MATLAB) its two-dimensional projection onto the plane $\langle x, e\rangle =3$. The result is the green line shown in the following figure where the axes $b,c$ are taken normal to $e$.

Extrema on Hyperbolic Surface

It can be seen that there are 3 points where the distance $q$ is maximal (red), and 3 points where the distance is minimal (blue). Let's call these 6 points extremal. Now it is easy to note that extremal points in general share a common feature, namely that the (blue and red) vectors originating at those points, in the direction normal to the surface of the hyperbola, meet the axis with axis vector $e$ - which is here, in the projection, the point $(0,0)$. So this is a necessary condition for extrema.

Conversely, a normal vector originating at a non-extremal point will not meet the axis with axis vector $e$. As an example, here the dashed dark green vector is plotted.

For all vectors, excuse my (hand-)drawing, they are only indicative.

We can now formalize this argument and generalize it to $n$ dimensions.

Ignoring for a moment the condition that the distance is to be measured on the hyperplane $\langle x, e\rangle =n$, we notice that the normal vector on a point of a surface $ F(x) = x_1 \cdot x_2 \cdots x_n = P$ is given by the gradient $\bigtriangledown _{x} F(x) = (P/x_1, P/x_2, ..., P/x_n)$. The necessary conditon that the normal vector, originating at ${\bf x}$, meets the axis with axis vector ${\bf e}$, is hence

$${\bf x} + a \, \bigtriangledown _{x} F(x) = b \, {\bf e}$$

with some scalar constants $a$ and $b$. Since this must hold for all dimensions, we obtain for all $x_i$ the component equations:

$$x_i + a \, P/x_i = b$$

which is a quadratic equation with two solutions $x_{+,-}$ which are the only two values which all components $x_i$ at the extremal points can attain. Explicitely, extremal points have $k$ components with value $x_+$ and $n-k$ components with value $x_-$, where $x_{+,-}$ are dependent on $k$.

The condition that the distance is to be measured on the hyperplane $\langle x, e\rangle =n$ doesn't change this argument, since it merely means that we have to subtract from $\bigtriangledown _{x} F(x)$ a component in the direction of ${\bf e}$, to make the distance vector lie in the plane $\langle x, e\rangle =n$. This subtracts, in the above component equations, for all dimensions the same value, leaving us again with two solutions which are identical for all $x_i$. This geometric argument could be formalized by considering directional derivatives, if necessary.

Now with this necessary (for the minimum distance) condition for $x_i$, and re-instating $P$, we identify for $k=1$: $x_+ = 1-\alpha$ and $x_- = 1+\frac{\alpha}{n-1}$

[see also the comment by Calvin Lin from Jun 12 '13 at 17:14].

We cannot have all $x_i$ equal. In the geometric picture, the vertex of the hyperbola is such a point. This would be a point meeting our necessary condition, but, after subtracting a component in the direction of ${\bf e}$ to lie in the plane $\langle x, e\rangle =n$, this point becomes projected to the "origin" of that plane, i.e. to ${\bf x}= {\bf e}$ which does not lie on the hyperbola.

So indeed, the minimum distance value that can be attained is at points which have one coordinate to be $x_+$ and (n-1) coordinates to be $x_-$, since then we have

$$\left\|x-e\right\|_2^2 = \alpha^2 + (n-1) \left(\frac{\alpha}{n-1} \right)^2 $$

which is the smallest we can get. So this is indeed a global minimum, which can also be shown explicitely for variations of $k$, see below. For all other points on the hyperbola and on the plane $\langle x, e\rangle =n$, the distance to ${\bf e}$ will be larger.

At those minimum distance points, the condition $\left\|x-e\right\|_2 \geq \alpha r$ holds with equality.

Hence, all requirements are satisfied.

We show additionally the minimum property by variating $k$, the number of coordinates which have the value $x_+$. I.e. $n-k$ coordinates will have the value $x_-$. To show that, get back to the orginal problem formulation. Obeying $\langle x, e\rangle =n$ can be ensured, with some yet unspecified $b = b(n,k)$, by chosing

$$ x_+ = 1 + \frac{b}{k} \quad ; \quad x_- = 1 - \frac{b}{n-k} $$

Then obeying $\left\|x-e\right\|_2 = \alpha r$ leads to $$ b = \alpha \sqrt{\frac{k(n-k)}{n-1}}$$

Now we need to show the product inequality, i.e. for all $k \in \{1,...,n-1\}$,

$$\left(1-\alpha\sqrt{\frac{n-k}{k(n-1)}}\right)^k\left(1+\alpha\sqrt{\frac{k}{(n-k)(n-1)}}\right)^{n-k} \ge \left(1-\alpha\right)\left(1+\frac{\alpha}{n-1}\right)^{n-1}$$ (where equality occurs exactly at $k=1$).

This, however, is exactly what one gets if one would have treated the problem using Lagrangian multipliers (we did not need this here). The inequality has been proven to be correct, see here: How can I prove this monster inequality?

This concludes the proof.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .