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 }$ ^[1].

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^[2]^,^[3] » : en ne modifiant que deux composantes $u \leq 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$ ^[4].
Pour toute fonction convexe $h:\mathbb {R} \to \mathbb {R}$ , on a^[5] $\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|$ ^[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

y\succ x

et les trois premières conditions^[7]

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)^[8] : 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) \geq g (k)$ pour tout $k$ . Si l'on a seulement $f (k) \geq 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 aussi

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

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Majorization » (voir la liste des auteurs).

↑ Pour ajouter de la confusion, certaines sources utilisent une notation opposée, c'est-à-dire $\succ$ au lieu de $\prec$ . 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.
↑ Arnold 1987, p. 13.
↑ Marshall, Olkin et Arnold 2011, p. 7.
↑ Arnold 1987, Theorem 2.1
↑ Arnold 1987, Theorem 2.9.
↑ Nielsen et Chuang 2000, Exercise 12.17.
↑ 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.
↑ Marshall, Olkin et Arnold 2011, p. 32-33.

Références

(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 »)

Liens externes

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

Portail des mathématiques

[1] Pour ajouter de la confusion, certaines sources utilisent une notation opposée, c'est-à-dire $\succ$ au lieu de $\prec$ . 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.

[Arnold21-4] Arnold 1987, Theorem 2.1

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]