Majorization

This article deals with the quasi-ordering of vectors in the . For functions, see Lorenz sorting . For rows, see majorant criterion ${\displaystyle \mathbb {R} ^{n}}$

Majorization in mathematics denotes the quasi-order in the vector space of real numbers . A vector is represented in this quasi-order by , in which the components of the vector remain the same, but they are sorted in descending order. ${\displaystyle {\vec {a}}\in \mathbb {R} ^{d}}$ ${\displaystyle {\vec {a}}^{\downarrow }\in \mathbb {R} ^{d}}$

Given two vectors , then weakly majorizes the vector from below (written as ) if and only if ${\displaystyle {\vec {a}},{\vec {b}}\in \mathbb {R} ^{d}}$ ${\displaystyle {\vec {a}}}$ ${\displaystyle {\vec {b}}}$ ${\displaystyle {\vec {a}}\succ _{w}{\vec {b}}}$

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

Equivalently, this condition can also be formulated as being weakly majorized by the vector from below , written as . ${\displaystyle {\vec {b}}}$ ${\displaystyle {\vec {a}}}$ ${\displaystyle {\vec {b}}\prec _{w}{\vec {a}}}$

Conversely, the vector weakly dominates from above , written as then and only if ${\displaystyle {\vec {a}}}$ ${\displaystyle {\vec {b}}}$ ${\displaystyle {\vec {a}}\succ ^{w}{\vec {b}}}$

${\displaystyle \sum _{i=k}^{d}a_{i}^{\downarrow }\leq \sum _{i=k}^{d}b_{i}^{\downarrow }\quad k=1,\dots ,d.}$

Is again equivalent to the statement that the vector of from above becomes weak outvoted, written as . ${\displaystyle {\vec {b}}}$ ${\displaystyle {\vec {a}}}$ ${\displaystyle {\vec {b}}\prec ^{w}{\vec {a}}}$

If also applies to the conditions mentioned above that , then outvoted the vector written as . The spelling is equivalent to this , spoken as being majorized by. It can be shown that it is true . ${\displaystyle \textstyle \sum _{i=1}^{d}a_{i}=\sum _{i=1}^{d}b_{i}}$ ${\displaystyle {\vec {a}}}$ ${\displaystyle {\vec {b}}}$ ${\displaystyle {\vec {a}}\succ {\vec {b}}}$ ${\displaystyle {\vec {b}}\prec {\vec {a}}}$ ${\displaystyle {\vec {b}}}$ ${\displaystyle {\vec {a}}}$ ${\displaystyle {\vec {a}}\succ {\vec {b}}\Leftrightarrow {\vec {a}}\succ _{w}{\vec {b}}\wedge {\vec {a}}\succ ^{w}{\vec {b}}}$

The sorting of the majorization does not depend on the sorting of the vectors and . It is important that it follows from and not that is. All components of the vectors are the same, but not necessarily in the same order. ${\displaystyle {\vec {a}}}$ ${\displaystyle {\vec {b}}}$ ${\displaystyle {\vec {a}}\succ {\vec {b}}}$ ${\displaystyle {\vec {b}}\succ {\vec {a}}}$ ${\displaystyle {\vec {a}}={\vec {b}}}$ ${\displaystyle {\vec {a}},{\vec {b}}}$

Confusingly, definitions are sometimes used in the literature in which the notation is used exactly the other way around, i.e. is replaced by , while in more recent versions (even of the literature that use the definition not mentioned here) fall back on the definition given here in the article. ${\displaystyle \succ }$ ${\displaystyle \prec }$

A function is called Schur convex if it follows that . Analogously, Schur is called concave if it follows that ${\displaystyle f\colon \mathbb {R} ^{d}\to \mathbb {R} }$ ${\displaystyle {\vec {a}}\succ {\vec {b}}}$ ${\displaystyle f({\vec {a}})\geq f({\vec {b}})}$ ${\displaystyle f}$ ${\displaystyle {\vec {a}}\succ {\vec {b}}}$ ${\displaystyle f({\vec {a}})\leq f({\vec {b}}).}$

For a distribution function , the majorization can be generalized to the Lorenz sorting .

Examples

The sorting of the entries does not affect the majorization, i.e. the expression is equivalent to . ${\displaystyle (1,2)\prec (0,3)}$ ${\displaystyle (2,1)\prec (3,0)}$

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

${\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 outvoted: . For vectors with entries: ${\displaystyle (1,2,3)\prec _{w}(1,3,3)\prec _{w}(1,3,4)}$ ${\displaystyle n}$

${\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

2D example of majorization

For we obtained when and only when in the complex envelope of all vectors which are obtained when the coordinates of the vector permuted be is. ${\displaystyle {\vec {x}},{\vec {y}}\in \mathbb {R} ^{n},}$ ${\displaystyle {\vec {x}}\prec {\vec {y}}}$ ${\displaystyle {\vec {x}}}$ ${\displaystyle {\vec {y}}}$

The figure on the left shows the convex hull in two dimensions for the vector . In the middle of this envelope is the vector . This is the shortest vector that satisfies for the vector given here . ${\displaystyle (3,1)}$ ${\displaystyle {\vec {x}}=(2,2)}$ ${\displaystyle {\vec {x}}\prec {\vec {y}}}$ ${\displaystyle {\vec {y}}}$

3D example of majorization

The second graphic shows the convex hull in three dimensions. Here the center point is a two-dimensional polygon, which is described by the vector , which is also the shortest vector given for this one . ${\displaystyle {\vec {x}}}$ ${\displaystyle {\vec {x}}\prec {\vec {y}}}$ ${\displaystyle {\vec {y}}}$

Equivalent statements

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

• ${\displaystyle {\vec {b}}=D{\vec {a}}}$for at least one double-stochastic matrix (see Arnold, Theorem 2.1). This is equivalent to saying that the permutations of can be represented as a weighted mean . ${\displaystyle D}$ ${\displaystyle {\vec {b}}}$ ${\displaystyle {\vec {a}}}$
• From can be obtained by performing a finite number of “Robin Hood operations” in which two elements are replaced with and , in which . (see Arnold, p. 11). ${\displaystyle {\vec {a}}}$ ${\displaystyle {\vec {b}}}$ ${\displaystyle a_{i},a_{j}<a_{i}}$ ${\displaystyle a_{i}-\varepsilon }$ ${\displaystyle a_{j}+\varepsilon }$ ${\displaystyle \varepsilon \in (0,a_{i}-a_{j})}$
• For every convex function : ${\displaystyle h\colon \mathbb {R} \to \mathbb {R} }$

${\displaystyle \sum _{i=1}^{d}h(a_{i})\geq \sum _{i=1}^{d}h(b_{i})}$ (see Arnold, Theorem 2.9).

• The following applies to all : ${\displaystyle t\in \mathbb {R} }$

${\displaystyle \sum _{j=1}^{d}|a_{j}-t|\geq \sum _{j=1}^{d}|b_{j}-t|}$. (see Nielsen and Chuang Exercise 12.17,)

In linear algebra

• Assume that for two real vectors it holds that is majorized by. Then it can be shown that a set of probabilities exists such that and a set of permutations implies the statement . Alternatively it can be shown that a doubly stochastic matrix exists such that it holds. ${\displaystyle v,v'\in \mathbb {R} ^{d}}$ ${\displaystyle v'}$ ${\displaystyle v}$ ${\displaystyle (p_{1},p_{2},\ldots ,p_{d})}$ ${\displaystyle \textstyle \sum _{i=1}^{d}p_{i}=1}$ ${\displaystyle (P_{1},P_{2},\ldots ,P_{d})}$ ${\displaystyle \textstyle v'=\sum _{i=1}^{d}p_{i}P_{i}v}$ ${\displaystyle D}$ ${\displaystyle vD=v'}$

• A Hermitian operator majorizes another Hermitian operator if the vector of the eigenvalues ​​of majorizes the vector of the eigenvalues ​​of , see majorization criterion . ${\displaystyle H}$ ${\displaystyle H'}$ ${\displaystyle H}$ ${\displaystyle H'}$

Individual evidence

1. ^ Roger A. Horn, Charles R. Johnson: Matrix analysis . Cambridge Univ. Press, 1985, ISBN 0-521-30586-1 , 4.3.24.
2. ^ Roger A. Horn, Charles R. Johnson: Matrix analysis . Cambridge Univ. Press, 2013, ISBN 978-0-521-54823-6 , 4.3.24.
3. ^ ^{A b c} Barry C. Arnold: Majorization and the Lorenz Order: A Brief Introduction. (= Lecture Notes in Statistics. Vol. 43). Springer-Verlag, 1987.
4. ↑ Michael A. Nielsen, Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000.

literature

• J. Karamata: Sur une inegalite relative aux fonctions convexes. In: Publ. Math. Univ. Belgrade. 1, 1932, pp. 145-158.
• GH Hardy, JE Littlewood, G. Pólya: Inequalities. 2nd Edition. Cambridge University Press, London 1952.
• Albert W. Marshall, Ingram Olkin, Barry Arnold: Inequalities: Theory of Majorization and Its Applications. (= Springer Series in Statistics ). 2nd Edition. Springer, New York 2011, ISBN 978-0-387-40087-7 .
• Albert W. Marshall, Ingram Olkin: Inequalities: Theory of Majorization and Its Applications. Academic Press, 1980, ISBN 0-12-473750-1 .
• A tribute to Marshall and Olkin's book "Inequalities: Theory of Majorization and its Applications".
• Michael A. Nielsen, Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000, ISBN 0-521-63503-9 .
• Rajendra Bhatia: Matrix Analysis. Springer, 1996, ISBN 0-387-94846-5 .
• Roger A. Horn, Charles R. Johnson: Topics in Matrix Analysis. Cambridge University Press, 1994, ISBN 0-521-46713-6 .
• Eduard Jorswieck, Holger Boche: Majorization and Matrix Monotone Functions in Wireless Communications. Now Publishers, 2007, ISBN 978-1-60198-040-3 .
• J. Michael Steele: The Cauchy Schwarz Master Class. Cambridge University Press, 2004, ISBN 0-521-54677-X .

Web links

• Majorization in MathWorld
• Majorization in PlanetMath
• GNU Octave / MATLAB code to check majorization