Majorization

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In mathematics, majorization is a preorder on vectors of real numbers. For a vector , we denote by the vector with the same components, but sorted in descending order. Given , we say that weakly majorizes (or dominates) from below written as iff

Equivalently, we say that is weakly majorized (or dominated) by from below, written as .

If and in addition , we say that majorizes (or dominates) , written as . Equivalently, we say that is majorized (or dominated) by , written as .

Note that the majorization order does not depend on the order of the components of the vectors or . Majorization is not a partial order, since and do not imply , it only implies that the components of each vector are equal, but not necessarily in the same order.

Note that the notation is inconsistent in the mathematical literature: some use the reverse notation, e.g., is replaced with .

A function is said to be Schur convex when implies . Similarly, is Schur concave when implies

The majorization partial order on finite sets, described here, can be generalized to the Lorenz ordering, a partial order on distribution functions. For example, a wealth distribution is Lorenz-greater than another iff its Lorenz curve lies below the other. As such, a Lorenz-greater wealth distribution has a higher Gini coefficient, and has more income inequality.

Examples[edit]

The order of the entries does not affect the majorization, e.g., the statement is simply equivalent to .

(Strong) majorization: . For vectors with n components

(Weak) majorization: . For vectors with n components:

Geometry of majorization[edit]

Figure 1. 2D majorization example

For we have if and only if is in the convex hull of all vectors obtained by permuting the coordinates of .

Figure 1 displays the convex hull in 2D for the vector . Notice that the center of the convex hull, which is an interval in this case, is the vector . This is the "smallest" vector satisfying for this given vector .

Figure 2. 3D Majorization Example

Figure 2 shows the convex hull in 3D; the center of the convex hull, which is a 2D polygon in this case, is the "smallest" vector satisfying for this given vector .

Equivalent conditions[edit]

Each of the following statements is true if and only if :

  • for some doubly stochastic matrix (see Arnold,[1] Theorem 2.1). This is equivalent to saying can be represented as a convex combination of the permutations of . Furthermore the permutations require at most.[2]
  • From we can produce by a finite sequence of "Robin Hood operations" where we replace two elements and with and , respectively, for some (see Arnold,[1] p. 11).
  • For every convex function , (see Arnold,[1] Theorem 2.9).
  • . (see Nielsen and Chuang Exercise 12.17,[3])

In linear algebra[edit]

  • Suppose that for two real vectors , majorizes . Then it can be shown that there exists a set of probabilities and a set of permutations such that .[2] Alternatively it can be shown that there exists a doubly stochastic matrix such that
  • We say that a hermitian operator, , majorizes another, , if the set of eigenvalues of majorizes that of .

In recursion theory[edit]

Given , then is said to majorize if, for all , . If there is some so that for all , then is said to dominate (or eventually dominate) . Alternatively, the preceding terms are often defined requiring the strict inequality instead of in the foregoing definitions.

Generalizations[edit]

Various generalizations of majorization are discussed in chapters 14 and 15 of the reference work Inequalities: Theory of Majorization and Its Applications. Albert W. Marshall, Ingram Olkin, Barry Arnold. Second edition. Springer Series in Statistics. Springer, New York, 2011. ISBN 978-0-387-40087-7

See also[edit]

Notes[edit]

  1. ^ a b c Barry C. Arnold. "Majorization and the Lorenz Order: A Brief Introduction". Springer-Verlag Lecture Notes in Statistics, vol. 43, 1987.
  2. ^ a b Xingzhi, Zhan (2003). "The sharp Rado theorem for majorizations". The American Mathematical Monthly. 110 (2): 152–153. doi:10.2307/3647776.
  3. ^ Nielsen, Michael A.; Chuang, Isaac L. (2010). Quantum Computation and Quantum Information (2nd ed.). Cambridge: Cambridge University Press. ISBN 978-1-107-00217-3. OCLC 844974180.

References[edit]

External links[edit]

Software[edit]