majorization

For any real vector $x=(x_1,x_2,\mathrm{\dots },x_n)\in {ℝ}^n$, let $x_{(1)}\ge x_{(2)}\ge \mathrm{\cdots }\ge x_{(n)}$ denote the components of $x$ in non-increasing order.

For $x,y\in {ℝ}^n$, we say that $x$ is majorized by $y$, or $y$ majorizes $x$, if

${\displaystyle \sum _{i=1}^m}{x}_{(i)}$$\le {\displaystyle \sum _{i=1}^m}{y}_{(i)},\text{ for }m=1,\mathrm{\dots },n-1\text{, and}$

${\displaystyle \sum _{i=1}^n}{x}_{(i)}$$={\displaystyle \sum _{i=1}^n}{y}_{(i)}$

A common notation for “$x$ is majorized by $y$” is $x\prec y$.

Remark:

A canonical example is that, if $y_1$, $y_2,\mathrm{\dots },y_n$ are non-negative real numbers such that their sum is equal to 1, then

$$(\frac{1}{n},\mathrm{\dots },\frac{1}{n})\prec (y_1,\mathrm{\dots },y_n).$$

In general, $x\prec y$ vaguely means that the components of $x$ is less spread out than are the components of $y$.

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 of Majorization and Its Applications, 1979, Acadamic Press, New York.