12
$\begingroup$

In some paper the authors make use of the following inequality without further explanation: Let $x\in\mathbb{R}^n$ with $x_1\le\cdots\le x_n$ and $\alpha\in[0,1]^n$ with $\sum_{i=1}^n \alpha_i=N\in\{1,2,\ldots,n\}$. Then $$\sum_{i=1}^n\alpha_i x_i\ge\sum_{i=1}^N x_i.$$

While I already have found a (quite lengthy) bare-hands-proof, I wonder if this inequality is just (some variant of) some commonly known inequality that I am just unaware of. Any hints?

$\endgroup$
5
$\begingroup$

(In a way this is a rephrasing of Iosif's answer, but from a different perspective. My main intention is to point out the connection to matroids.)

The inequality follows from:

Fact. The polytope $K = \Bigl\{\alpha \in [0,1]^n: \sum_{i = 1}^n\alpha_i = N\Bigr\}$ is the convex hull of indicator vectors of subsets of $[n] = \{1, \ldots, n\}$ of size $N$.

Assuming this fact, and because any linear function over a polytope achieves its minimum at a vertex, we have that $\sum_{i = 1}^n{\alpha_i x_i} \ge \sum_{i \in S} x_i$ for some set $S$ of size $N$. The right hand side is then clearly minimized for $S = \{1, \ldots, N\}$ if $x_1 \le x_2 \le \ldots \le x_n$.

To show the Fact, we need to show that every extreme point $\alpha$ of $K$ is an indicator vector of a set of size $N$. This is clearly true if $\alpha \in \{0,1\}^n$, so assume, towards contradiction, that for some $i$ we have $0 < \alpha_i < 1$. Then there must be at least one other $j \neq i$ such that $0 < \alpha_j < 1$, and we can write $\alpha$ as a convex combination of two vectors in $K$, one in which we add a tiny $h$ to $\alpha_i$ and subtract $h$ from $\alpha_j$, and one in which we reverse the signs. This means that $\alpha$ is not an extreme point, a contradiction. You can see that this argument is essentially the same as Iosif's.

Another way to state the Fact is that $K$ is the base polytope of the uniform matroid over $[n]$ of rank $N$. A vast generalization is the characterization of the facets of the base polytope of any matroid, due to Edmonds: see, e.g., Section 10.7 in these notes.

$\endgroup$
  • 1
    $\begingroup$ Ah, indeed. I think, the key word is en.wikipedia.org/wiki/Polymatroid $\endgroup$ – Fedor Petrov Feb 18 at 21:02
  • $\begingroup$ @FedorPetrov it's a good keyword :). Polymatroids are technically a little more general. $\endgroup$ – Sasho Nikolov Feb 18 at 21:07
  • $\begingroup$ @SashoNikolov There is a minor typo, as in the OP we were looking for the minimum of $\sum_{i=1}^n\alpha_ix_i$ for $\alpha\in K$, which then is attained for the indicator vector of $S=\{1,\ldots,N\}$, because we have assumed $x_1\le\cdots\le x_n$. $\endgroup$ – Robert Rauch Feb 19 at 9:54
  • $\begingroup$ @RobertRauch Thank you, I believe I fixed it. I had flipped the whole problem in my head somehow. $\endgroup$ – Sasho Nikolov Feb 19 at 18:06
15
$\begingroup$

Use Abel transform: denote $x_i=y_1+y_2+\dots+y_i$, then $$\sum \alpha_i x_i=\sum y_i (\alpha_i+\alpha_{i+1}+\dots+\alpha_n). $$ We have $\alpha_i+\alpha_{i+1}+\dots+\alpha_n=N-(\alpha_1+\dots+\alpha_{i-1})\geqslant N-i+1$ for $i=1,\dots,N$. Therefore $$ \sum \alpha_i x_i\geqslant Ny_1+(N-1)y_2+\dots+y_N=x_1+\dots+x_N. $$

$\endgroup$
7
$\begingroup$

$\newcommand{\al}{\alpha}$ The following, rather intuitive proof is done by induction on $n$. The case $n=1$ is trivial. Suppose now that $n\ge2$. By continuity, without loss of generality $x_1<\dots<x_n$. The minimum of $\sum_1^n\al_i x_i$ over all $\al=(\al_1,\dots,\al_n)$ as in the OP is attained. Let $\al=(\al_1,\dots,\al_n)$ be a point of such an attainment.

To obtain a contradiction, suppose that $\al_1<1$. Then the condition $\sum_1^n\al_i=N\ge1$ implies that $\al_j>0$ for some $j\in\{2,\dots,n\}$. Replacing $\al_1$ and $\al_j$ respectively by $\al_1+h$ and $\al_j-h$ for a small enough $h>0$, we get a smaller value of $\sum_1^n\al_i x_i$ (because $x_1<x_j$). This contradicts the assumption that $\al$ is a point of minimum of $\sum_1^n\al_i x_i$.

So, $\al_1=1$, and your inequality reduces to $\sum_2^n\al_i x_i\ge\sum_2^N x_i$ given that $\al_i\in[0,1]$ for all $i$ and $\sum_2^n\al_i=N-1$, and the latter inequality is true by induction.

$\endgroup$
  • 1
    $\begingroup$ Thanks for this interesting approach. However, the OP does not ask for (more) elementary proofs of this inequality ;-) $\endgroup$ – Robert Rauch Feb 18 at 13:51
  • 5
    $\begingroup$ @RobertRauch, aren't you the OP …? $\endgroup$ – LSpice Feb 18 at 15:27
  • 1
    $\begingroup$ This can almost be phrased as two applications of the rearrangement inequality. Since $\sum_{i=1}^n \alpha_i x_i$ is minimized, under rearrangement of the $\alpha_i$, when the $\alpha_i$ are decreasing, we may assume this is the case. (Note this doesn't change $\sum_{i=1}^n \alpha_i = N$.) The minimum varying the $\alpha$ (while keeping their sum as $N$) is now at $\alpha = (1,\ldots, 1, 0, \ldots, 0)$ since if $\alpha_k \not=0$ for some $k > N$ we can reduce $\sum_{i=1}^n \alpha_i x_i$ by increasing $\alpha_1 < 1$ and decreasing $\alpha_k$, exactly as the proof above. $\endgroup$ – Mark Wildon Feb 18 at 16:17
  • 1
    $\begingroup$ @RobertRauch : I have added the tag "reference-request" to your post. Perhaps this will help you to get a reference to a known more general inequality. $\endgroup$ – Iosif Pinelis Feb 18 at 17:01
  • 5
    $\begingroup$ I imagine Robert is the original poster. However, OP can stand for Original Post as well. Gerhard "Am I What I Write?" Paseman, 2019.02.18. $\endgroup$ – Gerhard Paseman Feb 18 at 17:05

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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