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,[1] 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.[2]

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,[3] 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,[3] 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,[3] 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,[4])

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.

Einzelnachweise

Roger A. Horn, Charles R. Johnson: Matrix analysis. Cambridge Univ. Press, 1985, ISBN 0-521-30586-1, 4.3.24.
Roger A. Horn, Charles R. Johnson: Matrix analysis. Cambridge Univ. Press, 2013, ISBN 978-0-521-54823-6, 4.3.24.
Barry C. Arnold: Majorization and the Lorenz Order: A Brief Introduction. (= Lecture Notes in Statistics. vol. 43). Springer-Verlag, 1987.
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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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

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

[NielsenChuang-4] Michael A. Nielsen, Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000.