Majorization

In mathematics, majorization is a preorder on vectors of real numbers. For two such vectors, ${\displaystyle \mathbf {x} ,\ \mathbf {y} \in \mathbb {R} ^{n}}$, we say that ${\displaystyle \mathbf {x} }$ weakly majorizes (or dominates) ${\displaystyle \mathbf {y} }$ from below, commonly denoted ${\displaystyle \mathbf {x} \succ _{w}\mathbf {y} ,}$ when

where ${\displaystyle x_{i}^{\downarrow }}$ denotes ${\displaystyle i}$^th largest entry of ${\displaystyle \mathbf {x} }$. If ${\displaystyle \mathbf {x} ,\mathbf {y} }$ further satisfy ${\displaystyle \sum _{i=1}^{n}x_{i}=\sum _{i=1}^{n}y_{i}}$, we say that ${\displaystyle \mathbf {x} }$ majorizes (or dominates) ${\displaystyle \mathbf {y} }$, commonly denoted ${\displaystyle \mathbf {x} \succ \mathbf {y} }$.

Both weak majorization and majorization are partial orders for vectors whose entries are non-decreasing, but only a preorder for general vectors, since majorization is agnostic to the ordering of the entries in vectors, e.g., the statement ${\displaystyle (1,2)\prec (0,3)}$ is simply equivalent to ${\displaystyle (2,1)\prec (3,0)}$.

Specifically, ${\displaystyle \mathbf {x} \succ \mathbf {y} \wedge \mathbf {y} \succ \mathbf {x} }$ if and only if ${\displaystyle \mathbf {x} ,\mathbf {y} }$ are permutations of each other. Similarly for ${\displaystyle \succ _{w}}$.

Majorizing also sometimes refers to entrywise ordering, e.g. the real-valued function f majorizes the real-valued function g when ${\displaystyle f(x)\geq g(x)}$ for all ${\displaystyle x}$ in the domain, or other technical definitions, such as majorizing measures in probability theory.

For ${\displaystyle \mathbf {x} ,\ \mathbf {y} \in \mathbb {R} ^{n},}$ we have ${\displaystyle \mathbf {x} \prec \mathbf {y} }$ if and only if ${\displaystyle \mathbf {x} }$ is in the convex hull of all vectors obtained by permuting the coordinates of ${\displaystyle \mathbf {y} }$. This is equivalent to saying that ${\displaystyle \mathbf {x} =\mathbf {D} \mathbf {y} }$ for some doubly stochastic matrix ${\displaystyle \mathbf {D} }$. In particular, ${\displaystyle \mathbf {x} }$ can be written as a convex combination of ${\displaystyle n}$ permutations of ${\displaystyle \mathbf {y} }$. In other words, ${\displaystyle \mathbf {x} }$ is in the permutahedron of ${\displaystyle \mathbf {y} }$.

Figure 1 displays the convex hull in 2D for the vector ${\displaystyle \mathbf {y} =(3,\,1)}$. Notice that the center of the convex hull, which is an interval in this case, is the vector ${\displaystyle \mathbf {x} =(2,\,2)}$. This is the "smallest" vector satisfying ${\displaystyle \mathbf {x} \prec \mathbf {y} }$ for this given vector ${\displaystyle \mathbf {y} }$. Figure 2 shows the convex hull in 3D. The center of the convex hull, which is a 2D polygon in this case, is the "smallest" vector ${\displaystyle \mathbf {x} }$ satisfying ${\displaystyle \mathbf {x} \prec \mathbf {y} }$ for this given vector ${\displaystyle \mathbf {y} }$.

Each of the following statements is true if and only if ${\displaystyle \mathbf {x} \succ \mathbf {y} }$.