Majorisierung

Majorisierung bezeichnet in der Mathematik die Quasiordnung im Vektorraum der reellen Zahlen. Ein Vektor ${\displaystyle {\vec {a}}\in \mathbb {R} ^{d}}$ wird in dieser Quasiordnung durch ${\displaystyle {\vec {a}}^{\downarrow }\in \mathbb {R} ^{d}}$ dargestellt, bei dem die Komponenten des Vektors gleich bleiben, diese aber in absteigender Reihenfolge sortiert sind.

Wenn zwei Vektoren ${\displaystyle {\vec {a}},{\vec {b}}\in \mathbb {R} ^{d}}$ gegeben sind, dann majorisiert ${\displaystyle {\vec {a}}}$ den Vektor ${\displaystyle {\vec {b}}}$ schwach von unten (geschrieben als ${\displaystyle {\vec {a}}\succ _{w}{\vec {b}}}$), dann und nur dann, wenn

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

Äquivalent kann diese Bedingung auch formuliert werden als ${\displaystyle {\vec {b}}}$ wird vom Vektor ${\displaystyle {\vec {a}}}$ von unten schwach majorisiert, geschrieben als ${\displaystyle {\vec {b}}\prec _{w}{\vec {a}}}$.

Andersherum majorisiert ${\displaystyle {\vec {a}}}$ den Vektor ${\displaystyle {\vec {b}}}$ schwach von oben, geschrieben als ${\displaystyle {\vec {a}}\succ ^{w}{\vec {b}}}$ dann und nur dann, wenn

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

Wieder dazu äquivalent ist die Aussage, dass der Vektor ${\displaystyle {\vec {b}}}$ von ${\displaystyle {\vec {a}}}$ von oben schwach majorisiert wird, geschrieben als ${\displaystyle {\vec {b}}\prec ^{w}{\vec {a}}}$.

Wenn zusätzlich zu den oben genannten Bedingungen gilt, dass ${\displaystyle \textstyle \sum _{i=1}^{d}a_{i}=\sum _{i=1}^{d}b_{i}}$, dann majorisiert ${\displaystyle {\vec {a}}}$ den Vektor ${\displaystyle {\vec {b}}}$, geschrieben als ${\displaystyle {\vec {a}}\succ {\vec {b}}}$. Äquivalent dazu ist die Schreibweise ${\displaystyle {\vec {b}}\prec {\vec {a}}}$, gesprochen als ${\displaystyle {\vec {b}}}$ wird durch ${\displaystyle {\vec {a}}}$ majorisiert. Es lässt sich zeigen, dass gilt ${\displaystyle {\vec {a}}\succ {\vec {b}}\Leftrightarrow {\vec {a}}\succ _{w}{\vec {b}}\wedge {\vec {a}}\succ ^{w}{\vec {b}}}$.

Die Sortierung der Majorisierung hängt nicht von der Sortierung der Vektoren ${\displaystyle {\vec {a}}}$ und ${\displaystyle {\vec {b}}}$ ab. Wichtig ist, dass aus ${\displaystyle {\vec {a}}\succ {\vec {b}}}$ und ${\displaystyle {\vec {b}}\succ {\vec {a}}}$ nicht folgt, dass ${\displaystyle {\vec {a}}={\vec {b}}}$ ist. Zwar sind alle Komponenten der Vektoren ${\displaystyle {\vec {a}},{\vec {b}}}$ gleich, allerdings nicht notwendigerweise in der gleichen Anordnung.

Verwirrenderweise werden in der Literatur teilweise Definitionen verwendet, bei denen die Notation genau umgekehrt verwendet wird, das heißt ${\displaystyle \succ }$ wird durch ${\displaystyle \prec }$ ersetzt, während in neueren Versionen (sogar der Literatur, die die hier nicht genannte Definition verwenden) auf die hier im Artikel aufgeführte Definition zurückgreifen.

Eine Funktion ${\displaystyle f\colon \mathbb {R} ^{d}\to \mathbb {R} }$ heißt Schur-konvex, wenn aus ${\displaystyle {\vec {a}}\succ {\vec {b}}}$ folgt, dass ${\displaystyle f({\vec {a}})\geq f({\vec {b}})}$. Analog heißt ${\displaystyle f}$ Schur-konkav, wenn aus ${\displaystyle {\vec {a}}\succ {\vec {b}}}$ folgt, dass ${\displaystyle f({\vec {a}})\leq f({\vec {b}}).}$

Für eine Verteilungsfunktion lässt sich die Majorisierung zur Lorenzsortierung verallgemeinern.

Beispiele

Die Sortierung der Einträge beeinflusst die Majorisierung nicht, das heißt der Ausdruck ${\displaystyle (1,2)\prec (0,3)}$ ist äquivalent zu ${\displaystyle (2,1)\prec (3,0)}$.

Starke Majorisierung: ${\displaystyle (1,2,3)\prec (0,3,3)\prec (0,0,6)}$. Für Vektoren mit ${\displaystyle n}$ Einträgen:

${\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).}$

Schwache Majorisierung: ${\displaystyle (1,2,3)\prec _{w}(1,3,3)\prec _{w}(1,3,4)}$. Für Vektoren mit ${\displaystyle n}$ Einträgen:

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

Geometrie der Majorisierung

Für ${\displaystyle {\vec {x}},{\vec {y}}\in \mathbb {R} ^{n},}$ erhalten wir ${\displaystyle {\vec {x}}\prec {\vec {y}}}$ dann und nur dann, wenn ${\displaystyle {\vec {x}}}$ in der konvexen Hülle von allen Vektoren, die man erhält, wenn die Koordinaten des Vektors ${\displaystyle {\vec {y}}}$ permutiert werden, ist.

Die Abbildung links zeigt die konvexe Hülle in zwei Dimensionen für den Vektor ${\displaystyle (3,1)}$. In der Mitte dieser Hülle ist der Vektor ${\displaystyle {\vec {x}}=(2,2)}$. Dies ist der kürzeste Vektor, der ${\displaystyle {\vec {x}}\prec {\vec {y}}}$ für den hier gegebenen Vektor ${\displaystyle {\vec {y}}}$ erfüllt.

Die zweite Grafik zeigt die konvexe Hülle in drei Dimensionen. Hier ist der Mittelpunkt ein zweidimensionales Polygon, der durch den Vektor ${\displaystyle {\vec {x}}}$ beschrieben wird, der auch hier der kürzeste Vektor ist, der ${\displaystyle {\vec {x}}\prec {\vec {y}}}$ für diesen gegebenen ${\displaystyle {\vec {y}}}$.

Äquivalente Aussagen

Jede der folgenden Aussagen ist wahr dann und nur dann, wenn ${\displaystyle {\vec {a}}\succ {\vec {b}}}$:

• ${\displaystyle {\vec {b}}=D{\vec {a}}}$ für mindestens eine doppelt-stochastische Matrizen ${\displaystyle D}$ (siehe Arnold, Theorem 2.1). Dies ist äquivalent zu sagen, dass ${\displaystyle {\vec {b}}}$ als gewichtetes Mittel der Permutationen von ${\displaystyle {\vec {a}}}$ dargestellt werden kann.
• Aus ${\displaystyle {\vec {a}}}$ kann ${\displaystyle {\vec {b}}}$ erhalten werden, indem endlich viele „Robin Hood Operationen“ durchgeführt werden, bei denen zwei Elemente ${\displaystyle a_{i},a_{j}<a_{i}}$ mit ${\displaystyle a_{i}-\varepsilon }$ und ${\displaystyle a_{j}+\varepsilon }$ ersetzt werden, bei dem ${\displaystyle \varepsilon \in (0,a_{i}-a_{j})}$ (siehe Arnold, p. 11).
• Für jede konvexe Funktion ${\displaystyle h\colon \mathbb {R} \to \mathbb {R} }$ gilt:

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

• Für alle ${\displaystyle t\in \mathbb {R} }$ gilt:

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

In der linearen Algebra

• Angenommen, dass für zwei reelle Vektoren ${\displaystyle v,v'\in \mathbb {R} ^{d}}$ gilt, dass ${\displaystyle v'}$ durch ${\displaystyle v}$ majorisiert wird. Dann kann gezeigt werden, dass eine Menge von Wahrscheinlichkeiten ${\displaystyle (p_{1},p_{2},\ldots ,p_{d})}$ existiert, sodass ${\displaystyle \textstyle \sum _{i=1}^{d}p_{i}=1}$ und eine Menge von Permutationen ${\displaystyle (P_{1},P_{2},\ldots ,P_{d})}$ die Aussage ${\displaystyle \textstyle v'=\sum _{i=1}^{d}p_{i}P_{i}v}$ impliziert. Alternativ kann gezeigt werden, dass eine doppelt-stochastische Matrix ${\displaystyle D}$ existiert, sodass ${\displaystyle vD=v'}$ gilt.

• Ein Hermitescher Operator ${\displaystyle H}$ majorisiert einen anderen hermiteschen Operator ${\displaystyle H'}$, wenn der Vektor der Eigenwerte von ${\displaystyle H}$ den Vektor der Eigenwerte von ${\displaystyle H'}$ majorisiert, siehe Majorisierungskriterium.

Einzelnachweise

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. 1 2 3 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.

Literatur

• J. Karamata: Sur une inegalite relative aux fonctions convexes. In: Publ. Math. Univ. Belgrade. 1, 1932, S. 145–158.
• G. H. Hardy, J. E. Littlewood, G. Pólya: Inequalities. 2. Auflage. Cambridge University Press, London 1952.
• Albert W. Marshall, Ingram Olkin, Barry Arnold: Inequalities: Theory of Majorization and Its Applications. (= Springer Series in Statistics). 2. Auflage. 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.

Weblinks

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