Majorisierung

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

Wenn zwei Vektoren $\overrightarrow{a},\overrightarrow{b}\in {ℝ}^d$ gegeben sind, dann majorisiert $\overrightarrow{a}$ den Vektor $\overrightarrow{b}$ schwach von unten (geschrieben als $\overrightarrow{a}{\succ }_w\overrightarrow{b}$), dann und nur dann, wenn

$\sum _{i=1}^k{a}_i^{\downarrow }\ge \sum _{i=1}^k{b}_i^{\downarrow }k=1,\dots ,d.$

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

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

$\sum _{i=k}^d{a}_i^{\downarrow }\le \sum _{i=k}^d{b}_i^{\downarrow }k=1,\dots ,d.$

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

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

Die Sortierung der Majorisierung hängt nicht von der Sortierung der Vektoren $\overrightarrow{a}$ und $\overrightarrow{b}$ ab. Wichtig ist, dass aus $\overrightarrow{a}\succ \overrightarrow{b}$ und $\overrightarrow{b}\succ \overrightarrow{a}$ nicht folgt, dass $\overrightarrow{a}=\overrightarrow{b}$ ist. Zwar sind alle Komponenten der Vektoren $\overrightarrow{a},\overrightarrow{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:{ℝ}^d\to ℝ$ heißt Schur-konvex, wenn aus $\overrightarrow{a}\succ \overrightarrow{b}$ folgt, dass $f(\overrightarrow{a})\ge f(\overrightarrow{b})$. Analog heißt $f$ Schur-konkav, wenn aus $\overrightarrow{a}\succ \overrightarrow{b}$ folgt, dass $f(\overrightarrow{a})\le f(\overrightarrow{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:

$(\frac{1}{n},\dots ,\frac{1}{n})\prec (\frac{1}{n-1},\dots ,\frac{1}{n-1},0)\prec \cdots \prec (\frac{1}{2},\frac{1}{2},0,\dots ,0)\prec (1,0,\dots ,0).$

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

$(\frac{1}{n},\dots ,\frac{1}{n}){\prec }_w(\frac{1}{n-1},\dots ,\frac{1}{n-1},1).$

Geometrie der Majorisierung

2D Beispiel der Majorisierung

Für $\overrightarrow{x},\overrightarrow{y}\in {ℝ}^n,$ erhalten wir $\overrightarrow{x}\prec \overrightarrow{y}$ dann und nur dann, wenn $\overrightarrow{x}$ in der konvexen Hülle von allen Vektoren, die man erhält, wenn die Koordinaten des Vektors $\overrightarrow{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 $\overrightarrow{x}=(2,2)$. Dies ist der kürzeste Vektor, der $\overrightarrow{x}\prec \overrightarrow{y}$ für den hier gegebenen Vektor $\overrightarrow{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 $\overrightarrow{x}$ beschrieben wird, der auch hier der kürzeste Vektor ist, der $\overrightarrow{x}\prec \overrightarrow{y}$ für diesen gegebenen $\overrightarrow{y}$.

Äquivalente Aussagen

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

• $\overrightarrow{b}=D\overrightarrow{a}$ für mindestens eine doppelt-stochastische Matrizen $D$ (siehe Arnold, Theorem 2.1). Dies ist äquivalent zu sagen, dass $\overrightarrow{b}$ als gewichtetes Mittel der Permutationen von $\overrightarrow{a}$ dargestellt werden kann.
• Aus $\overrightarrow{a}$ kann $\overrightarrow{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-\epsilon$ und $a_j+\epsilon$ ersetzt werden, bei dem $\epsilon \in (0,a_i-a_j)$ (siehe Arnold, p. 11).
• Für jede konvexe Funktion $h:ℝ\to ℝ$ gilt:

$\sum _{i=1}^{d}h(a_i)\ge \sum _{i=1}^{d}h(b_i)$ (siehe Arnold, Theorem 2.9).

• Für alle $t\in ℝ$ gilt:

$\sum _{j=1}^d|a_j-t|\ge \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^{\prime }\in {ℝ}^d$ gilt, dass $v^{\prime }$ durch $v$ majorisiert wird. Dann kann gezeigt werden, dass eine Menge von Wahrscheinlichkeiten $(p_1,p_2,\dots ,p_d)$ existiert, sodass ${\sum }_{i=1}^d{p}_i=1$ und eine Menge von Permutationen $(P_1,P_2,\dots ,P_d)$ die Aussage $v^{\prime }={\sum }_{i=1}^d{p}_i{P}_{i}v$ impliziert. Alternativ kann gezeigt werden, dass eine doppelt-stochastische Matrix $D$ existiert, sodass $vD=v^{\prime }$ gilt.

• Ein Hermitescher Operator $H$ majorisiert einen anderen hermiteschen Operator $H^{\prime }$, wenn der Vektor der Eigenwerte von $H$ den Vektor der Eigenwerte von $H^{\prime }$ 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