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

${\displaystyle \sum _{i=1}^{k}x_{i}^{\downarrow }\geq \sum _{i=1}^{k}y_{i}^{\downarrow }}$ for all ${\displaystyle k=1,\,\dots ,\,n}$,

where ${\displaystyle x_{i}^{\downarrow }}$ denotes ${\displaystyle i}$^th largest entry of ${\displaystyle 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} }$. Majorization is a partial order 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)}$.

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.^[1]