I'm having trouble understanding what should be a simple proof of a result in Marshal and Olkin's book on majorization (Inequalities: theory of majorization and its applications). Specifically, I'd like to understand Theorem 3.A.8 of that text.
I'll first state the necessary definitions for studying majorization. Given vectors $x,y\in\mathbb{R}^n$, the vector $y$ is said to weakly majorize the vector $x$ (denoted $x\prec_{\rm w}y$) if $$ x^{\downarrow}_1 + \cdots + x^\downarrow_k \leq y^{\downarrow}_1 + \cdots + y^\downarrow_k $$ for all $k\in\{1,\dots,n\}$, where $x^\downarrow$ is the vector obtained by rearranging the entries of $x$ in decreasing order. The vector $y$ is said to majorize $x$ (denoted $x\prec y$) if $x\prec_{\rm w}y$ and $x_1+\cdots +x_n = y_1+\cdots + y_n$. A function $\phi:\mathbb{R}^n\rightarrow\mathbb{R}$ is said to be Schur convex if the implication $$ x\prec y \,\Rightarrow\, \phi(x)\leq \phi(y) $$ holds for all $x,y\in\mathbb{R}^n$. Moreover, $\phi$ is said to be increasing if the implication $$ x\leq y \,\Rightarrow\, \phi(x)\leq \phi(y) $$ holds for all $x,y\in\mathbb{R}^n$, where $x\leq y$ is taken entrywise (i.e. $x_k\leq y_k$ for each $k\in\{1,\dots,n\}$).
Consider now the following characterization of functions that preserve the weak majorization order (c.f. Theorem 3.A.8 in Marshal and Olkin).
Theorem (Marshal and Olkin, 3.A.8). Let $\phi:\mathbb{R}^n\rightarrow\mathbb{R}$ be a function. The following are equivalent:
- $\phi$ is increasing and Schur convex
- For all $x,y\in\mathbb{R}^n$, if $x\prec_{\rm w}y$ then $\phi(x)\leq \phi(y)$.
The text does not give an explicit proof. I don't understand the explanation given in the text, and I can't quite figure out how to prove this myself. Any help in explaining or a concrete proof would appreciated.
Edit: I should mention that the proof of $2\Rightarrow 1$ is easy. Indeed, if either $x\leq y$ or $x\prec y$ hold then $x\prec_{\rm w}y$ also holds. The part that I don't understand is how to prove $1\Rightarrow 2$.
I figured out a nice explanation on my own. The following result is due to Ando (1989), where it is given as Corollary 1.8. It has a simple proof by induction.
Lemma (Ando (1989)). Let $x,y\in\mathbb{R}^n$ be vectors satisfying $x\prec_{\rm w}y$. There exists a vector $z\in\mathbb{R}^n$ satisfying $x\leq z\prec y$.
The proof of the direction $1\Rightarrow 2$ of the theorem in my question is now trivial. Indeed, suppose that $\phi$ is increasing and Schur convex and let $x,y\in\mathbb{R}^n$ be vectors satisfying $x\prec_{\rm w}y$. There exists a vector $z\in\mathbb{R}^n$ satisfying $x\leq z\prec y$, and thus $$ \phi(x)\leq \phi(z)\leq \phi(y). $$
The original explanation in Marshal and Olkin is terrible, and I'm rather surprised that they didn't use this simple proof!
References:
T. Ando. Majorization, Doubly Stochastic Matrices, and Comparison of Eigenvalues. Linear Algebra and its Applications 118:163-248 (1989).