# Majorization

In mathematics, majorization is a preorder on vectors of real numbers. For a vector $\mathbf {a} \in \mathbb {R} ^{d}$ , we denote by $\mathbf {a} ^{\downarrow }\in \mathbb {R} ^{d}$ the vector with the same components, but sorted in descending order. Given $\mathbf {a} ,\mathbf {b} \in \mathbb {R} ^{d}$ , we say that $\mathbf {a}$ weakly majorizes (or dominates) $\mathbf {b}$ from below written as $\mathbf {a} \succ _{w}\mathbf {b}$ iff

$\sum _{i=1}^{k}a_{i}^{\downarrow }\geq \sum _{i=1}^{k}b_{i}^{\downarrow }\quad {\text{for }}k=1,\dots ,d,$ Equivalently, we say that $\mathbf {b}$ is weakly majorized (or dominated) by $\mathbf {a}$ from below, written as $\mathbf {b} \prec _{w}\mathbf {a}$ .

If $\mathbf {a} \succ _{w}\mathbf {b}$ and in addition $\sum _{i=1}^{d}a_{i}=\sum _{i=1}^{d}b_{i}$ , we say that $\mathbf {a}$ majorizes (or dominates) $\mathbf {b}$ , written as $\mathbf {a} \succ \mathbf {b}$ . Equivalently, we say that $\mathbf {b}$ is majorized (or dominated) by $\mathbf {a}$ , written as $\mathbf {b} \prec \mathbf {a}$ .

Note that the majorization order does not depend on the order of the components of the vectors $\mathbf {a}$ or $\mathbf {b}$ . Majorization is not a partial order, since $\mathbf {a} \succ \mathbf {b}$ and $\mathbf {b} \succ \mathbf {a}$ do not imply $\mathbf {a} =\mathbf {b}$ , it only implies that the components of each vector are equal, but not necessarily in the same order.

Note that the notation is inconsistent in the mathematical literature: some use the reverse notation, e.g., $\succ$ is replaced with $\prec$ .

A function $f:\mathbb {R} ^{d}\to \mathbb {R}$ is said to be Schur convex when $\mathbf {a} \succ \mathbf {b}$ implies $f(\mathbf {a} )\geq f(\mathbf {b} )$ . Similarly, $f(\mathbf {a} )$ is Schur concave when $\mathbf {a} \succ \mathbf {b}$ implies $f(\mathbf {a} )\leq f(\mathbf {b} ).$ The majorization partial order on finite sets, described here, can be generalized to the Lorenz ordering, a partial order on distribution functions. For example, a wealth distribution is Lorenz-greater than another iff its Lorenz curve lies below the other. As such, a Lorenz-greater wealth distribution has a higher Gini coefficient, and has more income inequality.

## Examples

The order of the entries does not affect the majorization, e.g., the statement $(1,2)\prec (0,3)$ is simply equivalent to $(2,1)\prec (3,0)$ .

(Strong) majorization: $(1,2,3)\prec (0,3,3)\prec (0,0,6)$ . For vectors with n components

$\left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)\prec \left({\frac {1}{n-1}},\ldots ,{\frac {1}{n-1}},0\right)\prec \cdots \prec \left({\frac {1}{2}},{\frac {1}{2}},0,\ldots ,0\right)\prec \left(1,0,\ldots ,0\right).$ (Weak) majorization: $(1,2,3)\prec _{w}(1,3,3)\prec _{w}(1,3,4)$ . For vectors with n components:

$\left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)\prec _{w}\left({\frac {1}{n-1}},\ldots ,{\frac {1}{n-1}},1\right).$ ## Geometry of majorization

For $\mathbf {x} ,\mathbf {y} \in \mathbb {R} ^{n},$ we have $\mathbf {x} \prec \mathbf {y}$ if and only if $\mathbf {x}$ is in the convex hull of all vectors obtained by permuting the coordinates of $\mathbf {y}$ .

Figure 1 displays the convex hull in 2D for the vector $\mathbf {y} =(3,\,1)$ . Notice that the center of the convex hull, which is an interval in this case, is the vector $\mathbf {x} =(2,\,2)$ . This is the "smallest" vector satisfying $\mathbf {x} \prec \mathbf {y}$ for this given vector $\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 $\mathbf {x}$ satisfying $\mathbf {x} \prec \mathbf {y}$ for this given vector $\mathbf {y}$ .

## Equivalent conditions

Each of the following statements is true if and only if $\mathbf {a} \succ \mathbf {b}$ :

• $\mathbf {b} =D\mathbf {a}$ for some doubly stochastic matrix $D$ (see Arnold, Theorem 2.1). This is equivalent to saying $\mathbf {b}$ can be represented as a convex combination of the permutations of $\mathbf {a}$ . Furthermore the permutations require $d$ at most.
• From $\mathbf {a}$ we can produce $\mathbf {b}$ by a finite sequence of "Robin Hood operations" where we replace two elements $a_{i}$ and $a_{j} with $a_{i}-\varepsilon$ and $a_{j}+\varepsilon$ , respectively, for some $\varepsilon \in (0,a_{i}-a_{j})$ (see Arnold, p. 11).
• For every convex function $h:\mathbb {R} \to \mathbb {R}$ , $\sum _{i=1}^{d}h(a_{i})\geq \sum _{i=1}^{d}h(b_{i})$ (see Arnold, Theorem 2.9).
• $\forall t\in \mathbb {R} \quad \sum _{j=1}^{d}|a_{j}-t|\geq \sum _{j=1}^{d}|b_{j}-t|$ . (see Nielsen and Chuang Exercise 12.17,)

## In linear algebra

• Suppose that for two real vectors $v,v'\in \mathbb {R} ^{d}$ , $v$ majorizes $v'$ . Then it can be shown that there exists a set of probabilities $(p_{1},p_{2},\ldots ,p_{d}),\sum _{i=1}^{d}p_{i}=1$ and a set of permutations $(P_{1},P_{2},\ldots ,P_{d})$ such that $v'=\sum _{i=1}^{d}p_{i}P_{i}v$ . Alternatively it can be shown that there exists a doubly stochastic matrix $D$ such that $vD=v'$ • We say that a hermitian operator, $H$ , majorizes another, $H'$ , if the set of eigenvalues of $H$ majorizes that of $H'$ .

## In recursion theory

Given $f,g:\mathbb {N} \to \mathbb {N}$ , then $f$ is said to majorize $g$ if, for all $x$ , $f(x)\geq g(x)$ . If there is some $n$ so that $f(x)\geq g(x)$ for all $x>n$ , then $f$ is said to dominate (or eventually dominate) $g$ . Alternatively, the preceding terms are often defined requiring the strict inequality $f(x)>g(x)$ instead of $f(x)\geq g(x)$ in the foregoing definitions.

## Generalizations

Various generalizations of majorization are discussed in chapters 14 and 15 of the reference work Inequalities: Theory of Majorization and Its Applications. Albert W. Marshall, Ingram Olkin, Barry Arnold. Second edition. Springer Series in Statistics. Springer, New York, 2011. ISBN 978-0-387-40087-7