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éfinitionModifier

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

ExemplesModifier

  • 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 équivalentesModifier

 
Figure 1. Exemple de majorisation dans le plan.
 
Figure 2. Exemple de majorisation dans l'espace.

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 uv, 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! vecteurs σ 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 contextesModifier

  • 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 aussiModifier

Notes et référencesModifier

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Majorization » (voir la liste des auteurs).
  1. 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.
  2. Arnold 1987, p. 13.
  3. Marshall, Olkin et Arnold 2011, p. 7.
  4. Arnold 1987, Theorem 2.1
  5. Arnold 1987, Theorem 2.9.
  6. Nielsen et Chuang 2000, Exercise 12.17.
  7. 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.
  8. Marshall, Olkin et Arnold 2011, p. 32-33.

RéférencesModifier

Liens externesModifier