6
$\begingroup$

Let $a = (a_1, \cdots, a_n), b = (b_1, \cdots, b_n), c = (c_1, \cdots, c_n) \in \mathbb{R}^n$ with $a_1 \geq \cdots \geq a_n, b_1 \geq \cdots \geq b_n, 0 < c_1 \leq \cdots \leq c_n$.

In addition, assume that $\sum_{i=1}^k b_i \leq \sum_{i=1}^k a_i$ for all $k \in \{1, \cdots, n-1\}$ and $\sum_{i=1}^n b_i = \sum_{i=1}^n a_i$.

Let $A := \{(a_{\sigma(1)}, \cdots, a_{\sigma(n)}) \,|\, \sigma \in S_n\}$ and $K_A$ be the unique minimal convex set containing $A$.

For $b \in K_A$, does $$\sum_{i=1}^n c_i b_i \geq \sum_{i=1}^n c_i a_i$$ hold?

$\endgroup$
3
$\begingroup$

Given two ordered vectors $a_1\geq a_2\geq \cdots \geq a_n$ and $b_1\geq b_2\geq \cdots b_n$ with equal sums $a_1+\cdots a_n=b_1+\cdots +b_n$. The condition that $b\in K_A$ and the inequalities $\sum_{i=1}^k a_i\geq \sum_{i=1}^k b_i$ are equivalent and this is called the majorization order.

A fundamental result is that if $a=(a_i)$ majorizes $b=(b_i)$ then you can obtain $b$ from $a$ by a finite sequence of operations of the form $$R_{ij}(\epsilon)(a)=(a_1,\dots,a_i-\epsilon,\dots,a_j+\epsilon,\dots,a_n)$$ for some $i<j$ and $\epsilon\geq 0$ is small enough not to reverse the order of the entries. That is, there exist several $(i_k,j_k,\epsilon_k)$ with $i_k<j_k$ and $\epsilon_k\geq 0$ such that $$b=\prod R_{i_kj_k}(\epsilon_k)a$$

Thus it suffices to prove your inequality for each step individually. So we can assume $b=R_{ij}(\epsilon)a$. In which case the inequality reduces to $$c_i (a_i-\epsilon)+c_j(a_j+\epsilon)\geq c_ia_i+c_ja_j$$ $$\iff \epsilon (c_j-c_i)\geq 0$$ and we are done.

$\endgroup$
3
$\begingroup$

Write $c_k=p_1+\cdots+p_k$ with $p_k=c_k-c_{k-1}\ge0$. Then $$\sum_ic_ib_i-\sum_ic_ia_i=\sum_kp_k(s_k(b)-s_k(a))$$ with $s_k(a)=a_k+\cdots+a_n$. By assumption, $s_k(b)-s_k(a)\ge0$ and you are gone.

This proof is just Abel's resummation, that is discrete integration by parts.

$\endgroup$

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.