Øke

I matematikk , betegner vi ved majorization en viss preorder på elementene i vektorrommet av dimensjon $d$ på de reelle tall . Denne forhåndsbestillingen har mange bruksområder innen ulike grener av matematikk. $\ mathbb {R} ^ {d}$

Definisjon

For en vektor betegner vi at vektoren har de samme komponentene, men ordnet i avtagende rekkefølge. For eksempel . $y \ in \ mathbb {R} ^ {d}$ $y ^ {{\ downarrow}}$ $\ mathbb {R} ^ {d}$ $(2,5,3,2) ^ {{\ downarrow}} = (5,3,2,2)$

La $x$ og $y være$ to vektorer av . Vi sier at $y$ majoriserer eller dominerer $x$ , og vi betegner , eller igjen , hvis $\ mathbb {R} ^ {d}$ $y \ succ x$ $x \ prec y$

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

for og mer $k = 1, \ prikker, d-1$

\ sum _ {{i = 1}} ^ {d} y_ {i} = \ sum _ {{i = 1}} ^ {d} x_ {i}.

Per definisjon, betyr den majorization ikke avhengig av rekkefølgen av komponentene i de to vektorer, og det er derfor ikke en ordre forhold , siden og innebærer ikke at $y = x$ , men bare det . $y \ succ x$ $x \ suksess y$ $y ^ {{\ downarrow}} = x ^ {{\ downarrow}}$

En funksjon sies å være konveks i betydningen Schur hvis antyder . ${\ displaystyle f: \ mathbb {R} ^ {d} \ to \ mathbb {R}}$ $y \ succ x$ ${\ displaystyle f (y) \ geq f (x)}$

Majoriseringen, som definert her, kan utvides med en ordre som heter Lorenz order (in) , som er en delvis ordre på distribusjonsfunksjoner .

Eksempler

Siden rekkefølgen på oppføringene ikke påvirker økningen, har vi alt som . $(1,2) \ prec (0,3)$ $(2,1) \ prec (3,0)$
Tilsvarende . $(1,2,3) \ prec (0,3,3) \ prec (0,0,6)$
Mer interessant er følgende sekvens av vektorer av : $\ mathbb {R} ^ {d}$ $\ left ({\ frac 1d}, \ ldots, {\ frac 1d} \ right) \ prec \ left ({\ frac 1 {d-1}}, \ ldots, {\ frac 1 {d-1}}, 0 \ høyre) \ prec \ cdots \ prec \ left ({\ frac 12}, {\ frac 12}, 0, \ ldots, 0 \ right) \ prec \ left (1,0, \ ldots, 0 \ right) .$

Tilsvarende forhold

For er følgende egenskaper ekvivalent med . $x, y \ in \ mathbb {R} ^ {d}$ $y \ succ x$

Det eksisterer en endelig sekvens av vektorer der den første er $y$ , den siste er $x$ og etterfølgeren $b$ for hver vektor $a$ er en konveks kombinasjon av $a$ og en av dens transponeringer , som tilsvarer å si at vi går fra $a$ til $b$ ved en “ Robin Hood transfer ” : ved å modifisere bare to komponenter $u \leq v$ , øke $u$ med høyest $v - u$ og redusere $v$ med det samme.
$x$ er i den konvekse konvolutten til alle vektorene som oppnås ved å permere koordinatene til $y$ , det vil si av $d !$ vektorer $(y _ {{\ sigma (1)}}, \ ldots, y _ {{\ sigma (d)}}),$ der $σ$ krysser den symmetriske gruppen $S d$ .
Figur 1 viser den konvekse konvolutten, i blått, for vektoren $y = (3, 1)$ ; det er linjesegmentet som forbinder $(3, 1)$ til $(1, 3)$ . Blant alle vektorene $x$ på dette segmentet, er den som den første komponenten av er den minste for vektoren $x$ $= (2, 2)$ . Figur 2 viser en konveks konvolutt i 3D , som her er en plan polygon. Senteret er den "minste" vektoren $x$ slik at . $x ^ {\ downarrow}$ $x \ prec y$
Var $x = Ay$ til en dobbelt stokastisk matrise $A$ .
For enhver konveks funksjon har vi $h: \ mathbb {R} \ til \ mathbb {R}$ $\ sum _ {{i = 1}} ^ {d} h (y_ {i}) \ geq \ sum _ {{i = 1}} ^ {d} h (x_ {i})$ ( Karamata-ulikhet (en) ).
For ethvert reelt tall har vi $t$ $\ sum _ {{j = 1}} ^ {d} | y_ {j} -t | \ geq \ sum _ {{j = 1}} ^ {d} | x_ {j} -t |$ .
Det er en hermitisk matrise hvis " sett " med egenverdier er $y$ og sekvensen av diagonale oppføringer er $x$ ( Schur-Horn-setning ).

Bevis for ekvivalens mellom og de tre første forholdene

y \ succ x

Betegn med (0) tilstanden og (1), (2) og (3) de tre første betingelsene ovenfor. Vi vil unngå å bruke Birkhoff-von Neumann-teoremet , fordi det er nøyaktig demonstrert i artikkelen “ Bistokastisk matrise ” fra ekvivalensen mellom forhold (2) og (3). $y \ succ x$

(0) ⇒ (1): Anta og vis at vi kan gå fra y til x ved en endelig sekvens av overføringer. Siden transposisjonene er spesielle tilfeller av overføringer og at de genererer den symmetriske gruppen, kan vi anta at x og y har synkende koordinater og x ≠ y . La oss fortsette med induksjon på antall indekser i slik at x i ≠ y i (dette tallet er> 1 - fordi ∑ x i = ∑ y i - så dette vil til og med vise at d - 1 overføringer er tilstrekkelig). Det er tilstrekkelig å vite hvordan man ved en overføring på y konstruerer en vektor z som har x minst en felles koordinat på mer enn y , og som fremdeles er med synkende koordinater og større x . La j være den største indeksen slik at x j < y j (det er noen, ifølge hypotesene). La oss, blant indeksene større enn j , k den minste slik at x k > y k (det er noen fordi vi er lik den største indeksen slik at x i ≠ y i , vi har x i > y i ). Vi sjekker at for δ = min ( y j - x j , x k - y k ), er vektoren z trukket fra y ved å trekke δ fra j- th-koordinaten og legge δ til k- th passende. $x \ prec y$

(1) ⇒ (2): La Γ ( a ) betegne den konvekse konvolutten av permutene til en vektor a . For en hvilken som helst vektor b utledet fra a ved en overføring, inneholder Γ ( a ) b derfor (siden dette settet er konveks og stabilt av permutasjoner) inneholder det Γ ( b ). Så hvis x trekkes fra y av en endelig sekvens av overføringer, så tilhører den Γ ( y ).

(2) ⇒ (3): Enhver permutasjonsmatrise er bistokastisk, og enhver konveks kombinasjon av bistokastiske matriser er bistokastisk.

(3) ⇒ (0): Anta at x = Ay for en bistokastisk matrise og vis det . Først, $A = (a _ {{i, j}})$ $y \ succ x$ ${\ displaystyle \ sum _ {i} x_ {i} - \ sum _ {j} y_ {j} = \ sum _ {j} \ left [\ left (\ sum _ {i} a_ {i, j} \ høyre) -1 \ høyre] y_ {j} = 0.}$ Så, uten tap av generalitet, har x og y synkende koordinater (fordi ethvert produkt av A , venstre eller høyre, av permutasjonsmatriser, er bistokastisk). Så for alle 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} \ høyre] y_ {j} \ leq y_ {k} \ venstre \ {\ sum _ {j \ leq k} \ venstre [\ venstre (\ sum _ {i \ leq k} a_ {i, j} \ høyre) -1 \ høyre] + \ sum _ {j> k} \ venstre [\ sum _ {i \ leq k} a_ {i, j} \ høyre] \ høyre \} = y_ {k} \ sum _ {i \ leq k} \ left [\ left (\ sum _ {j} a_ {i, j} \ right) -1 \ right] = 0.}$

Bruk av begrepet i andre sammenhenger

Hvis $H$ og $H '$ er to Hermitiske matriser, sier vi at $H$ majoriserer $H'$ hvis settet med egenverdier av $H$ majoriserer det til $H '$ .
Gitt to sekvenser av naturlige heltall , sier vi at $f$ majoriserer $g$ hvis $f$ $($ $k$ $) \geq$ $g$ $($ $k$ $)$ for alle $k$ . Hvis vi bare har $f$ $($ $k$ $) \geq$ $g$ $($ $k$ $)$ for alle $k$ $>$ $n$ for noen $n$ , sier vi at $f til$ slutt majoriserer $g$ . $f, g: \ mathbb {N} \ til \ mathbb {N}$
Ulike andre applikasjoner og generaliseringer er diskutert i Marshall, Olkin og Arnold 2011 .

Se også

Muirhead ulikhet
Schur-konveks funksjon
Orden av dominans . Det er en svak versjon av majorisering brukt på naturlige tall.

Merknader og referanser

( fr ) Denne artikkelen er delvis eller helt hentet fra Wikipedia-artikkelen på engelsk med tittelen " Majorization " ( se listen over forfattere ) .

For å legge til forvirring bruker noen kilder motsatt notasjon, dvs. i stedet for . Dette er tilfelle i eldre engelske bøker, særlig i Horn og Johnson 1985 , definisjon 4.3.24. Deretter bruker disse forfatterne i Horn og Johnson 1994 notasjonen som er vedtatt her. $\ succ$ $\ prec$
Arnold 1987 , s. 1. 3.
Marshall, Olkin og Arnold 2011 , s. 7.
Arnold 1987 , teorem 2.1
Arnold 1987 , teorem 2.9.
Nielsen og Chuang 2000 , øvelse 12.17.
Kadison 2002 , lemma 5 og Kadison og Pedersen 1985 , lemma 13 s. 258-259 , viser ekvivalensen med de to første egenskapene i det spesielle tilfellet hvor koordinatene til $x$ og $y$ er ordnet i avtagende rekkefølge. Marshall, Olkin og Arnold 2011 , s. 32-34, demonstrer ekvivalensen med de tre første egenskapene (generelt sett) ved bruk av Birkhoff-von Neumann-setningen .
Marshall, Olkin og Arnold 2011 , s. 32-33.

Referanser

(in) Barry C. Arnold , Majorization and the Lorenz Order: A Brief Introduction , Springer al. "Kompendiet i Statistisk" ( n o 43),1987( DOI 10.1007 / 978-1-4615-7379-1 ) ( ISBN 978-0-387-96592-5 ) (trykk) ( ISBN 978-1-4615-7379-1 ) (eBok)
(en) Barry C. Arnold, “ Majorization: Here, There and Everywhere ” , Statistical Science , vol. 22, n o 3,2007, s. 407-413 ( DOI 10.1214 / 0883423060000000097 , matematiske anmeldelser MR2416816 , zbMATH 06075132 , arXiv 0801.4221 , les online )
(en) Rajendra Bhatia (en) , Matrix Analysis , Springer,1996, 349 s. ( ISBN 978-0-387-94846-1 , les online )

(en) Godfrey Harold Hardy , John Edensor Littlewood og George Pólya , Inequalities , London, Cambridge University Press , koll. "Cambridge Mathematical Library",1952, 2 nd ed. , 324 s. ( ISBN 978-0-521-35880-4 , les online )
(en) Roger A. Horn og Charles R. Johnson , Matrix Analysis , Cambridge University Press ,1985
(no) Roger A. Horn og Charles R. Johnson , Emner i matriseanalyse , Cambridge University Press ,1994, 607 s. ( ISBN 978-0-521-46713-1 , les online )
(no) Eduard Jorswieck og Holger Boche (de) , Majorization and Matrix Monotone Functions in Wireless Communications , Now Publishers,2007, 153 s. ( ISBN 978-1-60198-040-3 , les online )
(no) Richard V. Kadison , “ The Pythagorean Theorem: I. The finite case ” , PNAS , vol. 99, n o 7,2002, s. 4178-4184 ( les online )
(en) Richard V. Kadison og Gert K. Pedersen, “ Means and Convex Combinations of Unitary Operators ” , Math. Scand. , vol. 57,1985, s. 249-266 ( les online )

(en) Albert W. Marshall , Ingram Olkin og Barry C. Arnold , Inequalities: Theory of Majorization and Its Applications , New York, Springer Science + Business Media ,2011, 2 nd ed. ( ISBN 978-0-387-40087-7 , les online )- 1 st ed. : Marshall og Olkin, Academic Press , 1979 ( ISBN 978-0-12-473750-1 )
(en) Michael A. Nielsen (en) og Isaac L. Chuang (en) , Quantum Computation and Quantum Information , Cambridge University Press ,2000, 676 s. ( ISBN 978-0-521-63503-5 , les online )
(no) J. Michael Steele , The Cauchy Schwarz Master Class: En introduksjon til kunsten med matematiske ulikheter , Cambridge University Press ,2004, 306 s. ( ISBN 978-0-521-54677-5 , online presentasjon ) , kap. 13 (“Majorization and Schur Convexity”)

Eksterne linker

(no) Eric W. Weisstein , “ Majorization ” , om MathWorld
(no) " Majorization " , på PlanetMath