Muirheadova nerovnost - Muirheads inequality - Wikipedia

v matematika, Muirheadova nerovnost, pojmenoval podle Robert Franklin Muirhead, známá také jako metoda hromadění, zobecňuje nerovnost aritmetických a geometrických prostředků.

Předběžné definice

A-znamenat

Pro všechny nemovitý vektor

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

definovat "A-znamenat" [A] kladných reálných čísel X₁, ..., X_n podle

${ displaystyle [a] = { frac {1} {n!}} součet _ { sigma} x _ { sigma _ {1}} ^ {a_ {1}} cdots x _ { sigma _ {n }} ^ {a_ {n}},}$

kde součet přesahuje všechny obměny σ z {1, ..., n }.

Když prvky A jsou nezáporná celá čísla, A-mean lze ekvivalentně definovat pomocí monomiální symetrický polynom ${ displaystyle m_ {a} (x_ {1}, tečky, x_ {n})}$ tak jako

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

kde l je počet odlišných prvků v A, a k₁, ..., k_l jsou jejich multiplicity.

Všimněte si, že A-mean, jak je definováno výše, má pouze obvyklé vlastnosti a znamenat (např. pokud je průměr stejných čísel roven jim) pokud ${ displaystyle a_ {1} + cdots + a_ {n} = 1}$. Obecně lze místo toho zvážit ${ displaystyle [a] ^ {1 / (a_ {1} + cdots + a_ {n})}}$, který se nazývá a Muirhead znamená.^[1]

Příklady

• Pro A = (1, 0, ..., 0), the A- průměr je obyčejný aritmetický průměr z X₁, ..., X_n.
• Pro A = (1/n, ..., 1/n), A- znamená geometrický průměr z X₁, ..., X_n.
• Pro A = (X, 1-X), A- znamená Heinz myslí.

Dvojnásobně stochastické matice

An n × n matice P je dvojnásobně stochastický přesně pokud oba P a jeho transpozice P^T jsou stochastické matice. A stochastická matice je čtvercová matice nezáporných reálných záznamů, ve kterých je součet položek v každém sloupci 1. Dvojnásobně stochastická matice je tedy čtvercová matice nezáporných reálných záznamů, ve kterých je součet položek v každém řádku a součet položky v každém sloupci jsou 1.

Prohlášení

Muirheadova nerovnost uvádí, že [A] ≤ [b] pro všechny X takhle X_i > 0 pro každého i ∈ { 1, ..., n } právě když existuje nějaká dvojnásobně stochastická matice P pro který A = Pb.

Dále v takovém případě máme [A] = [b] právě tehdy A = b nebo všichni X_i jsou rovny.

Druhá podmínka může být vyjádřena několika ekvivalentními způsoby; jeden z nich je uveden níže.

Důkaz využívá skutečnosti, že každá dvojnásobně stochastická matice je váženým průměrem permutační matice (Birkhoffova-von Neumannova věta ).

Další ekvivalentní podmínka

Kvůli symetrii součtu se neztratí žádná obecnost seřazením exponentů do sestupného pořadí:

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

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

Pak existence dvojnásobně stochastické matice P takhle A = Pb je ekvivalentní následujícímu systému nerovností:

${ displaystyle { 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}. konec {zarovnáno}}}$

(The poslední jeden je rovnost; ostatní jsou slabé nerovnosti.)

Sekvence ${ displaystyle b_ {1}, ldots, b_ {n}}$ říká se specializovat sekvence ${ displaystyle a_ {1}, ldots, a_ {n}}$.

Symetrická notace součtu

Pro součty je vhodné použít speciální notaci. Úspěch při snižování nerovnosti v této podobě znamená, že jedinou podmínkou pro testování je ověření, zda je jedna exponentová sekvence (${ displaystyle alpha _ {1}, ldots, alpha _ {n}}$) převyšuje druhou.

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

Tato notace vyžaduje vývoj každé permutace, vývoj výrazu z n! monomials, například:

${ displaystyle { 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 {zarovnáno}}}$

Příklady

Aritmeticko-geometrický průměr nerovnosti

Nechat

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

a

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

My máme

${ displaystyle { 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 {zarovnáno}}}$

Pak

[A_A] ≥ [A_G],

který je

${ displaystyle { 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!}$

nerovnost.

Další příklady

Snažíme se to dokázat X² + y² ≥ 2xy pomocí seskupení (Muirheadova nerovnost). Transformujeme to v zápisu symetrického součtu:

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

Sekvence (2, 0) majorizuje sekvenci (1, 1), takže nerovnost platí hromaděním.

Podobně můžeme dokázat nerovnost

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

tak, že jej napíšeme pomocí symetrického součtu jako

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

což je stejné jako

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

Vzhledem k tomu, že posloupnost (3, 0, 0) majorizuje posloupnost (1, 1, 1), nerovnost platí hromaděním.

Viz také

• Nerovnost aritmetických a geometrických prostředků
• Dvojnásobně stochastická matice
• Monomiální symetrický polynom

Poznámky

Reference

• Kombinatorická teorie od Johna N. Guidiho na základě přednášek, které přednesl Gian-Carlo Rota v roce 1998, MIT Copy Technology Center, 2002.
• Kiran Kedlaya, A < B (A méně než B), průvodce řešením nerovností
• Muirheadova věta na PlanetMath.
• Hardy, G.H .; Littlewood, J. E.; Pólya, G. (1952), Nerovnosti, Cambridge Mathematical Library (2. vyd.), Cambridge: Cambridge University Press, ISBN  0-521-05206-8, PAN0046395, Zbl  0047.05302, Oddíl 2.18, Věta 45.