characterizations of majorization

Let ${ℰ}_n$ be the set of all $n\times n$ permutationmatrices that exchange two components. Such matrices have the form

A matrix $T$ is called a Pigou-Dalton transfer (PDT) if

$$T=\alpha I+(1-\alpha )E$$

for some $\alpha$ between 0 and 1, and $E\in {ℰ}_n$.

The following are equivalent

1. $x$ is majorized (http://planetmath.org/Majorization) by $y$.

2. $x=Dy$ for a doubly stochastic matrix $D$.

3. $x=T_1{T}_2\mathrm{\cdots }{T}_{k}y$ for finitely many PDT $T_1,\mathrm{\dots },T_k$.

4. ${\sum }_{i=1}^n\theta (x_i)\le {\sum }_{i=1}^n\theta (y_i)$ forall convex function $\theta$.

5. $x$ lies in the convex hull whose vertex set is

   $$\{(y_{\pi (1)},y_{\pi (2)},\mathrm{\dots },y_{\pi (n)}):\pi \text{ is a permutation of }\{1,\mathrm{\dots },n\}\}.$$

6. For any $n$ non-negative real numbers $a_1,\mathrm{\dots },a_n$,

   $$\sum _{\pi }{a}_1^{x_{\pi (1)}}{a}_2^{x_{\pi (2)}}\mathrm{\cdots }{a}_n^{x_{\pi (n)}}\le \sum _{\pi }{a}_1^{y_{\pi (1)}}{a}_2^{y_{\pi (2)}}\mathrm{\cdots }{a}_n^{y_{\pi (n)}}$$

   where summation is taken over all permutations of $\{1,\mathrm{\dots },n\}$.

The equivalence of the above conditions are due to Hardy,Littlewood, Pólya, Birkhoff, von Neumann and Muirhead.

Reference

• G. H. Hardy, J. E. Littlewood and G. Pólya, Inequalities, 2nd edition, 1952, Cambridge University Press,London.

• A. W. Marshall and I. Olkin, Inequalities: Theory ofMajorization and Its Applications, 1979, Acadamic Press, NewYork.