Majorization

In mathematics, majorization is a preorder on vectors of real numbers. For a vector formula_1, we denote by formula_2 the vector with the same components, but sorted in descending order. Given formula_3, we say that formula_4 weakly majorizes (or dominates) formula_5 from below written as formula_6 iff
Equivalently, we say that formula_8 is weakly majorized (or dominated) by formula_9 from below, written as formula_10.
If formula_6 and in addition formula_12, we say that formula_4 majorizes (or dominates) formula_5, written as formula_15. Equivalently, we say that formula_8 is majorized (or dominated) by formula_9, written as formula_18.
Note that the majorization order does not depend on the order of the components of the vectors formula_4 or formula_5. Majorization is not a partial order, since formula_15 and formula_22 do not imply formula_23, 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., formula_24 is replaced with formula_25.
A function formula_26 is said to be Schur convex when formula_27 implies formula_28. Similarly, formula_29 is Schur concave when formula_27 implies formula_31
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.
The order of the entries does not affect the majorization, e.g., the statement formula_32 is simply 
equivalent to formula_33.
(Strong) majorization: formula_34. For vectors with "n" components
(Weak) majorization: formula_36. For vectors with "n" components:
Geometry of majorization.
For formula_38 we have
formula_39 if and only if formula_40 is in the convex hull of all vectors obtained by permuting the coordinates of formula_41.
Figure 1 displays the convex hull in 2D for the vector formula_42. Notice that the center of the convex hull, which is an interval in this case, is the vector formula_43. This is the "smallest" vector satisfying formula_39 for this given vector formula_41.
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 formula_40 satisfying formula_39 for this given vector formula_41.
Equivalent conditions.
Each of the following statements is true if and only if formula_49:
In recursion theory.
Given formula_80, then formula_81 is said to "majorize" formula_82 if, for all formula_83, formula_84. If there is some formula_85 so that formula_84 for all formula_87, then formula_81 is said to "dominate" (or "eventually dominate") formula_82. Alternatively, the preceding terms are often defined requiring the strict inequality formula_90 instead of formula_84 in the foregoing definitions.
Generalizations.
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. 