Majorization

In mathematics, majorization is a preorder on vectors of real numbers. For two such vectors, $\mathbf {x} ,\ \mathbf {y} \in \mathbb {R} ^{n}$ , we say that $\mathbf {x}$ weakly majorizes (or dominates) $\mathbf {y}$ from below, commonly denoted $\mathbf {x} \succ _{w}\mathbf {y} ,$ when

\sum _{i=1}^{k}x_{i}^{\downarrow }\geq \sum _{i=1}^{k}y_{i}^{\downarrow }

for all

k=1,\,\dots ,\,n

,

where $x_{i}^{\downarrow }$ denotes $i$ ^th largest entry of $x$ . If $\mathbf {x} ,\mathbf {y}$ further satisfy $\sum _{i=1}^{n}x_{i}=\sum _{i=1}^{n}y_{i}$ , we say that $\mathbf {x}$ majorizes (or dominates) $\mathbf {y}$ , commonly denoted $\mathbf {x} \succ \mathbf {y}$ . Majorization is a partial order for vectors whose entries are non-decreasing, but only a preorder for general vectors, since majorization is agnostic to the ordering of the entries in vectors, e.g., the statement $(1,2)\prec (0,3)$ is simply equivalent to $(2,1)\prec (3,0)$ .

Majorizing also sometimes refers to entrywise ordering, e.g. the real-valued function f majorizes the real-valued function g when $f(x)\geq g(x)$ for all $x$ in the domain, or other technical definitions, such as majorizing measures in probability theory.^[1]

Equivalent conditions

Geometric definition

Figure 1. 2D majorization example

For $\mathbf {x} ,\ \mathbf {y} \in \mathbb {R} ^{n},$ we have $\mathbf {x} \prec \mathbf {y}$ if and only if $\mathbf {x}$ is in the convex hull of all vectors obtained by permuting the coordinates of $\mathbf {y}$ . This is equivalent to saying that $\mathbf {x} =\mathbf {D} \mathbf {y}$ for some doubly stochastic matrix $\mathbf {D}$ .^[2]^{: Thm. 2.1} In particular, $\mathbf {x}$ can be written as a convex combination of $n$ permutations of $\mathbf {y}$ .^[3]

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

Figure 2. 3D Majorization Example

Other definitions

Each of the following statements is true if and only if $\mathbf {x} \succ \mathbf {y}$ .

From $\mathbf {x}$ we can produce $\mathbf {y}$ 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})$ .^[2]^: 11
For every convex function $h:\mathbb {R} \to \mathbb {R}$ , $\sum _{i=1}^{d}h(x_{i})\geq \sum _{i=1}^{d}h(y_{i})$ .^[2]^{: Thm. 2.9}
- In fact, a special case suffices: $\sum _{i}{x_{i}}=\sum _{i}{y_{i}}$ and, for every $t$ , $\sum _{i=1}^{d}\max(0,x_{i}-t)\geq \sum _{i=1}^{d}\max(0,y_{i}-t)$ .^[4]
For every $t\in \mathbb {R}$ , $\sum _{j=1}^{d}|x_{j}-t|\geq \sum _{j=1}^{d}|y_{j}-t|$ .^[5]^{: Exercise 12.17}

Examples

Among non-negative vectors with three components, $(1,0,0)$ and permutations of it majorize all other vectors $(p_{1},p_{2},p_{3})$ such that $p_{1}+p_{2}+p_{3}=1$ . For example, $(1,0,0)\succ (1/2,0,1/2)$ . Similarly, $(1/3,1/3,1/3)$ is majorized by all other such vectors, so $(1/2,0,1/2)\succ (1/3,1/3,1/3)$ .

This behavior extends to general-length probability vectors: the singleton vector majorizes all other probability vectors, and the uniform distribution is majorized by all probability vectors.

Schur convexity

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

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

The majorization preorder can be naturally extended to density matrices in the context of quantum information.^[5]^[7] In particular, $\rho \succ \rho '$ exactly when $\mathrm {spec} [\rho ]\succ \mathrm {spec} [\rho ']$ (where $\mathrm {spec}$ denotes the state's spectrum).

Similarly, one can say a Hermitian operator, $\mathbf {H}$ , majorizes another, $\mathbf {M}$ , if the set of eigenvalues of $\mathbf {H}$ majorizes that of $\mathbf {M}$ .

Notes

^ Talagrand, Michel (1996-07-01). "Majorizing measures: the generic chaining". The Annals of Probability. 24 (3). doi:10.1214/aop/1065725175. ISSN 0091-1798.
^ ^a ^b ^c Barry C. Arnold. "Majorization and the Lorenz Order: A Brief Introduction". Springer-Verlag Lecture Notes in Statistics, vol. 43, 1987.
^ Xingzhi, Zhan (2003). "The sharp Rado theorem for majorizations". The American Mathematical Monthly. 110 (2): 152–153. doi:10.2307/3647776. JSTOR 3647776.
^ July 3, 2005 post by fleeting_guest on "The Karamata Inequality" thread, AoPS community forums. Archived 11 November 2020.
^ ^a ^b 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.
^ Marshall, Albert W. (2011). "14, 15". Inequalities : theory of majorization and its applications. Ingram Olkin, Barry C. Arnold (2nd ed.). New York: Springer Science+Business Media, LLC. ISBN 978-0-387-68276-1. OCLC 694574026.
^ Wehrl, Alfred (1 April 1978). "General properties of entropy". Reviews of Modern Physics. 50 (2): 221–260. Bibcode:1978RvMP...50..221W. doi:10.1103/RevModPhys.50.221.

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
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

Software

OCTAVE/MATLAB code to check majorization

[1] Talagrand, Michel (1996-07-01). "Majorizing measures: the generic chaining". The Annals of Probability. 24 (3). doi:10.1214/aop/1065725175. ISSN 0091-1798.

[Arnold-2] Barry C. Arnold. "Majorization and the Lorenz Order: A Brief Introduction". Springer-Verlag Lecture Notes in Statistics, vol. 43, 1987.

[Zhan-3] Xingzhi, Zhan (2003). "The sharp Rado theorem for majorizations". The American Mathematical Monthly. 110 (2): 152–153. doi:10.2307/3647776. JSTOR 3647776.

[4] July 3, 2005 post by fleeting_guest on "The Karamata Inequality" thread, AoPS community forums. Archived 11 November 2020.

[NielsenChuang-5] 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.

[6] Marshall, Albert W. (2011). "14, 15". Inequalities : theory of majorization and its applications. Ingram Olkin, Barry C. Arnold (2nd ed.). New York: Springer Science+Business Media, LLC. ISBN 978-0-387-68276-1. OCLC 694574026.

[7] Wehrl, Alfred (1 April 1978). "General properties of entropy". Reviews of Modern Physics. 50 (2): 221–260. Bibcode:1978RvMP...50..221W. doi:10.1103/RevModPhys.50.221.

[1]

[2]

[3]

[4]

[5]

[6]

[7]