Newtons identiteter

I matematik , og mere specifikt i algebra , er Newtons identiteter (også kendt som Newton-Girard-formler ) forhold mellem to typer symmetriske polynomer , elementære symmetriske polynomer og Newtons summer , det vil sige summen af ubestemte kræfter dem. Evalueret ved rødderne af et polynom P med en variabel tillader disse identiteter at udtrykke summen af k- th- kræfterne for alle rødderne af P(tælles med deres mangfoldighed) som en funktion af koefficienterne for P , uden at det er nødvendigt at bestemme disse rødder. Disse formler blev genopdaget af Isaac Newton omkring 1666, tilsyneladende uden at have haft kendskab til Albert Girards analoge arbejde i 1629. De har anvendelser inden for mange matematiske områder, såsom teorien om Galois , teorien om invariantere , teorien om grupper , kombinatorik , og endda inden for ikke-matematiske områder, såsom i generel relativitet .

Matematisk erklæring

Formulering i henhold til symmetriske polynomer

Lad $x 1 , ..., x n være$ variabler; for ethvert ikke-nul naturligt tal k betegner vi med $p k ( x 1 , ..., x n )$ summen af kræfterne $k-$ ths:

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

(kaldet Newtons sum )

og for $k \geq 0$ betegner vi ved $e k ( x 1 , ..., x n )$ det elementære symmetriske polynom, som er summen af de forskellige produkter af k forskellige variabler blandt n ; så især

{\ displaystyle {\ begin {align} 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 \ limits _ {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. \\\ ende {justeret}}}

De identiteter Newton derefter skrives:

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}),

ægte forhold til alt . Vi opnår således for de første værdier af k : $k \ in \ mathbb {N} ^ {*}$

{\ begin {align} 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}). \\\ slut {justeret}}

Formen på disse relationer afhænger ikke af antallet n af variabler (men venstre side bliver nul efter den nende identitet), hvilket gør det muligt for dem at blive angivet som identiteter i ringen af symmetriske polynomer . I denne ring har vi:

{\ begin {align} 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}, \\\ ende {justeret}}

Og så videre ; i dette tilfælde annulleres venstre side aldrig.

Disse ligninger tillader $e jeg$ skal udtrykkes ved induktion som funktion af $p k$ ; omvendt, omskrive dem som:

{\ begin {align} 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 {osv.}} \\\ ende {justeret}}

vi kan udtrykke p i som en funktion af e k .

Anvendelse på rødderne af et polynom

Den $x jeg$ bliver taget som parametre og ikke som variabler, lad os overveje enhed polynomium ved $t$ have til rødderne $x 1 , ..., x n$ :

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

hvor koefficienterne $a k$ er givet af de elementære symmetriske polynomier af rødderne: $a k = e k ( x 1 ,\dots, x n )$ . Summen af røddernes kræfter (som vi også kalder Newtonsummer ) kan derefter udtrykkes som en funktion af polynomets koefficienter ved at anvende Newtons identiteter trin for trin: $s_ {k} = p_ {k} (x_ {1}, \ ldots, x_ {n}) = \ sum _ {{i = 1}} ^ {n} x_ {i} ^ {k},$

{\ begin {align} 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 {osv.}} \\\ ende {justeret}}

Anvendelse på det karakteristiske polynom af en matrix

Når polynomium af det foregående afsnit er det karakteristiske polynomium af en matrix A , rødderne $x jeg$ er egenværdier af A (tælles med deres algebraisk multiplicitet). For ethvert heltal k har matrixen A k for egenværdier $x k i$ (med de tilsvarende multiplikationer). Koefficienterne for det karakteristiske polynomium af A k er givet ved de elementære symmetriske polynomier i disse beføjelser $x k i$ . Især summen af $x k i$ er givet ved spor af A k : $s k = tr ( A k )$ .

Newtons identiteter så forbinde fodsporene på en k koefficienterne i det karakteristiske polynomium A . Omvendt bruger dem til at beregne de elementære symmetriske polynomier fra summerne af beføjelser, de derfor gøre det muligt at bestemme det karakteristiske polynomium af A ved at beregne kun de beføjelser A og deres spor, og derefter ved at løse en trekantet ligningssystem. Den Cayley-Hamilton teorem tillader derefter simpelthen at fratrække den inverse matrix af A .

Alle disse beregninger (omskrevet i en effektiv form) udgør algoritmen Faddeev-Leverrier , der stammer fra 1840; en hurtig parallel implementering af denne algoritme skyldes Lazslo Csanky i 1976. Det kræver dog opdelinger (ved heltal) og kan derfor generelt kun bruges i felter med karakteristisk 0. Implementeringen af Csanky viser, at disse forskellige beregninger er ( i dette tilfælde) i NC-kompleksitetsklassen .

Forhold til Galois teori

For en given n danner de elementære symmetriske polynomer $e k ( x 1 ,\dots, x n )$ for k = 1,…, n et “ algebraisk grundlag ” for kommutativ algebra for symmetriske polynomer ved $x 1 , ..., x n$ , det vil sige, at ethvert symmetrisk polynom udtrykkes som en polynomfunktion af disse elementære symmetriske polynomier, og at dette udtryk er unikt. Dette generelle resultat, kendt under navnet den grundlæggende sætning af symmetriske polynomer , kan gøres eksplicit (ved hjælp af Newtons identiteter) i tilfælde af Newtons summer. Således anvendes det til enhedspolynomet, hvis koefficienter $a$ $k$ betragtes som parametre, at enhver polynomefunktion $S$ $($ $x$ $1$ $,\dots,$ $x$ $n$ $)$ af dens rødder kan skrives som en polynomfunktion $P$ $($ $a$ $1$ $,\dots,$ $a$ $n$ $)$ af dets koefficienter alene, det vil sige uden at det er nødvendigt at beregne disse rødder. Dette kan også udledes af Galois-teorien ved at se $a$ $k$ som elementer i et basisfelt; rødderne er derefter i en udvidelse af dette felt, og Galois-gruppen i denne udvidelse tillader dem i henhold til hele den symmetriske gruppe; feltet invariant af alle elementerne i denne Galois-gruppe er basisfeltet. $\ textstyle t ^ {n} + \ sum _ {{k = 1}} ^ {n} (- 1) ^ {{k}} a_ {k} t ^ {{nk}}$

Omvendt tillader Newtons identiteter os at udtrykke elementære symmetriske polynomer som en funktion af Newtons summer og demonstrere, at disse summer også danner et ”algebraisk grundlag” for den kommutative algebra af symmetriske polynomer.

Demonstrationer

Hver identitet kan verificeres direkte ved en simpel algebraisk beregning, men det generelle tilfælde kræver en demonstration. Her er nogle mulige veje:

Fra specialtilfældet n = k

Den k 'te Newtons identitet i k variabler opnås ved substitution i formel definerer $e k$ :

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

Ved at erstatte x j for t har vi:

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

Sammenfattende over sættet med j får vi:

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

(Udtrykkene ved i = 0 er adskilt fra summen, fordi p 0 normalt ikke er defineret.)

Denne ligning giver straks den efterspurgte identitet. Identiteterne svarende til n < k variabler udledes ved at annullere de resterende k - n variabler; tilfældet hvor n > k behandles ved at bemærke, at hvert monomium ikke indeholder mere end k variabler, og at dette monomium ikke ændres, hvis vi annullerer n - k andre variabler; det er så nok at bruge identiteten af Newton svarende til disse k- variabler.

Ved identifikation af formelle serier

Newtons identiteter kan også opnås ved hjælp af formelle identitetsbaserede manipulationer

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

forbinder rødderne og koefficienterne for en enhedspolynom. For at lette beregningerne starter vi med at erstatte 1 / t for t , og vi ganger de to medlemmer med t n , hvor vi opnår:

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

Ved at erstatte a i med de symmetriske polynomer får vi identiteten

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

Efter differentiering med hensyn til t og multiplikation med t kommer det:

{\ begin {align} \ 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) \ højre) \\ & = - \ venstre (\ sum _ {{i = 1}} ^ {n} {\ frac {x_ {i} t} {1-x_ {i} t}} \ højre) \ prod \ nolimits _ {{j = 1}} ^ {n} (1-x_ {j} t) \\ & = - \ left (\ sum _ {{i = 1}} ^ {n} \ sum _ {{j = 1}} ^ {\ infty} (x_ {i} t) ^ {j} \ højre) \ left (\ 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} \ højre), \\\ ende {justeret}}

hvor polynomet til højre først blev omskrevet som en rationel funktion , udviklede denne sig til en formel serie ved t , og koefficienterne for hver t j blev samlet for at opnå en sum af kræfter (konvergensen af serien er faktisk sikret for t tæt nok på nul, men da vi kun er interesserede i koefficienterne for t j , har dette spørgsmål om konvergens ingen reel betydning). Sammenligning af koefficienterne for t k for de to medlemmer får vi

(-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})

som er Newtons kende identitet.

Som en teleskopisk sum af identiteter

Den følgende afledning er formuleret i ringen af symmetriske polynomer , for da afhænger identiteterne ikke af antallet af variabler. For en fast k > 0 definerer vi (for 2 ≤ i ≤ k ) den symmetriske funktion r ( i ) som summen af de forskellige monomier af grad k opnået ved at multiplicere en variabel hævet til effekten i med k - i andre forskellige variabler. Især er r ( k ) = p k ; sagen r (1) er udelukket, fordi monomierne ikke længere ville have en variabel, der spiller en særlig rolle. Alle produkterne p i e k - i kan udtrykkes som en funktion af r ( j ) ( bortset fra de ekstreme tilfælde i = 1 og i = k ). Vi får , da hvert produkt af de vilkår på de venstre involverer forskellige variabler bidrager til r ( i ), mens de, hvor de variable af p jeg allerede vises blandt variablerne i tilsvarende periode af e k - jeg bidrager til r ( jeg + 1), og at alle vilkårene til højre således opnås en og kun en gang. For i = k , ved at gange med e 0 = 1, får vi trivielt . Endelig bringer produktet p 1 e k −1 (svarende til i = 1) bidrag til r ( i + 1) = r (2) som for de andre værdier af i < k , men de resterende bidrag er lig med k gange hvert monomium af e k , da hver af variablerne kan komme fra faktoren p 1 ; også . $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)$

Den k- th Newtons identitet opnås derefter ved at tage den alternerende sum af ligningerne, som er en teleskopisk sum. Alle vilkår for formen r ( i ) forsvinder.

Lignende identiteter

Der findes mange familier med lignende identiteter og tæt knyttet til Newtons identiteter.

Brug af fuldstændigt homogene symmetriske polynomer

Under bemærkning af h k det fuldstændig homogene symmetriske polynom (en) , det vil sige summen af alle monomier af grad k , tilføjer summen af kræfter identiteter svarende til Newtons, men hvis vilkår er alle positive. I ringen af symmetriske polynomer er de skrevet for alle k ≥ 1. I modsætning til Newtons identiteter forsvinder det venstre medlem ikke for k stort nok, og antallet af ikke-nul-termer for de rigtige medlemmer vokser på ubestemt tid. For de første værdier af k har vi $kh_ {k} = \ sum _ {{i = 1}} ^ {k} h _ {{ki}} p_ {i},$

{\ begin {align} h_ {1} & = p_ {1}, \\ 2h_ {2} & = h_ {1} p_ {1} + p_ {2}, \\ 3h_ {3} & = h_ {2 } p_ {1} + h_ {1} p_ {2} + p_ {3}. \\\ ende {justeret}}

Disse forhold kan demonstreres ved et argument svarende til det ovenstående ved hjælp af formelle serier, men ved hjælp af identiteten mellem genererende funktioner :

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

På den anden side kan de andre tidligere demonstrationer ikke let tilpasse sig disse nye identiteter.

Ekspression af elementære symmetriske polynomer som en funktion af Newton-summer

Som vi sagde tillader identiteten af Newton at udtrykke ved induktion de elementære symmetriske polynomer som en funktion af Newtons summer. Dette kræver division med heltal og kan derfor kun udføres i ringen Λ Q af symmetriske polynomer med rationelle koefficienter:

{\ displaystyle {\ begin {align} 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}), \\\ ende {justeret}}}

Og så videre. For et enhedspolynom udtrykker disse formler koefficienterne som en funktion af summen af røddernes kræfter ved at erstatte hver e i med a i og hver p k med s k .

Ekspression af fuldstændig homogene symmetriske polynomer som en funktion af Newton-summer

Analoge relationer vedrørende fuldstændig homogene symmetriske polynomer udvikler sig på samme måde, hvilket fører til ligningerne:

{\ displaystyle {\ begin {align} 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 {osv.}} \\\ ende {justeret}}}

hvor alle vilkår er positive. Disse udtryk svarer nøjagtigt til de indikatorer for cyklusser af polynomier af symmetriske grupper, ved at fortolke Newton summer p i som indeterminates: koefficienten af en monomial p 1 m 1 s 2 m 2 ... p l m l i ekspressionen af h k er lig med den del af alle permutationer af k med m 1 fixpunkter, m 2 cykler af længde 2, ..., og m l cykler af længde l . Mere præcist kan denne koefficient skrives $1 / N$ med ; N er antallet af permutationer med en fast permutation π med den tilsvarende cyklustype. Udtrykkene, der svarer til de elementære symmetriske funktioner, har koefficienter med de samme absolutte værdier, men et tegn svarende til signaturen af π, det vil sige til (-1) m 2 + m 4 +… . $N = \ Pi _ {{i = 1}} ^ {l} (m_ {i}! \, I ^ {{m_ {i}}})$

Ekspression af Newton-summer

Omvendt kan vi udtrykke Newtons summer som en funktion af elementære symmetriske polynomer, og disse udtryk har heltalskoefficienter:

{\ begin {align} 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 {osv.}} \\\ ende {justeret}}

men disse udtryk ser ikke ud til at følge en eksplicit regel. Vi ser imidlertid, at koefficienten for et monomial i udtrykket af $p$ $k$ har det samme tegn som koefficienten for det tilsvarende produkt i ekspressionen af $e$ $k$ givet ovenfor, dvs. (-1) m 2 + m 4 +… . Desuden er den absolutte værdi af koefficienten M summen, der er taget over sæt af sekvenser af elementære symmetriske polynomer, hvis produkt er M , af indekset for det sidste polynom i hver sekvens: således er koefficienten for $e$ $1$ $5$ $e$ $3$ $e$ $4$ $3$ i udtrykket, der giver p 20, er , da der blandt de forskellige ordrer af fem faktorer e 1 , en faktor e 3 og tre faktorer e 4 er 280, der slutter med e 1 , 56, der slutter med e 3 og 168, der slutter med e 4 . $M = \ Pi _ {{i = 1}} ^ {l} e_ {i} ^ {{m_ {i}}}$ $\ Pi _ {{i = 1}} ^ {l} p_ {i} ^ {{m_ {i}}}$ $(-1) ^ {{0 + 3}} (280 \ gange 1 + 56 \ gange 3 + 168 \ gange 4) = - 1120$

Endelig kan identiteterne vedrørende fuldstændig homogene polynomer også vendes, hvilket fører til:

{\ begin {align} 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} + 5t_ {2} ^ {2} h_ {1} + 5t_ {3} h_ {1} ^ {2} -5t_ {3} h_ {2} -5t_ {4} h_ {1 } + 5 t_ {5}, \\ p_ {6} & = - h_ {1} ^ {6} + 6 t_ {2} h_ {1} ^ {4} -9 t_ {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 {osv.}} \\\ ende {justeret} }

Disse identiteter har nøjagtig den samme form som de foregående, bortset fra tegnet: monomialets tegn er nu - (- 1) m 1 + m 2 + m 3 +… . $\ Pi _ {{i = 1}} ^ {l} h_ {i} ^ {{m_ {i}}}$

Udtryk som determinanter

De foregående udtryk, der svarer til løsningen af systemer med lineære ligninger, kan formuleres eksplicit ved hjælp af determinanter ved hjælp af Cramer's regel . For eksempel at skrive Newtons identiteter i form:

{\ begin {align} 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}, \\\ ende {justeret}}

og tager , , , ..., og som ukendte, får vi at det: $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}} \ slut {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}} = {\ start {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}}.

Beregningerne er analoge (men lidt mere komplicerede) for eller til udtryk som en funktion af fuldstændig homogene symmetriske polynomer; vi får endelig: $i$

e_ {n} = {\ frac 1 {n!}} {\ begynder {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}} {\ begin {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 && \ prikker & \ prikker \\ p _ {{n-1}} & p _ {{n-2}} & \ cdots & p_ {1} & 1-n \\ p_ {n} & p_ {{n-1 }} & \ cdots & p_ {2} & p_ {1} \ end {vmatrix}}.

Vi kan bemærke, at formlen for $h n$ opnås ved at tage matrixens permanente for $e n i$ stedet for dens determinant, og mere generelt, at et udtryk for ethvert Schur-polynom kan opnås ved at tage den tilsvarende immanant af denne matrix.

Noter og referencer

(fr) Denne artikel er helt eller delvist hentet fra den engelske Wikipedia- artikel med titlen " Newtons identiteter " ( se listen over forfattere ) .

(en) L. Csanky , " Fast Parallel matrix inversion algoritmer " , SIAM J. Comput. , Vol. 5, nr . 4,December 1976( læs online [PDF] ).
(in) DG Mead , " Newtons identiteter " , American Mathematical Monthly , Mathematical Association of America, bind. 99-8,1992, s. 749–751 ( DOI 10.2307 / 2324242 , JSTOR 2324242 ).
(i) Ian G. Macdonald , Symmetriske funktioner og Hall polynomier , Oxford, Clarendon Press, Oxford University Press, coll. "Oxford matematiske monografier",1979, viii + 180 s. ( ISBN 0-19-853530-9 , Matematiske anmeldelser 84g: 05003 ) , s. 20.
(in) Dudley E. Littlewood , teorien om gruppekarakterer og matrixrepræsentationer af grupper , Oxford, Oxford University Press ,1950, viii + 310 s. ( ISBN 0-8218-4067-3 ) , s. 84.

Se også

Relaterede artikler

Omvendt polynom
Symmetrisk gruppecyklusindikator
Væskeopløsning (in) , artikel, der giver en anvendelse af Newtons identiteter til at beregne det karakteristiske polynom af Einstein-tensoren i tilfælde af en perfekt væske

Bibliografi

(en) Jean-Pierre Tignol, Galois 'teori om algebraiske ligninger , Singapore, World Scientific ,2001, 333 s. ( ISBN 978-981-02-4541-2 , læs online )
(en) F. Bergeron, G. Labelle og P. Leroux, kombinatoriske arter og trælignende strukturer , Cambridge, Cambridge University Press ,1998, 457 s. ( ISBN 978-0-521-57323-8 , læs online )
(en) Peter J. Cameron , Permutationsgrupper , Cambridge, Cambridge University Press ,1999, 220 s. ( ISBN 978-0-521-65378-7 , læs online )
(da) David A. Cox , John Little et Don O'Shea , Idealer, Varianter og Algoritmer: en introduktion til beregningsalgebraisk geometri og kommutativ algebra , New York, Springer-Verlag ,2007, 3 e ed. ( ISBN 978-0-387-35651-8 , læs online )
(en) David Eppstein og Michael T. Goodrich (en) , "Rumeffektiv straggler-identifikation i rundstrømsdatastrømme via Newtons identiteter og invertible Bloom-filtre" , i algoritmer og datastrukturer , 10. internationale værksted, WADS 2007 , Springer , coll. "Forelæsningsnotater i datalogi" ( nr . 4619),2007, s. 637-648, “ 0704.3313 ” , fri adgangstekst, på arXiv .
(da) IG Macdonald , symmetriske funktioner og Hall polynomier , New York, Oxford Science Publications. The Clarendon Press, Oxford University Press, koll. "Matematiske monografier i Oxford",1995Anden udgave ( ISBN 0-19-853489-2 , matematiske anmeldelser 96h: 05207 ) , x + 475
(en) Richard P. Stanley , Enumerative Combinatorics , vol. 2 [ detaljer af udgaver ] ( online præsentation )
(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 ,19805. udgave , 476 s. ( ISBN 978-0-471-73507-6 )

eksterne links

(da) Eric W. Weisstein , “ Newton-Girard Formulas ” , på MathWorld
(da) Et matrixbevis for Newtons identiteter i Mathematics Magazine
(da) Pablo A Parrilo ( MIT ), Ansøgning om antallet af virkelige rødder