# Majorization

In mathematics, majorization is a partial order over vectors of real numbers. Given $\mathbf{a},\mathbf{b} \in \mathbb{R}^d$, we say that $\mathbf{a}$ majorizes $\mathbf{b}$, and we write $\mathbf{a} \succeq \mathbf{b}$, if $\sum_{i=1}^d a_i = \sum_{i=1}^d b_i$ and for all $k \in \{1, \ldots, d\}$,

$\sum_{i=1}^k a_i^{\downarrow} \geq \sum_{i=1}^k b_i^{\downarrow},$

where $a^{\downarrow}_i$ and $b^{\downarrow}_i$ are the elements of $\mathbf{a}$ and $\mathbf{b}$, respectively, sorted in decreasing order. Equivalently, we say that $\mathbf{a}$ dominates $\mathbf{b}$, or that $\mathbf{b}$ is majorized (or dominated) by $\mathbf{a}$.

A function $f:\mathbb{R}^d \to \mathbb{R}$ is said to be Schur convex when $\mathbf{a} \succeq \mathbf{b}$ implies $f(\mathbf{a}) \geq f(\mathbf{b})$. Similarly, $f(\mathbf{a})$ is Schur concave when $\mathbf{a} \succeq \mathbf{b}$ implies $f(\mathbf{a}) \leq f(\mathbf{b})$.

The majorization partial order on finite sets can be generalized to the Lorenz ordering, a partial order on distribution functions.

## Equivalent conditions

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

• $\mathbf{b} = D\mathbf{a}$ for some doubly stochastic matrix $D$ (see Arnold,[1] Theorem 2.1).
• 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 < a_i$ with $a_i-\varepsilon$ and $a_j+\varepsilon$, respectively, for some $\varepsilon \in (0, a_i-a_j)$ (see Arnold,[1] 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,[1] Theorem 2.9).

## 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_iP_iv$. 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 (sometimes written "eventually dominate") $f$.

## References

1. 1.0 1.1 1.2 Barry C. Arnold. "Majorization and the Lorenz Order: A Brief Introduction". Springer-Verlag Lecture Notes in Statistics, vol. 43, 1987.