Voir la source de Majorisation

En [[mathématiques]], on désigne par '''majorisation''' un certain [[préordre]] sur les éléments de l'[[espace vectoriel]] <math>\R^d</math> de [[Dimension d'un espace vectoriel|dimension]] {{math|''d''}} sur les [[nombre réel|nombres réels]]. Ce préordre a de nombreuses applications dans diverses branches des mathématiques.

== Définition ==

Pour un vecteur <math>y\in\R^d</math>, on note <math>y^{\downarrow}</math> le vecteur de <math>\R^d</math> qui a les mêmes composantes, mais rangées en ordre décroissant. Par exemple, <math>(2,5,3, 2)^{\downarrow}=(5,3,2,2)</math>. 

Soient {{math|''x''}} et {{math|''y''}} deux vecteurs de <math>\R^d</math>. On dit que {{math|''y''}} ''majorise'' ou ''domine'' {{math|''x''}}, et l'on note <math>y\succ x</math>, ou encore <math>x\prec y</math>, si
: <math>\sum_{i=1}^ky_i^{\downarrow}\ge\sum_{i=1}^kx_i^{\downarrow}</math>
pour <math>k=1,\dots,d-1</math> et de plus
: <math>\sum_{i=1}^dy_i=\sum_{i=1}^dx_i.</math>

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 <math>y\succ x</math> et <math>x\succ y</math> n'implique pas que {{math|1=''y = x''}}, mais seulement que <math>y^{\downarrow}=x^{\downarrow}</math><ref>Pour ajouter de la confusion, certaines sources utilisent une notation opposée, c'est-à-dire <math>\succ</math> au lieu de <math>\prec</math>. Il en est ainsi dans des livres anciens en anglais, notamment dans {{harvsp|Horn|Johnson|1985|loc=Definition 4.3.24}}. Ultérieurement, ces auteurs, dans {{harvsp|Horn|Johnson|1994}} utilisent la notation qui est adoptée ici.</ref>.

Une fonction <math>f:\R^d\to\R</math> est dite [[Fonction Schur-convexe|convexe au sens de Schur]] si <math>y\succ x</math> implique <math>f(y)\ge f(x)</math>.

La majorisation, comme définie ici, peut être étendue en un ordre appelé [[ordre de Lorenz]], qui est un [[ordre partiel]] sur des [[Fonction de répartition|fonctions de répartition]].

== Exemples ==
* Comme l'ordre des entrées n'influe par sur la majorisation, on a <math>(1,2)\prec (0,3)</math> tout comme <math>(2,1)\prec (3,0)</math>.
* De même, <math>(1,2,3)\prec (0,3,3)\prec (0,0,6)</math>.
* Plus intéressante est la séquence suivante de vecteurs de <math>\R^d</math> :{{indente|<math>
\left(\frac1d, \ldots, \frac1d\right)\prec \left(\frac1{d-1}, \ldots, \frac1{d-1},0\right)
\prec \cdots \prec
\left(\frac12,\frac12, 0, \ldots, 0\right) \prec \left(1, 0, \ldots, 0\right).
</math>}}

== Conditions équivalentes ==
[[File:2D Majorization Example.png|thumb|Figure 1. Exemple de majorisation dans le plan.]]
[[File:3D Majorization Example.png|thumb|Figure 2. Exemple de majorisation dans l'espace.]]
Pour <math>x,y\in\R^d</math>, les propriétés suivantes sont équivalentes à <math>y\succ x</math>.

*Il existe une suite finie de vecteurs dont le premier est {{math|''y''}}, le dernier est {{math|''x''}} et le successeur {{math|''b''}} de chaque vecteur {{math|''a''}} est une [[combinaison convexe]] de {{math|''a''}} et de l'un de ses [[Permutation#Permutations particulières|transposés]], ce qui revient à dire qu'on passe de {{math|''a''}} à {{math|''b''}} par un {{Citation|transfert de [[Robin des Bois]]<ref>{{Harvsp|Arnold|1987|p=13}}.</ref>{{,}}<ref>{{harvsp|Marshall, Olkin et Arnold 2011|p=7}}.</ref>}} : en ne modifiant que deux composantes {{math|''u'' ≤ ''v''}}, augmentant {{math|''u''}} d'au plus {{math|''v – u''}} et diminuant {{math|''v''}} d'autant.
*{{math|''x''}} est dans l'[[enveloppe convexe]] de tous les vecteurs obtenus en [[Permutation|permutant]] les coordonnées de {{math|''y''}}, c'est-à-dire des [[Factorielle|{{math|''d''!}}]] vecteurs{{Retrait|<math>(y_{\sigma(1)},\ldots,y_{\sigma(d)}),</math>}}où {{math|''σ''}} parcourt le [[groupe symétrique]] {{math|''S{{ind|d}}''}}.<br />La figure 1 montre l'enveloppe convexe, en bleu, pour le vecteur {{math|1=''y'' = (3, 1)}} ; c'est le [[Segment (mathématiques)|segment de droite]] joignant {{math|(3, 1)}} à {{math|(1, 3)}}. Parmi tous les vecteurs {{math|''x''}} sur ce segment, celui pour lequel la première composante de <math>x^\downarrow</math> est la plus petite est le vecteur {{math|1=''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 {{math|''x''}} tel que <math>x\prec y</math>.
*On a {{math|1=''x = Ay''}} pour une [[matrice bistochastique]] {{math|''A''}}<ref name="Arnold21">{{harvsp|Arnold|1987|loc= Theorem 2.1}}</ref>. 
*Pour toute [[fonction convexe]] <math>h:\R\to\R</math>, on a<ref name="Arnold29">{{harvsp|Arnold|1987|loc= Theorem 2.9}}.</ref>{{indente|<math>\sum_{i=1}^dh(y_i) \ge\sum_{i=1}^dh(x_i)</math> ({{Lien|trad=Karamata's inequality|inégalité de Karamata}}).}}
*Pour tout nombre réel <math>t</math>, on a {{indente|<math>\sum_{j=1}^d|y_j-t|\ge\sum_{j=1}^d|x_j-t|</math><ref>{{harvsp|Nielsen et Chuang 2000|loc=Exercise 12.17}}.</ref>.}}
*Il existe une [[matrice hermitienne]] dont l'« [[Multiensemble|ensemble]] » des [[valeurs propres]] est {{math|''y''}} et la suite des entrées diagonales est {{math|''x''}} ([[théorème de Schur-Horn]]).

{{Démonstration/début|titre=Preuve de l'équivalence entre <math>y\succ x</math> et les trois premières conditions<ref>{{Harvsp|Kadison|2002|loc=lemme 5}} et {{Harvsp|Kadison|Pedersen|1985|loc=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 {{math|''x''}} et {{math|''y''}} sont rangées dans un ordre décroissant. {{harvsp|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 [[Matrice bistochastique#Polytope de Birkhoff et théorème de Birkhoff-von Neumann|théorème de Birkhoff-von Neumann]].</ref>}}
Notons (0) la condition <math>y\succ x</math> et (1), (2) et (3) les trois premières conditions ci-dessus. Nous éviterons d'utiliser le [[Matrice bistochastique#Polytope de Birkhoff et théorème de Birkhoff-von Neumann|théorème de Birkhoff-von Neumann]], car il est justement démontré dans l'article « [[Matrice bistochastique]] » à partir de l'équivalence entre les conditions (2) et (3).

(0) ⇒ (1)<ref>{{harvsp|Marshall, Olkin et Arnold 2011|p=32-33}}.</ref> : Supposons <math>x\prec y</math> et montrons qu'on peut passer de ''y'' à ''x'' par une suite finie de transferts. Puisque les transpositions sont des cas particuliers de transferts et qu'elles engendrent le groupe symétrique, [[Sans perte de généralité|on peut supposer]] que ''x'' et ''y'' sont à coordonnées décroissantes et ''x'' ≠ ''y''. Procédons par récurrence sur le nombre d'indices ''i'' tels que ''x{{ind|i}}'' ≠ ''y{{ind|i}}'' (ce nombre est > 1 — car {{nobr|1=∑''x{{ind|i}}'' = ∑''y{{ind|i}}''}} — donc ceci montrera même que ''d'' – 1 transferts suffisent). Il suffit de savoir construire, par un transfert sur ''y'', un vecteur ''z'' ayant avec ''x'' au moins une coordonnée commune de plus que ''y'', et qui soit encore à coordonnées décroissantes et majorisant ''x''. Soit ''j'' le plus grand indice tel que ''x{{ind|j}}'' < ''y{{ind|j}}'' (il en existe, d'après les hypothèses). Puis, soit, parmi les indices supérieurs à ''j'', ''k'' le plus petit tel que ''x{{ind|k}}'' > ''y{{ind|k}}'' (il en existe car pour ''i'' égal au plus grand indice tel que ''x{{ind|i}}'' ≠ ''y{{ind|i}}'', on a ''x{{ind|i}}'' > ''y{{ind|i}}''). On vérifie que pour δ = min(''y{{ind|j}} – x{{ind|j}}'', ''x{{ind|k}} – y{{ind|k}}''), le vecteur ''z'' déduit de ''y'' en retranchant δ de la ''j''-ème coordonnée et en ajoutant δ à la ''k''-ième convient.

(1) ⇒ (2) : Notons Γ(''a'') l'enveloppe convexe des permutés d'un vecteur ''a''. Pour tout vecteur ''b'' déduit de ''a'' par un transfert, Γ(''a'') contient ''b'' donc (puisque cet ensemble est convexe et stable par permutations) il contient Γ(''b''). Donc si ''x'' se déduit de ''y'' par une suite finie de transferts alors il appartient à Γ(''y'').

(2) ⇒ (3) : Toute matrice de permutation est bistochastique et toute combinaison convexe de matrices bistochastiques est bistochastique.

(3) ⇒ (0) : Supposons que ''x = Ay'' pour une certaine matrice bistochastique <math>A=(a_{i,j})</math> et montrons que <math>y\succ x</math>. D'abord,
{{Retrait|<math>\sum_ix_i-\sum_jy_j=\sum_j\left[\left(\sum_ia_{i,j}\right)-1\right]y_j=0
.</math>}}
Ensuite, sans perte de généralité, ''x'' et ''y'' sont à coordonnées décroissantes (car tout produit de ''A'', à gauche ou à droite, par des matrices de permutation, est bistochastique). Alors, pour tout ''k'',
{{Retrait|<math>\sum_{i\le k}x_i-\sum_{j\le k}y_j=\sum_{j\le k}\left[\left(\sum_{i\le k}a_{i,j}\right)-1\right]y_j+\sum_{j>k}\left[\sum_{i\le k}a_{i,j}\right]y_j
\le y_k\left\{\sum_{j\le k}\left[\left(\sum_{i\le k}a_{i,j}\right)-1\right]+\sum_{j>k}\left[\sum_{i\le k}a_{i,j}\right]\right\}=y_k\sum_{i\le k}\left[\left(\sum_ja_{i,j}\right)-1\right]=0
.</math>}}
{{Démonstration/fin}}

== Emploi du terme dans d'autres contextes ==
*Si {{math|''H''}} et {{math|''H{{'}}''}} sont deux matrices hermitiennes, on dit que ''{{math|H}} majorise {{math|H'}}'' si l'ensemble des [[valeurs propres]] de {{math|''H''}} majorise celui de {{math|''H{{'}}''}}.
* Étant donné deux [[Suite d'entiers|suites d'entiers naturels]] <math>f,g:\N\to\N</math>, on dit que {{math|''f''}} ''majorise'' {{math|''g''}} si {{math|''f''(''k'') ≥ ''g''(''k'')}} pour tout {{math|''k''}}. Si l'on a seulement {{math|''f''(''k'') ≥ ''g''(''k'')}} pour tout {{math|''k'' > ''n''}} pour un certain {{math|''n''}}, on dit que ''{{math|f}} majorise {{refsou|date=avril 2015|ultimement}} {{math|g}}''.  
*Diverses autres applications et généralisations sont discutées dans l'ouvrage de référence {{harvsp|Marshall, Olkin et Arnold 2011}}.

== Voir aussi ==
* [[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 ==
{{Traduction/Référence|en|Majorization|579176455|type=note}}
{{Références}}

== Références ==
<!-- Arnold -->
*{{Ouvrage|langue=en|prénom1=Barry C.|nom1=Arnold|titre=Majorization and the Lorenz Order|sous-titre=A Brief Introduction|éditeur=Springer|collection=Lecture Notes in Statistics|numéro dans collection=43|année=1987|doi=10.1007/978-1-4615-7379-1}} {{ISBN|978-0-387-96592-5}} (print) {{ISBN|978-1-4615-7379-1}} (eBook)
* {{article|lang=en|auteur1=Barry C. Arnold|titre=Majorization: Here, There and Everywhere|journal=Statistical Science|volume=22|numéro=3|année=2007|pages=407-413|doi=10.1214/0883423060000000097 |math reviews=MR2416816|
zbl=06075132|url= http://projecteuclid.org/euclid.ss/1199285040|arxiv=0801.4221}}
*{{Ouvrage|langue=en|auteur1={{Lien|Rajendra Bhatia}}|titre=Matrix Analysis|éditeur=Springer|année=1996|pages totales=349|isbn=978-0-387-94846-1|lire en ligne=https://books.google.com/books?id=F4hRy1F1M6QC&printsec=frontcover}}

<!-- Hardy Littlewood Pólya -->
*{{Ouvrage|langue=en|auteur1=[[Godfrey Harold Hardy]]|auteur2=[[John Edensor Littlewood]]|auteur3=[[George Pólya]]|titre=Inequalities|lieu=Londres|éditeur=[[Cambridge University Press]]|collection=Cambridge Mathematical Library|année=1952|numéro d'édition=2|pages totales=324|isbn=978-0-521-35880-4|lire en ligne=https://books.google.com/books?id=t1RCSP8YKt8C&printsec=frontcover}}
<!-- Horn -->
*{{Ouvrage|langue=en|prénom1=Roger A.|nom1=Horn|prénom2=Charles R.|nom2=Johnson|titre=Matrix Analysis|éditeur=[[Cambridge University Press]]|année=1985}}
*{{Ouvrage|langue=en|prénom1=Roger A.|nom1=Horn|prénom2=Charles R.|nom2=Johnson|titre=Topics in Matrix Analysis|éditeur=[[Cambridge University Press]]|année=1994|pages totales=607|isbn=978-0-521-46713-1|lire en ligne=https://books.google.com/books?id=LeuNXB2bl5EC&printsec=frontcover}}
*{{Ouvrage|langue=en|auteur1=Eduard Jorswieck|auteur2={{Lien|lang=de|Holger Boche}}|titre=Majorization and Matrix Monotone Functions in Wireless Communications|éditeur=Now Publishers|année=2007|pages totales=153|isbn=978-1-60198-040-3|lire en ligne=https://books.google.com/books?id=MqE-6XYPOdsC&printsec=frontcover}}
*{{Article|lang=en|auteur=[[Richard Kadison|Richard V. Kadison]]|titre=The Pythagorean Theorem: I. The finite case|revue=[[PNAS]]|vol=99|numéro=7|année=2002|p.=4178-4184|url=http://www.pnas.org/content/99/7/4178.abstract?sid=ef06a39f-10b5-4780-a3e0-baaec1406b32}}
*{{Article|lang=en|auteur=Richard V. Kadison|auteur2=Gert K. Pedersen|titre=Means and Convex Combinations of Unitary Operators|revue=[[Math. Scand.]]|vol=57|année=1985|p.=249-266|url=http://www.mscand.dk/article/view/12116/10132}}
<!-- * J. Karamata. Sur une inégalité relative aux fonctions convexes. Publ. Math. Univ. Belgrade 1, 145-158, 1932-->

<!-- Marshall Olkin -->
*{{Ouvrage|langue=en|prénom1=Albert W.|nom1=Marshall|auteur2=[[Ingram Olkin]]|prénom3=Barry C.|nom3=Arnold|titre=Inequalities : Theory of Majorization and Its Applications|lieu=New York|éditeur=[[Springer Science+Business Media]]|année=2011|numéro d'édition=2|isbn=978-0-387-40087-7|lire en ligne=https://books.google.fr/books?id=I9wfajyOrooC&pg=PA32|id=Marshall, Olkin et Arnold 2011}}{{commentaire biblio SRL|{{1e}} éd. : Marshall et Olkin, [[Academic Press]], 1979 {{isbn|978-0-12-473750-1}}}}
*{{Ouvrage|langue=en|auteur1={{Lien|Michael Nielsen|texte=Michael A. Nielsen}}|auteur2={{Lien|Isaac Chuang|texte=Isaac L. Chuang}}|titre=Quantum Computation and Quantum Information|éditeur=[[Cambridge University Press]]|année=2000|pages totales=676|isbn=978-0-521-63503-5|lire en ligne=https://books.google.com/books?id=aai-P4V9GJ8C&printsec=frontcover|id=Nielsen et Chuang 2000}}
*{{Ouvrage|langue=en|auteur1=[[J. Michael Steele]]|titre=The Cauchy Schwarz Master Class|sous-titre=An Introduction to the Art of Mathematical Inequalities|éditeur=[[Cambridge University Press]]|année=2004|pages totales=306|isbn=978-0-521-54677-5|présentation en ligne=http://www-stat.wharton.upenn.edu/~steele/Publications/Books/CSMC/CSMC_index.html|numéro chapitre=13|titre chapitre=Majorization and Schur Convexity}}

== Liens externes ==
*{{MathWorld|nom_url=Majorization|titre=Majorization|auteur=Serge Belongie}}
*{{Planetmath|titre=Majorization}}

[[Catégorie:Théorie des ordres]]
[[Catégorie:Algèbre linéaire]]
{{portail|mathématiques}}