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 (en), 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).}$

Figure 1. Exemple de majorisation dans le plan.

Figure 2. Exemple de majorisation dans l'espace.

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

• (en) Barry C. Arnold, Majorization and the Lorenz Order : A Brief Introduction, Springer, coll. « Lecture Notes in Statistics » (n^o 43), 1987 (DOI 10.1007/978-1-4615-7379-1) (ISBN 978-0-387-96592-5) (print) (ISBN 978-1-4615-7379-1) (eBook)
• (en) Barry C. Arnold, « Majorization: Here, There and Everywhere », Statistical Science, vol. 22, n^o 3,‎ 2007, p. 407-413 (DOI 10.1214/0883423060000000097, MR MR2416816, zbMATH 06075132, arXiv 0801.4221, lire en ligne)
• (en) Rajendra Bhatia (en), Matrix Analysis, Springer, 1996, 349 p. (ISBN 978-0-387-94846-1, lire en ligne)

• (en) Godfrey Harold Hardy, John Edensor Littlewood et George Pólya, Inequalities, Londres, Cambridge University Press, coll. « Cambridge Mathematical Library », 1952, 2^e éd., 324 p. (ISBN 978-0-521-35880-4, lire en ligne)
• (en) Roger A. Horn et Charles R. Johnson, Matrix Analysis, Cambridge University Press, 1985
• (en) Roger A. Horn et Charles R. Johnson, Topics in Matrix Analysis, Cambridge University Press, 1994, 607 p. (ISBN 978-0-521-46713-1, lire en ligne)
• (en) Eduard Jorswieck et Holger Boche (de), Majorization and Matrix Monotone Functions in Wireless Communications, Now Publishers, 2007, 153 p. (ISBN 978-1-60198-040-3, lire en ligne)
• (en) Richard V. Kadison, « The Pythagorean Theorem: I. The finite case », PNAS, vol. 99, n^o 7,‎ 2002, p. 4178-4184 (lire en ligne)
• (en) Richard V. Kadison et Gert K. Pedersen, « Means and Convex Combinations of Unitary Operators », Math. Scand., vol. 57,‎ 1985, p. 249-266 (lire en ligne)

• (en) Albert W. Marshall, Ingram Olkin et Barry C. Arnold, Inequalities : Theory of Majorization and Its Applications, New York, Springer Science+Business Media, 2011, 2^e éd. (ISBN 978-0-387-40087-7, lire en ligne) — 1^re éd. : Marshall et Olkin, Academic Press, 1979 (ISBN 978-0-12-473750-1)
• (en) Michael A. Nielsen (en) et Isaac L. Chuang (en), Quantum Computation and Quantum Information, Cambridge University Press, 2000, 676 p. (ISBN 978-0-521-63503-5, lire en ligne)
• (en) J. Michael Steele, The Cauchy Schwarz Master Class : An Introduction to the Art of Mathematical Inequalities, Cambridge University Press, 2004, 306 p. (ISBN 978-0-521-54677-5, présentation en ligne), chap. 13 (« Majorization and Schur Convexity »)

• (en) Serge Belongie, « Majorization », sur MathWorld
• (en) « Majorization », sur PlanetMath