# Does anyone recognize this inequality?

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?

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

• Ah, indeed. I think, the key word is en.wikipedia.org/wiki/Polymatroid – Fedor Petrov Feb 18 '19 at 21:02
• @FedorPetrov it's a good keyword :). Polymatroids are technically a little more general. – Sasho Nikolov Feb 18 '19 at 21:07

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

• I think this approach (summation by parts) was also used in the answer by wj32 at the link math.stackexchange.com/questions/1582996/…, provided in the comment by Martin Sleziak. – Iosif Pinelis Feb 18 '19 at 16:40
• @IosifPinelis you are correct, of course – Fedor Petrov Feb 18 '19 at 19:36

$$\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. 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). 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.

• Thanks for this interesting approach. However, the post does not ask for (more) elementary proofs of this inequality ;-) – Robert Rauch Feb 18 '19 at 13:51
• 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. – Mark Wildon Feb 18 '19 at 16:17
• @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. – Iosif Pinelis Feb 18 '19 at 17:01
• @MarkWildon Great observation! Reading your comment was the first time I actually believed that the inequality is true :-) – Robert Rauch Feb 19 '19 at 9:32