The Muirhead-Rado inequality, 1 Vector majorization and the permutohedron

Abstract

Let $\mathbf{a}$ and $\mathbf{b}$ be vectors in ${\mathbf{R}}^n$ with nonnegative coordinates. Permuting the coordinates, we can assume that $a_1\ge \cdots \ge a_n$ and $b_1\ge \cdots \ge b_n$. The vector $\mathbf{a}$ majorizes the vector $\mathbf{b}$, denoted $\mathbf{b}⪯\mathbf{a}$, if ${\sum }_{i=1}^n{b}_i={\sum }_{i=1}^n{a}_i$ and ${\sum }_{i=1}^k{b}_i\le {\sum }_{i=1}^k{a}_i$ for all $k\in \{1,\dots ,n-1\}$. This paper proves theorems of Hardy-Littlewood-Pólya and Rado that $\mathbf{b}⪯\mathbf{a}$ if and only if $P\mathbf{a}=\mathbf{b}$ for some doubly stochastic matrix $P$ if and only if $\mathbf{b}$ is in the $S_n$-permutohedron generated by $\mathbf{a}$.

22 pages