Newton'un kimlikleri - Newton's identities

Gelen matematik , Newton kimlikleri olarak da bilinen, Girard Newton formüller , iki tip arasındaki ilişkileri elde simetrik polinom yani arasında, güç toplamlar ve temel simetrik polinomlar . En Değerlendirilen kökleri bir mghorta ait polinom P tek değişkenli, onlar toplamları ifade izin k -inci güçler her köklerinin P katsayıları açısından (kendi çokluğu ile sayılır) P aslında bu köklerini bulmadan. Bu kimlikler, 1666 civarında Isaac Newton tarafından , görünüşe göre Albert Girard'ın daha önceki çalışmalarının (1629) cehaletinde bulundu . Galois teorisi , değişmez teori , grup teorisi , kombinatorik dahil olmak üzere matematiğin birçok alanında uygulamalarının yanı sıra genel görelilik de dahil olmak üzere matematik dışındaki diğer uygulamalara sahiptirler .

matematiksel ifade

Simetrik polinomlar açısından formülasyon

Let x ₁ , ..., x _{, n} için değişkenler, göstermektedirler olmak k  ile 1 ≥ p _k ( X ₁ , ..., x _{, n} ) k inci güç toplamı :

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

ve k  ≥ 0 için e _k ( x ₁ , ..., x _n ) temel simetrik polinomu (yani, k farklı değişkenin tüm farklı ürünlerinin toplamı ) ifade eder, yani

${\displaystyle {\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},\\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{hizalı} }}$

O zaman Newton'un kimlikleri şu şekilde ifade edilebilir:

${\displaystyle 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}),}$

tüm n  ≥ 1 ve n  ≥ k  ≥ 1 için geçerlidir.

Ayrıca, bir

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

tüm k  >  n  ≥ 1 için.

Somut olarak, kişi k'nin ilk birkaç değeri için alınır :

${\displaystyle {\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{hizalı}}}$

Bu denklemlerin şekli ve geçerliliği değişkenlerin n sayısına bağlı değildir (her ne kadar sol tarafın 0 olduğu nokta, yani n -inci özdeşlikten sonra olsa da ), bu da onları denklemde özdeşlik olarak ifade etmeyi mümkün kılar. simetrik fonksiyonların halkası . o yüzükte bir tane var

${\displaystyle {\begin{aligned}e_{1}&=p_{1},\\2e_{2}&=e_{1}p_{1}-p_{2}=p_{1}^{2} -p_{2},\\3e_{3}&=e_{2}p_{1}-e_{1}p_{2}+p_{3}={\tfrac {1}{2}}p_{1 }^{3}-{\tfrac {3}{2}}p_{1}p_{2}+p_{3},\\4e_{4}&=e_{3}p_{1}-e_{2 }p_{2}+e_{1}p_{3}-p_{4}={\tfrac {1}{6}}p_{1}^{4}-p_{1}^{2}p_{2 }+{\tfrac {4}{3}}p_{1}p_{3}+{\tfrac {1}{2}}p_{2}^{2}-p_{4},\\\end{ hizalı}}}$

ve benzeri; burada sol taraflar asla sıfır olmaz. Bu denklemler, e _i'nin p _k cinsinden özyinelemeli olarak ifade edilmesini sağlar ; tersini yapabilmek için, kişi onları şu şekilde yeniden yazabilir:

${\displaystyle {\begin{aligned}p_{1}&=e_{1},\\p_{2}&=e_{1}p_{1}-2e_{2}=e_{1}^{2} -2e_{2},\\p_{3}&=e_{1}p_{2}-e_{2}p_{1}+3e_{3}=e_{1}^{3}-3e_{1} e_{2}+3e_{3},\\p_{4}&=e_{1}p_{3}-e_{2}p_{2}+e_{3}p_{1}-4e_{4}= e_{1}^{4}-4e_{1}^{2}e_{2}+4e_{1}e_{3}+2e_{2}^{2}-4e_{4},\\&{} \ \ \vdots \end{hizalı}}}$

Genel olarak, sahip olduğumuz

${\displaystyle p_{k}(x_{1},\ldots ,x_{n})=(-1)^{k-1}ke_{k}(x_{1},\ldots ,x_{n}) +\sum _{i=1}^{k-1}(-1)^{k-1+i}e_{ki}(x_{1},\ldots ,x_{n})p_{i}( x_{1},\ldots ,x_{n}),}$

tüm n  ≥ 1 ve n  ≥ k  ≥ 1 için geçerlidir.

Ayrıca, bir

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

tüm k  >  n  ≥ 1 için.

Bir polinomun köklerine uygulama

Kökleri x _i olan polinom şu şekilde genişletilebilir:

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

burada katsayılar yukarıda tanımlanan simetrik polinomlardır. Köklerin güç toplamları göz önüne alındığında${\displaystyle e_{k}(x_{1},\ldots ,x_{n})}$

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

Köklü polinomun katsayıları , güç toplamları cinsinden özyinelemeli olarak şu şekilde ifade edilebilir: ${\displaystyle x_{1},\ldots ,x_{n}}$

${\displaystyle {\begin{aligned}e_{0}&=1,\\[4pt]-e_{1}&=-p_{1},\\[4pt]e_{2}&={\frac { 1}{2}}(e_{1}p_{1}-p_{2}),\\[4pt]-e_{3}&=-{\frac {1}{3}}(e_{2} p_{1}-e_{1}p_{2}+p_{3}),\\[4pt]e_{4}&={\frac {1}{4}}(e_{3}p_{1} -e_{2}p_{2}+e_{1}p_{3}-p_{4}),\\&{}\ \ \vdots \end{aligned}}}$

Polinomları bu şekilde formüle etmek, bir analitik fonksiyonun sıfırlarını bulmak için Delves ve Lyness yöntemini kullanırken yararlıdır.

Bir matrisin karakteristik polinomuna uygulama

Polinom üzerinde olduğunda karakteristik polinom a matris A (özellikle de bir bir tamamlayıcı matris polinom), kökler olan özdeğerler cebirsel çokluğu ile sayılır matris. Herhangi bir pozitif tam sayı için k , matris bir ^k özdeğer güçler olarak var x _ı ^k ve her özdeğer bir A özdeğer bu onun çok sayıda katkı x _i ^k arasında bir ^k . Daha sonra, A ^k'nin karakteristik polinomunun katsayıları, x _i ^k kuvvetlerindeki temel simetrik polinomlar tarafından verilir . Özel olarak, toplamı x _i ^k olduğu, k inci güç toplamı p _k karakteristik polinomunun köklerinin A , onun ile verilir iz : ${\displaystyle x_{i}}$${\displaystyle x_{i}}$

${\displaystyle p_{k}=\operatöradı {tr} (A^{k})\,.}$

Newton kimlikler şimdi güçler izlerini ilgili bir ^k karakteristik polinomun katsayıları ile A . Temel simetrik polinomları kuvvet toplamları cinsinden ifade etmek için bunları tersine kullanarak, sadece A ^k kuvvetlerini ve izlerini hesaplayarak karakteristik polinomu bulmak için kullanılabilirler .

Bu hesaplama, A ^k matris güçlerinin izlerinin hesaplanmasını ve üçgensel bir denklem sisteminin çözülmesini gerektirir. Her ikisi de karmaşıklık sınıfı NC'de yapılabilir (üçgen bir sistemi çözmek böl ve yönet ile yapılabilir). Bu nedenle, bir matrisin karakteristik polinomu NC cinsinden hesaplanabilir. Tarafından Cayley- Hamilton teoremi , her matris tatmin karakteristik polinom ve basit bir dönüşüm bulmak için sağlar adjugate matrisi nc.

Hesaplamaların verimli bir biçimde yeniden düzenlenmesi, Faddeev-LeVerrier algoritmasına (1840) yol açar , bunun hızlı bir paralel uygulaması L. Csanky'ye (1976) bağlıdır. Dezavantajı, tamsayılarla bölme gerektirmesidir, bu nedenle genel olarak alan 0 karakteristiğine sahip olmalıdır.

Galois teorisi ile ilişkisi

Belirli bir n için , k  = 1,..., n için temel simetrik polinomlar e _k ( x ₁ ,..., x _n ) x ₁ ,...' deki simetrik polinomların uzayı için cebirsel bir temel oluşturur. x _{, n} : her polinom ifadesi x _i bu değişkenlerin her permütasyon bir tarafından verilir altında değişmeyen bir polinom bu temel simetrik polinom ekspresyon ve bu ifade polinom ifadelerin denklik özgü bağlıdır. Bu, simetrik polinomların temel teoremi olarak bilinen genel bir gerçektir ve Newton'un özdeşlikleri, kuvvet toplamı simetrik polinomları durumunda açık formüller sağlar. Uygulanan mghorta polinoma tüm katsayılı bir _k serbest parametreleri olarak kabul edilen her simetrik polinom ifadesi, bu araçlar S ( x ₁ , ..., x _{, n} , köklerindeki) kullanılarak bir polinom ifadesi olarak ifade edilebilir , P ( bir ₁ , ..., a _n ) sadece katsayıları cinsinden, başka bir deyişle kök bilgisi gerektirmeden. Bu gerçek aynı zamanda Galois teorisindeki genel değerlendirmelerden de kaynaklanmaktadır (biri, a _k'yi , Galois grubunun tam simetrik gruba göre izin verdiği bir uzatma alanındaki kökleri olan bir taban alanının elemanları ve Galois'in tüm unsurları altında sabitlenmiş alan olarak görülür. grup temel alandır). ${\textstyle t^{n}+\sum _{k=1}^{n}(-1)^{k}a_{k}t^{nk}}$

Newton özdeşlikleri, aynı zamanda, herhangi bir simetrik polinomun güç toplamlarında da ifade edilebileceğini göstererek, temel simetrik polinomları, kuvvet toplamı simetrik polinomları cinsinden ifade etmeye izin verir. Aslında ilk n kuvvet toplamları simetrik polinomların uzayı için cebirsel bir temel oluşturur.

İlgili kimlikler

Newton'un kimliklerinden ayırt edilmeleri gerekirken, onlarla çok yakından ilişkili bir dizi kimlik (aile) vardır.

Tam homojen simetrik polinomlar kullanan bir varyant

Tarafından belirten h _k tam homojen simetrik polinomu tüm toplamıdır monomiyallerin derece arasında  k , güç toplamı polinomları da Newton'un kimliklere benzer kimlikler tatmin, ancak herhangi bir eksi işaretlerini içermeyen. Simetrik fonksiyonların halkasında kimlikler olarak ifade edilirler , okurlar

${\displaystyle kh_{k}=\sum _{i=1}^{k}h_{ki}p_{i},}$

tüm n ≥ k  ≥ 1 için geçerlidir  . Newton'un özdeşliklerinin aksine, büyük k için sol taraflar sıfır olmaz  ve sağ taraflar her zamankinden daha fazla sıfır olmayan terim içerir. k'nin ilk birkaç değeri için ,

${\displaystyle {\begin{aligned}h_{1}&=p_{1},\\2h_{2}&=h_{1}p_{1}+p_{2},\\3h_{3}&= h_{2}p_{1}+h_{1}p_{2}+p_{3}.\\\end{hizalı}}}$

Bu ilişkiler, bu durumda üretici fonksiyon kimliğine dayalı olarak yukarıda verilen güç serilerindeki katsayıları karşılaştırarakkine benzer bir argümanla gerekçelendirilebilir.

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

Aşağıda verilenler gibi Newton kimliklerinin kanıtları, bu kimliklerin bu türevlerini kanıtlamak için kolayca uyarlanamaz.

Temel simetrik polinomları güç toplamları cinsinden ifade etme

Belirtildiği gibi, Newton'un kimlikleri, temel simetrik polinomları güç toplamları cinsinden özyinelemeli olarak ifade etmek için kullanılabilir. Bunu yapmak tamsayı paydalarının eklenmesini gerektirir, bu nedenle rasyonel katsayılı simetrik fonksiyonların Λ _Q halkasında yapılabilir :

${\displaystyle {\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{hizalı}}}$

ve benzeri. Genel formül uygun bir şekilde şu şekilde ifade edilebilir:

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

burada B _n tam üstel Bell polinomudur . Bu ifade aynı zamanda işlevler üretmek için aşağıdaki kimliğe de yol açar:

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

Uygulamalı bir mghorta polinoma, bu formülleri köklerinin güç toplamlarının açısından katsayıları ifade etmektedir: her yerine e _ı ile bir _i ve her bir p _{, k} ile s _k .

Tam homojen simetrik polinomları güç toplamları cinsinden ifade etme

Tam homojen simetrik polinomları içeren benzer ilişkiler, denklemler vererek benzer şekilde geliştirilebilir.

${\displaystyle {\begin{aligned}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}),\\&~~\vdots \\h_{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{hizalı}}}$

ve bunun gibi, içinde yalnızca artı işaretleri vardır. Tam Bell polinomu açısından,

${\displaystyle h_{n}={\frac {1}{n!}}B_{n}(p_{1},1!p_{2},2!p_{3},\ldots ,(n-1) )!p_{n}).}$

Bu ifadeler tam olarak karşılık döngü indeksi polinomlarla simetrik gruplar , eğer bir, yorumlanması güç toplamları s _i değişkenli olarak: ifadesinde katsayısı h _k bir monomial p ₁ ^{m ₁} p ₂ ^{m ₂} ... p _l ^{m _l} tüm permütasyon oranına eşit olan k sahip m, ₁ sabit noktalar, m ₂ , uzunluğu 2 döngüleri, ..., ve m, _l uzunluğu döngüleri l . Açıkça, bu katsayı olarak yazılabilir nerede ; bu N , verilen döngü tipinin herhangi bir π permütasyonuyla değişen permütasyonların sayısıdır  . Temel simetrik fonksiyonlar için ifadeler, aynı mutlak değere sahip katsayılara sahiptir, ancak π işaretine eşit bir işaret  , yani (-1) ^{m ₂ + m ₄ +...} . ${\görüntüleme stili 1/N}$${\displaystyle N=\prod _{i=1}^{l}(m_{i}!\,i^{m_{i}})}$

Aşağıdaki endüktif adım dikkate alınarak kanıtlanabilir:

${\displaystyle {\begin{aligned}mf(m;m_{1},\ldots ,m_{n})&=f(m-1;m_{1}-1,\ldots ,m_{n})+ \cdots +f(mn;m_{1},\ldots ,m_{n}-1)\\m_{1}\prod _{i=1}^{n}{\frac {1}{i^{ m_{i}}m_{i}!}}+\cdots +nm_{n}\prod _{i=1}^{n}{\frac {1}{i^{m_{i}}m_{i }!}}&=m\prod _{i=1}^{n}{\frac {1}{i^{m_{i}}m_{i}!}}\end{hizalı}}}$

'nin üretici fonksiyonunun türetilmesine benzer şekilde , güç toplamları cinsinden ' nin üretici fonksiyonunu da şu şekilde elde edebiliriz : ${\displaystyle e_{n}}$${\ Displaystyle h_{n}}$

${\displaystyle \sum _{n=0}^{\infty }h_{n}\,X^{n}=\exp \left(\sum _{n=1}^{\infty }{\frac { p_{n}}{n}}\,X^{n}\sağ).}$

Güç toplamlarını temel simetrik polinomlar cinsinden ifade etme

Paydaları içermeyen simetrik polinomlar cinsinden güç toplamlarını ifade etmek için Newton'un kimlikleri de kullanılabilir:

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

İlk dört formül Albert Girard tarafından 1629'da (böylece Newton'dan önce) elde edildi .

Genel formül (negatif olmayan tüm tamsayılar için m ):

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

Bu, sıradan Bell polinomları cinsinden şu şekilde ifade edilebilir:

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

veya eşdeğer olarak üreten fonksiyon olarak :

${\displaystyle {\begin{hizalanmış}\sum _{k=1}^{\infty }(-1)^{k-1}p_{k}{\frac {t^{k}}{k}} &=\ln \left(1+e_{1}t+e_{2}t^{2}+e_{3}t^{3}+\cdots \right)\\&=e_{1}t- {\frac {1}{2}}\left(e_{1}^{2}-2e_{2}\right)t^{2}+{\frac {1}{3}}\left(e_{ 1}^{3}-3e_{1}e_{2}+3e_{3}\sağ)t^{3}+\cdots,\end{aligned}}}$

önceki alt bölümde verilen Bell polinom üstel üretme fonksiyonuna benzer .

Yukarıdaki çoklu toplam formülü, aşağıdaki tümevarım adımı dikkate alınarak kanıtlanabilir:

${\displaystyle {\begin{aligned}f(m;\;r_{1},\ldots ,r_{n})={}&f(m-1;\;r_{1}-1,\cdots ,r_ {n})+\cdots +f(mn;\;r_{1},\ldots ,r_{n}-1)\\[8pt]={}&{\frac {1}{(r_{1} -1)!\cdots r_{n}!}}(m-1)(r_{1}+\cdots +r_{n}-2)!+\cdots \\&\cdots +{\frac {1} {r_{1}!\cdots (r_{n}-1)!}}(mn)(r_{1}+\cdots +r_{n}-2)!\\[8pt]={}&{\ frac {1}{r_{1}!\cdots r_{n}!}}\left[r_{1}(m-1)+\cdots +r_{n}(mn)\sağ]\left[r_{ 1}+\cdots +r_{n}-2\sağ]!\\[8pt]={}&{\frac {1}{r_{1}!\cdots r_{n}!}}\left[m (r_{1}+\cdots +r_{n})-m\sağ]\sol[r_{1}+\cdots +r_{n}-2\sağ]!\\[8pt]={}&{ \frac {m(r_{1}+\cdots +r_{n}-1)!}{r_{1}!\cdots r_{n}!}}\end{aligned}}}$

Güç toplamlarını tam homojen simetrik polinomlar cinsinden ifade etme

Son olarak, tam homojen simetrik polinomları içeren değişken kimlikler, benzer şekilde, güç toplamlarını terim cinsinden ifade etmek için kullanılabilir:

${\displaystyle {\begin{aligned}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}+5h_{2}^{2}h_{1}+5h_{3}h_{1}^{2}-5h_{3}h_{2}-5h_{4} h_{1}+5h_{5},\\p_{6}&=-h_{1}^{6}+6h_{2}h_{1}^{4}-9h_{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},\\\end{hizalı}}}$

ve benzeri. Her e _i'nin karşılık gelen h _i ile yer değiştirmesi dışında, önceki özdeşlikler ailesine göre tek değişiklik, bu durumda sadece mevcut faktörlerin sayısına bağlı olan terimlerin işaretlerindedir: tek terimli −(−1) ^{m ₁ + m ₂ + m ₃ +...} . Özellikle katsayıların mutlak değerinin yukarıdaki açıklaması burada da geçerlidir. ${\displaystyle \Pi _{i=1}^{l}h_{i}^{m_{i}}}$

Genel formül (negatif olmayan tüm tamsayılar için m ):

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

Belirleyici olarak ifadeler

Bir birinci göz önüne alınarak belirleyicileri halinde yukandaki ifadeler için açık formülleri elde edilebilir n temel simetrik fonksiyonlar bilinmektedir ve güç toplamları bilinmeyenler olan lineer denklem olarak (tam homojen polinomları için ya da karşıtları) Newton kimliklerinin (veya tam tersi) ve son bilinmeyenin çözümünü bulmak için Cramer kuralını uygulayın . Örneğin Newton'un kimliklerini formda almak

${\displaystyle {\begin{aligned}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 \\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} \end{hizalanmış}}}$

ve bilinmeyenler olarak düşünüyoruz ve sonuncusu için çözüyoruz, ${\displaystyle p_{1},-p_{2},p_{3},\ldots ,(-1)^{n}p_{n-1}}$${\displaystyle p_{n}}$

${\displaystyle {\begin{aligned}p_{n}={}&{\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}\end{vmatrix}}^{-1}\\[7pt]={(-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}}\\[7pt]={}&{\begin{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}}.\end{hizalı}}}$

Tam homojen simetrik polinomlar için benzer hesaplamalar gibi, için yerine için çözmek de benzerdir; her durumda ayrıntılar nihai sonuçlardan biraz daha karmaşıktır, bunlar (Macdonald 1979, s. 20): ${\displaystyle e_{n}}$${\displaystyle p_{n}}$

${\displaystyle {\begin{aligned}e_{n}={\frac {1}{n!}}&{\begin{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}}\\[7pt]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}}\\[7pt]h_{n}={\frac {1}{n!}}&{\begin{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}&1-n\\ p_{n}&p_{n-1}&\cdots &p_{2}&p_{1}\end{vmatrix}}.\end{aligned}}}$

Determinantların kullanımının, for formülüne kıyasla ek eksi işaretlerine sahip olmasına neden olurken, daha önce verilen genişletilmiş formun durumunun tersi olduğuna dikkat edin. De belirttiği gibi (Littlewood 1950, s. 84), bir alternatif olarak, formülü elde edilebilir alarak sürekli için matris yerine determinantının, ve daha genel olarak herhangi bir ekspresyon Schur polinom gelen alarak elde edilebilir immanant bu matris. ${\ Displaystyle h_{n}}$${\displaystyle e_{n}}$${\ Displaystyle h_{n}}$${\displaystyle e_{n}}$

kimliklerin türetilmesi

Newton'un kimliklerinin her biri, temel cebir ile kolaylıkla kontrol edilebilir; ancak genel olarak geçerliliklerinin bir kanıta ihtiyacı vardır. İşte bazı olası türevler.

n  =  k özel durumundan

Bir elde edebilirsiniz k içinde inci Newton kimlik k substıtüe değişkenler

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

aşağıdaki gibi. İkame x _j için T verir

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

Bütün üzerinden toplarsak j verir

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

burada i  = 0 terimleri toplamdan çıkarıldı çünkü p ₀ (genellikle) tanımlanmadı. Bu denklem hemen k değişkende k -th Newton kimliğini verir . Bu, k derecesinin simetrik polinomlarının (homojen) bir özdeşliği olduğundan , herhangi bir sayıda değişken için geçerliliği, k değişken için geçerliliğinden kaynaklanmaktadır . Somut olarak, n  <  k değişkenlerdeki kimlikler, k  -  n değişkenleri sıfıra ayarlanarak çıkarılabilir . K Newton kimlik ıncı n  >  k değişkenleri olandan denklemin her iki tarafında daha fazla terim içeren k değişkenleri, ancak geçerlilik sağlanacaktır herhangi monomial maçın katsayılar eğer. Herhangi bir tek tek terimli ibaret için k değişkenlerinin, tekterimli bazı kümesi için sıfır ikame hayatta N  -  k katsayılarının eşitlik ortaya çıkan biri daha sonra bir (diğer) değişkenleri, k Newton kimlik inci k (uygun şekilde seçilmiş) değişkenler.

Serideki katsayıları karşılaştırma

Bir başka türetme halkasındaki hesaplamaları elde edilebilir resmi güç serileri R [[ t ]], R, bir Z, [ X ₁ , ..., x _{, n} ], polinomların halka içinde N değişkenler X ₁ , ... , x _n tamsayılar üzerinde.

Temel ilişkiden yeniden başlayarak

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

ve 1 / değiştirilmesi ile "polinomların geri" t için t ve daha sonra her iki tarafı çarpılarak t ⁿ negatif güçleri çıkarmak için t verir

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

(yukarıdaki hesaplama yapılmalıdır fraksiyonların alan bir R [[ t ]] ya da alternatif olarak, kimlik sol tarafında ürün değerlendirilerek basit bir şekilde elde edilebilir)

Tarafları değiştirmek ve a _{i'yi temsil} ettikleri temel simetrik polinomlar olarak ifade etmek , kimliği verir.

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

Bir resmi ayırt göre, her iki tarafı , t , sonra tarafından çoğalır (kolaylık için) t , elde edilmesi için

${\displaystyle {\begin{hizalanmış}\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)\sağ] \\&=-\left(\sum _{i=1}^{n}{\frac {x_{i}t}{1-x_{i}t}}\sağ)\prod \nolimits _{j =1}^{n}(1-x_{j}t)\\&=-\sol[\sum _{i=1}^{n}\sum _{j=1}^{\infty }( x_{i}t)^{j}\sağ]\sol[\sum _{\ell =0}^{n}(-1)^{\ell }e_{\ell }(x_{1},\ ldots ,x_{n})t^{\ell }\sağ]\\&=\left[\sum _{j=1}^{\infty }p_{j}(x_{1},\ldots ,x_ {n})t^{j}\sağ]\sol[\sum _{\ell =0}^{n}(-1)^{\ell -1}e_{\ell }(x_{1}, \ldots ,x_{n})t^{\ell }\sağ],\\\end{hizalı}}}$

Sağ taraftaki polinom önce aşağıdaki gibi yazılabilir nerede rasyonel bir fonksiyonun toplamı üzerinden bir ürün üzerinden faktör edebilmek amacıyla, daha sonra toplam kısmı içinde fraksiyon bir dizi olarak geliştirilmiştir t , aşağıdaki formül kullanılarak,

${\displaystyle {\frac {X}{1-X}}=X+X^{2}+X^{3}+X^{4}+X^{5}+\cdots,}$

ve son olarak, bir güç toplamı vererek , her t  ^j'nin katsayısı toplandı. ( t'deki seri biçimsel bir kuvvet serisidir, ancak alternatif olarak , bu konuda daha rahat olanlar için t için 0'a yeterince yakın bir seri açılımı olarak düşünülebilir ; aslında burada fonksiyonla değil, sadece serinin katsayıları.) t ^k katsayılarının her iki tarafta karşılaştırılmasıyla elde edilen

${\displaystyle (-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}),}$

hangi k -th Newton kimliğini verir .

Simetrik fonksiyon kimliklerinin teleskopik toplamı olarak

Temel olarak (Mead, 1992)'de verilen aşağıdaki türetme, açıklık için simetrik fonksiyonlar halkasında formüle edilmiştir (tüm özdeşlikler değişken sayısından bağımsızdır). Bazı saptamak k  > 0 ve simetrik bir fonksiyonu tanımlayabilir r ( i 2 ≤ için)  i  ≤  k bütün tat toplamı olarak monomiyallerin derecesi k bir değişken çarpılması ile elde edilen kuvvete yükseltilmiş  ı ile k  -  ı (bu ayrı bir diğer değişkenler tek terimli simetrik m _γ fonksiyonudur , burada γ bir kanca şeklidir ( i ,1,1,...,1)). Özellikle r ( k ) =  p _k ; için r (1) açıklama bu miktarda olur e _k , ancak bu durum artık burada monomials beri dışlanan herhangi seçkin değişkeni edildi. Tüm ürünler s _i e _{k - ı} cinsinden ifade edilebilir r ( j , birinci ve son durum biraz özel anlamına gelir). Birinde var

${\displaystyle p_{i}e_{ki}=r(i)+r(i+1)\quad {\text{için }}1<i<k}$

sol kapsayan farklı değişkenler katkıda terimler her ürün yana r ( i ) 'den değişken burada olanlar ise p _ı daha önce gelen terimin değişkenler arasında meydana e _{k - ı} katkıda r ( i  + 1), ve sağdaki terimler tam olarak bir kez elde edilir. İçin i  =  K ile bir çarpma e ₀  trivially veren = 1,

${\displaystyle p_{k}e_{0}=p_{k}=r(k).}$

Son olarak ürün, p ₁ e _{k -1} için i  1 katkı verir = r ( i  + 1) =  R (2) diğer değerler için gibi i  <  k , ancak geri kalan katılım üretmek k her tekterimli kez e _k bir yana, değişkenlerden biri p ₁ faktöründen gelebilir ; Böylece

${\displaystyle p_{1}e_{k-1}=ke_{k}+r(2).}$

K Newton kimlik inci hemen bir şekilde tüm şartları içinde, bu denklem, dönüşümlü toplam alma ile elde edilir r ( i ) yok eder.

Kombinatoryal Kanıt

Newton'un Kimliklerinin kısa bir kombinatoryal kanıtı (Zeilberger, 1984)'de verilmiştir.

Ayrıca bakınız

• Güç toplamı simetrik polinom
• Temel simetrik polinom
• simetrik fonksiyon
• Akışkan çözümleri , mükemmel bir akışkan durumunda Einstein tensörünün karakteristik polinomunu hesaplamak için Newton kimliklerinin bir uygulamasını veren bir makale ve genel görelilikteki diğer tam çözüm türleri üzerine benzer makaleler .

Referanslar

• Tignol, Jean-Pierre (2001). Galois'in cebirsel denklemler teorisi . Singapur: Dünya Bilimsel. ISBN'si 978-981-02-4541-2.
• Bergeron, F.; Labelle, G. & Leroux, P. (1998). Kombinatoryal türler ve ağaç benzeri yapılar . Cambridge: Cambridge University Press. ISBN'si 978-0-521-57323-8.
• Cameron, Peter J. (1999). Permütasyon Grupları . Cambridge: Cambridge University Press. ISBN'si 978-0-521-65378-7.
• Cox, David ; Küçük, John & O'Shea, Donal (1992). İdealler, Çeşitler ve Algoritmalar . New York: Springer-Verlag. ISBN'si 978-0-387-97847-5.
• Eppstein, D .; Goodrich, MT (2007). "Newton'un kimlikleri ve ters çevrilebilir Bloom filtreleri aracılığıyla gidiş-dönüş veri akışlarında yer verimli straggler tanımlama". Algoritmalar ve Veri Yapıları, 10. Uluslararası Çalıştay, WADS 2007 . Springer-Verlag, Bilgisayar Bilimlerinde Ders Notları 4619. s. 637–648. arXiv : 0704.3313 . Bibcode : 2007arXiv0704.3313E .
• Littlewood, DE (1950). Grup karakterleri teorisi ve grupların matris gösterimleri . Oxford: Oxford University Press. viii+310. ISBN'si 0-8218-4067-3.
• Macdonald, IG (1979). Simetrik fonksiyonlar ve Hall polinomları . Oxford Matematik Monografları. Oxford: Clarendon Press, Oxford University Press. viii+180. ISBN'si 0-19-853530-9. MR  0553598 .
• Macdonald, IG (1995). Simetrik fonksiyonlar ve Hall polinomları . Oxford Matematiksel Monograflar (İkinci baskı). New York: Oxford Bilim Yayınları. Clarendon Press, Oxford University Press. P. x+475. ISBN'si 0-19-853489-2. MR  1354144 .
• Mead, DG (1992). "Newton'un Kimlikleri". Amerikan Matematiksel Aylık . Amerika Matematik Derneği. 99 (8): 749–751. doi : 10.2307/2324242 . JSTOR  2324242 .
• Stanley, Richard P. (1999). Sayısal Kombinatorics, Cilt. 2 . Cambridge Üniversitesi Yayınları. ISBN'si 0-521-56069-1. (ciltli). (ciltsiz).
• Sturmfels, Bernd (1992). Değişmez Teoride Algoritmalar . New York: Springer-Verlag. ISBN'si 978-0-387-82445-1.
• Tucker, Alan (1980). Uygulamalı Kombinatorik (5/e ed.). New York: Wiley. ISBN'si 978-0-471-73507-6.

Dış bağlantılar

• MathWorld'de Newton–Girard formülleri
• Matematik Dergisinde Newton'un Kimliklerinin Matris Kanıtı
• Gerçek kök sayısı uygulaması
• Doron Zeilberger tarafından Newton'un Kimliklerinin Bir Kombinatoryal Kanıtı