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

The following statements are true if and only if \mathbf{a}\geq_M \mathbf{b}:

  • \mathbf{b} = D\mathbf{a} for some doubly stochastic matrix D.
  • 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).
  • 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). (This result is known as Karamata's theorem.)

A function f:\mathbb{R}^d \to \mathbb{R} is said to be Schur convex when \mathbf{a} \geq_M \mathbf{b} implies f(\mathbf{a}) \geq f(\mathbf{b}). Similarly, f(\mathbf{a}) is Schur concave when \mathbf{a} \geq_M \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.

[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] 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
  • Barry C. Arnold. "Majorization and the Lorenz Order: A Brief Introduction". Springer-Verlag Lecture Notes in Statistics, vol. 43, 1987.
  • J. Karamata. Sur une inegalite relative aux fonctions convexes. Publ. Math. Univ. Belgrade 1, 145-158, 1932.
Retrieved from "http://en.wikipedia.org../../../m/a/j/Majorization.html"
In other languages