Majorizace - Majorization

v matematika, majorizace je předobjednávka na vektory z reálná čísla. Pro vektor ${ displaystyle mathbf {a} in mathbb {R} ^ {d}}$ , označujeme ${ displaystyle mathbf {a} ^ { downarrow} in mathbb {R} ^ {d}}$ vektor se stejnými komponentami, ale seřazený sestupně. Dáno ${ displaystyle mathbf {a}, mathbf {b} in mathbb {R} ^ {d}}$ , říkáme to ${ displaystyle mathbf {a}}$ slabě majorizuje (nebo dominuje) ${ displaystyle mathbf {b}}$ zespodu psáno jako ${ displaystyle mathbf {a} succ _ {w} mathbf {b}}$ iff

{ displaystyle sum _ {i = 1} ^ {k} a_ {i} ^ { downarrow} geq sum _ {i = 1} ^ {k} b_ {i} ^ { downarrow} quad { text {pro}} k = 1, tečky, d,}

Rovněž to říkáme ${ displaystyle mathbf {b}}$ je slabě majorizováno (nebo dominuje) ${ displaystyle mathbf {a}}$ zespodu, psáno jako ${ displaystyle mathbf {b} prec _ {w} mathbf {a}}$ .

Li ${ displaystyle mathbf {a} succ _ {w} mathbf {b}}$ a navíc ${ displaystyle sum _ {i = 1} ^ {d} a_ {i} = sum _ {i = 1} ^ {d} b_ {i}}$ , říkáme to ${ displaystyle mathbf {a}}$ specializuje (nebo dominuje) ${ displaystyle mathbf {b}}$ , psáno jako ${ displaystyle mathbf {a} succ mathbf {b}}$ . Rovněž to říkáme ${ displaystyle mathbf {b}}$ je specializovaný (nebo dominuje) ${ displaystyle mathbf {a}}$ , psáno jako ${ displaystyle mathbf {b} prec mathbf {a}}$ .

Všimněte si, že pořadí majorizace nezávisí na pořadí složek vektorů ${ displaystyle mathbf {a}}$ nebo ${ displaystyle mathbf {b}}$ . Majorizace není a částečná objednávka, od té doby ${ displaystyle mathbf {a} succ mathbf {b}}$ a ${ displaystyle mathbf {b} succ mathbf {a}}$ nenaznačují ${ displaystyle mathbf {a} = mathbf {b}}$ , znamená to pouze, že komponenty každého vektoru jsou stejné, ale ne nutně ve stejném pořadí.

Všimněte si, že notace je v matematické literatuře nekonzistentní: někteří používají obrácenou notaci, například ${ displaystyle succ}$ je nahrazen ${ displaystyle prec}$ .

Funkce ${ displaystyle f: mathbb {R} ^ {d} to mathbb {R}}$ se říká, že je Schur konvexní když ${ displaystyle mathbf {a} succ mathbf {b}}$ naznačuje ${ displaystyle f ( mathbf {a}) geq f ( mathbf {b})}$ . Podobně, ${ displaystyle f ( mathbf {a})}$ je Schur konkávní když ${ displaystyle mathbf {a} succ mathbf {b}}$ naznačuje ${ displaystyle f ( mathbf {a}) leq f ( mathbf {b}).}$

Zde popsaný majorizační dílčí řád na konečných množinách lze zobecnit na Lorenz objednává, částečná objednávka dne distribuční funkce. Například a rozdělení majetku je Lorenz větší než jiný, pokud je jeho Lorenzova křivka lži níže jiný. Distribuce bohatství s Lorenzem má tedy vyšší Giniho koeficient, a má více nerovnost příjmů.

Příklady

Pořadí položek neovlivňuje majorizaci, např. Příkaz ${ displaystyle (1,2) prec (0,3)}$ je prostě ekvivalentní s ${ displaystyle (2,1) prec (3,0)}$ .

(Silná) specializace: ${ displaystyle (1,2,3) prec (0,3,3) prec (0,0,6)}$ . Pro vektory s n komponenty

{ displaystyle 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).}

(Slabá) specializace: ${ displaystyle (1,2,3) prec _ {w} (1,3,3) prec _ {w} (1,3,4)}$ . Pro vektory s n komponenty:

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

Geometrie majorizace

Obrázek 1. Příklad 2D majorizace

Pro ${ displaystyle mathbf {x}, mathbf {y} in mathbb {R} ^ {n},}$ my máme ${ displaystyle mathbf {x} prec mathbf {y}}$ kdyby a jen kdyby ${ displaystyle mathbf {x}}$ je v konvexním trupu všech vektorů získaných permutací souřadnic ${ displaystyle mathbf {y}}$ .

Obrázek 1 zobrazuje konvexní trup ve 2D pro vektor ${ displaystyle mathbf {y} = (3, , 1)}$ . Všimněte si, že střed konvexního trupu, který je v tomto případě intervalem, je vektor ${ displaystyle mathbf {x} = (2, , 2)}$ . Toto je "nejmenší" vyhovující vektor ${ displaystyle mathbf {x} prec mathbf {y}}$ pro tento daný vektor ${ displaystyle mathbf {y}}$ .

Obrázek 2. Příklad 3D majorizace

Obrázek 2 ukazuje konvexní trup ve 3D. Střed konvexního trupu, který je v tomto případě 2D polygon, je „nejmenší“ vektor ${ displaystyle mathbf {x}}$ uspokojující ${ displaystyle mathbf {x} prec mathbf {y}}$ pro tento daný vektor ${ displaystyle mathbf {y}}$ .

Rovnocenné podmínky

Každé z následujících tvrzení je pravdivé právě tehdy ${ displaystyle mathbf {a} succ mathbf {b}}$ :

${ displaystyle mathbf {b} = D mathbf {a}}$ pro některé dvojnásobně stochastická matice ${ displaystyle D}$ .^[1]^{:Thm. 2.1} To je ekvivalent k říkání ${ displaystyle mathbf {b}}$ lze reprezentovat jako a konvexní kombinace permutací ${ displaystyle mathbf {a}}$ ; jeden může ověřit, že existuje taková konvexní reprezentace pomocí maximálně ${ displaystyle d}$ obměny ${ displaystyle mathbf {a}}$ .^[2]
Z ${ displaystyle mathbf {a}}$ můžeme vyrobit ${ displaystyle mathbf {b}}$ konečnou posloupností „operací Robina Hooda“, kde nahradíme dva prvky ${ displaystyle a_ {i}}$ a ${ displaystyle a_ {j}$ s ${ displaystyle a_ {i} - varepsilon}$ a ${ displaystyle a_ {j} + varepsilon}$ pro některé ${ displaystyle varepsilon in (0, a_ {i} -a_ {j})}$ .^[1]^:11
Pro každou konvexní funkci ${ displaystyle h: mathbb {R} do mathbb {R}}$ $h: { mathbb {R}} na { mathbb {R}}$ , ${ displaystyle sum _ {i = 1} ^ {d} h (a_ {i}) geq sum _ {i = 1} ^ {d} h (b_ {i})}$ $sum _ {{i = 1}} ^ {d} h (a_ {i}) geq sum _ {{i = 1}} ^ {d} h (b_ {i})$ .^[1]^{:Thm. 2.9}
- Ve skutečnosti stačí speciální případ: ${ displaystyle sum _ {i} {a_ {i}} = sum _ {i} {b_ {i}}}$ a pro každého $t$ , ${ displaystyle sum _ {i = 1} ^ {d} { max {(0, a_ {i} -t)}} geq sum _ {i = 1} ^ {d} { max {( 0, b_ {i} -t)}}}$ .^[3]
${ displaystyle forall t in mathbb {R} quad sum _ {j = 1} ^ {d} | a_ {j} -t | geq sum _ {j = 1} ^ {d} | b_ {j} -t |}$ .^[4]^{:Cvičení 12.17}

V lineární algebře

Předpokládejme, že pro dva skutečné vektory ${ displaystyle v, v ' in mathbb {R} ^ {d}}$ , ${ displaystyle v}$ specializuje ${ displaystyle v '}$ . Pak lze ukázat, že existuje množina pravděpodobností ${ displaystyle (p_ {1}, p_ {2}, ldots, p_ {d}), sum _ {i = 1} ^ {d} p_ {i} = 1}$ a sada obměny ${ displaystyle (P_ {1}, P_ {2}, ldots, P_ {d})}$ takhle ${ displaystyle v '= součet _ {i = 1} ^ {d} p_ {i} P_ {i} v}$ .^[2] Alternativně lze ukázat, že existuje a dvojnásobně stochastická matice ${ displaystyle D}$ takhle ${ displaystyle vD = v '}$

Říkáme, že a Hermitovský operátor, ${ displaystyle H}$ , specializuje další, ${ displaystyle H '}$ , pokud je sada vlastních čísel ${ displaystyle H}$ vyzdvihuje to z ${ displaystyle H '}$ .

V teorii rekurze

Dáno ${ displaystyle f, g: mathbb {N} až mathbb {N}}$ , pak ${ displaystyle f}$ říká se specializovat ${ displaystyle g}$ pokud pro všechny ${ displaystyle x}$ , ${ displaystyle f (x) geq g (x)}$ . Pokud nějaké jsou ${ displaystyle n}$ aby ${ displaystyle f (x) geq g (x)}$ pro všechny ${ displaystyle x> n}$ , pak ${ displaystyle f}$ říká se ovládat (nebo nakonec dominovat) ${ displaystyle g}$ . Alternativně jsou často definovány předchozí pojmy vyžadující přísnou nerovnost ${ displaystyle f (x)> g (x)}$ namísto ${ displaystyle f (x) geq g (x)}$ ve výše uvedených definicích.

Zobecnění

Různá zevšeobecnění majorizace jsou popsána v kapitolách 14 a 15 referenční práce Nerovnosti: Teorie majorizace a její aplikace. Albert W. Marshall, Ingram Olkin Barry Arnold. Druhé vydání. Springerova řada ve statistice. Springer, New York, 2011. ISBN 978-0-387-40087-7

Viz také

Muirheadova nerovnost
Karamatova nerovnost
Schur-konvexní funkce
Schur – Hornova věta vztahující diagonální položky matice k jejím vlastním číslům.
Pro pozitivní celá čísla, nazývá se slabá majorizace Objednávka dominance.

Poznámky

^ ^A ^b ^C Barry C. Arnold. „Majorisation and the Lorenz Order: A Brief Introduction“. Springer-Verlag Poznámky k přednášce ve statistice, roč. 43, 1987.
^ ^A ^b Xingzhi, Zhan (2003). "Ostrá Radova věta pro majorizace". Americký matematický měsíčník. 110 (2): 152–153. doi:10.2307/3647776.
^ 3. července 2005 příspěvek od Fleeting_guest dne Vlákno „Nerovnost Karamata“, AoPS komunitní fóra. Archivováno 11. listopadu 2020.
^ Nielsen, Michael A.; Chuang, Isaac L. (2010). Kvantové výpočty a kvantové informace (2. vyd.). Cambridge: Cambridge University Press. ISBN 978-1-107-00217-3. OCLC 844974180.

Reference

J. Karamata. "Konvexní relativní pomocná písma sur une inegalite." Publ. Matematika. Univ. Bělehrad 1, 145–158, 1932.
G. H. Hardy, J. E. Littlewood a G. Pólya, Nerovnosti, 2. vydání, 1952, Cambridge University Press, London.
Nerovnosti: Teorie majorizace a její aplikace Albert W. Marshall, Ingram Olkin Barry Arnold, druhé vydání. Springerova řada ve statistice. Springer, New York, 2011. ISBN 978-0-387-40087-7
Nerovnosti: Teorie majorizace a její aplikace (1980) Albert W. Marshall, Ingram Olkin Akademický tisk, ISBN 978-0-12-473750-1
Pocta knize Marshalla a Olkina „Nerovnosti: Teorie majorizace a její aplikace“
Maticová analýza (1996) Rajendra Bhatia, Springer, ISBN 978-0-387-94846-1
Témata maticové analýzy (1994) Roger A. Horn a Charles R. Johnson, Cambridge University Press, ISBN 978-0-521-46713-1
Majoritní a maticové monotónní funkce v bezdrátové komunikaci (2007) Eduard Jorswieck a Holger Boche, nyní vydavatelé, ISBN 978-1-60198-040-3
Cauchy Schwarz Master Class (2004) J. Michael Steele, Cambridge University Press, ISBN 978-0-521-54677-5

externí odkazy

Software

OKTÁVA /MATLAB kód pro kontrolu majorizace

[Arnold-1] A ^b ^C Barry C. Arnold. „Majorisation and the Lorenz Order: A Brief Introduction“. Springer-Verlag Poznámky k přednášce ve statistice, roč. 43, 1987.

[Zhan-2] A ^b Xingzhi, Zhan (2003). "Ostrá Radova věta pro majorizace". Americký matematický měsíčník. 110 (2): 152–153. doi:10.2307/3647776.

[3] 3. července 2005 příspěvek od Fleeting_guest dne Vlákno „Nerovnost Karamata“, AoPS komunitní fóra. Archivováno 11. listopadu 2020.

[NielsenChuang-4] Nielsen, Michael A.; Chuang, Isaac L. (2010). Kvantové výpočty a kvantové informace (2. vyd.). Cambridge: Cambridge University Press. ISBN 978-1-107-00217-3. OCLC 844974180.

[1]

[2]

[3]

[4]