Majorization

In mathematics, majorization is a preorder on vectors of real numbers. For a vector ${\displaystyle \mathbf {a} \in \mathbb {R} ^{d}}$, we denote by ${\displaystyle \mathbf {a} ^{\downarrow }\in \mathbb {R} ^{d}}$ the vector with the same components, but sorted in descending order. Given ${\displaystyle \mathbf {a} ,\mathbf {b} \in \mathbb {R} ^{d}}$, we say that ${\displaystyle \mathbf {a} }$ weakly majorizes (or dominates) ${\displaystyle \mathbf {b} }$ from below written as ${\displaystyle \mathbf {a} \succ _{w}\mathbf {b} }$ iff

${\displaystyle \sum _{i=1}^{k}a_{i}^{\downarrow }\geq \sum _{i=1}^{k}b_{i}^{\downarrow }\quad {\text{for }}k=1,\dots ,d,}$

Equivalently, we say that ${\displaystyle \mathbf {b} }$ is weakly majorized (or dominated) by ${\displaystyle \mathbf {a} }$ from below, written as ${\displaystyle \mathbf {b} \prec _{w}\mathbf {a} }$.

If ${\displaystyle \mathbf {a} \succ _{w}\mathbf {b} }$ and in addition ${\displaystyle \sum _{i=1}^{d}a_{i}=\sum _{i=1}^{d}b_{i}}$, we say that ${\displaystyle \mathbf {a} }$ majorizes (or dominates) ${\displaystyle \mathbf {b} }$, written as ${\displaystyle \mathbf {a} \succ \mathbf {b} }$. Equivalently, we say that ${\displaystyle \mathbf {b} }$ is majorized (or dominated) by ${\displaystyle \mathbf {a} }$, written as ${\displaystyle \mathbf {b} \prec \mathbf {a} }$.

Note that the majorization order does not depend on the order of the components of the vectors ${\displaystyle \mathbf {a} }$ or ${\displaystyle \mathbf {b} }$. Majorization is not a partial order, since ${\displaystyle \mathbf {a} \succ \mathbf {b} }$ and ${\displaystyle \mathbf {b} \succ \mathbf {a} }$ do not imply ${\displaystyle \mathbf {a} =\mathbf {b} }$, 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., ${\displaystyle \succ }$ is replaced with ${\displaystyle \prec }$.

A function ${\displaystyle f:\mathbb {R} ^{d}\to \mathbb {R} }$ is said to be Schur convex when ${\displaystyle \mathbf {a} \succ \mathbf {b} }$ implies ${\displaystyle f(\mathbf {a} )\geq f(\mathbf {b} )}$. Similarly, ${\displaystyle f(\mathbf {a} )}$ is Schur concave when ${\displaystyle \mathbf {a} \succ \mathbf {b} }$ implies ${\displaystyle f(\mathbf {a} )\leq f(\mathbf {b} ).}$

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 ${\displaystyle (1,2)\prec (0,3)}$ is simply equivalent to ${\displaystyle (2,1)\prec (3,0)}$.

(Strong) majorization: ${\displaystyle (1,2,3)\prec (0,3,3)\prec (0,0,6)}$. For vectors with n components

${\displaystyle \left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)\prec \left({\frac {1}{n-1}},\ldots ,{\frac {1}{n-1}},0\right)\prec \cdots \prec \left({\frac {1}{2}},{\frac {1}{2}},0,\ldots ,0\right)\prec \left(1,0,\ldots ,0\right).}$

(Weak) majorization: ${\displaystyle (1,2,3)\prec _{w}(1,3,3)\prec _{w}(1,3,4)}$. For vectors with n components:

${\displaystyle \left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)\prec _{w}\left({\frac {1}{n-1}},\ldots ,{\frac {1}{n-1}},1\right).}$

Geometry of majorization

Figure 1. 2D majorization example

For ${\displaystyle \mathbf {x} ,\mathbf {y} \in \mathbb {R} ^{n},}$ we have ${\displaystyle \mathbf {x} \prec \mathbf {y} }$ if and only if ${\displaystyle \mathbf {x} }$ is in the convex hull of all vectors obtained by permuting the coordinates of ${\displaystyle \mathbf {y} }$.

Figure 1 displays the convex hull in 2D for the vector ${\displaystyle \mathbf {y} =(3,\,1)}$. Notice that the center of the convex hull, which is an interval in this case, is the vector ${\displaystyle \mathbf {x} =(2,\,2)}$. This is the "smallest" vector satisfying ${\displaystyle \mathbf {x} \prec \mathbf {y} }$ for this given vector ${\displaystyle \mathbf {y} }$.

Figure 2. 3D Majorization Example

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 ${\displaystyle \mathbf {x} }$ satisfying ${\displaystyle \mathbf {x} \prec \mathbf {y} }$ for this given vector ${\displaystyle \mathbf {y} }$.

Equivalent conditions

Each of the following statements is true if and only if ${\displaystyle \mathbf {a} \succ \mathbf {b} }$:

• ${\displaystyle \mathbf {b} =D\mathbf {a} }$ for some doubly stochastic matrix ${\displaystyle D}$.[1]^{:Thm. 2.1} This is equivalent to saying ${\displaystyle \mathbf {b} }$ can be represented as a convex combination of the permutations of ${\displaystyle \mathbf {a} }$; one can verify that there exists such a convex representation using at most ${\displaystyle d}$ permutations of ${\displaystyle \mathbf {a} }$.[2]
• From ${\displaystyle \mathbf {a} }$ we can produce ${\displaystyle \mathbf {b} }$ by a finite sequence of "Robin Hood operations" where we replace two elements ${\displaystyle a_{i}}$ and ${\displaystyle a_{j}<a_{i}}$ with ${\displaystyle a_{i}-\varepsilon }$ and ${\displaystyle a_{j}+\varepsilon }$, respectively, for some ${\displaystyle \varepsilon \in (0,a_{i}-a_{j})}$.[1]^:11
• For every convex function ${\displaystyle h:\mathbb {R} \to \mathbb {R} }$, ${\displaystyle \sum _{i=1}^{d}h(a_{i})\geq \sum _{i=1}^{d}h(b_{i})}$.[1]^{:Thm. 2.9}
  • In fact, a special case suffices: ${\displaystyle \sum _{i}{a_{i}}=\sum _{i}{b_{i}}}$ and, for every t, ${\displaystyle \sum _{i=1}^{d}{\max {(0,a_{i}-t)}}\geq \sum _{i=1}^{d}{\max {(0,b_{i}-t)}}}$.[3]
• ${\displaystyle \forall t\in \mathbb {R} \quad \sum _{j=1}^{d}|a_{j}-t|\geq \sum _{j=1}^{d}|b_{j}-t|}$.[4]^{:Exercise 12.17}

In linear algebra

• Suppose that for two real vectors ${\displaystyle v,v'\in \mathbb {R} ^{d}}$, ${\displaystyle v}$ majorizes ${\displaystyle v'}$. Then it can be shown that there exists a set of probabilities ${\displaystyle (p_{1},p_{2},\ldots ,p_{d}),\sum _{i=1}^{d}p_{i}=1}$ and a set of permutations ${\displaystyle (P_{1},P_{2},\ldots ,P_{d})}$ such that ${\displaystyle v'=\sum _{i=1}^{d}p_{i}P_{i}v}$.[2] Alternatively it can be shown that there exists a doubly stochastic matrix ${\displaystyle D}$ such that ${\displaystyle vD=v'}$

• We say that a Hermitian operator, ${\displaystyle H}$, majorizes another, ${\displaystyle H'}$, if the set of eigenvalues of ${\displaystyle H}$ majorizes that of ${\displaystyle H'}$.

In recursion theory

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

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.

Notes

1. Barry C. Arnold. "Majorization and the Lorenz Order: A Brief Introduction". Springer-Verlag Lecture Notes in Statistics, vol. 43, 1987.
2. Xingzhi, Zhan (2003). "The sharp Rado theorem for majorizations". The American Mathematical Monthly. 110 (2): 152–153. doi:10.2307/3647776. JSTOR 3647776.
3. July 3, 2005 post by fleeting_guest on "The Karamata Inequality" thread, AoPS community forums. Archived 11 November, 2020.
4. 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

• 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

External links

• Majorization in MathWorld
• Majorization in PlanetMath

Software

• OCTAVE/MATLAB code to check majorization