# A sufficient condition for weak majorization from below

I posed this question on math.stackexchange.com but have gotten no answer. So I post the question here in order to obtain an answer.

$$\forall x\in \mathbf R^{n+1}$$, let $$x_{(0)}\le x_{(1)}\le\,\cdots\le x_{(n)}$$ denote the non-decreasing rearrangement of $$x$$. Suppose $$x,y\in\mathbf R^{n+1}$$, $$\sum_{i=0}^k x_{i}\le \sum_{i=0}^k y_{i},\quad \forall k\in\{0,1,2,\cdots,n\} \tag1$$ and $$x_{i-1}\le y_i,\quad\forall i\in\{1,2,\cdots,n\}. \tag2$$ Show $$\sum_{i=0}^k x_{(i)}\le \sum_{i=0}^k y_{(i)},\quad \forall k\in\{0,1,2,\cdots,n\}.$$

Here is my attempt at the proof with one obstacle I fail to overcome.

Let $$l_i$$ be the permutation of $$\{0,1,2,\cdots,n\}$$ such that $$y_{(i)}=y_{l_i},\, \forall i\in\{0,1,2,\cdots,n\}$$. For any $$k\in\{1,2,\cdots,n\}$$, $$\sum_{i=0}^k (y_{(i)}-x_{(i)})=I\big(0\in\{l_i|i\in\{0,1,\cdots,k\}\}\big)(y_0-x_{(k)})+\sum_{\substack{i=0\\l_i\neq0}}^k (y_{l_i}-x_{l_i-1})+\Big(\sum_{\substack{i=0\\l_i\neq0}}^k x_{l_i-1}-\sum_{i=0}^{k-1}x_{(i)}\Big)$$ where $$I$$ stands for the characteristic function. Every term in the first summation term on the right hand side of the above equation is nonnegative by inequality $$(2)$$. The term in the second parenthesis is nonnegative by virtue of the definition of $$x_{(i)}$$. Presumably I should use Inequality $$(1)$$ to show the nonnegativity of the first term of the above equation. But I do not see how.

We should prove that the sum of any $$k$$ $$y$$'s is not less than the sum of certain $$k$$ $$x$$'s (indeed, this property is equivalent to the condition that the sum of $$k$$ smallest $$y$$'s is not less than the sum of $$k$$ smallest $$x$$'s.) Let our $$k$$ $$y$$'s contain $$y_i$$'s for $$i=0,1,\ldots,p$$, but do not contain $$y_{p+1}$$ (there exists unique such $$p$$). Bound the sum $$y_0+\ldots+y_p$$ by $$x_0+\ldots+x_p$$ and other $$y_i$$'s by corresponding $$x_{i-1}$$'s.
• $p$ is defined in the sentence in which it appears. The condition "the sum of any $k$ $y$'s is not less than the sum of certain $k$ $x$'s" is equivalent to weak majorization Oct 21, 2021 at 20:07