Majorisierung

Majorisierung bezeichnet in der Mathematik die Quasiordnung im Vektorraum der reellen Zahlen. Ein Vektor ${\vec {a}}\in \mathbb {R} ^{d}$ wird in dieser Quasiordnung durch ${\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 ${\vec {a}},{\vec {b}}\in \mathbb {R} ^{d}$ gegeben sind, dann majorisiert ${\vec {a}}$ den Vektor ${\vec {b}}$ schwach von unten (geschrieben als ${\vec {a}}\succ _{w}{\vec {b}}$), dann und nur dann, wenn

$\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 ${\vec {b}}$ wird vom Vektor ${\vec {a}}$ von unten schwach majorisiert, geschrieben als ${\vec {b}}\prec _{w}{\vec {a}}$.

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

$\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 ${\vec {b}}$ von ${\vec {a}}$ von oben schwach majorisiert wird, geschrieben als ${\vec {b}}\prec ^{w}{\vec {a}}$.

Wenn zusätzlich zu den oben genannten Bedingungen gilt, dass $\textstyle \sum _{i=1}^{d}a_{i}=\sum _{i=1}^{d}b_{i}$, dann majorisiert ${\vec {a}}$ den Vektor ${\vec {b}}$, geschrieben als ${\vec {a}}\succ {\vec {b}}$. Äquivalent dazu ist die Schreibweise ${\vec {b}}\prec {\vec {a}}$, gesprochen als ${\vec {b}}$ wird durch ${\vec {a}}$ majorisiert. Es lässt sich zeigen, dass gilt ${\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 ${\vec {a}}$ und ${\vec {b}}$ ab. Wichtig ist, dass aus ${\vec {a}}\succ {\vec {b}}$ und ${\vec {b}}\succ {\vec {a}}$ nicht folgt, dass ${\vec {a}}={\vec {b}}$ ist. Zwar sind alle Komponenten der Vektoren ${\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 $\succ$ wird durch $\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 $f\colon \mathbb {R} ^{d}\to \mathbb {R}$ heißt Schur-konvex, wenn aus ${\vec {a}}\succ {\vec {b}}$ folgt, dass $f({\vec {a}})\geq f({\vec {b}})$. Analog heißt $f$ Schur-konkav, wenn aus ${\vec {a}}\succ {\vec {b}}$ folgt, dass $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 $(1,2)\prec (0,3)$ ist äquivalent zu $(2,1)\prec (3,0)$.

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

$\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: $(1,2,3)\prec _{w}(1,3,3)\prec _{w}(1,3,4)$. Für Vektoren mit $n$ Einträgen:

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

2D Beispiel der Majorisierung

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

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

3D Beispiel der Majorisierung

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

Äquivalente Aussagen

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

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

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

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

$\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 $v,v'\in \mathbb {R} ^{d}$ gilt, dass $v'$ durch $v$ majorisiert wird. Dann kann gezeigt werden, dass eine Menge von Wahrscheinlichkeiten $(p_{1},p_{2},\ldots ,p_{d})$ existiert, sodass $\textstyle \sum _{i=1}^{d}p_{i}=1$ und eine Menge von Permutationen $(P_{1},P_{2},\ldots ,P_{d})$ die Aussage $\textstyle v'=\sum _{i=1}^{d}p_{i}P_{i}v$ impliziert. Alternativ kann gezeigt werden, dass eine doppelt-stochastische Matrix $D$ existiert, sodass $vD=v'$ gilt.

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

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