Newtonovy identity

V matematice , a zejména v algebře , jsou Newtonovy identity (také známé jako Newton-Girardovy vzorce ) vztahy mezi dvěma typy symetrických polynomů , elementárními symetrickými polynomy a Newtonovými součty , to znamená součty mocnin neurčitého ty. Vyhodnoceno na kořenech jednoho polynomu P jedné proměnné, tyto identity umožňují vyjádřit částky z K -tý sil všech kořenů P(počítáno s jejich multiplicitou) jako funkce koeficientů P , aniž by bylo nutné tyto kořeny určovat. Tyto vzorce byly znovuobjeveny Isaacem Newtonem kolem roku 1666, zjevně bez znalosti analogické práce Alberta Girarda v roce 1629. Mají uplatnění v mnoha matematických oblastech, jako je teorie Galois , teorie invariants , teorie skupin , kombinatorika , a dokonce i v nematematických polích, například v obecné relativitě .

Matematický výrok

Formulace podle symetrických polynomů

Nechť $x 1 , ..., x n jsou$ proměnné; pro libovolné nenulové přirozené číslo k označíme $p k ( x 1 , ..., x n )$ součet mocnin $k$ -ths:

{\ displaystyle p_ {k} (x_ {1}, \ ldots, x_ {n}): = \ součet _ {i = 1} ^ {n} x_ {i} ^ {k} = x_ {1} ^ { k} + \ cdots + x_ {n} ^ {k}}

(nazývá se Newtonova suma )

a pro $k \geq 0$ , označíme $e k ( x 1 , ..., x n )$ elementární symetrický polynom , který je součtem z výrazných výrobků k- různých proměnných, mezi n ; tak zejména

{\ displaystyle {\ begin {aligned} e_ {0} (x_ {1}, \ ldots, x_ {n}) & = 1, \\ e_ {1} (x_ {1}, \ ldots, x_ {n} ) & = x_ {1} + x_ {2} + \ cdots + x_ {n}, \\ e_ {2} (x_ {1}, \ ldots, x_ {n}) & = \ textstyle \ sum \ limity _ {1 \ leq i <j \ leq n} x_ {i} x_ {j}, \\ ... \\ e_ {n} (x_ {1}, \ ldots, x_ {n}) & = x_ {1 } x_ {2} \ cdots x_ {n}, \\ e_ {k} (x_ {1}, \ ldots, x_ {n}) & = 0, \ quad {\ text {for}} \ k> n. \\\ end {zarovnáno}}}

Tyto identity Newton jsou pak napsal:

ke_ {k} (x_ {1}, \ ldots, x_ {n}) = \ sum _ {{i = 1}} ^ {k} (- 1) ^ {{i-1}} e _ {{ki }} (x_ {1}, \ ldots, x_ {n}) p_ {i} (x_ {1}, \ ldots, x_ {n}),

skutečné vztahy pro všechno . Takto získáme pro první hodnoty k : $k \ in \ mathbb {N} ^ {*}$

{\ begin {aligned} e_ {1} (x_ {1}, \ ldots, x_ {n}) & = p_ {1} (x_ {1}, \ ldots, x_ {n}), \\ 2e_ {2 } (x_ {1}, \ ldots, x_ {n}) & = e_ {1} (x_ {1}, \ ldots, x_ {n}) p_ {1} (x_ {1}, \ ldots, x_ { n}) - p_ {2} (x_ {1}, \ ldots, x_ {n}), \\ 3e_ {3} (x_ {1}, \ ldots, x_ {n}) & = e_ {2} ( x_ {1}, \ ldots, x_ {n}) p_ {1} (x_ {1}, \ ldots, x_ {n}) - e_ {1} (x_ {1}, \ ldots, x_ {n}) p_ {2} (x_ {1}, \ ldots, x_ {n}) + p_ {3} (x_ {1}, \ ldots, x_ {n}). \\\ end {aligned}}

Forma těchto vztahů nezávisí na počtu n proměnných (ale levá strana se po n- té identitě stává nulovou ), což umožňuje, aby byly uvedeny jako identity v kruhu symetrických polynomů . V tomto kruhu máme:

{\ begin {aligned} e_ {1} & = p_ {1}, \\ 2e_ {2} & = e_ {1} p_ {1} -p_ {2}, \\ 3e_ {3} & = e_ {2 } p_ {1} -e_ {1} p_ {2} + p_ {3}, \\ 4e_ {4} & = e_ {3} p_ {1} -e_ {2} p_ {2} + e_ {1} p_ {3} -p_ {4}, \\\ end {zarovnáno}}

A tak dále ; v tomto případě se levá strana nikdy nezruší.

Tyto rovnice umožňují vyjádření $e i$ indukcí jako funkci $p k$ ; naopak, přepsat je jako:

{\ begin {aligned} p_ {1} & = e_ {1}, \\ p_ {2} & = e_ {1} p_ {1} -2e_ {2}, \\ p_ {3} & = e_ {1 } p_ {2} -e_ {2} p_ {1} + 3e_ {3}, \\ p_ {4} & = e_ {1} p_ {3} -e_ {2} p_ {2} + e_ {3} p_ {1} -4e_ {4}, \ quad {\ text {atd.}} \\\ konec {zarovnáno}}

můžeme vyjádřit p i jako funkci e k .

Aplikace na kořeny polynomu

Když je $x i$ bráno jako parametry a ne jako proměnné, uvažujme jednotkový polynom v $t,$ který má pro kořeny $x 1 , ..., x n$ :

\ prod _ {{i = 1}} ^ {n} \ left (t-x_ {i} \ right) = \ sum _ {{k = 0}} ^ {n} (- 1) ^ {{k} } a_ {k} t ^ {{nk}},

kde koeficienty $a k$ jsou dány elementárními symetrickými polynomy kořenů: $a k = e k ( x 1 ,\dots, x n )$ . Součty mocnin kořenů (které také nazýváme Newtonovy součty ) lze poté vyjádřit jako funkci koeficientů polynomu postupným použitím Newtonových identit: $s_ {k} = p_ {k} (x_ {1}, \ ldots, x_ {n}) = \ sum _ {{i = 1}} ^ {n} x_ {i} ^ {k},$

{\ begin {aligned} s_ {1} & = a_ {1}, \\ s_ {2} & = a_ {1} s_ {1} -2a_ {2}, \\ s_ {3} & = a_ {1 } s_ {2} -a_ {2} s_ {1} + 3a_ {3}, \\ s_ {4} & = a_ {1} s_ {3} -a_ {2} s_ {2} + a_ {3} s_ {1} -4a_ {4}, \ quad {\ text {atd.}} \\\ konec {zarovnáno}}

Aplikace na charakteristický polynom matice

Když polynom předchozího odstavce je charakteristický polynom z matice A , kořeny $x i$ jsou vlastní hodnoty z A (počítáno s jejich algebraické multiplicity). Pro jakékoli celé číslo k má matice A k pro vlastní čísla $x k i$ (s odpovídajícími multiplicitami). Koeficienty charakteristického polynomu A k jsou pak dány elementárními symetrickými polynomy v těchto mocninách $x k i$ . Zejména součet $x k i$ je dán stopy z A k : $s k = tr ( k )$ .

Newtonovy identity tak připojit stopách A K koeficienty charakteristického polynomu A . Naopak, jejich použitím k výpočtu elementárních symetrických polynomů ze součtů mocnin, proto umožňují určit charakteristický polynom A tím, že vypočítají pouze mocniny A a jejich stopy a poté vyřeší trojúhelníkový systém rovnic. Cayley-Hamilton teorém pak umožňuje jednoduše odečíst inverzní matici A .

Všechny tyto výpočty (přepsané do efektivní formy) tvoří algoritmus Faddeev-Leverrier z roku 1840; rychlá paralelní implementace tohoto algoritmu je způsobena Lazslem Csankym v roce 1976. Vyžaduje však dělení (podle celých čísel), a je proto použitelná obecně pouze v oblastech s charakteristikou 0. Implementace Csanky ukazuje, že tyto různé výpočty jsou ( v tomto případě) ve třídě složitosti NC .

Vztah k Galoisově teorii

Pro dané n tvoří elementární symetrické polynomy $e k ( x 1 , ..., x n )$ pro k = 1, ..., n „ algebraický základ “ komutativní algebry symetrických polynomů v $x 1 , ..., x n$ , to znamená, že jakýkoli symetrický polynom je vyjádřen jako polynomiální funkce těchto elementárních symetrických polynomů a že tento výraz je jedinečný. Tento obecný výsledek, známý pod názvem základní věty symetrických polynomů , lze v případě Newtonových součtů učinit explicitní (pomocí Newtonových identit). Pokud tedy použijeme jednotkový polynom, jehož koeficienty $a$ $k$ jsou považovány za parametry, znamená to, že jakoukoli polynomickou funkci $S$ $($ $x$ $1$ $, ...,$ $x$ $n$ $)$ jejích kořenů lze zapsat jako polynomiální funkci $P$ $($ $a$ $1$ $, ...,$ $a$ $n$ $)$ samotných jeho koeficientů, to znamená, aniž by bylo nutné tyto kořeny vypočítat. To lze také odvodit z Galoisovy teorie , kdy $a$ $k$ vidíme jako prvky základního pole; kořeny jsou pak v prodloužení tohoto pole a Galoisova skupina tohoto rozšíření je permutuje podle celé symetrické skupiny; pole neměnné všemi prvky této skupiny Galois je základní pole. $\ textstyle t ^ {n} + \ sum _ {{k = 1}} ^ {n} (- 1) ^ {{k}} a_ {k} t ^ {{nk}}$

Naopak Newtonovy identity nám umožňují vyjádřit elementární symetrické polynomy jako funkci Newtonových součtů a prokázat, že tyto součty také tvoří „algebraický základ“ komutativní algebry symetrických polynomů.

Demonstrace

Každou identitu lze ověřit přímo jednoduchým algebraickým výpočtem, ale obecný případ vyžaduje demonstraci. Zde je několik možných cest:

Ze zvláštního případu n = k

K -té Newtonova identity k- proměnných se získá substitucí ve vzorci definující $e K$ :

{\ displaystyle \ prod _ {i = 1} ^ {k} (t-x_ {i}) = \ součet _ {i = 0} ^ {k} (- 1) ^ {ki} e_ {ki} (x_ {1}, \ ldots, x_ {k}) t ^ {i}.}

Dosazením x j za t máme:

{\ displaystyle 0 = \ součet _ {i = 0} ^ {k} (- 1) ^ {ki} e_ {ki} (x_ {1}, \ ldots, x_ {k}) {x_ {j}} ^ {i} \ quad {\ text {pro}} 1 \ leq j \ leq k.}

Sečtením množiny j dostaneme:

{\ displaystyle 0 = (- 1) ^ {k} ke_ {k} (x_ {1}, \ ldots, x_ {k}) + \ sum _ {i = 1} ^ {k} (- 1) ^ { ki} e_ {ki} (x_ {1}, \ ldots, x_ {k}) p_ {i} (x_ {1}, \ ldots, x_ {k}).}

(Výrazy na i = 0 jsou od součtu odděleny, protože p 0 je obvykle nedefinováno.)

Tato rovnice okamžitě dává hledanou identitu. Identity odpovídající n < k proměnným jsou odvozeny zrušením zbývajících k - n proměnných; případ, kdy se n > k zachází s povšimnutím, že každý monomiál neobsahuje více než k proměnných a že tento monomiál se nezmění, pokud zrušíme n - k dalších proměnných; pak stačí použít identitu Newtona odpovídající těmto k proměnným.

Identifikací formální řady

Newtonovy identity lze také získat pomocí formálních manipulací založených na identitě

\ prod _ {{i = 1}} ^ {n} (t-x_ {i}) = \ sum _ {{k = 0}} ^ {n} (- 1) ^ {{k}} a_ {k } t ^ {{nk}}

spojující kořeny a koeficienty jednotkového polynomu. Abychom usnadnili výpočty, začneme dosazením 1 / t za t a dva členy vynásobíme t n , přičemž získáme:

{\ displaystyle \ textstyle \ prod _ {i = 1} ^ {n} (1-x_ {i} t) = \ součet _ {k = 0} ^ {n} (- 1) ^ {k} a_ {k } t ^ {k}.}

Nahrazením a i symetrickými polynomy získáme identitu

\ sum _ {{k = 0}} ^ {n} (- 1) ^ {{k}} e_ {k} (x_ {1}, \ ldots, x_ {n}) t ^ {k} = \ prod _ {{i = 1}} ^ {n} (1-x_ {i} t).

Po diferenciaci s ohledem na t a vynásobení t přichází:

{\ begin {aligned} \ sum _ {{k = 0}} ^ {n} (- 1) ^ {{k}} ke_ {k} (x_ {1}, \ ldots, x_ {n}) t ^ {k} & = t \ sum _ {{i = 1}} ^ {n} \ left ((- x_ {i}) \ prod \ nolimits _ {{j \ neq i}} (1-x_ {j} t) \ right) \\ & = - \ left (\ sum _ {{i = 1}} ^ {n} {\ frac {x_ {i} t} {1-x_ {i} t}} \ right) \ prod \ nolimits _ {{j = 1}} ^ {n} (1-x_ {j} t) \\ & = - \ left (\ sum _ {{i = 1}} ^ {n} \ sum _ {{j = 1}} ^ {\ infty} (x_ {i} t) ^ {j} \ vpravo) \ vlevo (\ sum _ {{\ ell = 0}} ^ {n} (- 1) ^ { \ ell} e _ {\ ell} (x_ {1}, \ ldots, x_ {n}) t ^ {\ ell} \ right) \\ & = \ left (\ sum _ {{j = 1}} ^ {\ infty} p_ {j} (x_ {1}, \ ldots, x_ {n}) t ^ {j} \ right) \ left (\ sum _ {{\ ell = 0}} ^ {n} (- 1) ^ {{\ ell -1}} e _ {\ ell} (x_ {1}, \ ldots, x_ {n}) t ^ {\ ell} \ right), \\\ end {zarovnáno}}

kde polynomial na pravé straně byl nejprve přepsán jako racionální funkce , pak se tento vyvinul do formální řady v t a koeficienty každého t j seskupeny dohromady, aby získaly součet sil (konvergence řady je ve skutečnosti zajištěna pro t dostatečně blízko nule, ale protože nás zajímají pouze koeficienty t j , tato otázka konvergence nemá žádný skutečný význam). Porovnáním koeficientů t k dvou členů získáme

(-1) ^ {{k}} ke_ {k} (x_ {1}, \ ldots, x_ {n}) = \ sum _ {{j = 1}} ^ {k} (- 1) ^ {{ kj-1}} p_ {j} (x_ {1}, \ ldots, x_ {n}) e _ {{kj}} (x_ {1}, \ ldots, x_ {n})

což je Newtonova k - ta identita.

Jako teleskopický součet identit

Následující derivace je formulována v kruhu symetrických polynomů , protože pak identity nezávisí na počtu proměnných. Pro pevné k > 0, definujeme (pro 2 ≤ i ≤ k ) symetrický funkce R ( i ) jako součet různých monomials stupně k získané vynásobením proměnnou umocněný na i o k - i jiný odlišný proměnné. Zejména r ( k ) = p k ; případ r (1) je vyloučen, protože monomialy by již neměly proměnnou, která by hrála zvláštní roli. Všechny produkty p i e k - i lze vyjádřit jako funkci r ( j ) ( kromě extrémních případů i = 1 a i = k ). Získáváme , protože každý součin členů nalevo zahrnujících odlišné proměnné přispívá k r ( i ), zatímco ty, kde se proměnné p i již objevují mezi proměnnými příslušného členu e k - i přispívají k r ( i + 1) a že všechny podmínky na pravé straně jsou tak získány jednou a pouze jednou. Pro i = k vynásobením e 0 = 1 dostaneme triviálně . Nakonec součin p 1 e k −1 (odpovídající i = 1) přináší příspěvky do r ( i + 1) = r (2) jako u ostatních hodnot i < k , ale zbývající příspěvky se rovnají k krát každý monomiál e k , protože každá z proměnných může pocházet z faktoru p 1 ; stejně . $p_ {i} e _ {{ki}} = r (i) + r (i + 1) \ quad {\ text {pro}} 1 <i <k$ $p_ {k} e_ {0} = p_ {k} = r (k) \,$ $p_ {1} e _ {{k-1}} = ke_ {k} + r (2)$

K -té Newtonova identity se pak získá tím, že střídavý součet rovnic, která je teleskopická součet všech hlediska formy r ( i ) zmizí.

Podobné identity

Existuje mnoho rodin podobných identit a úzce souvisejících s Newtonovými identitami.

Použití zcela homogenních symetrických polynomů

Poznamenat, H K o zcela homogenní symetrický polynomu (en) , to znamená, že součet všech monomials stupně k , součty sil splňují identity podobné těm, Newton, ale jejichž podmínky jsou pozitivní. V kruhu symetrických polynomů jsou psány pro všechna k ≥ 1. Na rozdíl od Newtonových identit levý člen nezmizí pro k dostatečně velký a počet nenulových členů pravých členů roste neomezeně. Pro první hodnoty k máme $kh_ {k} = \ sum _ {{i = 1}} ^ {k} h _ {{ki}} p_ {i},$

{\ begin {aligned} h_ {1} & = p_ {1}, \\ 2h_ {2} & = h_ {1} p_ {1} + p_ {2}, \\ 3h_ {3} & = h_ {2 } p_ {1} + h_ {1} p_ {2} + p_ {3}. \\\ end {zarovnáno}}

Tyto vztahy lze prokázat argumentem podobným výše uvedenému pomocí formální řady, ale s použitím identity mezi generujícími funkcemi :

\ sum _ {{k = 0}} ^ {\ infty} h_ {k} (X_ {1}, \ ldots, X_ {n}) t ^ {k} = \ prod _ {{i = 1}} ^ {n} {\ frac 1 {1-X_ {i} t}}

Na druhou stranu se ostatní dříve uvedené demonstrace nemohou snadno přizpůsobit těmto novým identitám.

Vyjádření elementárních symetrických polynomů jako funkce Newtonových součtů

Jak jsme řekli, Newtonovy identity umožňují vyjádřit indukcí elementární symetrické polynomy jako funkci Newtonových součtů. To vyžaduje dělení na celá čísla, a proto je lze provést pouze v kruhu Λ Q symetrických polynomů s racionálními koeficienty:

{\ displaystyle {\ begin {aligned} e_ {1} & = p_ {1}, \\ e_ {2} & = \ textstyle {\ frac {1} {2}} p_ {1} ^ {2} - { \ frac {1} {2}} p_ {2} && = \ textstyle {\ frac {1} {2}} (p_ {1} ^ {2} -p_ {2}), \\ e_ {3} & = \ textstyle {\ frac {1} {6}} p_ {1} ^ {3} - {\ frac {1} {2}} p_ {1} p_ {2} + {\ frac {1} {3} } p_ {3} && = \ textstyle {\ frac {1} {6}} (p_ {1} ^ {3} -3p_ {1} p_ {2} + 2p_ {3}), \\ e_ {4} & = \ textstyle {\ frac {1} {24}} p_ {1} ^ {4} - {\ frac {1} {4}} p_ {1} ^ {2} p_ {2} + {\ frac { 1} {8}} p_ {2} ^ {2} + {\ frac {1} {3}} p_ {1} p_ {3} - {\ frac {1} {4}} p_ {4} && = \ textstyle {\ frac {1} {24}} (p_ {1} ^ {4} -6p_ {1} ^ {2} p_ {2} + 3p_ {2} ^ {2} + 8p_ {1} p_ { 3} -6p_ {4}), \\\ end {zarovnáno}}}

A tak dále. Pro jednotné polynomu, tyto vzorce vyjádřit koeficientů jako funkce částek mocnin kořenů, nahrazením každé E i o v i a každý p k u s k .

Vyjádření zcela homogenních symetrických polynomů jako funkce Newtonových součtů

Analogické vztahy týkající se zcela homogenních symetrických polynomů se vyvíjejí stejným způsobem, což vede k rovnicím:

{\ displaystyle {\ begin {aligned} h_ {1} & = p_ {1}, \\ h_ {2} & = \ textstyle {\ frac {1} {2}} p_ {1} ^ {2} + { \ frac {1} {2}} p_ {2} && = \ textstyle {\ frac {1} {2}} (p_ {1} ^ {2} + p_ {2}), \\ h_ {3} & = \ textstyle {\ frac {1} {6}} p_ {1} ^ {3} + {\ frac {1} {2}} p_ {1} p_ {2} + {\ frac {1} {3} } p_ {3} && = \ textstyle {\ frac {1} {6}} (p_ {1} ^ {3} + 3p_ {1} p_ {2} + 2p_ {3}), \\ h_ {4} & = \ textstyle {\ frac {1} {24}} p_ {1} ^ {4} + {\ frac {1} {4}} p_ {1} ^ {2} p_ {2} + {\ frac { 1} {8}} p_ {2} ^ {2} + {\ frac {1} {3}} p_ {1} p_ {3} + {\ frac {1} {4}} p_ {4} && = \ textstyle {\ frac {1} {24}} (p_ {1} ^ {4} + 6p_ {1} ^ {2} p_ {2} + 3p_ {2} ^ {2} + 8p_ {1} p_ { 3} + 6p_ {4}), {\ text {atd.}} \\\ konec {zarovnáno}}}

kde jsou všechny podmínky kladné. Tyto výrazy přesně odpovídají indikátorům cyklů polynomů symetrických skupin interpretací newtonských součtů p i jako neurčitých: koeficient monomálu p 1 m 1 p 2 m 2 … p l m l ve vyjádření h k je roven podílu všech permutací k , který má m 1 pevné body, m 2 cykly o délce 2, ..., a m l cykly o délce l . Přesněji lze tento koeficient zapsat $1 / N$ , s ; N je počet permutací s pevnou permutací π majících odpovídající typ cyklu. Výrazy odpovídající elementárních symetrických funkcí mají koeficienty, které mají stejné absolutní hodnoty, ale znamením, která se rovná podpisu z n, to znamená, že se (1) m 2 + m 4 + ... . $N = \ Pi _ {{i = 1}} ^ {l} (m_ {i}! \, I ^ {{m_ {i}}})$

Vyjádření newtonských součtů

Naopak můžeme Newtonovy součty vyjádřit jako funkci elementárních symetrických polynomů a tyto výrazy mají celočíselné koeficienty:

{\ begin {aligned} p_ {1} & = e_ {1}, \\ p_ {2} & = e_ {1} ^ {2} -2e_ {2}, \\ p_ {3} & = e_ {1 } ^ {3} -3e_ {2} e_ {1} + 3e_ {3}, \\ p_ {4} & = e_ {1} ^ {4} -4e_ {2} e_ {1} ^ {2} + 4._ {3} e_ {1} + 2e_ {2} ^ {2} -4e_ {4}, \\ p_ {5} & = e_ {1} ^ {5} -5e_ {2} e_ {1} ^ { 3} + 5e_ {2} ^ {2} e_ {1} + 5e_ {3} e_ {1} ^ {2} -5e_ {3} e_ {2} -5e_ {4} e_ {1} + 5e_ {5 }, \\ p_ {6} & = e_ {1} ^ {6} -6e_ {2} e_ {1} ^ {4} + 9e_ {2} ^ {2} e_ {1} ^ {2} + 6e_ {3} e_ {1} ^ {3} -2e_ {2} ^ {3} -12e_ {3} e_ {2} e_ {1} -6e_ {4} e_ {1} ^ {2} + 3e_ {3 } ^ {2} + 6e_ {4} e_ {2} + 6e_ {1} e_ {5} -6e_ {6}, {\ text {atd.}} \\\ end {zarovnáno}}

ale zdá se, že tyto výrazy nenásledují explicitní pravidlo. Vidíme však, že koeficient monomia ve výrazu $p$ $k$ má stejné znaménko jako koeficient příslušného součinu ve výrazu $e$ $k$ uvedený výše, tj. (−1) m 2 + m 4 +… . Absolutní hodnota koeficientu M je navíc součtem indexu posledního polynomu každé sekvence převzatého ze sady posloupností elementárních symetrických polynomů, jejichž součinem je M : koeficient $e$ $1$ $5$ $e$ $3$ $e$ $4$ $3$ ve výrazu dávajícím p 20 je , protože mezi odlišnými řády pěti faktorů e 1 , jednoho faktoru e 3 a tří faktorů e 4 , existuje 280 končících na e 1 , 56 končících na e 3 a 168 končících na e 4 . $M = \ Pi _ {{i = 1}} ^ {l} e_ {i} ^ {{m_ {i}}}$ $\ Pi _ {{i = 1}} ^ {l} p_ {i} ^ {{m_ {i}}}$ $(-1) ^ {{0 + 3}} (280 \ krát 1 + 56 \ krát 3 + 168 \ krát 4) = - 1120$

Nakonec lze také obrátit identity týkající se zcela homogenních polynomů, což vede k:

{\ begin {aligned} p_ {1} & = + h_ {1}, \\ p_ {2} & = - h_ {1} ^ {2} + 2h_ {2}, \\ p_ {3} & = + h_ {1} ^ {3} -3h_ {2} h_ {1} + 3h_ {3}, \\ p_ {4} & = - h_ {1} ^ {4} + 4h_ {2} h_ {1} ^ {2} -4h_ {3} h_ {1} -2h_ {2} ^ {2} + 4h_ {4}, \\ p_ {5} & = + h_ {1} ^ {5} -5h_ {2} h_ {1} ^ {3} + 5h_ {2} ^ {2} h_ {1} + 5h_ {3} h_ {1} ^ {2} -5h_ {3} h_ {2} -5h_ {4} h_ {1 } + 5h_ {5}, \\ p_ {6} & = - h_ {1} ^ {6} + 6h_ {2} h_ {1} ^ {4} -9h_ {2} ^ {2} h_ {1} ^ {2} -6h_ {3} h_ {1} ^ {3} + 2h_ {2} ^ {3} + 12h_ {3} h_ {2} h_ {1} + 6h_ {4} h_ {1} ^ { 2} -3h_ {3} ^ {2} -6h_ {4} h_ {2} -6h_ {1} h_ {5} + 6h_ {6}, {\ text {atd.}} \\\ konec {zarovnáno} }

Tyto identity mají přesně stejný tvar jako předchozí, s výjimkou znaménka: znaménko monomia je nyní - (- 1) m 1 + m 2 + m 3 +… . $\ Pi _ {{i = 1}} ^ {l} h_ {i} ^ {{m_ {i}}}$

Výrazy jako determinanty

Předchozí výrazy odpovídající řešení systémů lineárních rovnic je lze formulovat explicitně pomocí determinantů pomocí Cramerova pravidla . Například psaní Newtonových identit ve formuláři:

{\ begin {aligned} e_ {1} & = 1p_ {1}, \\ 2e_ {2} & = e_ {1} p_ {1} -1p_ {2}, \\ 3e_ {3} & = e_ {2 } p_ {1} -e_ {1} p_ {2} + 1p_ {3}, \\\ vdots & = \ vdots \\ ne_ {n} & = e _ {{n-1}} p_ {1} - e_ {{n-2}} p_ {2} + \ cdots + (- 1) ^ {n} e_ {1} p _ {{n-1}} + (- 1) ^ {{n-1}} p_ {n}, \\\ end {zarovnáno}}

a přijímání , , ..., a jak znám, dostaneme k ní: $p_1$ ${-p_ {2}}$ $p_3$ $(-1) ^ {n} p _ {{n-1}}$ $p_ {n}$

p_ {n} = {\ frac {{\ begin {vmatrix} 1 & 0 & \ cdots && e_ {1} \\ e_ {1} & 1 & 0 & \ cdots & 2e_ {2} \\ e_ {2} & e_ {1} & 1 && 3e_ {3} \ \\ vdots && \ ddots & \ ddots & \ vdots \\ e _ {{n-1}} & \ cdots & e_ {2} & e_ {1} & ne_ {n} \ end {vmatrix}}} {{\ begin {vmatrix} 1 & 0 & \ cdots & \\ e_ {1} & 1 & 0 & \ cdots \\ e_ {2} & e_ {1} & 1 & \\\ vdots && \ ddots & \ ddots \\ e _ {{n-1}} & \ cdots & e_ {2} & e_ {1} & (- 1) ^ {{n-1}} \ end {vmatrix}}}} = {\ frac {1} {(- 1) ^ {{n-1}}}} {\ begin {vmatrix} 1 & 0 & \ cdots && e_ {1} \\ e_ { 1} & 1 & 0 & \ cdots & 2e_ {2} \\ e_ {2} & e_ {1} & 1 && 3e_ {3} \\\ vdots && \ ddots & \ ddots & \ vdots \\ e _ { {n-1}} & \ cdots & e_ {2} & e_ {1} & ne_ {n} \ end {vmatrix}} = {\ begin {vmatrix} e_ {1} & 1 & 0 & \ cdots \\ 2e_ {2} & e_ {1} & 1 & 0 & \ cdots \\ 3e_ {3} & e_ {2} & e_ {1} & 1 \\\ vdots &&& \ ddots & \ ddots \\ ne_ {n} & e _ ​​{{n-1}} & \ cdots && e_ {1} \ end {vmatrix}}.

Výpočty jsou analogické (ale trochu komplikovanější) pro nebo pro výrazy jako funkce zcela homogenních symetrických polynomů; konečně dostaneme: $v$

e_ {n} = {\ frac 1 {n!}} {\ begin {vmatrix} p_ {1} & 1 & 0 & \ cdots \\ p_ {2} & p_ {1} & 2 & 0 & \ cdots \ \\ vdots && \ ddots & \ ddots \\ p _ {{n-1}} & p _ {{n-2}} & \ cdots & p_ {1} & n-1 \\ p_ {n} & p _ {{n-1}} & \ cdots & p_ {2} & p_ {1} \ end {vmatrix}}, \ qquad p_ {n} = (- 1) ^ {{n-1}} {\ začátek {vmatrix} h_ {1} & 1 & 0 & \ cdots \\ 2h_ {2} & h_ {1} & 1 & 0 & \ cdots \\ 3h_ {3} & h_ {2} & h_ {1} & 1 \\\ vdots &&& \ ddots & \ ddots \\ nh_ {n} & h _ {{n-1}} & \ cdots && h_ {1} \ end {vmatrix}}, \ qquad h_ {n} = {\ frac 1 {n!}} {\ begin {vmatrix} p_ {1} & - 1 & 0 & \ cdots \\ p_ {2} & p_ {1} & -2 & 0 & \ cdots \\\ vdots && \ ddots & \ ddots \\ p _ {{n-1}} & p _ {{n-2}} & \ cdots & p_ {1} & 1-n \\ p_ {n} & p_ {{n-1 }} & \ cdots & p_ {2} & p_ {1} \ end {vmatrix}}.

Můžeme si všimnout, že vzorec pro $h n se$ získá převzetím permanentu matice pro $e n$ namísto jeho determinantu a obecněji, že výraz pro libovolný Schurův polynom lze získat převzetím odpovídajícího imanantu této matice.

Poznámky a odkazy

(fr) Tento článek je částečně nebo zcela převzat z článku anglické Wikipedie s názvem „ Newtonovy identity “ ( viz seznam autorů ) .

(en) L. Csanky , „ Algoritmy rychlé paralelní maticové inverze “ , SIAM J. Comput. , sv. 5, n O 4,Prosinec 1976( číst online [PDF] ).
(in) DG Mead , „ Newton's Identities “ , American Mathematical Monthly , Mathematical Association of America, sv. 99-8,1992, str. 749–751 ( DOI 10.2307 / 2324242 , JSTOR 2324242 ).
(in) Ian G. Macdonald , Symetrické funkce a Hallovy polynomy , Oxford, Clarendon Press, Oxford University Press, kol. "Oxfordské matematické monografie",1979, viii + 180 s. ( ISBN 0-19-853530-9 , Math Reviews 84g: 05003 ) , s. 20.
(in) Dudley E. Littlewood , The theory of group characters and matrix representations of groups , Oxford, Oxford University Press ,1950, viii + 310 s. ( ISBN 0-8218-4067-3 ) , str. 84.

Podívejte se také

Související články

Inverzní polynom
Symetrický indikátor cyklu skupiny
Fluidní roztok (in) , článek poskytující aplikaci Newtonových identit pro výpočet charakteristického polynomu Einsteinova tenzoru v případě dokonalé tekutiny

Bibliografie

(en) Jean-Pierre Tignol, Galoisova teorie algebraických rovnic , Singapur, World Scientific ,2001, 333 s. ( ISBN 978-981-02-4541-2 , číst online )
(en) F. Bergeron, G. Labelle a P. Leroux, kombinatorické druhy a struktury podobné stromům , Cambridge, Cambridge University Press ,1998, 457 s. ( ISBN 978-0-521-57323-8 , číst online )
(en) Peter J. Cameron , permutační skupiny , Cambridge, Cambridge University Press ,1999, 220 s. ( ISBN 978-0-521-65378-7 , číst online )
(en) David A. Cox , John Little et Don O'Shea , Ideály, odrůdy a algoritmy: úvod do výpočetní algebraické geometrie a komutativní algebry , New York, Springer-Verlag ,2007, 3 e ed. ( ISBN 978-0-387-35651-8 , číst online )
(en) David Eppstein a Michael T. Goodrich (en) , „Prostorově efektivní identifikace opozdilců v datových tocích zpáteční cestou prostřednictvím Newtonových identit a invertibilních Bloomových filtrů“ , Algoritmy a datové struktury , 10. mezinárodní workshop, WADS 2007 , Springer , kol. "Lecture Notes in Computer Science" ( n O 4619),2007, str. 637-648, „ 0704.3313 “ , volný text přístup na arXiv .
(en) IG Macdonald , Symetrické funkce a Hallovy polynomy , New York, Oxford Science Publications. Clarendon Press, Oxford University Press, kol. "Oxfordské matematické monografie",1995, Druhé vydání. ( ISBN 0-19-853489-2 , Math Reviews 96h: 05207 ) , x + 475
(en) Richard P. Stanley , Enumerative Combinatorics , sv. 2 [ detail vydání ] ( online prezentace )
(en) Bernd Sturmfels , Algorithms in Invariant Theory , New York, Springer-Verlag ,1992( ISBN 978-0-387-82445-1 )
(en) Alan Tucker, Applied Combinatorics , New York, Wiley ,1980, 5. vyd. , 476 s. ( ISBN 978-0-471-73507-6 )

externí odkazy

(en) Eric W. Weisstein , „ Newton-Girardovy vzorce “ , na MathWorld
(en) Maticový důkaz Newtonových identit v časopise Mathematics Magazine
(en) Pablo A Parrilo ( MIT ), Žádost o počet skutečných kořenů