Majorization

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

<math>\sum_{i=1}^k a_i^{\downarrow} \geq \sum_{i=1}^k b_i^{\downarrow},</math>

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

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

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 <math>\mathbf{a}\succeq \mathbf{b}</math>:

• <math>\mathbf{b} = D\mathbf{a}</math> for some doubly stochastic matrix <math>D</math> (see Arnold, Theorem 2.1).
• From <math>\mathbf{a}</math> we can produce <math>\mathbf{b}</math> by a finite sequence of "Robin Hood operations" where we replace two elements <math>a_i</math> and <math>a_j < a_i</math> with <math>a_i-\varepsilon</math> and <math>a_j+\varepsilon</math>, respectively, for some <math>\varepsilon \in (0, a_i-a_j)</math> (see Arnold, p. 11).
• For every convex function <math>h:\mathbb{R}\to \mathbb{R}</math>, <math>\sum_{i=1}^d h(a_i) \geq \sum_{i=1}^d h(b_i)</math> (see Arnold, Theorem 2.9).

In linear algebra

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

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

• We say that a hermitian operator, <math>H</math>, majorizes another, <math>H'</math>, if the set of eigenvalues of <math>H</math> majorizes that of <math>H'</math>.

In recursion theory

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

References

• Quantum Computation and Quantum Information, (2000) Michael A. Nielsen and Isaac L. Chuang, Cambridge University Press
• Majorization and its applications to quantum information theory, (1999) Michael A, Nielsen, personal notes
• Majorization in Mathworld
• J. Karamata. Sur une inegalite relative aux fonctions convexes. Publ. Math. Univ. Belgrade 1, 145-158, 1932.he:מיוריזציה