Newtonovy identity

V matematice definují Newtonovy identity , také známé jako Newton-Girardovy vzorce , vztahy mezi dvěma typy symetrických polynomů , jmenovitě mezi elementárními symetrickými polynomy a Newtonovými součty mocnin. Pro libovolný polynom P umožňují vyjádřit součet k -tých mocnin všech kořenů P (s přihlédnutím k násobnosti) pomocí koeficientů P , aniž by se kořeny skutečně nacházely. Tyto identity objevil Isaac Newton kolem roku 1666 a možná v rané práci (1629) Alberta Girarda . Nacházejí uplatnění v mnoha oblastech matematiky, včetně Galoisovy teorie , invariantní teorie , teorie grup , kombinatoriky a dalších věd, včetně obecné teorie relativity .

Prohlášení totožnosti

Pro proměnné a pro zvažte součty --tých mocnin těchto proměnných: $x_1,\tečky,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}.

Značíme také elementárními symetrickými polynomy . Polynom je součet všech možných součinů různých proměnných, zejména $e_{k}(x_{1},\tečky ,x_{n})$ $e_{k}(x_{1},\tečky ,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{aligned}}

Potom lze Newtonovy identity zapsat následovně:

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

pro všechny . Zejména pro $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}),

Pro prvních několik hodnot dostáváme: $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},\ldots ,x_{n})+p_{3}(x_{1},\ldots ,x_{n}).\\\end{aligned}}

Pravdivost těchto identit nezávisí na počtu proměnných, i když se levá a pravá strana rovná nule. Tyto rovnosti nám umožňují rekurzivně vyjádřit v termínech : $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}}

Metody důkazu

Každá jednotlivá Newtonova identita může být ověřena pomocí elementárních algebraických operací, ale obecný vzorec potřebuje důkaz. Existuje několik různých způsobů, jak odvozovat identity.

Níže označíme počet proměnných , a identifikační číslo (počet členů v součtu na pravé straně) . $n$ $k$

Prostřednictvím speciálního případu $k=n$

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

Proto, protože máme ${\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

Když to shrneme , dostaneme $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}),

Tento výraz okamžitě implikuje Newtonovu --tou identitu proměnných. Protože jde o identitu mezi symetrickými homogenními polynomy . $k$ $k$

Z této skutečnosti vyplývá vše. Pro , identita zjevně vyplývá z přiřazení v identitě pro $n<k$ $x_{n+1}=x_{n+2}=\dots =x_{k}=0$ $n=k$

Nechte teď . Označte levou a pravou stranu identity. Z naplnění identity u , vyplývá, že $n=k+1$ $f(x_{1},\tečky ,x_{n})$ $g(x_{1},\tečky ,x_{n})$ $n=k$

{\begin{aligned}&f(0,x_{2},\tečky ,x_{k},x_{k+1})=g(0,x_{2},\tečky ,x_{k} ,x_{k+1})\\&f(x_{1},0,\tečky ,x_{k},x_{k+1})=g(x_{1},0,\tečky ,x_{k },x_{k+1})\\&\tečky \\&f(x_{1},x_{2},\tečky ,0,x_{k+1})=g(x_{1},x_{ 2},\tečky ,0,x_{k+1})\\&f(x_{1},x_{2},\tečky ,x_{k},0)=g(x_{1},x_{2 },\tečky ,x_{k},0)\end{aligned}}

Z toho však plyne, že rozdíl může být reprezentován ve tvaru pro libovolný (pokud ne, pak pro některé by byl rozdíl nenulový a jedna z výše naznačených rovností by neplatila). Rozdíl tedy může být reprezentován jako , ale to je nemožné, protože plná mocnina a a je rovna . $fg$ ${\displaystyle h(x_{1},\tečky ,x_{n})x_{i))$ $i$ ${\displaystyle x_{1},\tečky ,x_{i-1},x_{i+1},\tečky ,x_{k+1))$ $fg$ ${\displaystyle h(x_{1},\tečky ,x_{n})x_{1}x_{2}\tečky x_{k}x_{k+1))$ $F$ $G$ $k$

Podobné argumenty pro dávají induktivní přechod a dokazují identity pro libovolný . $n>k+1$ $n$

Prostřednictvím formálních mocninných řad

Přímým otevřením závorek to lze získat

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

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

Označení , dostaneme . $s={\frac {1}{t))$ $\prod _{i=1}^{n}(1-x_{i}s)=\sum _{k=0}^{n}(-1)^{k}e_{k}( x_{1},\tečky ,x_{n})s^{k}$

Formálním derivováním (vzetím derivace) vzhledem k a vynásobením obou částí dostaneme $s$ $s$

{\begin{aligned}\sum _{k=0}^{n}(-1)^{k}ke_{k}(x_{1},\ldots ,x_{n})s^{ k}&=s\součet _{i=1}^{n}\left[(-x_{i})\prod \nolimits _{j\neq i}(1-x_{j}s)\vpravo] \\&=-\left(\sum _{i=1}^{n}{\frac {x_{i}s}{1-x_{i}s}}\right)\prod \nolimits _{j =1}^{n}(1-x_{j}s)\\&=-\left[\součet _{i=1}^{n}\součet _{j=1}^{\infty }( x_{i}s)^{j}\right]\left[\součet _{\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}\right]\left[\sum _{\ell =0}^{n}(-1)^{\ell -1}e_{\ell }(x_{1}, \ldots ,x_{n})s^{\ell }\right],\\\end{aligned}}

Protože identická rovnost polynomů implikuje rovnost všech koeficientů, pak to podle pravidel násobení polynomů přímo znamená, že

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

Přes teleskopický rozsah

Nechte některé opravit . Označme součtem všech monočlenů , skládajících se z různých proměnných, z nichž jedna je zahrnuta v monočlenu se stupněm , a všechny ostatní - se stupněm 1. Takové monočleny přirozeně vznikají v součinu (proměnné se stupněm „pocházejí“ z polynomu , a zbytek zařazen do monomiálu s prvním stupněm - od ). $k\geq 1$ $r_{i}^{(k)}(x_{1},\tečky,x_{n})$ $k$ $i$ $p_{i}(x_{1},\tečky ,x_{n})e_{ki}(x_{1},\tečky ,x_{n})$ $i$ $p_{i}$ ${\displaystyle e_{ki))$

Konkrétněji lze snadno ověřit následující identity:

{\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{aligned}}

Zvláštnost prvního z nich je dána, zhruba řečeno, tím, že pro monočlen je jednoznačně jasné, která proměnná je převzata z a která - z , takže každý takový polynom je zahrnut do součinu s koeficientem . V tomto případě se polynom vyskytne v součinu právě jednou - jako každé možné násobení jedné z proměnných se zbytkem monočlenu: . Tím získáme koeficient $i\geq 2$ ${\displaystyle x_{0}^{i}x_{1}\dots x_{ki))$ $p_{i}$ ${\displaystyle e_{ki))$ ${\displaystyle p_{i}e_{ki))$ $jeden$ $i=1$ ${\displaystyle x_{1},\tečky ,x_{k))$ ${\displaystyle p_{1}e_{k-1))$ $k$ $x_{1}x_{2}\tečky x_{k-1}x_{k}=x_{1}\cdot x_{2}x_{3}\tečky x_{k-1}x_{k} =x_{2}\cdot x_{1}x_{3}\tečky x_{k-1}x_{k}=\tečky =x_{k}\cdot x_{1}x_{2}\tečky x_{k -2}x_{k-1}$ $k$ $e_{k}$

Z výše uvedených identit to lze snadno získat

{\begin{aligned}&p_{1}e_{k-1}-p_{2}e_{k-2}+\tečky +(-1)^{k-1}p_{k}=\ \&=ke_{k}+r_{2}^{(k)}-\left({r_{2}^{(k)}+r_{3}^{(k)}}\right)+\ left({r_{3}^{(k)}+r_{4}^{(k)}}\right)-\tečky +(-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)}\tečky +(-1)^{k-1}r_{k}^{(k)}+( -1)^{k}r_{k}^{(k)}=\\&=ke_{k}\\\end{aligned}}

Související identity

Přímé reprezentace elementárních symetrických polynomů pomocí mocnin

Explicitním rozšířením výrazu přes , získáme reprezentace $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}\součet _{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}}

Obecný vzorec lze také přepsat jako

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

kde je Bellův polynom . Taková reprezentace vede zejména k následující identitě generujících funkcí: $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}\right).

Přímá reprezentace mocninných součtů pomocí elementárních symetrických polynomů

Podobně to lze získat přímým rozšířením rekurzních výrazů

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

První čtyři vzorce získal Albert Girard před Newtonem v roce 1629. Obecný vzorec je následující:

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}}.

To lze přeformulovat pomocí Bellových polynomů:

p_{m}=(-1)^{m}m\součet _{k=1}^{m}{\frac {1}{k}}{\hat {B}}_{m, k}(-e_{1},\tečky ,-e_{m-k+1}).

Aplikace

Aplikace na kořeny polynomů

Polynom s kořeny může být reprezentován jako $f(x)$ $x_{1},\tečky ,x_{n}$

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

kde koeficienty jsou symetrické polynomy definované výše. Pro známé hodnoty mocninných součtů lze koeficienty polynomu nalézt z rekurzivních vzorců. $e_{k}=e_{k}(x_{1},\tečky,x_{n})$ $p_{k}(x_{1},\tečky ,x_{n})=\sum \limits _{i=1}^{n}{{x_{i}}^{k}}$ $f(x)$

Aplikace na charakteristické polynomy matic

Newtonovy identity nám umožňují zredukovat výpočet koeficientů charakteristického polynomu matice na výpočet stopy jejích různých mocnin. $A$

Uvažujme charakteristický polynom nějaké matice . Jeho kořeny jsou vlastními hodnotami této matice (každý kořen je reprezentován svou vlastní násobností). Poté jsou koeficienty charakteristického polynomu vyjádřeny pomocí symetrických polynomů . $A$ $x_{1},\tečky ,x_{n}$ $e_{i}$

U každého kladného čísla jsou vlastními hodnotami matice mocniny . Vzhledem k tomu, že součet vlastních hodnot matice je roven její stopě $k$ $A^{k}$ ${x_{1}}^{k},\dots ,{x_{n}}^{k}$

p_{k}(x_{1},\tečky ,x_{n})=tr(A^{k})

Proto, a , a koeficienty charakteristického polynomu mohou být vyjádřeny lineárně z . Výpočet koeficientů polynomu se tak redukuje na dva kroky: $e_{1},\tečky ,e_{n}$ $tr(A),\tečky ,tr(A^{n})$

výpočet maticových mocnin a jejich trasování $A$
řešení soustavy lineárních rovnic s trojúhelníkovou maticí

Oba stupně patří do třídy složitosti NC , takže do třídy NC patří i problém hledání koeficientů charakteristického polynomu. Na této myšlence je založen Fadeev-Leverrierův algoritmus (1840) .

Protože podle Hamiltonovy-Cayleyovy věty je jakákoli matice kořenem jejího charakteristického polynomu, pak rychlý výpočet koeficientů tohoto polynomu poskytuje rychlý způsob, jak najít inverzní matici.

Aplikace na trigonometrické součty

Newtonovy identity lze použít při odhadu racionálních goniometrických součtů modulo prime k jedinečnému nalezení speciálního případu Vinogradovova integrálu se stejným počtem proměnných a rovnic.

Poznámky

Tignol, Jean-Pierre. Galoisova teorie algebraických rovnic (neopr.) . - Singapur: World Scientific , 2001. - ISBN 978-981-02-4541-2 .
Bergeron, F.; Labelle, G.; Leroux, P. Kombinatorické druhy a stromové struktury (anglicky) . - Cambridge: Cambridge University Press , 1998. - ISBN 978-0-521-57323-8 .
Cameron, Peter J. Permutační skupiny (neurčité) . - Cambridge: Cambridge University Press , 1999. - ISBN 978-0-521-65378-7 .
Cox, David; Little, John, a O'Shea, Donal. Ideály, odrůdy a algoritmy (neurčité) . - New York: Springer-Verlag , 1992. - ISBN 978-0-387-97847-5 .
Eppstein, D.; Goodrich, M. T. (2007). „Vesmírně efektivní identifikace opozdilců ve zpátečních datových tocích prostřednictvím Newtonových identit a invertibilních Bloomových filtrů“. Algoritmy a datové struktury, 10. mezinárodní workshop, WADS 2007 . Springer-Verlag, Lecture Notes in Computer Science 4619. pp. 637-648. arXiv : 0704.3313 . Bibcode : 2007arXiv0704.3313E .
Littlewood, D.E. Teorie skupinových znaků a maticové reprezentace skupin . - Oxford: Oxford University Press , 1950. - P. viii+310. — ISBN 0-8218-4067-3 .
Macdonald, I. G. Symetrické funkce a Hallovy polynomy . — Oxford: The Clarendon Press, Oxford University Press, 1979. — P. viii+180. — (Oxfordské matematické monografie). — ISBN 0-19-853530-9 .
Macdonald, I. G. Symetrické funkce a Hallovy polynomy . - Druhý. — New York: Oxford Science Publications. The Clarendon Press, Oxford University Press, 1995. P. x+475. — (Oxfordské matematické monografie). — ISBN 0-19-853489-2 .
Mead, DG Newton's Identities // The American Mathematical Monthly : journal. - Mathematical Association of America, 1992. - Sv. 99 , č. 8 . - str. 749-751 . - doi : 10.2307/2324242 . — .
Stanley, Richard P. Enumerative Combinatorics, sv. 2 (neopr.) . - Cambridge University Press , 1999. - ISBN 0-521-56069-1 .
Prasolov V.V. Polynomy. - 3. vydání, Rev. — M.: MTsNMO, 2003. — 336 s. — ISBN 5-94057-077-1