Majorisation
# Majorisation

En mathématiques, on désigne par majorisation un certain préordre sur les éléments de l'espace vectoriel $\mathbb {R} ^{d}$ de dimension d 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 \mathbb {R} ^{d}$, on note $y^{\downarrow }$ le vecteur de $\mathbb {R} ^{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 x et y deux vecteurs de $\mathbb {R} ^{d}$. On dit que y majorise ou domine x, et l'on note $y\succ x$, ou encore $x\prec y$, si

    $\sum _{i=1}^{k}y_{i}^{\downarrow }\geq \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 y = x, mais seulement que $y^{\downarrow }=x^{\downarrow }$.

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

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

* 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 $\mathbb {R} ^{d}$ :$\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).$

## Conditions équivalentes

Pour $x,y\in \mathbb {R} ^{d}$, les propriétés suivantes sont équivalentes à $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^,$ » : 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$(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 $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 $x\prec y$.
* On a x = Ay pour une matrice bistochastique A.
* Pour toute fonction convexe $h:\mathbb {R} \to \mathbb {R}$, on a$\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 $t$, on a $\sum _{j=1}^{d}|y_{j}-t|\geq \sum _{j=1}^{d}|x_{j}-t|$.
* 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).

$y\succ x$

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 $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 $A=(a_{i,j})$ et montrons que $y\succ x$. D'abord, $\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, $\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.$

## Emploi du terme dans d'autres contextes

* 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 $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 g.
* Diverses autres applications et généralisations sont discutées dans l'ouvrage de référence Marshall, Olkin et Arnold 2011.
