Newton identitását

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 .

Személyazonossági nyilatkozat

Változók esetén , és vegye figyelembe e változók -edik hatványainak összegét : $x_1,\pontok,x_n$ $k\geq 1$ $k$

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

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 $e_{k}(x_{1},\dots ,x_{n})$ $e_{k}(x_{1},\dots ,x_{n})$ $k$

{\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 _{1 \leq i<j\leq n}x_{i}x_{j},\\&{}\ \ \vdots \\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{igazított}}

Ekkor Newton azonosságai a következőképpen írhatók fel:

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

mindenkinek . Különösen azért $k\geq 1$ $k>n\geq 1$

0=\sum _{i=kn}^{k}(-1)^{i-1}e_{ki}(x_{1},\ldots ,x_{n})p_{i}( x_{1},\ldots ,x_{n}),

Az első néhány értéknél a következőket kapjuk: $k$

{\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},\lpontok ,x_{n})+p_{3}(x_{1},\lpontok ,x_{n}).\\\end{igazított}}

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 : $p_{i}$ $e_{i}$

{\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},\\&{}\ \ \vdots \end{aligned}}

Bizonyítási módszerek

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 . $n$ $k$

Egy speciális eseten keresztül $k=n$

Definíció szerint, $\prod _{i=1}^{k}(t-x_{i})=\sum _{i=0}^{k}(-1)^{ki}e_{ki}(x_ {1},\ldots ,x_{k})t^{i}$

Ezért nekünk van ${\displaystyle t=x_{j))$

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

Mindent összegezve azt kapjuk $j$

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

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 . $k$ $k$

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 $n<k$ $x_{n+1}=x_{n+2}=\pontok =x_{k}=0$ $n=k$

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 $n=k+1$ $f(x_{1},\dots ,x_{n})$ $g(x_{1},\dots ,x_{n})$ $n=k$

{\begin{aligned}&f(0,x_{2},\dots ,x_{k},x_{k+1})=g(0,x_{2},\dots ,x_{k} ,x_{k+1})\\&f(x_{1},0,\pontok ,x_{k},x_{k+1})=g(x_{1},0,\pontok ,x_{k },x_{k+1})\\&\dots \\&f(x_{1},x_{2},\dots ,0,x_{k+1})=g(x_{1},x_{ 2},\pontok ,0,x_{k+1})\\&f(x_{1},x_{2},\pontok ,x_{k},0)=g(x_{1},x_{2 },\pontok ,x_{k},0)\end{igazított}}

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 . $fg$ ${\displaystyle h(x_{1},\dots ,x_{n})x_{i))$ $én$ ${\displaystyle x_{1},\dots ,x_{i-1},x_{i+1},\dots ,x_{k+1))$ $fg$ ${\displaystyle h(x_{1},\dots ,x_{n})x_{1}x_{2}\dots x_{k}x_{k+1))$ $f$ $g$ $k$

Hasonló érvek induktív átmenetet adnak, és azonosságot bizonyítanak egy tetszőleges . $n>k+1$ $n$

Formális hatványsorokon keresztül

A zárójelek közvetlen kinyitásával ezt megkaphatja

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

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

Jelölve azt kapjuk . $s={\frac {1}{t))$ $\prod _{i=1}^{n}(1-x_{i}s)=\sum _{k=0}^{n}(-1)^{k}e_{k}( x_{1},\pontok ,x_{n})s^{k}$

Formálisan differenciálva (származékot véve) és mindkét részt megszorozva -val , megkapjuk $s$ $s$

{\begin{aligned}\sum _{k=0}^{n}(-1)^{k}ke_{k}(x_{1},\ldots ,x_{n})s^{ k}&=s\sum _{i=1}^{n}\left[(-x_{i})\prod \nolimits _{j\neq i}(1-x_{j}s)\right] \\&=-\left(\sum _{i=1}^{n}{\frac {x_{i}s}{1-x_{i}s}}\right)\prod \nolimits _{j =1}^{n}(1-x_{j}s)\\&=-\left[\sum _{i=1}^{n}\sum _{j=1}^{\infty }( x_{i}s)^{j}\jobbra]\left[\sum _{\ell =0}^{n}(-1)^{\ell }e_{\ell }(x_{1},\ ldots ,x_{n})s^{\ell }\right]\\&=\left[\sum _{j=1}^{\infty }p_{j}(x_{1},\ldots ,x_ {n})s^{j}\jobbra]\left[\sum _{\ell =0}^{n}(-1)^{\ell -1}e_{\ell }(x_{1}, \ldots ,x_{n})s^{\ell }\right],\\\end{igazított}}

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

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

A teleszkópos tartományon keresztül

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 ). $k\geq 1$ $r_{i}^{(k)}(x_{1},\pontok ,x_{n})$ $k$ $én$ $p_{i}(x_{1},\pontok ,x_{n})e_{ki}(x_{1},\pontok ,x_{n})$ $én$ $p_{i}$ ${\displaystyle e_{ki))$

Pontosabban, a következő személyazonosságok könnyen ellenőrizhetők:

{\begin{aligned}&p_{1}e_{k-1}=ke_{k}+r_{2}^{(k)}\\&p_{i}e_{ki}=r_{i} ^{(k)}+r_{i+1}^{(k)},&1<i<k\\&p_{k}e_{0}=p_{k}=r_{k}^{(k) }\end{igazított}}

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 $i\geq 2$ ${\displaystyle x_{0}^{i}x_{1}\dots x_{ki))$ $p_{i}$ ${\displaystyle e_{ki))$ ${\displaystyle p_{i}e_{ki))$ $egy$ $i=1$ ${\displaystyle x_{1},\dots ,x_{k))$ ${\displaystyle p_{1}e_{k-1))$ $k$ $x_{1}x_{2}\dots x_{k-1}x_{k}=x_{1}\cdot x_{2}x_{3}\dots x_{k-1}x_{k} =x_{2}\cdot x_{1}x_{3}\pontok x_{k-1}x_{k}=\pontok =x_{k}\cdot x_{1}x_{2}\pontok x_{k -2}x_{k-1}$ $k$ $e_{k}$

A fenti identitásokból könnyen kivehető az

{\begin{aligned}&p_{1}e_{k-1}-p_{2}e_{k-2}+\dots +(-1)^{k-1}p_{k}=\ \&=ke_{k}+r_{2}^{(k)}-\left({r_{2}^{(k)}+r_{3}^{(k)}}\jobbra)+\ bal({r_{3}^{(k)}+r_{4}^{(k)}}\jobbra)-\pontok +(-1)^{k}r_{k}^{(k)} =\\&=ke_{k}+r_{2}^{(k)}-r_{2}^{(k)}-r_{3}^{(k)}+r_{3}^{( k)}+r_{4}^{(k)}-r_{4}^{(k)}\pontok +(-1)^{k-1}r_{k}^{(k)}+( -1)^{k}r_{k}^{(k)}=\\&=ke_{k}\\\end{igazított}}

Kapcsolódó identitások

Elemi szimmetrikus polinomok közvetlen ábrázolása hatványösszegekkel

A kifejezést explicit módon kiterjesztve a -n keresztül , megkapjuk a reprezentációkat $e_{i}$ $p_{i}$

{\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}),\\&~~\vdots \\e_{n}&=(-1)^{n}\sum _{m_{1}+2m_{2}+\cdots +nm_ {n}=n \atop m_{1}\geq 0,\ldots ,m_{n}\geq 0}\prod _{i=1}^{n}{\frac {(-p_{i})^ {m_{i}}}{m_{i}!i^{m_{i}}}}\\\end{aligned}}

Az általános képlet átírható így is

e_{n}={\frac {(-1)^{n}}{n!}}B_{n}(-p_{1},-1!p_{2},-2!p_{ 3},\lpontok ,-(n-1)!p_{n}),

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: $B_{n}$

\sum _{n=0}^{\infty }e_{n}\,X^{n}=\exp \left(\sum _{n=1}^{\infty }{\frac { (-1)^{n+1}}{n}}p_{n}\,X^{n}\jobbra).

Hatványösszegek közvetlen ábrázolása elemi szimmetrikus polinomokkal

Hasonlóképpen, a rekurziós kifejezések közvetlen kiterjesztésével ezt kaphatjuk meg

{\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}+4e_{3}e_{1}+2e_{2}^{2}-4e_{4},\\p_{5}&=e_{1}^{5}-5e_{2}e_{1 }^{3}+5e_{3}e_{1}^{2}+5e_{2}^{2}e_{1}-5e_{4}e_{1}-5e_{3}e_{2}+ 5e_{5},\\p_{6}&=e_{1}^{6}-6e_{2}e_{1}^{4}+6e_{3}e_{1}^{3}+9e_{ 2}^{2}e_{1}^{2}-6e_{4}e_{1}^{2}-12e_{3}e_{2}e_{1}+6e_{5}e_{1}- 2e_{2}^{3}+3e_{3}^{2}+6e_{4}e_{2}-6e_{6}.\end{aligned}}

Az első négy képletet Albert Girard szerezte meg Newton előtt, 1629-ben. Az általános képlet a következő:

p_{m}=\sum _{r_{1}+2r_{2}+\cdots +mr_{m}=m \atop r_{1}\geq 0,\ldots ,r_{m}\geq 0}(-1)^{m}{\frac {m(r_{1}+r_{2}+\cdots +r_{m}-1)!}{r_{1}!r_{2}!\ cdots r_{m}!}}\prod _{i=1}^{m}(-e_{i})^{r_{i}}.

Ez újrafogalmazható Bell-polinomokkal:

p_{m}=(-1)^{m}m\sum _{k=1}^{m}{\frac {1}{k}}{\hat {B}}_{m, k}(-e_{1},\pontok ,-e_{m-k+1}).

Alkalmazások

Alkalmazások polinomok gyökereire

A gyököket tartalmazó polinom a következőképpen ábrázolható $f(x)$ $x_{1},\pontok,x_{n}$

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

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. $e_{k}=e_{k}(x_{1},\pontok ,x_{n})$ $p_{k}(x_{1},\dots ,x_{n})=\sum \limits _{i=1}^{n}{{x_{i}}^{k}}$ $f(x)$

Alkalmazások mátrixok karakterisztikus polinomjaira

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. $A$

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 . $A$ $x_{1},\pontok,x_{n}$ $e_{i}$

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 $k$ $A^{k}$ ${x_{1}}^{k},\dots ,{x_{n}}^{k}$

p_{k}(x_{1},\dots ,x_{n})=tr(A^{k})

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: $e_{1},\pontok ,e_{n}$ $tr(A),\dots ,tr(A^{n})$

mátrixhatványok számítása és nyomuk $A$
lineáris egyenletrendszer megoldása háromszögmátrixszal

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.

Alkalmazások trigonometrikus összegekre

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.

Jegyzetek

Tignol, Jean-Pierre. Galois algebrai egyenletek elmélete (neopr.) . - Szingapúr: World Scientific , 2001. - ISBN 978-981-02-4541-2 .
Bergeron, F.; Labelle, G.; Leroux, P. Kombinatorikus fajok és faszerű struktúrák (angol) . - Cambridge: Cambridge University Press , 1998. - ISBN 978-0-521-57323-8 .
Cameron, Peter J. Permutációs csoportok (határozatlan) . - Cambridge: Cambridge University Press , 1999. - ISBN 978-0-521-65378-7 .
Cox, David; Little, John és O'Shea, Donal. Ideálok, változatok és algoritmusok (határozatlan) . - New York: Springer-Verlag , 1992. - ISBN 978-0-387-97847-5 .
Eppstein, D.; Goodrich, M. T. (2007). „Tér-hatékony kóbor azonosítás az oda-vissza adatfolyamokban Newton identitásain és megfordítható Bloom szűrőin keresztül”. Algoritmusok és adatstruktúrák, 10. nemzetközi műhely, WADS 2007 . Springer-Verlag, Lecture Notes in Computer Science 4619. pp. 637-648. arXiv : 0704.3313 . Iránykód : 2007arXiv0704.3313E .
Littlewood, D.E. A csoportkarakterek elmélete és a csoportok mátrixábrázolása . - Oxford: Oxford University Press , 1950. - P. viii+310. — ISBN 0-8218-4067-3 .
Macdonald, I. G. Szimmetrikus függvények és Hall-polinomok . – Oxford: The Clarendon Press, Oxford University Press, 1979. – P. viii+180. — (Oxford Mathematical Monographs). — ISBN 0-19-853530-9 .
Macdonald, I. G. Szimmetrikus függvények és Hall-polinomok . — Másodszor. – New York: Oxford Science Publications. The Clarendon Press, Oxford University Press, 1995. P. x+475. — (Oxford Mathematical Monographs). — ISBN 0-19-853489-2 .
Mead, DG Newton's Identities // The American Mathematical Monthly : folyóirat. - Mathematical Association of America, 1992. - Vol. 99 , sz. 8 . - P. 749-751 . - doi : 10.2307/2324242 . — .
Stanley, Richard P. Enumerative Combinatorics, Vol. 2 (neopr.) . - Cambridge University Press , 1999. - ISBN 0-521-56069-1 .
Prasolov V.V. Polinomok. - 3. kiadás, Rev. — M.: MTsNMO, 2003. — 336 p. — ISBN 5-94057-077-1