Definitions

# Majorization

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

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

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

Similarly, we say that $mathbf\left\{a\right\}$ weakly majorizes $mathbf\left\{b\right\}$ written as $mathbf\left\{a\right\} succeq_w mathbf\left\{b\right\}$ iff

$sum_\left\{i=1\right\}^k a_i^\left\{downarrow\right\} geq sum_\left\{i=1\right\}^k b_i^\left\{downarrow\right\} quad text\left\{for \right\} k=1,dots,d.$

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

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\left\{a\right\}succeq mathbf\left\{b\right\}$:

• $mathbf\left\{b\right\} = Dmathbf\left\{a\right\}$ for some doubly stochastic matrix $D$ (see Arnold, Theorem 2.1).
• From $mathbf\left\{a\right\}$ we can produce $mathbf\left\{b\right\}$ 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 \left(0, a_i-a_j\right)$ (see Arnold, p. 11).
• For every convex function $h:mathbb\left\{R\right\}to mathbb\left\{R\right\}$, $sum_\left\{i=1\right\}^d h\left(a_i\right) geq sum_\left\{i=1\right\}^d h\left(b_i\right)$ (see Arnold, Theorem 2.9).
• $forall t in mathbb\left\{R\right\} quad sum_\left\{j=1\right\}^d |a_j-t| geq sum_\left\{j=1\right\}^n |b_j-t|$.

## In linear algebra

• Suppose that for two real vectors $v,v\text{'} in mathbb\left\{R\right\}^d$, $v$ majorizes $v\text{'}$. Then it can be shown that there exists a set of probabilities $\left(p_1,p_2,ldots,p_d\right),$

sum_{i=1}^d p_i=1 and a set of permutations $\left(P_1,P_2,ldots,P_d\right)$ such that $v\text{'}=sum_\left\{i=1\right\}^d p_iP_iv$. Alternatively it can be shown that there exists a doubly stochastic matrix $D$ such that $vD=v\text{'}$

• We say that a hermitian operator, $H$, majorizes another, $H\text{'}$, if the set of eigenvalues of $H$ majorizes that of $H\text{'}$.

## In recursion theory

Given $f, g : mathbb\left\{N\right\} tomathbb\left\{N\right\}$, then $f$ is said to majorize $g$ if, for all $x$, $f\left(x\right)geq g\left(x\right)$. If there is some $n$ so that $f\left(x\right)geq g\left(x\right)$ for all $x > n$, then $f$ is said to dominate (sometimes written "eventually dominate") $f$.