Majorisierung

Quasiordnung im Vektorraum der reellen Zahlen

Majorisierung bezeichnet in der Mathematik die Quasiordnung im Vektorraum der reellen Zahlen. Ein Vektor wird in dieser Quasiordnung durch dargestellt, bei dem die Komponenten des Vektors gleich bleiben, diese aber in absteigender Reihenfolge sortiert sind.

Wenn zwei Vektoren gegeben sind, dann majorisiert den Vektor schwach von unten (geschrieben als ), dann und nur dann, wenn

Äquivalent kann diese Bedingung auch formuliert werden als wird vom Vektor von unten schwach majorisiert, geschrieben als .

Andersherum majorisiert den Vektor schwach von oben, geschrieben als dann und nur dann, wenn

Wieder dazu äquivalent ist die Aussage, dass der Vektor von von oben schwach majorisiert wird, geschrieben als .

Wenn zusätzlich zu den oben genannten Bedingungen gilt, dass , dann majorisiert den Vektor , geschrieben als . Äquivalent dazu ist die Schreibweise , gesprochen als wird durch majorisiert. Es lässt sich zeigen, dass gilt .

Die Sortierung der Majorisierung hängt nicht von der Sortierung der Vektoren und ab. Wichtig ist, dass aus und nicht folgt, dass ist. Zwar sind alle Komponenten der Vektoren 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 wird durch 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 heißt Schur-konvex, wenn aus folgt, dass . Analog heißt Schur-konkav, wenn aus folgt, dass

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

Beispiele

Bearbeiten

Die Sortierung der Einträge beeinflusst die Majorisierung nicht, das heißt der Ausdruck   ist äquivalent zu  .

Starke Majorisierung:  . Für Vektoren mit   Einträgen:

 

Schwache Majorisierung:  . Für Vektoren mit   Einträgen:

 

Geometrie der Majorisierung

Bearbeiten
 
2D Beispiel der Majorisierung

Für   erhalten wir   dann und nur dann, wenn   in der konvexen Hülle von allen Vektoren, die man erhält, wenn die Koordinaten des Vektors   permutiert werden, ist.

Die Abbildung links zeigt die konvexe Hülle in zwei Dimensionen für den Vektor  . In der Mitte dieser Hülle ist der Vektor  . Dies ist der kürzeste Vektor, der   für den hier gegebenen Vektor   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   beschrieben wird, der auch hier der kürzeste Vektor ist, der   für diesen gegebenen  .

Äquivalente Aussagen

Bearbeiten

Jede der folgenden Aussagen ist wahr dann und nur dann, wenn  :

  •   für mindestens eine doppelt-stochastische Matrizen   (siehe Arnold,[3] Theorem 2.1). Dies ist äquivalent zu sagen, dass   als gewichtetes Mittel der Permutationen von   dargestellt werden kann.
  • Aus   kann   erhalten werden, indem endlich viele „Robin Hood Operationen“ durchgeführt werden, bei denen zwei Elemente   mit   und   ersetzt werden, bei dem   (siehe Arnold,[3] p. 11).
  • Für jede konvexe Funktion   gilt:
  (siehe Arnold,[3] Theorem 2.9).
  • Für alle   gilt:
 . (siehe Nielsen and Chuang Aufgabe 12.17,[4])

In der linearen Algebra

Bearbeiten
  • Angenommen, dass für zwei reelle Vektoren   gilt, dass   durch   majorisiert wird. Dann kann gezeigt werden, dass eine Menge von Wahrscheinlichkeiten   existiert, sodass   und eine Menge von Permutationen   die Aussage   impliziert. Alternativ kann gezeigt werden, dass eine doppelt-stochastische Matrix   existiert, sodass   gilt.
  • Ein Hermitescher Operator   majorisiert einen anderen hermiteschen Operator  , wenn der Vektor der Eigenwerte von   den Vektor der Eigenwerte von   majorisiert, siehe Majorisierungskriterium.

Einzelnachweise

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

Literatur

Bearbeiten
  • 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.
Bearbeiten