Muirheads ojämlikhet

Inom matematiken generaliserar Muirheads ojämlikhet , uppkallad efter Robert Franklin Muirhead , även känd som "bunching"-metoden, olikheten mellan aritmetiska och geometriska medel .

Preliminära definitioner

ett -medelvärde

För vilken riktig vektor som helst

$a=(a_{1},\dots ,a_{n})$

definiera " a -medelvärde" [ a ] ​​för positiva reella tal x ₁ , ..., x _n med

$[a]={\frac {1}{n!}}\summa _{\sigma }x_{\sigma _{1}}^{ a_{1}}\cdots x_{\sigma _{n}}^{a_{n}},$

där summan sträcker sig över alla permutationer σ av { 1, ..., n }.

När elementen i a är icke-negativa heltal, kan a -medelvärdet definieras ekvivalent via det monomisymmetriska polynomet $m_{a}(x_{1},\dots ,x_ {n})$ som

$[a]={\frac {k_{1}!\cdots k_{l}!}{n!}}m_{a}(x_{1} ,\dots ,x_{n}),$

där ℓ är antalet distinkta element i a , och k ₁ , ..., k _ℓ är deras multiplicitet.

Observera att a -medelvärdet enligt definitionen ovan endast har de vanliga egenskaperna för ett medelvärde (t.ex. om medelvärdet av lika tal är lika med dem) om $a_{1}+\ cdots +a_{n}=1$ . I det allmänna fallet kan man istället överväga $[a]^{1/(a_{1}+\cdots +a_{n})}$ , som kallas ett Muirhead-medelvärde.

Exempel

• För a = (1, 0, ..., 0) är a -medelvärdet bara det vanliga aritmetiska medelvärdet av x ₁ , ..., x _n .
• För a = (1/ n , ..., 1/ n ), är a -medelvärdet det geometriska medelvärdet av x ₁ , ..., x _n .
• För a = ( x , 1 − x ) är a -medelvärdet Heinz-medelvärdet .
• Muirhead-medelvärdet för a = (−1, 0, ..., 0) är det harmoniska medelvärdet .

Dubbelstokastiska matriser

Huvudartikel: Dubbelstokastisk matris

En n × n matris P är dubbelt stokastisk precis om både P och dess transponerade P ^T är stokastiska matriser . En stokastisk matris är en kvadratisk matris av icke-negativa reala poster där summan av posterna i varje kolumn är 1. En dubbelstokastisk matris är alltså en kvadratisk matris av icke-negativa reala poster där summan av posterna i varje rad och summan av posterna i varje kolumn är 1.

Påstående

Muirheads olikhet säger att [ a ] ​​≤ [ b ] för alla x så att x _i > 0 för varje i ∈ { 1, ..., n } om och endast om det finns någon dubbelstokastisk matris P för vilken a = Pb .

Dessutom har vi i så fall [ a ] ​​= [ b ] om och bara om a = b eller alla x _i är lika.

Det senare villkoret kan uttryckas på flera likvärdiga sätt; en av dem ges nedan.

Beviset använder sig av det faktum att varje dubbelstokastisk matris är ett viktat medelvärde av permutationsmatriser ( Birkhoff-von Neumanns teorem) .

Ett annat likvärdigt villkor

På grund av summans symmetri går ingen generalitet förlorad genom att sortera exponenterna i fallande ordning:

$a_{1}\geq a_{2}\geq \cdots \geq a_{n}$

$b_{1}\geq b_{2}\geq \cdots \geq b_{n}.$

Då finns det en dubbelstokastisk matris P så att a = Pb är ekvivalent med följande system av ojämlikheter:

${\begin{aligned}a_{1}&\leq b_{1}\\a_{1}+a_{2}&\leq b_{1}+b_{2}\\a_{1}+ a_{2}+a_{3}&\leq b_{1}+b_{2}+b_{3}\\&\,\,\,\vdots \\a_{1}+\cdots +a_{n -1}&\leq b_{1}+\cdots +b_{n-1}\\a_{1}+\cdots +a_{n}&=b_{1}+\cdots +b_{n}.\ end{aligned}}$

(Den sista är en jämlikhet, de andra är svaga ojämlikheter.)

Sekvensen $b_{1},\ldots ,b_{n}$ sägs majorisera sekvensen $a_{1},\ldots ,a_ {n}$ .

Symmetrisk summanotation

Det är bekvämt att använda en speciell notation för summorna. En framgång med att minska en ojämlikhet i denna form innebär att det enda villkoret för att testa den är att verifiera om en exponentsekvens ( $\alpha _{1},\ldots ,\alpha _{n }$ ) majoriserar den andra.

$\sum _{\text{sym}}x_{1}^{\alpha _{1}}\cdots x_{n}^{\alpha _{n }}$

Denna notation kräver att man utvecklar varje permutation, utvecklar ett uttryck gjord av n ! monomer , till exempel:

${\begin{aligned}\sum _{\text{sym}}x^{3}y^{ 2}z^{0}&=x^{3}y^{2}z^{0}+x^{3}z^{2}y^{0}+y^{3}x^{2 }z^{0}+y^{3}z^{2}x^{0}+z^{3}x^{2}y^{0}+z^{3}y^{2}x ^{0}\\&=x^{3}y^{2}+x^{3}z^{2}+y^{3}x^{2}+y^{3}z^{2 }+z^{3}x^{2}+z^{3}y^{2}\end{aligned}}$

Exempel

Aritmetisk-geometrisk medelolikhet

Huvudartikel: Olikhet mellan aritmetiska och geometriska medel

Låta

$a_{G}=\left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)$

och

$a_{A}=(1,0,0,\ldots ,0).$

Vi har

${\begin{aligned}a_{A1}=1&>a_{G1}={\frac {1}{n}},\\a_{A1}+a_{A2} =1&>a_{G1}+a_{G2}={\frac {2}{n}},\\&\,\,\,\vdots \\a_{A1}+\cdots +a_{An}& =a_{G1}+\cdots +a_{Gn}=1.\end{aligned}}$

Sedan

[ a _A ] ≥ [ a _G ],

vilket är

${\frac {1}{n!}}(x_{1}^{1}\cdot x_{2}^{0}\cdots x_{n}^{0}+\cdots +x_{1 }^{0}\cdots x_{n}^{1})(n-1)!\geq {\frac {1}{n!}}(x_{1}\cdot \cdots \cdot x_{n} )^{1/n}n!$

ger ojämlikheten.

Andra exempel

Vi försöker bevisa att x ² + y ² ≥ 2 xy genom att använda bunching (Muirheads ojämlikhet). Vi transformerar det i den symmetriska summan:

$\sum _{\mathrm {sym} }x^{2}y^{0}\geq \sum _{\mathrm {sym} }x^{1}y^{1}.$

Sekvensen (2, 0) majoriserar sekvensen (1, 1), sålunda håller ojämlikheten genom buntning.

På samma sätt kan vi bevisa ojämlikheten

$x^{3}+y^{3}+z^{3}\geq 3xyz$

genom att skriva den med symmetrisk summanotation som

$\sum _{\mathrm {sym} }x^{3}y^{0}z^{0}\geq \sum _{\mathrm {sym} }x^{1}y^{1}z^{1},$

vilket är samma som

$2x^{3}+2y^{3}+2z^{3}\geq 6xyz.$

Eftersom sekvensen (3, 0, 0) majoriserar sekvensen (1, 1, 1), kvarstår ojämlikheten genom buntning.

Se även

• Olikhet mellan aritmetiska och geometriska medel
• Dubbelstokastisk matris
• Monomial symmetrisk polynom

Anteckningar

• Combinatorial Theory av John N. Guidi, baserad på föreläsningar som hölls av Gian-Carlo Rota 1998, MIT Copy Technology Center, 2002.
• Kiran Kedlaya, A < B ( A mindre än B ) , en guide för att lösa ojämlikheter
• Muirheads teorem vid PlanetMath .
•     Hardy, GH; Littlewood, JE; Pólya, G. (1952), Inequalities, Cambridge Mathematical Library (2. ed.), Cambridge: Cambridge University Press, ISBN 0-521-05206-8 , MR 0046395 , Zbl 0047.05302 , Section 2.18, Theorem 45.