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 $a i$ and $a j < a i$ 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.^{[citation needed]}

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 $v D = 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"

Categories: Articles with unsourced statements since February 2007 | All articles with unsourced statements | Order theory | Linear algebra