Majorisering

Inom matematiken är majorisering en förbeställning på vektorer av reella tal . Låt ${\displaystyle {x}_{(i)}^{},\ i=1,\,\ldots ,\,n} beteckna i {$ \ $i }$ -th största elementet i vektorn $\mathbf {x} \in \mathbb {R} ^{n}$ . Givet ${\displaystyle \mathbf {x} ,\ \mathbf {y} \in \mathbb {R} ^{n}} ,$ säger vi att $\mathbf {x}$ majoriserar svagt (eller dominerar) $\mathbf {y}$ underifrån (eller motsvarande säger vi att $\mathbf {y}$ är svagt majoriserad (eller domineras) av $\mathbf {x}$ underifrån ) betecknad som $\mathbf {x} \succ _{w}\mathbf {y}$ om ${\displaystyle \sum _{i=1}^{k}x_{(i)}^{}\geq \sum _{i=1}^{k}y_{(i)}^{}} för$ alla $k=1,\,\dots ,\,d$ . Om dessutom $\sum _{i=1}^{d}x_{i}^{}=\summa _{i=1}^ {d}y_{i}^{}$ , vi säger att $\mathbf {x}$ majoriserar (eller dominerar) $\mathbf {y}$ , skrivet som $y} }$ ${\displaystyle \ mathbf {x} \succ \mathbf$ { , eller motsvarande, vi säger att $\mathbf {y}$ majoriseras (eller domineras) av $\mathbf {x}$ . Ordningen för inmatningarna av vektorerna $\mathbf {x}$ eller $\mathbf {y}$ påverkar inte majoriteten, t.ex. påståendet $(1,2)\prec (0,3)$ är helt enkelt ekvivalent med $(2,1)\prec (3,0)$ . Som en konsekvens är majorisering inte en partiell ordning , eftersom $\mathbf {x} \succ \mathbf {y}$ och $\mathbf {y} \succ \mathbf {x}$ antyder inte ${\displaystyle \mathbf {x} =\mathbf {y} } ,$ det antyder bara att komponenterna i varje vektor är lika, men inte nödvändigtvis i samma ordning.

Majoriseringens partiella ordning på ändliga dimensionella vektorer, som beskrivs här, kan generaliseras till Lorenz-ordningen , en partiell ordning på fördelningsfunktioner . Till exempel är en förmögenhetsfördelning Lorenz-större än en annan om dess Lorenz-kurva ligger under den andra. Som sådan har en Lorenz-större förmögenhetsfördelning en högre Gini-koefficient och har större inkomstskillnader . Olika andra generaliseringar av majoritet diskuteras i kapitel 14 och 15 i.

Exempel

(Stark) majorisering: $(1,2,3)\prec (0,3,3)\prec (0,0) ,6)$ . För vektorer med $n$ komponenter

\left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)\prec \left({\frac {1}{n-1}} ,\ldots ,{\frac {1}{n-1}},0\right)\prec \cdots \prec \left({\frac {1}{2}},{\frac {1}{2} },0,\ldots ,0\right)\prec \left(1,0,\ldots ,0\right).

(Svag) majorisering: $(1,2,3)\prec _{w}(1,3 ,3)\prec _{w}(1,3,4)$ . För vektorer med $n$ komponenter:

\left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)\prec _{w}\left({\frac {1}{n -1}},\ldots ,{\frac {1}{n-1}},1\right).

Majoriseringsgeometri

Figur 1. Exempel på 2D-majorisering

För ${\displaystyle \mathbf {x} ,\ \mathbf {y} \i \mathbb {R} ^{n},} har vi x ≺$ y $\mathbf {x} \ prec \mathbf {y} }$ om och endast om $\mathbf {x}$ finns i det konvexa skrovet för alla vektorer som erhålls genom att permutera koordinaterna för $\mathbf {y}$ . Figur 1 visar det konvexa skrovet i 2D för vektorn $\mathbf {y} =(3,\,1)$ . Lägg märke till att mitten av det konvexa skrovet, som är ett intervall i detta fall, är vektorn $\mathbf {x} =(2,\,2)$ . Detta är den "minsta" vektorn som uppfyller $\mathbf {x} \prec \mathbf {y}$ för denna givna vektor $\mathbf {y}$ . Figur 2 visar det konvexa skrovet i 3D. Mitten av det konvexa skrovet, som i detta fall är en 2D-polygon, är den "minsta" vektorn $\mathbf {x}$ som uppfyller $\mathbf {x} \prec \mathbf {y }$ för denna givna vektor $\mathbf {y}$ .

Figur 2. Exempel på 3D-majorisering

Schur konvexitet

En funktion $f:\mathbb {R} ^{n}\to \mathbb {R}$ sägs vara Schur konvex när $\mathbf {x} \succ \mathbf {y}$ antyder $f(\mathbf {x} )\geq f(\mathbf {y} )$ . Därför översätter Schur-konvexa funktioner ordningen av vektorer till en standardordning i $\mathbb {R}$ . På liknande sätt är $f(\mathbf {x} )$ Schur konkav när $\mathbf {x} \succ \mathbf {y}$ antyder $f(\mathbf {x} )\leq f(\mathbf {y} ).$

Ett exempel på en Schur-konvex funktion är maxfunktionen, $\max(\mathbf {x} )=x_{(1)}^{}$ . Schur konvexa funktioner är nödvändigtvis symmetriska så att posterna i it-argumentet kan bytas utan att ändra värdet på funktionen. Därför är linjära funktioner, som är konvexa, inte Schur-konvexa om de inte är symmetriska. Om en funktion är symmetrisk och konvex så är den Schur-konvex.

Likvärdiga förhållanden

Var och en av följande påståenden är sanna om och endast om $\mathbf {x} \succ \mathbf {y}$ :

$\mathbf {y} =\mathbf {D} \mathbf {x}$ för någon dubbelstokastisk matris $\mathbf {D}$ . Detta motsvarar att säga att $\mathbf {y}$ kan representeras som en konvex kombination av permutationerna av $\mathbf {x}$ ; man kan verifiera att det finns en sådan konvex representation genom att använda högst $n$ permutationer av $\mathbf {x}$ .
Från $\mathbf {x}$ kan vi producera $\mathbf {y}$ med en ändlig sekvens av "Robin Hood-operationer" där vi ersätter två element $x_{i}$ och $x_{j}<x_{i}$ med $x_{i}-\varepsilon$ och $x_{j}+\varepsilon$ , respektive för vissa $\varepsilon \in (0,x_{i}-x_{j})$ .
För varje konvex funktion $h:\mathbb {R} \to \mathbb {R}$ $h:{\mathbb {R}}\to {\mathbb {R}}$ , $\sum _{i=1}^{d}h(x_{i})\geq \sum _{i=1}^{d}h(y_{i})$ $\sum _{i=1}^{d}h(x_{i})\geq \sum _{i=1}^{d}h(y_{i})$ .
- I själva verket räcker det med ett specialfall: $\sum _{i}{x_{i}}=\summa _{i}{y_{i}}$ och för varje $t$ , $\sum _{i=1}^{d}\max(0,x_ {i}-t)\geq \sum _{i=1}^{d}\max(0,y_{i}-t)$ .
$\forall t\in \mathbb {R} \quad \sum _{j=1}^{d}|x_{j}-t|\geq \sum _{j=1}^{d}| y_{j}-t|$ .

I linjär algebra

Antag att för två reella vektorer ${\displaystyle \mathbf {x} ,\ \mathbf {y} \in \mathbb {R} ^{d}} , x {\displaystyle \mathbf {$ x $}$ majoriserar $\mathbf {y}$ . Då kan det visas att det finns en uppsättning sannolikheter $(p_{1},p_{2},\ldots ,p_{d}),\ \sum _{i=1}^{d}p_{i}=1$ och en uppsättning permutationer $(P_{ 1},P_{2},\ldots ,P_{d})$ så att $\mathbf {y} =\summa _{i=1}^{ d}p_{i}P_{i}\mathbf {x}$ . Alternativt kan det visas att det finns en dubbel stokastisk matris $\mathbf {D}$ så att $\mathbf {D} \mathbf {x} =\mathbf {y}$

Vi säger att en hermitisk operator , $\mathbf {H}$ , majoriserar en annan, $\mathbf {M}$ , om uppsättningen egenvärden för $\mathbf {H}$ majoriserar den för $\mathbf {M}$ .

I beräkningsbarhetsteori

Givet ${\displaystyle f,\ g:\mathbb {N} \to \mathbb {N} } ,$ då sägs $f$ majorisera $g$ om, för alla $x$ , $f(x)\geq g(x)$ . Om det finns några $n$ så att $f(x)\geq g(x)$ för alla $x>n$ , då $f$ sägs dominera (eller så småningom dominera ) $g$ . Alternativt definieras de föregående termerna ofta som kräver den strikta olikheten $f(x)>g(x)$ istället för $f( x)\geq g(x)$ i de föregående definitionerna.

Se även

Muirheads ojämlikhet
Karamatas ojämlikhet
Schur-konvex funktion
Schur-Horns sats som relaterar diagonala ingångar i en matris till dess egenvärden.
För positiva heltal kallas svag majorisering dominansordning .
Leximin ordning

Anteckningar

^ Marshall, Albert W. (2011). Ojämlikheter: teori om majoritet och dess tillämpningar . Ingram Olkin, Barry C. Arnold (2:a upplagan). New York: Springer Science+Business Media, LLC. ISBN 978-0-387-68276-1 . OCLC 694574026 .
^ ^a ^b ^c Barry C. Arnold. "Majorisering och Lorenzorden: En kort introduktion". Springer-Verlag Lecture Notes in Statistics, vol. 43, 1987.
^ ^a ^b Xingzhi, Zhan (2003). "Den skarpa Rado-satsen för majoriseringar". American Mathematical Monthly . 110 (2): 152–153. doi : 10.2307/3647776 . JSTOR 3647776 .
^ 3 juli 2005 inlägg av fleeting_guest i tråden "The Karamata Inequality" , AoPS- gemenskapsforum. Arkiverad 11 november 2020.
^ Nielsen, Michael A. ; Chuang, Isaac L. (2010). Quantum Computation and Quantum Information (2:a upplagan). Cambridge: Cambridge University Press. ISBN 978-1-107-00217-3 . OCLC 844974180 .

J. Karamata. "Sur une inegalite relativa aux fonctions convexes." Publ. Matematik. Univ. Belgrad 1, 145–158, 1932.
GH Hardy, JE Littlewood och G. Pólya, Inequalities , 2:a upplagan, 1952, Cambridge University Press, London.
Inequalities: Theory of Majorization and its Applications Albert W. Marshall, Ingram Olkin , Barry Arnold, Andra upplagan. Springer-serien i statistik. Springer, New York, 2011. ISBN 978-0-387-40087-7
En hyllning till Marshall och Olkins bok "Inequalities: Theory of Majorization and its Applications"
Matrix Analysis (1996) Rajendra Bhatia, Springer, ISBN 978-0-387-94846-1
Ämnen i matrisanalys (1994) Roger A. Horn och Charles R. Johnson, Cambridge University Press, ISBN 978-0-521-46713-1
Majorization and Matrix Monotone Functions in Wireless Communications (2007) Eduard Jorswieck och Holger Boche, Now Publishers, ISBN 978-1-60198-040-3
The Cauchy Schwarz Master Class (2004) J. Michael Steele, Cambridge University Press, ISBN 978-0-521-54677-5

externa länkar

programvara

OCTAVE / MATLAB -kod för att kontrollera majoritet

[1] Marshall, Albert W. (2011). Ojämlikheter: teori om majoritet och dess tillämpningar . Ingram Olkin, Barry C. Arnold (2:a upplagan). New York: Springer Science+Business Media, LLC. ISBN 978-0-387-68276-1 . OCLC 694574026 .

[Arnold-2] Barry C. Arnold. "Majorisering och Lorenzorden: En kort introduktion". Springer-Verlag Lecture Notes in Statistics, vol. 43, 1987.

[Zhan-3] Xingzhi, Zhan (2003). "Den skarpa Rado-satsen för majoriseringar". American Mathematical Monthly . 110 (2): 152–153. doi : 10.2307/3647776 . JSTOR 3647776 .

[4] 3 juli 2005 inlägg av fleeting_guest i tråden "The Karamata Inequality" , AoPS- gemenskapsforum. Arkiverad 11 november 2020.

[NielsenChuang-5] Nielsen, Michael A. ; Chuang, Isaac L. (2010). Quantum Computation and Quantum Information (2:a upplagan). Cambridge: Cambridge University Press. ISBN 978-1-107-00217-3 . OCLC 844974180 .