Majorisation
En mathématiques, on désigne par majorisation un certain préordre sur les éléments de l'espace vectoriel de dimension d sur les nombres réels. Ce préordre a de nombreuses applications dans diverses branches des mathématiques.
Définition
modifierPour un vecteur , on note le vecteur de qui a les mêmes composantes, mais rangées en ordre décroissant. Par exemple, .
Soient x et y deux vecteurs de . On dit que y majorise ou domine x, et l'on note , ou encore , si
pour et de plus
Par définition, la majorisation ne dépend pas de l’ordre des composantes des deux vecteurs, et ce n'est donc pas une relation d'ordre, puisque et n'implique pas que y = x, mais seulement que [1].
Une fonction est dite convexe au sens de Schur si implique .
La majorisation, comme définie ici, peut être étendue en un ordre appelé ordre de Lorenz (en), qui est un ordre partiel sur des fonctions de répartition.
Exemples
modifier- Comme l'ordre des entrées n'influe par sur la majorisation, on a tout comme .
- De même, .
- Plus intéressante est la séquence suivante de vecteurs de :
Conditions équivalentes
modifier![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e1/2D_Majorization_Example.png/220px-2D_Majorization_Example.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/95/3D_Majorization_Example.png/220px-3D_Majorization_Example.png)
Pour , les propriétés suivantes sont équivalentes à .
- Il existe une suite finie de vecteurs dont le premier est y, le dernier est x et le successeur b de chaque vecteur a est une combinaison convexe de a et de l'un de ses transposés, ce qui revient à dire qu'on passe de a à b par un « transfert de Robin des Bois[2],[3] » : en ne modifiant que deux composantes u ≤ v, augmentant u d'au plus v – u et diminuant v d'autant.
- x est dans l'enveloppe convexe de tous les vecteurs obtenus en permutant les coordonnées de y, c'est-à-dire des d! vecteursoù σ parcourt le groupe symétrique Sd.
La figure 1 montre l'enveloppe convexe, en bleu, pour le vecteur y = (3, 1) ; c'est le segment de droite joignant (3, 1) à (1, 3). Parmi tous les vecteurs x sur ce segment, celui pour lequel la première composante de est la plus petite est le vecteur x = (2, 2). La figure 2 montre une enveloppe convexe en 3D, qui est ici un polygone plan. Son centre est le « plus petit » vecteur x tel que . - On a x = Ay pour une matrice bistochastique A[4].
- Pour toute fonction convexe , on a[5] (inégalité de Karamata (en)).
- Pour tout nombre réel , on a [6].
- Il existe une matrice hermitienne dont l'« ensemble » des valeurs propres est y et la suite des entrées diagonales est x (théorème de Schur-Horn).
Emploi du terme dans d'autres contextes
modifier- Si H et H' sont deux matrices hermitiennes, on dit que H majorise H' si l'ensemble des valeurs propres de H majorise celui de H'.
- Étant donné deux suites d'entiers naturels , on dit que f majorise g si f(k) ≥ g(k) pour tout k. Si l'on a seulement f(k) ≥ g(k) pour tout k > n pour un certain n, on dit que f majorise ultimement[réf. souhaitée] g.
- Diverses autres applications et généralisations sont discutées dans l'ouvrage de référence Marshall, Olkin et Arnold 2011.
Voir aussi
modifier- Inégalité de Muirhead
- Fonction Schur-convexe
- Ordre de domination. C'est une version faible de majorisation appliquée aux entiers naturels.
Notes et références
modifier- Pour ajouter de la confusion, certaines sources utilisent une notation opposée, c'est-à-dire au lieu de . Il en est ainsi dans des livres anciens en anglais, notamment dans Horn et Johnson 1985, Definition 4.3.24. Ultérieurement, ces auteurs, dans Horn et Johnson 1994 utilisent la notation qui est adoptée ici.
- Arnold 1987, p. 13.
- Marshall, Olkin et Arnold 2011, p. 7.
- Arnold 1987, Theorem 2.1
- Arnold 1987, Theorem 2.9.
- Nielsen et Chuang 2000, Exercise 12.17.
- Kadison 2002, lemme 5 et Kadison et Pedersen 1985, lemme 13 p. 258-259, démontrent l'équivalence avec les deux premières propriétés dans le cas particulier où les coordonnées de x et y sont rangées dans un ordre décroissant. Marshall, Olkin et Arnold 2011, p. 32-34, démontrent l'équivalence avec les trois premières propriétés (dans le cas général) en utilisant le théorème de Birkhoff-von Neumann.
- Marshall, Olkin et Arnold 2011, p. 32-33.
Références
modifier- (en) Barry C. Arnold, Majorization and the Lorenz Order : A Brief Introduction, Springer, coll. « Lecture Notes in Statistics » (no 43), (DOI 10.1007/978-1-4615-7379-1) (ISBN 978-0-387-96592-5) (print) (ISBN 978-1-4615-7379-1) (eBook)
- (en) Barry C. Arnold, « Majorization: Here, There and Everywhere », Statistical Science, vol. 22, no 3, , p. 407-413 (DOI 10.1214/0883423060000000097, MR MR2416816, zbMATH 06075132, arXiv 0801.4221, lire en ligne)
- (en) Rajendra Bhatia (en), Matrix Analysis, Springer, , 349 p. (ISBN 978-0-387-94846-1, lire en ligne)
- (en) Godfrey Harold Hardy, John Edensor Littlewood et George Pólya, Inequalities, Londres, Cambridge University Press, coll. « Cambridge Mathematical Library », , 2e éd., 324 p. (ISBN 978-0-521-35880-4, lire en ligne)
- (en) Roger A. Horn et Charles R. Johnson, Matrix Analysis, Cambridge University Press,
- (en) Roger A. Horn et Charles R. Johnson, Topics in Matrix Analysis, Cambridge University Press, , 607 p. (ISBN 978-0-521-46713-1, lire en ligne)
- (en) Eduard Jorswieck et Holger Boche (de), Majorization and Matrix Monotone Functions in Wireless Communications, Now Publishers, , 153 p. (ISBN 978-1-60198-040-3, lire en ligne)
- (en) Richard V. Kadison, « The Pythagorean Theorem: I. The finite case », PNAS, vol. 99, no 7, , p. 4178-4184 (lire en ligne)
- (en) Richard V. Kadison et Gert K. Pedersen, « Means and Convex Combinations of Unitary Operators », Math. Scand., vol. 57, , p. 249-266 (lire en ligne)
- (en) Albert W. Marshall, Ingram Olkin et Barry C. Arnold, Inequalities : Theory of Majorization and Its Applications, New York, Springer Science+Business Media, , 2e éd. (ISBN 978-0-387-40087-7, lire en ligne) — 1re éd. : Marshall et Olkin, Academic Press, 1979 (ISBN 978-0-12-473750-1)
- (en) Michael A. Nielsen (en) et Isaac L. Chuang (en), Quantum Computation and Quantum Information, Cambridge University Press, , 676 p. (ISBN 978-0-521-63503-5, lire en ligne)
- (en) J. Michael Steele, The Cauchy Schwarz Master Class : An Introduction to the Art of Mathematical Inequalities, Cambridge University Press, , 306 p. (ISBN 978-0-521-54677-5, présentation en ligne), chap. 13 (« Majorization and Schur Convexity »)
Liens externes
modifier- (en) Serge Belongie, « Majorization », sur MathWorld
- (en) « Majorization », sur PlanetMath