Majorization

From Wikipedia, the free encyclopedia

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-1\},

\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}.

Similarly, we say that \mathbf{a} weakly majorizes \mathbf{b} written as \mathbf{a} \succeq_w \mathbf{b} iff \sum_{i=1}^d a_i^{\downarrow} \geq \sum_{i=1}^d b_i^{\downarrow} \quad \forall k=1,...,d

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.

Contents

[edit] 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 ai and aj < ai 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).
  • \forall t \in \mathbb{R} \quad \sum_{j=1}^d |a_j-t| \geq \sum_{j=1}^n |b_j-t|.[citation needed]

[edit] 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'.

[edit] 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.

[edit] See also

[edit] References

  1. ^ a b c Barry C. Arnold. "Majorization and the Lorenz Order: A Brief Introduction". Springer-Verlag Lecture Notes in Statistics, vol. 43, 1987.