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
where and are the elements of and , respectively, sorted in decreasing order. Equivalently, we say that is weakly majorized (or dominated) by from below, denoted as .
Similarly, we say that weakly majorizes from above written as iff
Equivalently, we say that is weakly majorized by from above, denoted as .
If and in addition we say that majorizes (or dominates) written as . Equivalently, we say that is majorized (or dominated) by , denoted as .
It is easy to see that if and only if and .
Note that the majorization order do 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.
Regrettably, to confuse the matter, some literature sources use the reverse notation, e.g., is replaced with , most notably, in Horn and Johnson, Matrix analysis (Cambridge Univ. Press, 1985), Definition 4.3.24, while the same authors switch to the traditional notation, introduced here, later in their Topics in Matrix Analysis (1994), and in the second edition of Matrix analysis (2013).
A function is said to be Schur convex when implies . Similarly, is Schur concave when implies
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
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 .
Each of the following statements is true if and only if :
- for some doubly stochastic matrix (see Arnold, Theorem 2.1). This is equivalent to saying b can be represented as a weighted average of the permutations of .
- 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, p. 11).
- For every convex function , (see Arnold, Theorem 2.9).
- . (see Nielsen and Chuang Exercise 12.17,)
In linear algebra
- 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 . 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
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.
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
- Muirhead'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.
- Barry C. Arnold. "Majorization and the Lorenz Order: A Brief Introduction". Springer-Verlag Lecture Notes in Statistics, vol. 43, 1987.
- Nielsen and Chuang. "Quantum Computation and Quantum Information". Cambridge University Press, 2000
- 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"
- Quantum Computation and Quantum Information, (2000) Michael A. Nielsen and Isaac L. Chuang, Cambridge University Press, ISBN 978-0-521-63503-5
- 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