Majorisation

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

Soient x et y deux vecteurs de ${\displaystyle \mathbb {R} ^{d}}$. On dit que y majorise ou domine x, et l'on note ${\displaystyle y\succ x}$, ou encore ${\displaystyle x\prec y}$, si

${\displaystyle \sum _{i=1}^{k}y_{i}^{\downarrow }\geq \sum _{i=1}^{k}x_{i}^{\downarrow }}$

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

${\displaystyle \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 ${\displaystyle y\succ x}$ et ${\displaystyle x\succ y}$ n'implique pas que y = x, mais seulement que ${\displaystyle y^{\downarrow }=x^{\downarrow }}$^[1].

Une fonction ${\displaystyle f:\mathbb {R} ^{d}\to \mathbb {R} }$ est dite convexe au sens de Schur si ${\displaystyle y\succ x}$ implique ${\displaystyle f(y)\geq 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.

• Comme l'ordre des entrées n'influe par sur la majorisation, on a ${\displaystyle (1,2)\prec (0,3)}$ tout comme ${\displaystyle (2,1)\prec (3,0)}$.
• De même, ${\displaystyle (1,2,3)\prec (0,3,3)\prec (0,0,6)}$.
• Plus intéressante est la séquence suivante de vecteurs de ${\displaystyle \mathbb {R} ^{d}}$ :${\displaystyle \left({\frac {1}{d}},\ldots ,{\frac {1}{d}}\right)\prec \left({\frac {1}{d-1}},\ldots ,{\frac {1}{d-1}},0\right)\prec \cdots \prec \left({\frac {1}{2}},{\frac {1}{2}},0,\ldots ,0\right)\prec \left(1,0,\ldots ,0\right).}$

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

• 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! vecteurs${\displaystyle (y_{\sigma (1)},\ldots ,y_{\sigma (d)}),}$où σ parcourt le groupe symétrique S_d.
  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 ${\displaystyle x^{\downarrow }}$ 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 ${\displaystyle x\prec y}$.
• On a x = Ay pour une matrice bistochastique A^[4].
• Pour toute fonction convexe ${\displaystyle h:\mathbb {R} \to \mathbb {R} }$, on a^[5]${\displaystyle \sum _{i=1}^{d}h(y_{i})\geq \sum _{i=1}^{d}h(x_{i})}$ (inégalité de Karamata (en)).
• Pour tout nombre réel ${\displaystyle t}$, on a ${\displaystyle \sum _{j=1}^{d}|y_{j}-t|\geq \sum _{j=1}^{d}|x_{j}-t|}$^[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).

Preuve de l'équivalence entre ${\displaystyle y\succ x}$ et les trois premières conditions^[7]

Notons (0) la condition ${\displaystyle 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)^[8] : Supposons ${\displaystyle 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 x_i ≠ y_i (ce nombre est > 1 — car ∑x_i = ∑y_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_j < y_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_k > y_k (il en existe car pour i égal au plus grand indice tel que x_i ≠ y_i, on a x_i > y_i). On vérifie que pour δ = min(y_j – x_j, x_k – y_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 ${\displaystyle A=(a_{i,j})}$ et montrons que ${\displaystyle y\succ x}$. D'abord, ${\displaystyle \sum _{i}x_{i}-\sum _{j}y_{j}=\sum _{j}\left[\left(\sum _{i}a_{i,j}\right)-1\right]y_{j}=0.}$ 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, ${\displaystyle \sum _{i\leq k}x_{i}-\sum _{j\leq k}y_{j}=\sum _{j\leq k}\left[\left(\sum _{i\leq k}a_{i,j}\right)-1\right]y_{j}+\sum _{j>k}\left[\sum _{i\leq k}a_{i,j}\right]y_{j}\leq y_{k}\left\{\sum _{j\leq k}\left[\left(\sum _{i\leq k}a_{i,j}\right)-1\right]+\sum _{j>k}\left[\sum _{i\leq k}a_{i,j}\right]\right\}=y_{k}\sum _{i\leq k}\left[\left(\sum _{j}a_{i,j}\right)-1\right]=0.}$

• 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 ${\displaystyle f,g:\mathbb {N} \to \mathbb {N} }$, 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.

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