A matematikában a Newton-azonosságok , más néven Newton-Girard-képletek , kétféle szimmetrikus polinom között határoznak meg kapcsolatokat , nevezetesen az elemi szimmetrikus polinomok és a Newton-hatványösszegek között. Egy tetszőleges P polinom esetén lehetővé teszik P összes gyökének k -edik hatványainak összegét (a multiplicitás figyelembevételével) P együtthatóival kifejezve anélkül, hogy ténylegesen megtalálnánk a gyököket. Ezeket az azonosságokat Isaac Newton fedezte fel 1666 körül, és valószínűleg Albert Girard korai munkájában (1629) . A matematika számos területén alkalmazhatók, beleértve a Galois -elméletet , az invariáns elméletet , a csoportelméletet , a kombinatorikát , valamint más tudományokat, beleértve az általános relativitáselméletet is .
Változók esetén , és vegye figyelembe e változók -edik hatványainak összegét :
Jelöljük elemi szimmetrikus polinomokkal is . A polinom a különböző változók összes lehetséges szorzatának összege , különösen
Ekkor Newton azonosságai a következőképpen írhatók fel:
mindenkinek . Különösen azért
Az első néhány értéknél a következőket kapjuk:
Ezeknek az azonosságoknak az igazsága nem függ a változók számától, még akkor sem, ha a bal és a jobb oldal nullával egyenlő. Ezek az egyenlőségek lehetővé teszik számunkra, hogy rekurzív módon fejezzük ki :
A Newton-azonosságok mindegyike ellenőrizhető elemi algebrai műveletekkel, de az általános képlet bizonyítást igényel. Az identitások származtatásának számos különböző módja van.
Az alábbiakban a változók számát jelöljük , az azonosító számot (a jobb oldali összegben szereplő tagok számát) pedig -vel .
Definíció szerint,
Ezért nekünk van
Mindent összegezve azt kapjuk
Ez a kifejezés azonnal magában foglalja a változók Newton -edik azonosságát . Mert ez egy azonosság szimmetrikus homogén polinomok között .
Ebből a tényből minden következik. A számára az azonosság nyilvánvalóan a for azonosságban szereplő hozzárendelésből következik
Most engedd . Jelölje az identitás bal és jobb oldalát. Az azonosság teljesüléséből a -nál az következik, hogy
Ebből azonban az következik, hogy a különbség bármelyikre ábrázolható formában (ha nem, akkor egyeseknél a különbség nullától eltérő lenne, és a fent jelzett egyenlőségek egyike nem állna fenn). Ezért a különbséget ábrázolhatjuk így is , de ez lehetetlen, mert és és teljes hatványa egyenlő -val .
Hasonló érvek induktív átmenetet adnak, és azonosságot bizonyítanak egy tetszőleges .
A zárójelek közvetlen kinyitásával ezt megkaphatja
Jelölve azt kapjuk .
Formálisan differenciálva (származékot véve) és mindkét részt megszorozva -val , megkapjuk
Mivel a polinomok azonos egyenlősége magában foglalja az összes együttható egyenlőségét, akkor a polinomok szorzásának szabályai szerint ez közvetlenül azt jelenti, hogy
Néhányat javítsanak ki . Jelölje az összes olyan monom összegét , amely különböző változókból áll, amelyek közül az egyik a monomiban benne van a fokozattal , a többi pedig az 1-es fokozattal. Az ilyen monomok természetesen előfordulnak a szorzatban (a fokozatú változók a polinomból származnak , a többi pedig monomiálisan szerepel az első fokozattal - tól ).
Pontosabban, a következő személyazonosságok könnyen ellenőrizhetők:
Az első sajátossága durván szólva abból adódik, hogy egy monom esetében egyértelműen egyértelmű, hogy melyik változóból és melyik -ből származik , így minden ilyen polinom együtthatóval szerepel a szorzatban . Ebben az esetben a polinom pontosan egyszer fordul elő a szorzatban - mivel az egyik változó minden lehetséges szorzata a monom többi részével: . Ez adja az együtthatót
A fenti identitásokból könnyen kivehető az
A kifejezést explicit módon kiterjesztve a -n keresztül , megkapjuk a reprezentációkat
Az általános képlet átírható így is
hol van a Bell polinom . Egy ilyen ábrázolás különösen a következő generáló függvények azonosságához vezet:
Hasonlóképpen, a rekurziós kifejezések közvetlen kiterjesztésével ezt kaphatjuk meg
Az első négy képletet Albert Girard szerezte meg Newton előtt, 1629-ben. Az általános képlet a következő:
Ez újrafogalmazható Bell-polinomokkal:
A gyököket tartalmazó polinom a következőképpen ábrázolható
,ahol az együtthatók a fent definiált szimmetrikus polinomok. A hatványösszeg ismert értékeihez a polinom együtthatói rekurzív képletekből kereshetők.
A Newton-azonosságok lehetővé teszik, hogy egy mátrix karakterisztikus polinomjának együtthatóinak számítását a különböző hatványainak nyomkövetésére redukáljuk.
Tekintsük valamely mátrix karakterisztikus polinomját . Gyökei ennek a mátrixnak a sajátértékei ( mindegyik gyökér a saját multiplicitásával van ábrázolva). Ekkor a karakterisztikus polinom együtthatóit szimmetrikus polinomokban fejezzük ki .
Bármely pozitív esetén a mátrix sajátértékei a hatványai . Mivel egy mátrix sajátértékeinek összege egyenlő a nyomával , akkor
Ezért, és , és a karakterisztikus polinom együtthatói lineárisan fejezhetők ki -ból . A polinom együtthatóinak kiszámítása így két lépésre csökken:
Mindkét fokozat az NC komplexitási osztályba tartozik , így a karakterisztikus polinom együtthatóinak megtalálása is az NC osztályhoz tartozik. A Fadeev-Leverrier algoritmus (1840) ezen az elgondoláson alapul .
Mivel a Hamilton-Cayley-tétel szerint bármely mátrix a karakterisztikus polinom gyökere, akkor ennek a polinomnak az együtthatóinak gyors kiszámítása gyors módot ad az inverz mátrix megtalálására.
A Newton-azonosságok felhasználhatók a racionális trigonometrikus összegek modulo prím becslésére, hogy egyedileg megtaláljuk a Vinogradov-integrál egy speciális esetét azonos számú változóval és egyenlettel.