Majorization

In mathematics, majorization is a preorder on vectors of real numbers. Let $^_,\ i=1,\,\ldots,\,n$ denote the $i$-th largest element of the vector $\mathbf\in\mathbb^n$. Given $\mathbf,\ \mathbf \in \mathbb^n$, we say that $\mathbf$ weakly majorizes (or dominates) $\mathbf$ from below (or equivalently, we say that $\mathbf$ is weakly majorized (or dominated) by $\mathbf$ from below) denoted as $\mathbf \succ_w \mathbf$ if $\sum_^k x_^ \geq \sum_^k y_^$ for all $k=1,\,\dots,\,d$. If in addition $\sum_^d x_i^ = \sum_^d y_i^$, we say that $\mathbf$ majorizes (or dominates) $\mathbf$, written as $\mathbf \succ \mathbf$, or equivalently, we say that $\mathbf$ is majorized (or dominated) by $\mathbf$. The order of the entries of the vectors $\mathbf$ or $\mathbf$ does not affect the majorization, e.g., the statement $(1,2)\prec (0,3)$ is simply equivalent to $(2,1)\prec (3,0)$. As a consequence, majorization is not a partial order, since $\mathbf \succ \mathbf$ and $\mathbf \succ \mathbf$ do not imply $\mathbf = \mathbf$, 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.

Examples

(Strong) majorization: $(1,2,3)\prec (0,3,3)\prec (0,0,6)$. For vectors with $n$ components
: $\left(\frac, \ldots, \frac\right)\prec \left(\frac, \ldots, \frac,0\right) \prec \cdots \prec \left(\frac,\frac, 0, \ldots, 0\right) \prec \left(1, 0, \ldots, 0\right).$

(Weak) majorization: $(1,2,3)\prec_w (1,3,3)\prec_w (1,3,4)$. For vectors with $n$ components:
: $\left(\frac, \ldots, \frac\right)\prec_w \left(\frac, \ldots, \frac,1\right).$

Geometry of majorization

For $\mathbf,\ \mathbf \in \mathbb^n,$ we have $\mathbf \prec \mathbf$ if and only if $\mathbf$ is in the convex hull of all vectors obtained by permuting the coordinates of $\mathbf$.
Figure 1 displays the convex hull in 2D for the vector $\mathbf=(3,\,1)$. Notice that the center of the convex hull, which is an interval in this case, is the vector $\mathbf=(2,\,2)$. This is the "smallest" vector satisfying $\mathbf \prec \mathbf$ for this given vector $\mathbf$.
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 $\mathbf$ satisfying $\mathbf \prec \mathbf$ for this given vector $\mathbf$.

Schur convexity

A function $f:\mathbb^n \to \mathbb$ is said to be Schur convex when $\mathbf \succ \mathbf$ implies $f(\mathbf) \geq f(\mathbf)$. Hence, Schur-convex functions translate the ordering of vectors to a standard ordering in $\mathbb$. Similarly, $f(\mathbf)$ is Schur concave when $\mathbf \succ \mathbf$ implies $f(\mathbf) \leq f(\mathbf).$

An example of a Schur-convex function is the max function, $\max(\mathbf)=x_^$. 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 $\mathbf\succ \mathbf$:

* $\mathbf = \mathbf\mathbf$ for some doubly stochastic matrix $\mathbf$.Barry C. Arnold. "Majorization and the Lorenz Order: A Brief Introduction". Springer-Verlag Lecture Notes in Statistics, vol. 43, 1987. This is equivalent to saying $\mathbf$ can be represented as a convex combination of the permutations of $\mathbf$; one can verify that there exists such a convex representation using at most $n$ permutations of $\mathbf$.
* From $\mathbf$ we can produce $\mathbf$ by a finite sequence of "Robin Hood operations" where we replace two elements $x_i$ and $x_j < x_i$ with $x_i-\varepsilon$ and $x_j+\varepsilon$, respectively, for some $\varepsilon \in (0, x_i-x_j)$.
* For every convex function $h:\mathbb\to \mathbb$, $\sum_^d h(x_i) \geq \sum_^d h(y_i)$.
**In fact, a special case suffices: $\sum_i=\sum_i$ and, for every , $\sum_^d \max(0,x_i-t) \geq\sum_^d \max(0,y_i-t)$.July 3, 2005 post by fleeting_guest o
"The Karamata Inequality" thread
AoPS community forums.
Archived
11 November 2020.
*$\forall t \in \mathbb \quad \sum_^d , x_j-t, \geq \sum_^d , y_j-t,$.

In linear algebra

* Suppose that for two real vectors $\mathbf,\ \mathbf \in \mathbb^d$, $\mathbf$ majorizes $\mathbf$. Then it can be shown that there exists a set of probabilities $(p_1,p_2,\ldots,p_d),\ \sum_^d p_i=1$ and a set of permutations $(P_1,P_2,\ldots,P_d)$ such that $\mathbf=\sum_^d p_iP_i\mathbf$. Alternatively it can be shown that there exists a doubly stochastic matrix $\mathbf$ such that $\mathbf\mathbf=\mathbf$

*We say that a Hermitian operator, $\mathbf$, majorizes another, $\mathbf$, if the set of eigenvalues of $\mathbf$ majorizes that of $\mathbf$.

In computability theory

Given $f, \ g : \mathbb \to\mathbb$, then $f$ is said to ''majorize'' $g$ if, for all $x$, $f(x)\geq g(x)$. If there is some $n$ so that $f(x)\geq g(x)$ for all $x > n$, then $f$ is said to ''dominate'' (or ''eventually dominate'') $g$. Alternatively, the preceding terms are often defined requiring the strict inequality $f(x) > g(x)$ instead of $f(x)\geq g(x)$ 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, {{ISBN, 978-0-521-54677-5

External links

Software

* OCTAVE/ MATLABbr>code to check majorization

Order theory
Linear algebra