Majorisation

En mathématiques, on désigne par majorisation un certain préordre sur les éléments de l'espace vectoriel ${ℝ}^d$ de dimension Modèle:Math sur les nombres réels. Ce préordre a de nombreuses applications dans diverses branches des mathématiques.

Définition

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

Soient Modèle:Math et Modèle:Math deux vecteurs de ${ℝ}^d$. On dit que Modèle:Math majorise ou domine Modèle:Math, et l'on note $y\succ x$, ou encore $x\prec y$, si

$\sum _{i=1}^k{y}_i^{\downarrow }\ge \sum _{i=1}^k{x}_i^{\downarrow }$

pour $k=1,\dots ,d-1$ et de plus

$\sum _{i=1}^d{y}_i=\sum _{i=1}^d{x}_i.$

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 $y\succ x$ et $x\succ y$ n'implique pas que Modèle:Math, mais seulement que $y^{\downarrow }=x^{\downarrow }$.

Une fonction $f:{ℝ}^d\to ℝ$ est dite convexe au sens de Schur si $y\succ x$ implique $f(y)\ge f(x)$.

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

Exemples

• Comme l'ordre des entrées n'influe par sur la majorisation, on a $(1,2)\prec (0,3)$ tout comme $(2,1)\prec (3,0)$.
• De même, $(1,2,3)\prec (0,3,3)\prec (0,0,6)$.
• Plus intéressante est la séquence suivante de vecteurs de ${ℝ}^d$ :Modèle:Indente

Conditions équivalentes

Figure 1. Exemple de majorisation dans le plan.

Figure 2. Exemple de majorisation dans l'espace.

Pour $x,y\in {ℝ}^d$, les propriétés suivantes sont équivalentes à $y\succ x$.

• Il existe une suite finie de vecteurs dont le premier est Modèle:Math, le dernier est Modèle:Math et le successeur Modèle:Math de chaque vecteur Modèle:Math est une combinaison convexe de Modèle:Math et de l'un de ses transposés, ce qui revient à dire qu'on passe de Modèle:Math à Modèle:Math par un Modèle:Citation : en ne modifiant que deux composantes Modèle:Math, augmentant Modèle:Math d'au plus Modèle:Math et diminuant Modèle:Math d'autant.
• Modèle:Math est dans l'enveloppe convexe de tous les vecteurs obtenus en permutant les coordonnées de Modèle:Math, c'est-à-dire des [[Factorielle|Modèle:Math]] vecteursModèle:Retraitoù Modèle:Math parcourt le groupe symétrique Modèle:Math.
  La figure 1 montre l'enveloppe convexe, en bleu, pour le vecteur Modèle:Math ; c'est le segment de droite joignant Modèle:Math à Modèle:Math. Parmi tous les vecteurs Modèle:Math sur ce segment, celui pour lequel la première composante de $x^{\downarrow }$ est la plus petite est le vecteur Modèle:Math. La figure 2 montre une enveloppe convexe en 3D, qui est ici un polygone plan. Son centre est le « plus petit » vecteur Modèle:Math tel que $x\prec y$.
• On a Modèle:Math pour une matrice bistochastique Modèle:Math.
• Pour toute fonction convexe $h:ℝ\to ℝ$, on aModèle:Indente
• Pour tout nombre réel $t$, on a Modèle:Indente
• Il existe une matrice hermitienne dont l'« ensemble » des valeurs propres est Modèle:Math et la suite des entrées diagonales est Modèle:Math (théorème de Schur-Horn).

Modèle:Démonstration/début Notons (0) la condition $y\succ x$ et (1), (2) et (3) les trois premières conditions ci-dessus. Nous éviterons d'utiliser le 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) : Supposons $x\prec y$ 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, 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 xModèle:Ind ≠ yModèle:Ind (ce nombre est > 1 — car Modèle:Nobr — 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 xModèle:Ind < yModèle:Ind (il en existe, d'après les hypothèses). Puis, soit, parmi les indices supérieurs à j, k le plus petit tel que xModèle:Ind > yModèle:Ind (il en existe car pour i égal au plus grand indice tel que xModèle:Ind ≠ yModèle:Ind, on a xModèle:Ind > yModèle:Ind). On vérifie que pour δ = min(yModèle:Ind – xModèle:Ind, xModèle:Ind – yModèle:Ind), 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 $A=(a_{i,j})$ et montrons que $y\succ x$. D'abord, Modèle:Retrait 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, Modèle:Retrait Modèle:Démonstration/fin

Emploi du terme dans d'autres contextes

• Si Modèle:Math et Modèle:Math sont deux matrices hermitiennes, on dit que Modèle:Math majorise Modèle:Math si l'ensemble des valeurs propres de Modèle:Math majorise celui de Modèle:Math.
• Étant donné deux suites d'entiers naturels $f,g:\mathbb{N}\to \mathbb{N}$, on dit que Modèle:Math majorise Modèle:Math si Modèle:Math pour tout Modèle:Math. Si l'on a seulement Modèle:Math pour tout Modèle:Math pour un certain Modèle:Math, on dit que Modèle:Math majorise Modèle:Refsou Modèle:Math.
• Diverses autres applications et généralisations sont discutées dans l'ouvrage de référence Modèle:Harvsp.

Voir aussi

• Inégalité de Muirhead
• Fonction Schur-convexe
• Ordre de domination. C'est une version faible de majorisation appliquée aux entiers naturels.

Références

• Modèle:Ouvrage Modèle:ISBN (print) Modèle:ISBN (eBook)
• Modèle:Article
• Modèle:Ouvrage

• Modèle:Ouvrage
• Modèle:Ouvrage
• Modèle:Ouvrage
• Modèle:Ouvrage
• Modèle:Article
• Modèle:Article

• Modèle:OuvrageModèle:Commentaire biblio SRL
• Modèle:Ouvrage
• Modèle:Ouvrage

Liens externes

• Modèle:MathWorld
• Modèle:Planetmath