# Majorization

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.

## Contents

## 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]

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 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]

- Muirhead's inequality
- Karamata's Inequality
- Schur-convex function
- Schur–Horn theorem relating diagonal entries of a matrix to its eigenvalues.
- For positive integer numbers, weak majorization is called Dominance order.

## Notes[edit]

- ^
^{a}^{b}^{c}Barry C. Arnold. "Majorization and the Lorenz Order: A Brief Introduction". Springer-Verlag Lecture Notes in Statistics, vol. 43, 1987. - ^
^{a}^{b}Xingzhi, Zhan (2003). "The sharp Rado theorem for majorizations".*The American Mathematical Monthly*.**110**(2): 152–153. doi:10.2307/3647776. **^**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]

- J. Karamata. "Sur une inegalite relative aux fonctions convexes."
*Publ. Math. Univ. Belgrade*1, 145–158, 1932. - G. H. Hardy, J. E. Littlewood and G. Pólya,
*Inequalities*, 2nd edition, 1952, Cambridge University Press, London. *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*Inequalities: Theory of Majorization and Its Applications*(1980) Albert W. Marshall, Ingram Olkin, Academic Press, ISBN 978-0-12-473750-1- A tribute to Marshall and Olkin's book "Inequalities: Theory of Majorization and its Applications"
*Matrix Analysis*(1996) Rajendra Bhatia, Springer, ISBN 978-0-387-94846-1*Topics in Matrix Analysis*(1994) Roger A. Horn and Charles R. Johnson, Cambridge University Press, ISBN 978-0-521-46713-1*Majorization and Matrix Monotone Functions in Wireless Communications*(2007) Eduard Jorswieck and Holger Boche, Now Publishers, ISBN 978-1-60198-040-3*The Cauchy Schwarz Master Class*(2004) J. Michael Steele, Cambridge University Press, ISBN 978-0-521-54677-5