Newtons identiteter

Inom matematiken definierar Newtons identiteter , även kända som Newton-Girard-formler , samband mellan två typer av symmetriska polynom , nämligen mellan elementära symmetriska polynom och Newtons potenssummor. För ett godtyckligt polynom P gör de det möjligt att uttrycka summan av k -te potenser av alla rötter av P (med hänsyn till multipliciteten) i termer av koefficienterna för P , utan att faktiskt hitta rötterna. Dessa identiteter upptäcktes av Isaac Newton omkring 1666, och möjligen i det tidiga arbetet (1629) av Albert Girard . De finner tillämpning inom många områden av matematik, inklusive Galois teori , invariant teori , gruppteori , kombinatorik , såväl som andra vetenskaper, inklusive allmän relativitet .

Uppgift om identiteter

För variabler och för att överväga summan av de -: te potenserna av dessa variabler: $x_1,\dots,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}.

Vi betecknar också med elementära symmetriska polynom . Ett polynom är summan av alla möjliga produkter av olika variabler, i synnerhet $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{för))\ k> n.\\\end{aligned}}

Då kan Newtons identiteter skrivas på följande sätt:

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

för alla . I synnerhet för $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}),

För de första värdena får vi: $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}}

Sanningen i dessa identiteter beror inte på antalet variabler, även när vänster och höger sida är lika med noll. Dessa jämlikheter tillåter oss att rekursivt uttrycka i termer av : $pi}$ $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}}

Bevismetoder

Varje individ av Newtons identiteter kan verifieras med hjälp av elementära algebraiska operationer, men den allmänna formeln behöver bevisas. Det finns flera olika sätt att härleda identiteter.

Nedan betecknar vi antalet variabler med , och identitetsnumret (antalet termer i summan på höger sida) med . $n$ $k$

Genom ett specialfall $k=n$

Per definition, $\prod _{i=1}^{k}(t-x_{i})=\summa _{i=0}^{k}(-1)^{ki}e_{ki}(x_ {1},\ldots ,x_{k})t^{i}$

Därför, för vi har ${\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

Sammanfattningsvis får vi $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}),

Detta uttryck antyder omedelbart Newtons -e identitet för variabler. Eftersom det är en identitet mellan symmetriska homogena polynom . $k$ $k$

Allt följer av detta faktum. För , identiteten följer uppenbarligen av uppdraget i identiteten för $n<k$ $x_{n+1}=x_{n+2}=\dots =x_{k}=0$ $n=k$

Låt nu . Beteckna med respektive vänster och höger sida av identiteten. Av uppfyllelsen av identiteten vid , följer det att $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,\dots ,x_{k},x_{k+1})=g(x_{1},0,\dots ,x_{k },x_{k+1})\\&\dots \\&f(x_{1},x_{2},\dots ,0,x_{k+1})=g(x_{1},x_{ 2},\dots ,0,x_{k+1})\\&f(x_{1},x_{2},\dots ,x_{k},0)=g(x_{1},x_{2 },\dots ,x_{k},0)\end{aligned}}

Det följer emellertid av detta att skillnaden kan representeras i formen för vilken som helst (om inte, så skulle skillnaden för vissa vara icke-noll och en av de ovan angivna likheterna skulle inte hålla). Därför kan skillnaden representeras som , men detta är omöjligt eftersom den fulla kraften av och och är lika med . $fg$ ${\displaystyle h(x_{1},\dots ,x_{n})x_{i))$ $i$ ${\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$

Liknande argument för att ge en induktiv övergång och bevisa identiteter för en godtycklig . $n>k+1$ $n$

Genom formell maktserie

Genom att öppna fästena direkt kan man få det

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

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

Betecknar , vi får . $s={\frac {1}{t))$ $\prod _{i=1}^{n}(1-x_{i}s)=\summa _{k=0}^{n}(-1)^{k}e_{k}( x_{1},\dots ,x_{n})s^{k}$

Formellt differentiera (att ta en derivata) med avseende på och multiplicera båda delarna med , får vi $s$ $s$

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

Eftersom den identiska likheten för polynom innebär likheten för alla koefficienter, innebär detta, enligt reglerna för multiplikation av polynom, direkt att

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

Genom teleskopområdet

Låt några fixas . Beteckna med summan av alla monomialer , bestående av olika variabler, varav en ingår i monomialen med grad , och alla andra - med grad 1. Sådana monomialer uppstår naturligt i produkten (variabler med grad "kommer" från polynomet , och resten ingår i monomial med första graden - från ). $k\geq 1$ $r_{i}^{(k)}(x_{1},\dots ,x_{n})$ $k$ $i$ $p_{i}(x_{1},\dots ,x_{n})e_{ki}(x_{1},\dots ,x_{n})$ $i$ $pi}$ ${\displaystyle e_{ki))$

Mer specifikt kan följande identiteter enkelt verifieras:

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

Det speciella med den första av dem beror i grova drag på det faktum att det för en monomial är unikt tydligt vilken variabel som tas från och vilken - från , så att varje sådant polynom ingår i produkten med en koefficient . I fallet kommer polynomet att förekomma exakt en gång i produkten - som varje möjlig multiplikation av en av variablerna med resten av monomet: . Detta ger koefficienten $i\geq 2$ ${\displaystyle x_{0}^{i}x_{1}\dots x_{ki))$ $pi}$ ${\displaystyle e_{ki))$ ${\displaystyle p_{i}e_{ki))$ $ett$ $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}\dots x_{k-1}x_{k}=\dots =x_{k}\cdot x_{1}x_{2}\dots x_{k -2}x_{k-1}$ $k$ $e_{k}$

Från ovanstående identiteter är det lätt att få det

{\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)}}\right)+\ vänster({r_{3}^{(k)}+r_{4}^{(k)}}\höger)-\prickar +(-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)}\dots +(-1)^{k-1}r_{k}^{(k)}+( -1)^{k}r_{k}^{(k)}=\\&=ke_{k}\\\end{aligned}}

Relaterade identiteter

Direkta representationer av elementära symmetriska polynom med potenssummor

Genom att explicit expandera uttrycket genom , får vi fram representationerna $e_{i}$ $pi}$

{\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}& =\textstil {\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}\summa _{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}}

Den allmänna formeln kan också skrivas om som

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

var är Bellpolynomet . En sådan representation leder i synnerhet till följande identitet för genererande funktioner: $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}\höger).

Direkt representation av potenssummor i termer av elementära symmetriska polynom

På liknande sätt, genom att utöka rekursionsuttrycken direkt, kan man få det

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

De fyra första formlerna erhölls av Albert Girard före Newton, 1629. Den allmänna formeln är följande:

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

Detta kan omformuleras i termer av Bell polynom:

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

Applikationer

Tillämpningar på rötter av polynom

Ett polynom med rötter kan representeras som $f(x)$ $x_{1},\dots ,x_{n}$

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

där koefficienterna är de symmetriska polynomen definierade ovan. För kända värden på potenssummor kan koefficienterna för ett polynom hittas från rekursiva formler. $e_{k}=e_{k}(x_{1},\dots ,x_{n})$ $p_{k}(x_{1},\dots ,x_{n})=\summa \limits _{i=1}^{n}{{x_{i}}^{k}}$ $f(x)$

Tillämpningar på karakteristiska polynom av matriser

Newtons identiteter tillåter oss att reducera beräkningen av koefficienterna för det karakteristiska polynomet i en matris till beräkningen av spåret av dess olika potenser. $A$

Betrakta det karakteristiska polynomet för någon matris . Dess rötter är egenvärdena för denna matris (varje rot representeras med sin egen mångfald). Sedan uttrycks koefficienterna för det karakteristiska polynomet i termer av symmetriska polynom . $A$ $x_{1},\dots ,x_{n}$ $e_{i}$

För alla positiva är matrisens egenvärden potenserna av . Eftersom summan av egenvärdena för en matris är lika med dess spår , alltså $k$ $A^{k}$ ${x_{1}}^{k},\dots ,{x_{n}}^{k}$

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

Därför och , Och koefficienterna för det karakteristiska polynomet kan uttryckas linjärt från . Beräkningen av koefficienterna för ett polynom reduceras alltså till två steg: $e_{1},\dots ,e_{n}$ $tr(A),\dots ,tr(A^{n})$

beräkning av matrispotenser och deras spår $A$
lösning av ett system av linjära ekvationer med en triangulär matris

Båda stegen tillhör NC-komplexitetsklassen , så problemet med att hitta koefficienterna för det karakteristiska polynomet tillhör också NC-klassen. Fadeev-Leverrier-algoritmen (1840) är baserad på denna idé .

Eftersom, enligt Hamilton-Cayley-satsen, vilken matris som helst är roten till dess karakteristiska polynom, ger en snabb beräkning av koefficienterna för detta polynom ett snabbt sätt att hitta den inversa matrisen.

Tillämpningar på trigonometriska summor

Newtons identiteter kan användas för att uppskatta rationella trigonometriska summor modulo prime för att unikt hitta ett specialfall av Vinogradov-integralen med lika många variabler och ekvationer.

Anteckningar

Tignol, Jean-Pierre. Galois teori om algebraiska ekvationer (neopr.) . - Singapore: World Scientific , 2001. - ISBN 978-981-02-4541-2 .
Bergeron, F.; Labelle, G.; Leroux, P. Kombinatoriska arter och trädliknande strukturer (engelska) . - Cambridge: Cambridge University Press , 1998. - ISBN 978-0-521-57323-8 .
Cameron, Peter J. Permutationsgrupper (obestämd) . - Cambridge: Cambridge University Press , 1999. - ISBN 978-0-521-65378-7 .
Cox, David; Little, John och O'Shea, Donal. Ideal, varianter och algoritmer (obestämd) . - New York: Springer-Verlag , 1992. - ISBN 978-0-387-97847-5 .
Eppstein, D.; Goodrich, M.T. (2007). "Rymdseffektiv eftersläpande identifiering i dataströmmar tur och retur via Newtons identiteter och inverterbara Bloom-filter". Algoritmer och datastrukturer, 10:e internationella workshopen, WADS 2007 . Springer-Verlag, Lecture Notes in Computer Science 4619. pp. 637-648. arXiv : 0704.3313 . Bibcode : 2007arXiv0704.3313E .
Littlewood, D.E. Teorin om gruppkaraktärer och matrisrepresentationer av grupper . - Oxford: Oxford University Press , 1950. - P. viii+310. — ISBN 0-8218-4067-3 .
Macdonald, I. G. Symmetriska funktioner och Hall polynom . — Oxford: The Clarendon Press, Oxford University Press, 1979. — P. viii+180. — (Oxford Mathematical Monographs). — ISBN 0-19-853530-9 .
Macdonald, I. G. Symmetriska funktioner och Hall polynom . — För det andra. — New York: Oxford Science Publications. The Clarendon Press, Oxford University Press, 1995. P. x+475. — (Oxford Mathematical Monographs). — ISBN 0-19-853489-2 .
Mead, GD Newtons identiteter // The American Mathematical Monthly : tidskrift. - Mathematical Association of America, 1992. - Vol. 99 , nr. 8 . - s. 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. Polynom. - 3:e uppl., Rev. — M.: MTsNMO, 2003. — 336 sid. — ISBN 5-94057-077-1