# Majorization

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Majorization
> Markdown URL: https://mediated.wiki/source/Majorization.md
> Source: https://en.wikipedia.org/wiki/Majorization
> Source revision: 1350550559
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Preorder on vectors of real numbers}}
{{about|a specific ordering on real vectors|ordering in general|Partially ordered set}}

In [mathematics](/source/mathematics), '''majorization''' is a [preorder](/source/preorder) on [vectors](/source/vector_space) of [real numbers](/source/real_numbers). For two such vectors, <math>\mathbf{x},\ \mathbf{y} \in \mathbb{R}^n</math>, we say that <math> \mathbf{x} </math> '''weakly majorizes''' (or dominates) <math> \mathbf{y} </math> '''from below''', commonly denoted <math> \mathbf{x} \succ_w \mathbf{y}, </math> when
: <math> \sum_{i=1}^k x_i^{\downarrow} \geq \sum_{i=1}^k y_i^{\downarrow}</math> for all <math> k=1,\,\dots,\,n</math>,
where <math>x_i^{\downarrow}</math> denotes the <math>i</math><sup>th</sup> largest entry of <math>\mathbf{x}</math>. If <math>\mathbf{x}, \mathbf{y}</math> further satisfy <math>\sum_{i=1}^n x_i = \sum_{i=1}^n y_i</math>, we say that <math> \mathbf{x} </math> '''majorizes''' (or dominates) <math> \mathbf{y} </math>, commonly denoted <math> \mathbf{x} \succ \mathbf{y}</math>. 

Both weak majorization and majorization are [partial orders](/source/partially_ordered_set) for vectors whose entries are non-decreasing, but only a [preorder](/source/preorder) for general vectors, since majorization is agnostic to the ordering of the entries in vectors, e.g., the statement <math>(1,2)\prec (0,3)</math> is simply equivalent to <math>(2,1)\prec (3,0)</math>.

Specifically, <math> \mathbf{x} \succ \mathbf{y} \wedge \mathbf{y} \succ \mathbf{x}</math> if and only if <math> \mathbf{x}, \mathbf{y}</math> are permutations of each other. Similarly for <math> \succ_w</math>.

Majorizing also sometimes refers to entrywise ordering, e.g. the real-valued function ''f'' majorizes the real-valued function ''g'' when <math>f(x) \geq g(x)</math> for all <math>x</math> in the domain, or other technical definitions, such as majorizing measures in [probability theory](/source/probability_theory).<ref>{{Cite journal |last=Talagrand |first=Michel |date=1996-07-01 |title=Majorizing measures: the generic chaining |journal=The Annals of Probability |volume=24 |issue=3 |doi=10.1214/aop/1065725175 |issn=0091-1798|doi-access=free }}</ref>

==Equivalent conditions==
=== Geometric definition ===
thumb|250px|Figure 1. 2D majorization example
For <math>\mathbf{x},\ \mathbf{y} \in \mathbb{R}^n,</math> we have <math>\mathbf{x} \prec \mathbf{y}</math> if and only if <math>\mathbf{x}</math> is in the [convex hull](/source/convex_hull) of all vectors obtained by permuting the coordinates of <math>\mathbf{y}</math>. This is equivalent to saying that <math>\mathbf{x} = \mathbf{D}\mathbf{y}</math> for some [doubly stochastic matrix](/source/doubly_stochastic_matrix) <math>\mathbf{D}</math>.<ref name="Arnold">Barry C. Arnold.  "Majorization and the Lorenz Order: A Brief Introduction".  Springer-Verlag Lecture Notes in Statistics, vol. 43, 1987.</ref>{{Rp|Thm. 2.1}} In particular, <math>\mathbf{x}</math> can be written as a [convex combination](/source/convex_combination) of <math>n</math> permutations of <math>\mathbf{y}</math>.<ref name="Zhan">{{cite journal|last1=Xingzhi|first1=Zhan|title=The sharp Rado theorem for majorizations|journal=The American Mathematical Monthly|date=2003|volume=110|issue=2|pages=152–153|doi=10.2307/3647776|jstor=3647776}}</ref> In other words, <math>\mathbf{x}</math> is in the [permutahedron](/source/Permutohedron) of <math>\mathbf{y}</math>.

Figure 1 displays the convex hull in 2D for the vector <math>\mathbf{y}=(3,\,1)</math>. Notice that the center of the convex hull, which is an interval in this case, is the vector <math>\mathbf{x}=(2,\,2)</math>. This is the "smallest" vector satisfying  <math>\mathbf{x} \prec \mathbf{y}</math> for this given vector <math>\mathbf{y}</math>.
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 <math>\mathbf{x}</math> satisfying  <math>\mathbf{x} \prec \mathbf{y}</math> for this given vector <math>\mathbf{y}</math>.
thumb|250px|Figure 2. 3D Majorization Example

=== Other definitions ===
Each of the following statements is true if and only if <math>\mathbf{x}\succ \mathbf{y}</math>.
* From <math>\mathbf{x}</math> we can produce <math>\mathbf{y}</math> by a finite sequence of "Robin Hood operations" where we replace two elements <math>x_i</math> and <math>x_j < x_i</math> with <math>x_i-\varepsilon</math> and <math>x_j+\varepsilon</math>, respectively, for some <math>\varepsilon \in (0, x_i-x_j)</math>.<ref name="Arnold" />{{Rp|11}}
* For every convex function <math>h:\mathbb{R}\to \mathbb{R}</math>, <math>\sum_{i=1}^d h(x_i) \geq \sum_{i=1}^d h(y_i)</math>.<ref name="Arnold" />{{Rp|Thm. 2.9}}
**In fact, a special case suffices: <math>\sum_i{x_i}=\sum_i{y_i}</math> and, for every {{mvar|t}}, <math>\sum_{i=1}^d \max(0,x_i-t) \geq\sum_{i=1}^d \max(0,y_i-t)</math>.<ref>July 3, 2005 post by fleeting_guest on [https://artofproblemsolving.com/community/c6h14975p106317 "The Karamata Inequality" thread], [AoPS](/source/Art_of_Problem_Solving) community forums.  [https://archive.today/20201112031735/https://artofproblemsolving.com/community/c6h14975p106317 Archived] 11 November 2020.</ref>
*For every <math>t \in \mathbb{R}</math>, <math> \sum_{j=1}^d |x_j-t| \geq \sum_{j=1}^d |y_j-t|</math>.<ref name="NielsenChuang">{{Cite book|last1=Nielsen|first1=Michael A.|authorlink1=Michael Nielsen|last2=Chuang|first2=Isaac L.|authorlink2=Isaac Chuang|title=[Quantum Computation and Quantum Information](/source/Quantum_Computation_and_Quantum_Information_(book))|publisher=Cambridge University Press|location=Cambridge|year=2010|edition=2nd|oclc=844974180|isbn=978-1-107-00217-3}}</ref>{{Rp|Exercise 12.17}}
*thumb|Three vectors and their concave curves, illustrating <math>x \succ z, y \succ z, \neg(x \succ y), \neg(y  \succ x)</math>.Each vector <math>\mathbf{x}</math> can be plotted as a concave curve by connecting <math>(0,0), (1, x_1^{\downarrow}), (2, x_1^{\downarrow}+x_2^{\downarrow}), \dots, (n, x_1^{\downarrow}+x_2^{\downarrow} + \dots +x_n^{\downarrow})</math>. Then <math>\mathbf{x}\succ \mathbf{y}</math> is equivalent to the curve of <math>\mathbf{x}</math> being higher than that of <math>\mathbf{y}</math>.

==Examples==
Among non-negative vectors with three components, <math>(1, 0, 0)</math> and permutations of it majorize all other vectors <math>(p_1, p_2, p_3)</math> such that <math>p_1 + p_2 + p_3 = 1</math>. For example, <math>(1, 0, 0) \succ (1/2, 0, 1/2)</math>. Similarly, <math>(1/3, 1/3, 1/3)</math> is majorized by all other such vectors, so <math>(1/2, 0, 1/2) \succ (1/3, 1/3, 1/3)</math>.

This behavior extends to general-length [probability vector](/source/probability_vector)s: the singleton vector majorizes all other probability vectors, and the uniform distribution is majorized by all probability vectors.

== Schur convexity ==
{{Main|Schur-convex function}}
A function <math>f:\mathbb{R}^n \to \mathbb{R}</math> is said to be [Schur convex](/source/Schur-convex_function) when <math>\mathbf{x} \succ \mathbf{y}</math> implies <math>f(\mathbf{x}) \geq  f(\mathbf{y})</math>. Hence, Schur-convex functions translate the ordering of vectors to a standard ordering in <math>\mathbb{R}</math>. Similarly, <math>f(\mathbf{x})</math> is '''Schur concave''' when <math>\mathbf{x} \succ \mathbf{y}</math> implies <math>f(\mathbf{x}) \leq f(\mathbf{y}).</math>

An example of a Schur-convex function is the max function, <math>\max(\mathbf{x})=x_{1}^{\downarrow}</math>. 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.

== Generalizations ==
Majorization can be generalized to the [Lorenz ordering](/source/Lorenz_curve), a partial order on [distribution functions](/source/cumulative_distribution_function). For example, a [wealth distribution](/source/Income_distribution) is Lorenz-greater than another if its [Lorenz curve](/source/Lorenz_curve) lies below the other. As such, a Lorenz-greater wealth distribution has a higher [Gini coefficient](/source/Gini_coefficient), and has more [income disparity](/source/income_inequality).<ref>{{Cite book |last=Marshall |first=Albert W. |title=Inequalities : theory of majorization and its applications |date=2011 |publisher=Springer Science+Business Media, LLC |others=Ingram Olkin, Barry C. Arnold |isbn=978-0-387-68276-1 |edition=2nd |location=New York |oclc=694574026|chapter=14, 15}}</ref>

The majorization preorder can be naturally extended to [density matrices](/source/density_matrix) in the context of [quantum information](/source/quantum_information).<ref name=NielsenChuang /><ref>{{cite journal|first1=Alfred|last1=Wehrl|title=General properties of entropy|url=https://link.aps.org/doi/10.1103/RevModPhys.50.221|journal=Reviews of Modern Physics|date=1 April 1978|pages=221–260|volume=50|issue=2|doi=10.1103/RevModPhys.50.221|bibcode=1978RvMP...50..221W |url-access=subscription}}</ref> In particular, <math>\rho\succ\rho'</math> exactly when <math>\mathrm{spec}[\rho]\succ\mathrm{spec}[\rho']</math> (where <math>\mathrm{spec}</math> denotes the state's [spectrum](/source/spectrum_of_a_matrix)).

Similarly, one can say a [Hermitian operator](/source/Hermitian_operator), <math>\mathbf{H}</math>, majorizes another, <math>\mathbf{M}</math>, if the set of eigenvalues of <math>\mathbf{H}</math> majorizes that of <math>\mathbf{M}</math>.

==See also==
* [Muirhead's inequality](/source/Muirhead's_inequality)
* [Karamata's Inequality](/source/Karamata's_Inequality)
* [Schur-convex function](/source/Schur-convex_function)
* [Schur–Horn theorem](/source/Schur%E2%80%93Horn_theorem) relating diagonal entries of a matrix to its eigenvalues.
* For positive [integer number](/source/integer_number)s, weak majorization is called [Dominance order](/source/Dominance_order).
* [Leximin order](/source/Leximin_order)

==Notes==
<references/>

==References==
* J. Karamata. "Sur une inegalite relative aux fonctions convexes." ''Publ. Math. Univ. Belgrade''&nbsp;1, 145&ndash;158, 1932.
* [G. H. Hardy](/source/G._H._Hardy), [J. E. Littlewood](/source/J._E._Littlewood) and [G. Pólya](/source/G._P%C3%B3lya), ''Inequalities'', 2nd edition, 1952, Cambridge University Press, London.
* ''Inequalities: Theory of Majorization and Its Applications'' Albert W. Marshall, [Ingram Olkin](/source/Ingram_Olkin), Barry Arnold, Second edition. Springer Series in Statistics. Springer, New York, 2011. {{ISBN|978-0-387-40087-7}}
* [https://arxiv.org/abs/0801.4221v1 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==
* [http://mathworld.wolfram.com/Majorization.html Majorization in MathWorld]
* [https://web.archive.org/web/20080705151536/http://planetmath.org/encyclopedia/Majorization.html Majorization in PlanetMath]

==Software==
* [OCTAVE](/source/OCTAVE)/[MATLAB](/source/MATLAB) [http://www.mathworks.com/matlabcentral/fileexchange/26962-majorization-check code to check majorization]

Category:Order theory
Category:Linear algebra

---
Adapted from the Wikipedia article [Majorization](https://en.wikipedia.org/wiki/Majorization) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Majorization?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.