Tożsamości Newtona

W matematyce , a dokładniej w algebrze , tożsamości Newtona (znane również jako wzory Newtona-Girarda ) są relacjami między dwoma typami wielomianów symetrycznych , elementarnymi wielomianami symetrycznymi i sumami Newtona , czyli sumami potęg te. Oceniano u korzeni o wielomianu P z jednej zmiennej, te tożsamości pozwalają wyrazić sum k -tego uprawnień wszystkich korzeni P(liczonych z ich krotnością) w funkcji współczynników P , bez konieczności wyznaczania tych pierwiastków. Wzory te zostały ponownie odkryte przez Izaaka Newtona około 1666 roku, najwyraźniej bez znajomości analogicznej pracy Alberta Girarda z 1629 roku. Mają zastosowanie w wielu dziedzinach matematycznych, takich jak teoria Galois , teoria niezmienników , teoria grup , kombinatoryki , a nawet w dziedzinach niematematycznych, takich jak ogólna teoria względności .

Stwierdzenie matematyczne

Formułowanie według wielomianów symetrycznych

Niech $x 1 , ..., x n będą$ zmiennymi; dla dowolnej niezerowej liczby naturalnej k oznaczamy przez $p k ( x 1 , ..., x n )$ sumę potęg $k$ -tych:

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

(zwana sumą Newtona )

i $k \geq 0$ , to oznacza w $e k ( x 1 , ..., x n )$ elementarna wielomian symetryczny , który jest sumą różnych produktów k różnych zmiennych wśród N ; tak w szczególności

{\ displaystyle {\ begin {wyrównany} 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}) & = \ styl tekstu \ suma \ 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. \\\ koniec {wyrównany}}}

Do tożsamości Newtona są następnie zapisywane:

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

prawdziwe relacje na wszystko . W ten sposób otrzymujemy dla pierwszych wartości k : $k \ in \ mathbb {N} ^ {*}$

{\ begin {wyrównany} 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 {wyrównany}}

Postać tych relacji nie zależy od liczby n zmiennych (ale lewa strona staje się zero po n- tej tożsamości), co pozwala na określenie ich jako tożsamości w pierścieniu wielomianów symetrycznych . W tym ringu mamy:

{\ begin {wyrównany} 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 {wyrównany}}

I tak dalej ; w tym przypadku lewa strona nigdy się nie anuluje.

Równania te pozwalają na wyrażenie $e i$ przez indukcję jako funkcję $p k$ ; odwrotnie, przepisując je jako:

{\ początek {wyrównany} 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 {\ tekst {itd.}} \\\ koniec {wyrównany}}

możemy wyrazić p I jako funkcja e k .

Zastosowanie do pierwiastków wielomianu

Przyjmując $x i$ jako parametry, a nie jako zmienne, rozważmy wielomian jednostkowy w $t$ mający dla pierwiastków $x 1 , ..., x n$ :

\ prod _ {{i = 1}} ^ {n} \ lewa (t-x_ {i} \ prawa) = \ suma _ {{k = 0}} ^ {n} (- 1) ^ {{k} } a_ {k} t ^ {{nk}},

gdzie współczynniki $a k$ są określone przez elementarne symetryczne wielomiany pierwiastków: $a k = e k ( x 1 ,\dots, x n )$ . Sumy potęg pierwiastków (które nazywamy również sumami Newtona ) można następnie wyrazić jako funkcję współczynników wielomianu, stosując tożsamości Newtona krok po kroku: $s_ {k} = p_ {k} (x_ {1}, \ ldots, x_ {n}) = \ suma _ {{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 {\ tekst {itd.}} \\\ koniec {wyrównany}}

Zastosowanie do wielomianu charakterystycznego macierzy

Gdy wielomianem poprzednim ustępie, jest charakterystyczny wielomian z macierzy A , korzenie $x i$ są wartości własne z A (liczonych z ich wielokrotności algebraicznych). Dla dowolnej liczby całkowitej k macierz A k ma dla wartości własnych $x k ja$ (z odpowiednimi krotnościami). Współczynniki wielomianu charakterystycznego A k są następnie podane przez elementarne wielomiany symetryczne w tych potęgach $x k ja$ . W szczególności suma $x k ja$ jest przez ślad z A k : $y k = tR ( K )$ .

Tożsamości Newtona połącz więc ślady A k ze współczynnikami wielomianu charakterystycznego A . I odwrotnie, używając ich do obliczania elementarnych wielomianów symetrycznych z sum potęg, umożliwiają zatem wyznaczenie wielomianu charakterystycznego A , obliczając tylko potęgi A i ich ślady, a następnie rozwiązując trójkątny układ równań. Twierdzenie Cayleya-Hamiltona pozwala więc po prostu wydedukować macierz odwrotną A .

Wszystkie te obliczenia (przepisane w efektywnej formie) składają się na algorytm Faddeeva-Leverriera z 1840 r.; szybka równoległa implementacja tego algorytmu została dokonana przez Lazslo Csanky'ego w 1976 roku. Wymaga on jednak dzielenia (przez liczby całkowite) i dlatego jest ogólnie użyteczny tylko w polach o charakterystyce 0. Implementacja Csanky'ego pokazuje, że te różne obliczenia są ( w tym przypadku) w klasie złożoności NC .

Związek z teorią Galois

Dla danego n elementarne wielomiany symetryczne $e k ( x 1 ,\dots, x n )$ dla k = 1,…, n tworzą „ bazę algebraiczną” algebry przemiennej wielomianów symetrycznych przy $x 1 , ..., x n$ , to znaczy, że każdy wielomian symetryczny jest wyrażony jako funkcja wielomianowa tych elementarnych wielomianów symetrycznych i że to wyrażenie jest niepowtarzalne. Ten ogólny wynik, znany pod nazwą fundamentalnego twierdzenia o wielomianach symetrycznych , może być wyjaśniony (przy użyciu tożsamości Newtona) w przypadku sum Newtona. Zatem w odniesieniu do wielomianu jednostkowego, którego współczynniki $a$ $k$ są uważane za parametry, oznacza to, że dowolną funkcję wielomianową $S$ $($ $x$ $1$ $,\dots,$ $x$ $n$ $)$ jej pierwiastków można zapisać jako funkcję wielomianową $P$ $($ $a$ $1$ $,\dots,$ $a$ $n$ $)$ samych jego współczynników, to znaczy bez konieczności obliczania tych pierwiastków. To również może być wyprowadzona z teorii Galois , widząc $jak$ $k$ jako elementów polu bazowej; korzenie znajdują się wówczas na przedłużeniu tego pola, a grupa Galois tego rozszerzenia permutuje je zgodnie z całą grupą symetryczną; polem niezmiennikiem wszystkich elementów tej grupy Galois jest pole bazowe. $\ styl tekstu t ^ {n} + \ suma _ {{k = 1}} ^ {n} (- 1) ^ {{k}} a_ {k} t ^ {{nk}}$

I odwrotnie, tożsamości Newtona pozwalają nam wyrazić elementarne wielomiany symetryczne jako funkcję sum Newtona i wykazać, że te sumy tworzą również „bazę algebraiczną” algebry przemiennej wielomianów symetrycznych.

Demonstracje

Każdą tożsamość można zweryfikować bezpośrednio za pomocą prostego obliczenia algebraicznego, ale ogólny przypadek wymaga demonstracji. Oto kilka możliwych dróg:

Ze szczególnego przypadku n = k

K -tego tożsamości Newtona w k zmiennej uzyskuje się przez podstawienie we wzorze określającym $e k$ :

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

Podstawiając x j za t , otrzymujemy:

{\ displaystyle 0 = \ suma _ {i = 0} ^ {k} (- 1) ^ {ki} e_ {ki} (x_ {1}, \ ldots, x_ {k}) {x_ {j}} ^ {i} \ quad {\ tekst {dla}} 1 \ leq j \ leq k.}

Sumując zbiór j , otrzymujemy:

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

(Warunki przy i = 0 są oddzielone od sumy, ponieważ p 0 jest zwykle niezdefiniowane).

To równanie natychmiast daje poszukiwaną tożsamość. Tożsamości odpowiadające n < k zmiennym są wydedukowane poprzez anulowanie k - n pozostałych zmiennych; przypadek, w którym n > k jest traktowane przez zauważenie, że każdy jednomian nie zawiera więcej niż k zmiennych i że ten jednomian nie zmienia się, jeśli anulujemy n - k innych zmiennych; wystarczy wtedy użyć tożsamości Newtona odpowiadającej tym k zmiennym.

Poprzez identyfikację serii formalnych

Tożsamości Newtona można również uzyskać za pomocą formalnych manipulacji opartych na tożsamości

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

łączenie pierwiastków i współczynników wielomianu jednostkowego. Aby ułatwić obliczenia, zaczynamy od podstawienia 1 / t za t i mnożymy oba elementy przez t n , otrzymując:

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

Zastępując a i wielomianami symetrycznymi otrzymujemy tożsamość

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

Po zróżnicowaniu względem t i pomnożeniu przez t otrzymujemy :

{\ początek {wyrównany} \ 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) \ prawo) \\ & = - \ lewo (\ suma _ {{i = 1}} ^ {n} {\ frac {x_ {i} t} {1-x_ {i} t}} \ po prawej) \ prod \ nolimits _ {{j = 1}} ^ {n} (1-x_ {j} t) \\ & = - \ lewo (\ suma _ {{i = 1}} ^ {n} \ suma _ {{j = 1}} ^ {\ infty} (x_ {i} t) ^ {j} \ prawy) \ lewy (\ sum _ {{\ ell = 0}} ^ {n} (- 1) ^ { \ ell} e _ {\ ell} (x_ {1}, \ ldots, x_ {n}) t ^ {\ ell} \ prawo) \\ & = \ lewo (\ sum _ {{j = 1}} ^ { \ infty} p_ {j} (x_ {1}, \ ldots, x_ {n}) t ^ {j} \ prawo) \ lewo (\ sum _ {{\ ell = 0}} ^ {n} (- 1 ) ^ {{\ ell -1}} e _ {\ ell} (x_ {1}, \ ldots, x_ {n}) t ^ {\ ell} \ po prawej), \\\ end {wyrównany}}

gdzie wielomian po prawej został po raz pierwszy przepisany jako funkcja wymierna , wtedy ten rozwinął się w szereg formalny w t , a współczynniki każdego t j zgrupowane razem w celu uzyskania sumy potęg (zbieżność szeregu jest w rzeczywistości zapewniona dla t wystarczająco bliskiego zeru, ale ponieważ interesują nas tylko współczynniki t j , ta kwestia zbieżności nie ma realnego znaczenia). Porównując współczynniki t k dwóch elementów otrzymujemy

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

co jest k- tą tożsamością Newtona.

Jako teleskopowa suma tożsamości

Następujące wyprowadzenie jest sformułowane w pierścieniu wielomianów symetrycznych , ponieważ wtedy tożsamości nie zależą od liczby zmiennych. Dla ustalonego k > 0 definiujemy (dla 2 ≤ i ≤ k ) symetryczną funkcję r ( i ) jako sumę różnych jednomianów stopnia k uzyskanych przez pomnożenie zmiennej podniesionej do potęgi i przez k - i inne różne zmienne . W szczególności, r ( k ) = p k ; przypadek r (1) jest wykluczony, ponieważ jednomiany nie miałyby już zmiennej odgrywającej szczególną rolę. Wszystkie iloczyny p i e k - i można wyrazić w funkcji r ( j ) ( poza skrajnymi przypadkami i = 1 oraz i = k ). Otrzymujemy , ponieważ każdy iloczyn terminów po lewej stronie obejmujący różne zmienne przyczynia się do r ( i ), podczas gdy te, w których zmienne p i pojawiają się już wśród zmiennych odpowiedniego wyrazu e k - i przyczyniają się do r ( i + 1) oraz że wszystkie warunki po prawej stronie są w ten sposób uzyskane tylko raz. Dla i = k , mnożąc przez e 0 = 1, otrzymujemy trywialnie . Ostatecznie iloczyn p 1 e k −1 (odpowiadający i = 1) wnosi wkłady do r ( i + 1) = r (2) jak dla pozostałych wartości i < k , ale pozostałe wkłady są równe k razy każdy jednomian e k , ponieważ każda ze zmiennych może pochodzić z czynnika p 1 ; jak również . $p_ {i} e _ {{ki}} = r (i) + r (i + 1) \ quad {\ text {for}} 1 <i <k$ $p_ {k} e_ {0} = p_ {k} = r (k) \,$ $p_ {1} e_ {{k-1}} = ke_ {k} + r (2)$

K -tego tożsamości Newtona jest następnie otrzymuje się przez zsumowanie przemienne równań, który jest teleskopowa suma Wszystkie terminy formularza R ( I ) zniknie.

Podobne tożsamości

Istnieje wiele rodzin o podobnych tożsamościach i blisko spokrewnionych z tożsamościami Newtona.

Wykorzystanie całkowicie jednorodnych wielomianów symetrycznych

Stwierdzając wys K z całkowicie jednorodną wielomian symetryczny (en) , to znaczy sumę wszystkich jednomianów stopnia k , sumy potęg zaspokojenia tożsamości podobne do tych, Newton, ale których warunki są pozytywne. W pierścieniu wielomianów symetrycznych zapisuje się je dla wszystkich k ≥ 1. W przeciwieństwie do tożsamości Newtona, lewy element nie znika dla k wystarczająco dużego, a liczba niezerowych członów prawych elementów rośnie w nieskończoność. Dla pierwszych wartości k mamy $kh_ {k} = \ suma _ {{i = 1}} ^ {k} h _ {{ki}} p_ {i},$

{\ początek {wyrównany} 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 {wyrównany}}

Relacje te można wykazać za pomocą argumentu podobnego do podanego powyżej za pomocą szeregów formalnych, ale wykorzystując identyczność funkcji generujących :

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

Z drugiej strony, inne przedstawione wcześniej demonstracje nie mogą łatwo dostosować się do tych nowych tożsamości.

Wyrażanie elementarnych wielomianów symetrycznych w funkcji sum Newtona

Jak powiedzieliśmy, tożsamości Newtona pozwalają wyrazić przez indukcję elementarne wielomiany symetryczne w funkcji sum Newtona. Wymaga to dzielenia przez liczby całkowite i dlatego można to zrobić tylko w pierścieniu Λ Q wielomianów symetrycznych o współczynnikach wymiernych:

{\ displaystyle {\ begin {wyrównany} 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} -6 p_ {1} ^ {2} p_ {2} + 3 p_ {2} ^ {2} + 8 p_ {1} p_ { 3} -6p_ {4}), \\\ end {wyrównany}}}

I tak dalej. W przypadku wielomianu unitarnego wzory te wyrażają współczynniki jako funkcję sum potęg pierwiastków, zastępując każde e i przez a i oraz każde p k przez s k .

Wyrażenie całkowicie jednorodnych wielomianów symetrycznych w funkcji sum Newtona

Analogiczne relacje dotyczące całkowicie jednorodnych wielomianów symetrycznych rozwijają się w ten sam sposób, prowadząc do równań:

{\ displaystyle {\ begin {wyrównany} 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} + 6 p_ {1} ^ {2} p_ {2} + 3 p_ {2} ^ {2} + 8 p_ {1} p_ { 3} + 6p_ {4}), {\ tekst {itd.}} \\\ koniec {wyrównany}}}

gdzie wszystkie warunki są pozytywne. Wyrażenia te odpowiadają dokładnie wskaźnikom cykli wielomianów grup symetrycznych, interpretując sumy Newtona p i jako nieokreślone: współczynnik jednomianu p 1 m 1 p 2 m 2 … p l m l w wyrażeniu h k jest równy stosunkowi wszystkich permutacji k mających m 1 punktów stałych, m 2 cykli o długości 2,… i m l cykli o długości l . Dokładniej, współczynnik ten można zapisać $1 / N$ , z ; N to liczba permutacji ze stałą permutacją π o odpowiednim typie cyklu. Wyrażenia odpowiadające elementarnym funkcjom symetrycznym mają współczynniki mające te same wartości bezwzględne, ale znak równy sygnaturze π, czyli (−1) m 2 + m 4 +… . $N = \ Pi _ {{i = 1}} ^ {l} (m_ {i}! \, I ^ {{m_ {i}}})$

Wyrażenie sum Newtona

I odwrotnie, sumy Newtona możemy wyrazić jako funkcję elementarnych wielomianów symetrycznych, a te wyrażenia mają współczynniki całkowite:

{\ początek {wyrównany} 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} -12 e_ {3} e_ {2} e_ {1} -6 e_ {4} e_ {1} ^ {2} + 3 e_ {3 } ^ {2} + 6e_ {4} e_ {2} + 6e_ {1} e_ {5} -6e_ {6}, {\ tekst {itd.}} \\\ koniec {wyrównany}}

ale te wyrażenia nie wydają się podążać za wyraźną regułą. Widzimy jednak, że współczynnik jednomianu w wyrażeniu $p$ $k$ ma taki sam znak jak współczynnik odpowiedniego iloczynu w wyrażeniu $e$ $k$ podanym powyżej, tj. (−1) m 2 + m 4 +… . Co więcej, wartość bezwzględna współczynnika M jest sumą, przejętą przez zbiór ciągów elementarnych wielomianów symetrycznych, których iloczynem jest M , indeksu ostatniego wielomianu każdego ciągu: zatem współczynnik $e$ $1$ $5$ $e$ $3$ $e$ $4$ $3$ w wyrażeniu dającym p 20 jest , ponieważ wśród odrębnych rzędów pięciu czynników e 1 , jednego czynnika e 3 i trzech czynników e 4 , są 280 kończące się na e 1 , 56 kończące się na e 3 , a 168 kończące się na e 4 . $M = \ Pi _ {{i = 1}} ^ {l} e_ {i} ^ {{m_ {i}}}$ $\ Pi _ {{i = 1}} ^ {l} p_ {i} ^ {{m_ {i}}}$ $(-1) ^ {{0 + 3}} (280 \ razy 1 + 56 \ razy 3 + 168 \ razy 4) = - 1120$

Wreszcie tożsamości dotyczące całkowicie jednorodnych wielomianów można również odwrócić, prowadząc do:

{\ 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}, {\ tekst {itd.}} \\\ koniec {wyrównany} }

Te tożsamości mają dokładnie taką samą formę jak poprzednie, z wyjątkiem znaku: teraz znakiem jednomianu jest - (- 1) m 1 + m 2 + m 3 +… . $\ Pi _ {{i = 1}} ^ {l} h_ {i} ^ {{m_ {i}}}$

Wyrażenia jako wyznaczniki

Powyższe wyrażenia odpowiadające rozwiązywaniu układów równań liniowych można sformułować wprost za pomocą wyznaczników , stosując regułę Cramera . Na przykład pisanie tożsamości Newtona w postaci:

{\ begin {wyrównany} 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}, \\\ koniec {wyrównany}}

i biorąc , , , ... i jak nie wiadomo, dochodzimy do tego: $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}} \ koniec {vmatrix}}}} = {\ frac {1} {(- 1) ^ {{n-1}}}} { \ początek {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}} = {\ początek {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}}.

Obliczenia są analogiczne (ale nieco bardziej skomplikowane) dla , lub dla wyrażeń w funkcji całkowicie jednorodnych wielomianów symetrycznych; w końcu otrzymujemy: $w$

e_ {n} = {\ frac 1 {n!}} {\ początek {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} \ koniec {vmatrix}}, \ qquad p_ {n} = (- 1) ^ {{n-1}} {\ począ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}}.

Można zauważyć, że wzór na $h n jest$ otrzymana poprzez stałe matrycy o $e n$ zamiast jego determinantę, a bardziej ogólnie, że wyrażenie dowolnego wielomianu Schur może być otrzymana poprzez odpowiedni immanant tej matrycy.

Uwagi i referencje

(fr) Ten artykuł jest częściowo lub w całości zaczerpnięty z artykułu w angielskiej Wikipedii zatytułowanego " Tożsamości Newtona " ( zobacz listę autorów ) .

(en) L. Csanky , „ Szybkie algorytmy odwracania macierzy równoległych ” , SIAM J. Comput. , tom. 5, n O 4,grudzień 1976( przeczytaj online [PDF] ).
(w) DG Mead , „ Tożsamości Newtona ” , American Mathematical Monthly , Mathematical Association of America, tom. 99-8,1992, s. 749–751 ( DOI 10.2307 / 2324242 , JSTOR 2324242 ).
(w) Ian G. Macdonald , Funkcje symetryczne i wielomiany Halla , Oxford, Clarendon Press, Oxford University Press, coll. "Oksfordskie Monografie Matematyczne",1979, viii + 180 pkt. ( ISBN 0-19-853530-9 , Math Reviews 84g: 05003 ) , s. 20.
(w) Dudley E. Littlewood , Teoria znaków grupowych i macierzowe reprezentacje grup , Oxford, Oxford University Press ,1950, viii + 310 pkt. ( ISBN 0-8218-4067-3 ) , s. 84.

Zobacz również

Powiązane artykuły

Odwrotny wielomian
Symetryczny wskaźnik cyklu grupowego
Płynne rozwiązanie (w) , artykuł przedstawiający zastosowanie tożsamości Newtona do obliczenia wielomianu charakterystycznego tensora Einsteina w przypadku płynu doskonałego

Bibliografia

(en) Jean-Pierre Tignol, Teoria równań algebraicznych Galois , Singapur, World Scientific ,2001, 333 pkt. ( ISBN 978-981-02-4541-2 , czytaj online )
(en) F. Bergeron, G. Labelle i P. Leroux, Gatunki kombinatoryczne i struktury drzewiaste , Cambridge, Cambridge University Press ,1998, 457 s. ( ISBN 978-0-521-57323-8 , czytaj online )
(en) Peter J. Cameron , Permutation Groups , Cambridge, Cambridge University Press ,1999, 220 pkt. ( ISBN 978-0-521-65378-7 , czytaj online )
(en) David A. Cox , John Little et Don O'Shea , Ideas, Varieties and Algorithms: wprowadzenie do obliczeniowej geometrii algebraicznej i algebry przemiennej , New York, Springer-Verlag ,2007, 3 e wyd. ( ISBN 978-0-387-35651-8 , czytaj online )
(en) David Eppstein i Michael T. Goodrich (en) , „Space-efficient straggler identity in round-trip data streams via tożsamości Newtona i odwracalne filtry Blooma” , w Algorithms and Data Structures , 10th International Workshop, WADS 2007 , Springer , płk. "Lecture Notes in Computer Science" ( n O 4619),2007, s. 637-648, „ 0704.3313 ” , tekst o swobodnym dostępie, na arXiv .
(en) IG Macdonald , Funkcje symetryczne i wielomiany Halla , Nowy Jork, Oxford Science Publications. Clarendon Press, Oxford University Press, coll. "Oksfordskie Monografie Matematyczne",1995, wyd. drugie . ( ISBN 0-19-853489-2 , Math Reviews 96h: 05207 ) , x + 475
(en) Richard P. Stanley , Enumeratywna Kombinatoryka , tom. 2 [ szczegóły wydań ] ( prezentacja online )
(pl) Bernd Sturmfels , Algorytmy w teorii niezmienności , New York, Springer-Verlag ,1992( ISBN 978-0-387-82445-1 )
(pl) Alan Tucker, Applied Combinatorics , Nowy Jork, Wiley ,1980, wyd. , 476 s. ( ISBN 978-0-471-73507-6 )

Linki zewnętrzne

(en) Eric W. Weisstein , „ Formuły Newtona-Girarda ” , o MathWorld
(pl) Matrycowy dowód tożsamości Newtona w magazynie matematycznym
(pl) Pablo A Parrilo ( MIT ), Aplikacja na liczbę prawdziwych korzeni