Majorization
From Wikipedia, the free encyclopedia
In mathematics, majorization is a partial order over vectors of real numbers. Given , we say that majorizes , and we write , if and for all ,
where and are the elements of and , respectively, sorted in decreasing order. Equivalently, we say that dominates , or that is majorized (or dominated) by .
Similarly, we say that weakly majorizes written as iff
A function is said to be Schur convex when implies . Similarly, is Schur concave when implies .
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 :
- for some doubly stochastic matrix D (see Arnold,[1] Theorem 2.1).
- From we can produce by a finite sequence of "Robin Hood operations" where we replace two elements ai and aj < ai with and , respectively, for some (see Arnold,[1] p. 11).
- For every convex function , (see Arnold,[1] Theorem 2.9).
- .[citation needed]
[edit] In linear algebra
- Suppose that for two real vectors , v majorizes v'. Then it can be shown that there exists a set of probabilities and a set of permutations such that . 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 , then f is said to majorize g if, for all x, . If there is some n so that for all x > n, then f is said to dominate (sometimes written "eventually dominate") f.
[edit] See also
[edit] References
- ^ a b c Barry C. Arnold. "Majorization and the Lorenz Order: A Brief Introduction". Springer-Verlag Lecture Notes in Statistics, vol. 43, 1987.
- 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.