Majorization

In mathematics, majorization is a preorder on vectors of real numbers. Let  denote the -th largest element of the vector . Given , we say that  weakly majorizes (or dominates)  from below (or equivalently, we say that  is weakly majorized (or dominated) by  from below) denoted as  if  for all . If in addition , we say that  majorizes (or dominates) , written as , or equivalently, we say that  is majorized (or dominated) by . The order of the entries of the vectors  or  does not affect the majorization, e.g., the statement  is simply equivalent to . As a consequence, 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.

The majorization partial order on finite dimensional vectors, 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 if its Lorenz curve lies below the other. As such, a Lorenz-greater wealth distribution has a higher Gini coefficient, and has more income disparity. Various other generalizations of majorization are discussed in chapters 14 and 15 of.

The majorization preorder can be naturally extended to density matrices in the context of quantum information. In particular,  exactly when  (where  denotes the state's spectrum).

Examples
(Strong) majorization: . For vectors with  components
 

(Weak) majorization: . For vectors with  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 .

Schur convexity 
A function  is said to be Schur convex when  implies . Hence, Schur-convex functions translate the ordering of vectors to a standard ordering in . Similarly,  is Schur concave when  implies 

An example of a Schur-convex function is the max function, . Schur convex functions are necessarily symmetric that the entries of it argument can be switched without modifying the value of the function. Therefore, linear functions, which are convex, are not Schur-convex unless they are symmetric. If a function is symmetric and convex, then it is Schur-convex.

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

  for some doubly stochastic matrix .  This is equivalent to saying  can be represented as a convex combination of the permutations of ; one can verify that there exists such a convex representation using at most  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 .
 For every convex function , .
In fact, a special case suffices:  and, for every , .
.

In linear algebra: Majorization of operators

We say that a Hermitian operator, , majorizes another, , if the set of eigenvalues of  majorizes that of .

In computability 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.

See also
 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.
 Leximin order

Notes

References
 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. 
 A tribute to Marshall and Olkin's book "Inequalities: Theory of Majorization and its Applications"
 Matrix Analysis (1996) Rajendra Bhatia, Springer, 
 Topics in Matrix Analysis (1994) Roger A. Horn and Charles R. Johnson, Cambridge University Press, 
 Majorization and Matrix Monotone Functions in Wireless Communications (2007)  Eduard Jorswieck and Holger Boche, Now Publishers, 
 The Cauchy Schwarz Master Class (2004) J. Michael Steele, Cambridge University Press,

External links
 Majorization in MathWorld
 Majorization in PlanetMath

Software
 OCTAVE/MATLAB code to check majorization

Order theory
Linear algebra