Newton'un kimlikleri
Gelen matematik ve daha özel olarak cebir , Newton kimlikleri (aynı zamanda Newton Girard formüller ) iki tip arasındaki ilişkiler simetrik polinomlar , temel simetrik polinomlar , ve Newton toplamlar , o belirsiz yetkilerinin miktarda demek olduğu olanlar. Tek değişkenli bir P polinomunun köklerinde değerlendirilen bu özdeşlikler , P'nin tüm köklerinin k -inci kuvvetlerinin toplamını ifade etmeye izin verir. (çokluklarıyla sayılır) P katsayılarının bir fonksiyonu olarak, bu kökleri belirlemeye gerek kalmadan. Bu formüller tarafından yeniden keşfedildi Isaac Newton'un görünüşe ait benzer çalışmaların bilgisi vardı kalmadan, 1666 civarında Albert Girard Bunlar gibi birçok matematiksel alanlarda uygulamalar, var 1629. yılında Galois teorisinin , değişmezler teorisi , grup teorisi , kombinatorik ve hatta genel görelilik gibi matematiksel olmayan alanlarda .
matematiksel ifade
Simetrik polinomlara göre formülasyon
Let x 1 , ..., x n olmak değişkenler; sıfır olmayan herhangi bir doğal sayı için k , k -ths kuvvetlerinin toplamını p k ( x 1 , ..., x n ) ile gösteririz:
pk(x1,...,xdeğil): =∑ben=1değilxbenk=x1k+⋯+xdeğilk{\ displaystyle p_ {k} (x_ {1}, \ ldots, x_ {n}): = \ toplam _ {i = 1} ^ {n} x_ {i} ^ {k} = x_ {1} ^ { k} + \ cdots + x_ {n} ^ {k}}( Newton toplamı denir )
ve için k ≥ 0 , biz ile ifade e k ( X 1 , ..., x , n ) temel simetrik polinom belirgin ürünler toplamıdır K arasında farklı değişkenler n ; yani özellikle
e0(x1,...,xdeğil)=1,e1(x1,...,xdeğil)=x1+x2+⋯+xdeğil,e2(x1,...,xdeğil)=∑1≤ben<j≤değilxbenxj,...edeğil(x1,...,xdeğil)=x1x2⋯xdeğil,ek(x1,...,xdeğil)=0,için k>değil.{\ displaystyle {\ başlangıç {hizalanmış} 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 \ toplam \ limitler _ {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, \ dörtlü {\ metin {for}} \ k> n. \\\ bitiş {hizalanmış}}}Newton kimlikleri daha sonra yazılır:
kek(x1,...,xdeğil)=∑ben=1k(-1)ben-1ek-ben(x1,...,xdeğil)pben(x1,...,xdeğil),{\ displaystyle ke_ {k} (x_ {1}, \ ldots, x_ {n}) = \ toplam _ {i = 1} ^ {k} (- 1) ^ {i-1} e_ {ki} (x_ {1}, \ ldots, x_ {n}) p_ {i} (x_ {1}, \ ldots, x_ {n}),}her şey için gerçek ilişkiler . Böylece k'nin ilk değerleri için elde ederiz :
k∈DEĞİL∗{\ displaystyle k \ in \ mathbb {N} ^ {*}}
e1(x1,...,xdeğil)=p1(x1,...,xdeğil),2e2(x1,...,xdeğil)=e1(x1,...,xdeğil)p1(x1,...,xdeğil)-p2(x1,...,xdeğil),3e3(x1,...,xdeğil)=e2(x1,...,xdeğil)p1(x1,...,xdeğil)-e1(x1,...,xdeğil)p2(x1,...,xdeğil)+p3(x1,...,xdeğil).{\ displaystyle {\ başlangıç {hizalanmış} 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 {hizalanmış}}}Bu bağıntıların biçimi değişkenlerin n sayısına bağlı değildir (ancak n- inci özdeşlikten sonra sol taraf sıfır olur ), bu da onların simetrik polinomlar halkasında özdeşlik olarak belirtilmesine izin verir . Bu halkada, bizde:
e1=p1,2e2=e1p1-p2,3e3=e2p1-e1p2+p3,4e4=e3p1-e2p2+e1p3-p4,{\ displaystyle {\ start {hizalanmış} e_ {1} & = p_ {1}, \\ 2e_ {2} & = e_ {1} p_ {1} -p_ {2}, \\ 3e_ {3} & = e_ {2} p_ {1} -e_ {1} p_ {2} + p_ {3}, \\ 4e_ {4} & = e_ {3} p_ {1} -e_ {2} p_ {2} + e_ {1} p_ {3} -p_ {4}, \\\ end {hizalanmış}}}Ve benzeri ; bu durumda, sol taraf asla iptal etmez.
Bu denklemler, e i'nin p k'nin bir fonksiyonu olarak tümevarım yoluyla ifade edilmesini sağlar ; tersine, onları şu şekilde yeniden yazmak:
p1=e1,p2=e1p1-2e2,p3=e1p2-e2p1+3e3,p4=e1p3-e2p2+e3p1-4e4,vb.{\ displaystyle {\ start {hizalı} 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}, \ dörtlü {\ metin {vb.}} \\\ bitiş {hizalı}}}Biz ifade edebilen p i bir fonksiyonu olarak e k .
Bir polinomun köklerine uygulama
X i bize düşünelim, parametre olarak değil, değişken olarak atılıyor birim polinomu de t kökleri için olan x 1 , ..., x n :
∏ben=1değil(t-xben)=∑k=0değil(-1)kdektdeğil-k,{\ displaystyle \ prod _ {i = 1} ^ {n} \ sol (t-x_ {i} \ sağ) = \ toplam _ {k = 0} ^ {n} (- 1) ^ {k} a_ { k} t ^ {nk},}burada a k katsayıları köklerin temel simetrik polinomları tarafından verilir: a k = e k ( x 1 ,…, x n ) . Köklerin kuvvetlerinin toplamı (ki buna Newton toplamları da diyoruz ), Newton'un özdeşlikleri adım adım uygulanarak polinomun katsayılarının bir fonksiyonu olarak ifade edilebilir:
sk=pk(x1,...,xdeğil)=∑ben=1değilxbenk,{\ displaystyle s_ {k} = p_ {k} (x_ {1}, \ ldots, x_ {n}) = \ toplam _ {i = 1} ^ {n} x_ {i} ^ {k},}
s1=de1,s2=de1s1-2de2,s3=de1s2-de2s1+3de3,s4=de1s3-de2s2+de3s1-4de4,vb.{\ displaystyle {\ başlangıç {hizalanmış} s_ {1} & = a_ {1}, \\ s_ {2} & = a_ {1} s_ {1} -2a_ {2}, \\ s_ {3} & = a_ {1} s_ {2} -a_ {2} s_ {1} + 3a_ {3}, \\ s_ {4} & = a_ {1} s_ {3} -a_ {2} s_ {2} + a_ {3} s_ {1} -4a_ {4}, \ dörtlü {\ metin {vb.}} \\\ bitiş {hizalı}}}
Bir matrisin karakteristik polinomuna uygulama
Önceki paragrafın polinom olduğunda karakteristik polinom a matris A , kökler x i olan özdeğerler ve A (cebirsel çokluğu ile sayılmıştır). Herhangi bir k tamsayı için , A k matrisinin özdeğerleri için xk
i(karşılık gelen çokluklarla birlikte). A k'nin karakteristik polinomunun katsayıları daha sonra bu x kuvvetlerindeki temel simetrik polinomlar tarafından verilir.k
i. Özellikle, x toplamık
iverilir izi arasında bir k : s k = tr ( A k ) .
Newton'un özdeşlikleri, A k'nin ayak izlerini , karakteristik polinom A'nın katsayıları ile birleştirir . Tersine, onları kuvvetler toplamlarından temel simetrik polinomları hesaplamak için kullanarak, bu nedenle A'nın karakteristik polinomunu yalnızca A'nın kuvvetlerini ve izlerini hesaplayarak , sonra bir üçgen denklem sistemini çözerek belirlemeyi mümkün kılarlar. Cayley-Hamilton teoremi sonra sadece ters matris indirilmesine imkan A .
Tüm bu hesaplamalar (etkili bir biçimde yeniden yazılmıştır) 1840'tan kalma Faddeev-Leverrier algoritmasını oluşturur ; bu algoritmanın hızlı bir paralel uygulaması 1976'da Lazslo Csanky'den kaynaklanmaktadır. Bununla birlikte, bölmeler (tamsayılarla) gerektirir ve bu nedenle genel olarak yalnızca karakteristik 0 alanlarında kullanılabilir. Csanky'nin uygulanması, bu çeşitli hesaplamaların ( bu durumda) NC karmaşıklık sınıfında .
Galois teorisi ile ilişkisi
Bir için verilen n , temel simetrik polinomlar e k ( X 1 , ..., x , n ) için k = 1, ..., n, bir “oluşturmak cebirsel temel olarak simetrik polinomların değişmeli cebir” x 1 , ..., x n , yani herhangi bir simetrik polinom, bu temel simetrik polinomların bir polinom fonksiyonu olarak ifade edilir ve bu ifade benzersizdir. Simetrik polinomların temel teoremi adı altında bilinen bu genel sonuç, Newton'un toplamları durumunda (Newton özdeşlikleri kullanılarak) açık hale getirilebilir. Böylece, a k katsayıları parametre olarak kabul edilen birim polinoma uygulandığında , köklerinin herhangi bir polinom fonksiyonu S ( x 1 ,…, x n ) bir polinom fonksiyonu P ( a 1 ,…, a) olarak yazılabilir. n ) katsayılarının tek başına, yani bu kökleri hesaplamaya gerek kalmadan. Bu , a k'yi bir temel alanın öğeleri olarak gören Galois teorisinden de çıkarılabilir ; kökler o zaman bu alanın bir uzantısındadır ve bu uzantının Galois grubu onları tüm simetrik gruba göre değiştirir; bu Galois grubunun tüm elemanları tarafından değişmeyen alan, temel alandır.
tdeğil+∑k=1değil(-1)kdektdeğil-k{\ displaystyle \ textstyle t ^ {n} + \ toplam _ {k = 1} ^ {n} (- 1) ^ {k} a_ {k} t ^ {nk}}
Tersine, Newton'un özdeşlikleri, Newton'un toplamlarının bir fonksiyonu olarak temel simetrik polinomları ifade etmemize ve bu toplamların aynı zamanda simetrik polinomların değişmeli cebirinin "cebirsel temelini" oluşturduğunu göstermemize izin verir.
gösteriler
Her kimlik, basit bir cebirsel hesaplama ile doğrudan doğrulanabilir, ancak genel durum bir gösteri gerektirir. İşte bazı olası yollar:
n = k özel durumundan
K Newton kimliği inci k değişkenlerinin tanımlanması formülde ikame ile elde edilir , e k :
∏ben=1k(t-xben)=∑ben=0k(-1)k-benek-ben(x1,...,xk)tben.{\ displaystyle \ prod _ {i = 1} ^ {k} (t-x_ {i}) = \ toplam _ {i = 0} ^ {k} (- 1) ^ {ki} e_ {ki} (x_ {1}, \ ldots, x_ {k}) t ^ {i}.}İkame x j için t elimizde:
0=∑ben=0k(-1)k-benek-ben(x1,...,xk)xjbeniçin 1≤j≤k.{\ displaystyle 0 = \ toplam _ {i = 0} ^ {k} (- 1) ^ {ki} e_ {ki} (x_ {1}, \ ldots, x_ {k}) {x_ {j}} ^ {i} \ dörtlü {\ metin {için}} 1 \ leq j \ leq k.}j kümesini toplayarak şunu elde ederiz:
0=(-1)kkek(x1,...,xk)+∑ben=1k(-1)k-benek-ben(x1,...,xk)pben(x1,...,xk).{\ displaystyle 0 = (- 1) ^ {k} ke_ {k} (x_ {1}, \ ldots, x_ {k}) + \ toplam _ {i = 1} ^ {k} (- 1) ^ { ki} e_ {ki} (x_ {1}, \ ldots, x_ {k}) p_ {i} (x_ {1}, \ ldots, x_ {k}).}( i = 0'daki terimler toplamdan ayrılır çünkü p 0 genellikle tanımsızdır.)
Bu denklem hemen aranan kimliği verir. n < k değişkene karşılık gelen kimlikler , kalan k - n değişkenleri iptal ederek çıkarılır ; vaka n > k her birinin fark ile tedavi edilir tekterimli daha içermiyor k değişkenleri ve biz iptal edersek bu tekterimli değişmemesini n - k diğer değişkenleri; o zaman bu k değişkene karşılık gelen Newton kimliğini kullanmak yeterlidir .
Resmi serilerin tanımlanmasıyla
Newton'un kimlikleri, resmi kimlik tabanlı manipülasyonlar kullanılarak da elde edilebilir.
∏ben=1değil(t-xben)=∑k=0değil(-1)kdektdeğil-k{\ displaystyle \ prod _ {i = 1} ^ {n} (t-x_ {i}) = \ toplam _ {k = 0} ^ {n} (- 1) ^ {k} a_ {k} t ^ {nk}}Bir birim polinomun köklerini ve katsayılarını birleştirir. Hesaplamaları kolaylaştırmak için, 1 / değiştirilmesi ile başlangıç t için t ve biz çarpın iki üye t , n , elde edilmiştir:
∏ben=1değil(1-xbent)=∑k=0değil(-1)kdektk.{\ displaystyle \ textstyle \ prod _ {i = 1} ^ {n} (1-x_ {i} t) = \ toplam _ {k = 0} ^ {n} (- 1) ^ {k} a_ {k } t ^ {k}.}Değiştirme a i simetrik polinomlarla biz kimlik elde
∑k=0değil(-1)kek(x1,...,xdeğil)tk=∏ben=1değil(1-xbent).{\ displaystyle \ toplam _ {k = 0} ^ {n} (- 1) ^ {k} e_ {k} (x_ {1}, \ ldots, x_ {n}) t ^ {k} = \ ürün _ {i = 1} ^ {n} (1-x_ {i} t).}İle ilgili farklılaşma sonra t ile, ve çarpma t , bu gelir:
∑k=0değil(-1)kkek(x1,...,xdeğil)tk=t∑ben=1değil((-xben)∏j≠ben(1-xjt))=-(∑ben=1değilxbent1-xbent)∏j=1değil(1-xjt)=-(∑ben=1değil∑j=1∞(xbent)j)(∑ℓ=0değil(-1)ℓeℓ(x1,...,xdeğil)tℓ)=(∑j=1∞pj(x1,...,xdeğil)tj)(∑ℓ=0değil(-1)ℓ-1eℓ(x1,...,xdeğil)tℓ),{\ displaystyle {\ başlangıç {hizalanmış} \ toplam _ {k = 0} ^ {n} (- 1) ^ {k} ke_ {k} (x_ {1}, \ ldots, x_ {n}) t ^ { k} & = t \ toplam _ {i = 1} ^ {n} \ sol ((- x_ {i}) \ prod \ nolimits _ {j \ neq i} (1-x_ {j} t) \ sağ) \\ & = - \ sol (\ toplam _ {i = 1} ^ {n} {\ frac {x_ {i} t} {1-x_ {i} t}} \ sağ) \ prod \ limitler _ {j = 1} ^ {n} (1-x_ {j} t) \\ & = - \ sol (\ toplam _ {i = 1} ^ {n} \ toplam _ {j = 1} ^ {\ infty} ( x_ {i} t) ^ {j} \ sağ) \ sol (\ toplam _ {\ ell = 0} ^ {n} (- 1) ^ {\ ell} e _ {\ ell} (x_ {1}, \ ldots, x_ {n}) t ^ {\ ell} \ sağ) \\ & = \ sol (\ toplam _ {j = 1} ^ {\ infty} p_ {j} (x_ {1}, \ ldots, x_ {n}) t ^ {j} \ sağ) \ sol (\ toplam _ {\ ell = 0} ^ {n} (- 1) ^ {\ ell -1} e _ {\ ell} (x_ {1 }, \ ldots, x_ {n}) t ^ {\ ell} \ sağ), \\\ end {hizalanmış}}}Sağdaki polinom öncelikle olarak yeniden yazıldı nerede rasyonel fonksiyonu , daha sonra dönüşmüştür bu bir resmi serinin en t ve her katsayıları t j gruplanmış kuvvetlerinin toplamını (dizi yakınsama aslında sağlanır elde etmek için t biz sadece katsayıları ilgilenen gibi yakın, yeterli uzunlukta sıfıra, ancak t j , yakınlaşma bu soru) gerçek öneme sahiptir. İki üyenin t k katsayılarını karşılaştırarak , şunu elde ederiz:
(-1)kkek(x1,...,xdeğil)=∑j=1k(-1)k-j-1pj(x1,...,xdeğil)ek-j(x1,...,xdeğil){\ displaystyle (-1) ^ {k} ke_ {k} (x_ {1}, \ ldots, x_ {n}) = \ toplam _ {j = 1} ^ {k} (- 1) ^ {kj- 1} p_ {j} (x_ {1}, \ ldots, x_ {n}) e_ {kj} (x_ {1}, \ ldots, x_ {n})},
bu Newton'un k- inci özdeşliğidir.
Kimliklerin teleskopik bir toplamı olarak
Aşağıdaki türetme simetrik polinomlar halkasında formüle edilmiştir , çünkü bu durumda kimlikler değişken sayısına bağlı değildir. Bir için sabit k > 0 ise, tanımlar (2 ≤ için i  k ) simetrik bir fonksiyonu r ( I derece belirgin monomials toplamı olarak) k kuvvete yükseltilmiş bir değişken çarpılması ile elde edilen I tarafından k - ı belirgin diğer değişkenler. Özellikle, içinde r ( k ) = p k ; tek terimlilerin artık özel bir rol oynayan bir değişkeni olmayacağı için r (1) durumu hariç tutulmuştur. Tüm p i e k - i ürünleri r ( j ) ' nin bir fonksiyonu olarak ifade edilebilir ( i = 1 ve i = k uç durumları dışında). Biz elde sol içeren farklı değişkenler katkıda terimler, her bir ürün için, r ( i değişkenleri burada olanlar ise,) p ı daha önce mukabil teriminin değişkenler arasında görünür e k - ı katkı r ( i + 1) ve sağdaki tüm terimler böylece bir kez ve yalnızca bir kez elde edilir. İçin i = k tarafından çarpılarak, e 0 = 1, biz trivially olsun . Son olarak, p 1 e k −1 ( i = 1'e karşılık gelir) çarpımı , i < k'nin diğer değerlerinde olduğu gibi r ( i + 1) = r (2)'ye katkılar getirir , ancak kalan katkılar k'ye eşittir. değişkenlerin her biri p 1 faktöründen gelebileceğinden , e k'nin her bir tek terimlisinin çarpımı ; ayrıca .
pbenek-ben=r(ben)+r(ben+1)için 1<ben<k{\ displaystyle p_ {i} e_ {ki} = r (i) + r (i + 1) \ dörtlü {\ metin {için}} 1 <i <k}pke0=pk=r(k){\ displaystyle p_ {k} e_ {0} = p_ {k} = r (k) \,}p1ek-1=kek+r(2){\ displaystyle p_ {1} e_ {k-1} = ke_ {k} + r (2)}
Daha sonra k- th Newton kimliği, teleskopik bir toplam olan denklemlerin alternatif toplamı alınarak elde edilir . r ( i ) formunun tüm terimleri kaybolur.
benzer kimlikler
Benzer kimliklere sahip ve Newton'un kimlikleriyle yakından ilişkili birçok aile mevcuttur.
Tamamen homojen simetrik polinomların kullanımı
Kaydeden h k tamamen homojen simetrik polinomu (tr) derecesi olan bütün monomiyallerin toplamını demek ki, k , güçlerin toplamları görev süreleri hepsi pozitif Newton olanlar, ancak benzer kimlikler karşılamaktadır. Gelen simetrik polinomların halka , yazıldıkları herkes için,
k Newton kimliklere ≥ 1. aksine, sol üyesi için ortadan yok k yeterince büyük ve sağ üyelerin sıfır olmayan terimlerin sayısı süresiz büyür. k'nin ilk değerleri için ,
khk=∑ben=1khk-benpben,{\ displaystyle kh_ {k} = \ toplam _ {i = 1} ^ {k} h_ {ki} p_ {i},}
h1=p1,2h2=h1p1+p2,3h3=h2p1+h1p2+p3.{\ displaystyle {\ başlangıç {hizalanmış} 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 {hizalanmış}}}Bu ilişkiler, biçimsel seriler kullanılarak, ancak üreten işlevler arasındaki özdeşlik kullanılarak, yukarıda verilene benzer bir argümanla gösterilebilir :
∑k=0∞hk(X1,...,Xdeğil)tk=∏ben=1değil11-Xbent{\ displaystyle \ toplam _ {k = 0} ^ {\ infty} h_ {k} (X_ {1}, \ ldots, X_ {n}) t ^ {k} = \ prod _ {i = 1} ^ { n} {\ frac {1} {1-X_ {i} t}}}.
Öte yandan daha önce verilen diğer gösterimler bu yeni kimliklere kolay kolay uyum sağlayamıyor.
Newton toplamlarının bir fonksiyonu olarak temel simetrik polinomların ifadesi
Söylediğimiz gibi, Newton'un özdeşlikleri, Newton toplamlarının bir fonksiyonu olarak temel simetrik polinomların tümevarım yoluyla ifade edilmesini sağlar. Bu, tamsayılara bölme gerektirir ve bu nedenle yalnızca rasyonel katsayılı simetrik polinomların Λ Q halkasında yapılabilir :
e1=p1,e2=12p12-12p2=12(p12-p2),e3=16p13-12p1p2+13p3=16(p13-3p1p2+2p3),e4=124p14-14p12p2+18p22+13p1p3-14p4=124(p14-6p12p2+3p22+8p1p3-6p4),{\ displaystyle {\ start {hizalanmış} 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} && = \ metin stili {\ 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}), \\\ end {hizalanmış}}}Ve benzeri. Üniter polinom, bu formüller, her değiştirerek köklerinin güçlerin toplamları bir fonksiyonu olarak katsayıları ifade E'yi i ile bir i ve her bir p , k ile s k .
Newton toplamlarının bir fonksiyonu olarak tamamen homojen simetrik polinomların ifadesi
Tamamen homojen simetrik polinomlarla ilgili benzer ilişkiler aynı şekilde gelişir ve denklemlere yol açar:
h1=p1,h2=12p12+12p2=12(p12+p2),h3=16p13+12p1p2+13p3=16(p13+3p1p2+2p3),h4=124p14+14p12p2+18p22+13p1p3+14p4=124(p14+6p12p2+3p22+8p1p3+6p4), vb.{\ displaystyle {\ start {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} && = \ metin stili {\ 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}), {\ metin {vb.}} \\\ end {hizalanmış}}}tüm terimlerin pozitif olduğu yer. Bu ifadeler tam olarak karşılık döngüleri göstergeleri Newton toplamları yorumlayarak simetrik grupların, polinomlar p i değişkenli: a monomial katsayısı p 1 m 1 p 2 m 2 ... p l m l ekspresyonunda h k m 1 sabit nokta, m 2 döngü uzunluğu 2,… ve m l uzunluk l döngüye sahip k'nin tüm permütasyonlarının oranına eşittir . Daha doğrusu bu katsayı 1 / N ile ; N , karşılık gelen döngü tipine sahip sabit bir permütasyon π ile permütasyon sayısıdır. Temel simetrik fonksiyonlara karşılık gelen ifadeler, aynı mutlak değerlere sahip katsayılara sahiptir, ancak π imzasına eşittir , yani (-1) m 2 + m 4 +… .DEĞİL=Πben=1ben(mben!benmben){\ displaystyle N = \ Pi _ {i = 1} ^ {l} (m_ {i}! \, ben ^ {m_ {i}})}
Newton toplamlarının ifadesi
Tersine, Newton'un toplamlarını temel simetrik polinomların bir fonksiyonu olarak ifade edebiliriz ve bu ifadelerin tamsayı katsayıları vardır:
p1=e1,p2=e12-2e2,p3=e13-3e2e1+3e3,p4=e14-4e2e12+4e3e1+2e22-4e4,p5=e15-5e2e13+5e22e1+5e3e12-5e3e2-5e4e1+5e5,p6=e16-6e2e14+9e22e12+6e3e13-2e23-12e3e2e1-6e4e12+3e32+6e4e2+6e1e5-6e6, vb.{\ displaystyle {\ start {hizalı} 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_ {2} ^ {2} e_ {1} + 5e_ {3} e_ {1} ^ {2} -5e_ {3} e_ {2} -5e_ {4} e_ {1} + 5e_ {5}, \\ p_ {6} & = e_ {1} ^ {6} -6e_ {2} e_ {1} ^ {4} + 9e_ {2} ^ {2} e_ {1} ^ {2 } + 6e_ {3} e_ {1} ^ {3} -2e_ {2} ^ {3} -12e_ {3} e_ {2} e_ {1} -6e_ {4} e_ {1} ^ {2} + 3e_ {3} ^ {2} + 6e_ {4} e_ {2} + 6e_ {1} e_ {5} -6e_ {6}, {\ metin {vb.}} \\\ end {hizalanmış}}}ancak bu ifadeler açık bir kurala uymuyor gibi görünüyor. Bununla birlikte , p k ifadesindeki bir tek terimlinin katsayısının, yukarıda verilen e k ifadesindeki karşılık gelen ürünün katsayısı ile aynı işarete sahip olduğunu görüyoruz , yani (-1) m 2 + m 4 +… . Ayrıca, M katsayısının mutlak değeri , çarpımı M olan temel simetrik polinomların dizileri kümesi üzerinden, her dizinin son polinomunun indeksinin toplamıdır : böylece, e 1 5 e 3 katsayısı e 4 3 veren ifade p 20 olan beş faktör belirgin emirler arasındaki yana e 1 , tek bir faktör e 3 ve üç faktör e 4 , orada sona eren 280 olan e 1 56 biten, e 3 , 168 ile biten e 4 .
M=Πben=1benebenmben{\ displaystyle M = \ Pi _ {i = 1} ^ {l} e_ {i} ^ {m_ {i}}} Πben=1benpbenmben{\ displaystyle \ Pi _ {i = 1} ^ {l} p_ {i} ^ {m_ {i}}} (-1)0+3(280×1+56×3+168×4)=-1120{\ displaystyle (-1) ^ {0 + 3} (280 \ kere 1 + 56 \ kere 3 + 168 \ kere 4) = - 1120}
Son olarak, tamamen homojen polinomlarla ilgili kimlikler de tersine çevrilebilir, bu da aşağıdakilere yol açar:
p1=+h1,p2=-h12+2h2,p3=+h13-3h2h1+3h3,p4=-h14+4h2h12-4h3h1-2h22+4h4,p5=+h15-5h2h13+5h22h1+5h3h12-5h3h2-5h4h1+5h5,p6=-h16+6h2h14-9h22h12-6h3h13+2h23+12h3h2h1+6h4h12-3h32-6h4h2-6h1h5+6h6, vb.{\ displaystyle {\ start {hizalanmış} 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}, {\ text {etc.}} \\\ end {hizalı}}}Bu kimlikler, işaret dışında, öncekilerle tamamen aynı forma sahiptir: tek terimlinin işareti şimdi - (- 1) m 1 + m 2 + m 3 +… .
Πben=1benhbenmben{\ displaystyle \ Pi _ {i = 1} ^ {l} h_ {i} ^ {m_ {i}}}
Belirleyici olarak ifadeler
Lineer denklem sistemlerinin çözümüne karşılık gelen önceki ifadeler , Cramer kuralı kullanılarak determinantların yardımıyla açıkça formüle edilebilir . Örneğin, Newton'un kimliklerini şu şekilde yazmak:
e1=1p1,2e2=e1p1-1p2,3e3=e2p1-e1p2+1p3,⋮=⋮değiledeğil=edeğil-1p1-edeğil-2p2+⋯+(-1)değile1pdeğil-1+(-1)değil-1pdeğil,{\ displaystyle {\ start {hizalı} 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 & = \ 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}, \\ \ bitiş {hizalanmış}}}ve , , , ... alarak ve bilinmeyen olarak ona ulaşırız:
p1{\ görüntü stili p_ {1}}-p2{\ görüntü stili {-p_ {2}}}p3{\ görüntü stili p_ {3}}(-1)değilpdeğil-1{\ görüntü stili (-1) ^ {n} p_ {n-1}}pdeğil{\ görüntü stili p_ {n}}
pdeğil=|10⋯e1e110⋯2e2e2e113e3⋮⋱⋱⋮edeğil-1⋯e2e1değiledeğil||10⋯e110⋯e2e11⋮⋱⋱edeğil-1⋯e2e1(-1)değil-1|=1(-1)değil-1|10⋯e1e110⋯2e2e2e113e3⋮⋱⋱⋮edeğil-1⋯e2e1değiledeğil|=|e110⋯2e2e110⋯3e3e2e11⋮⋱⋱değiledeğiledeğil-1⋯e1|.{\ displaystyle p_ {n} = {\ frac {\ başlangıç {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}} {\ başlangıç {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}}} = {\ frac {1} {(- 1) ^ {n-1}}} {\ başlangıç {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} \ bitiş {vmatrix}} = {\ başlangıç {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} \ bitiş {vmatrix}}. }Hesaplamalar, tamamen homojen simetrik polinomların bir fonksiyonu olarak ifadeler için benzerdir (ancak biraz daha karmaşıktır) ; sonunda şunu elde ederiz:
edeğil{\ görüntü stili e_ {n}}
edeğil=1değil!|p110⋯p2p120⋯⋮⋱⋱pdeğil-1pdeğil-2⋯p1değil-1pdeğilpdeğil-1⋯p2p1|,pdeğil=(-1)değil-1|h110⋯2h2h110⋯3h3h2h11⋮⋱⋱değilhdeğilhdeğil-1⋯h1|,hdeğil=1değil!|p1-10⋯p2p1-20⋯⋮⋱⋱pdeğil-1pdeğil-2⋯p11-değilpdeğilpdeğil-1⋯p2p1|.{\ displaystyle e_ {n} = {\ frac {1} {n!}} {\ başlangıç {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}}, \ qquad p_ {n} = (- 1) ^ {n-1} {\ başlangıç {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 }}, \ qquad h_ {n} = {\ frac {1} {n!}} {\ başlangıç {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} \ bitiş {vmatrix}}.}Biz, formül fark edilebilir h n olduğu alarak elde kalıcı için matris e n için bir ifade bu daha genel olarak bunun yerine determinantının ve herhangi bir Schur polinom alarak elde edilebilir gelen immanant Bu matrisin.
Notlar ve referanslar
(fr) Bu makale kısmen veya tamamen alınır
İngilizce Vikipedi başlıklı makalesinde
" Newton'un kimlikleri " ( yazarların listesini görmek ) .
-
(tr) L. Csanky , " Hızlı Paralel matris ters çevirme algoritmaları " , SIAM J. Comput. , cilt. 5, n o 4,Aralık 1976( çevrimiçi okuyun [PDF] ).
-
(in) DG Mead , " Newton's Identities " , American Mathematical Monthly , Mathematical Association of America, cilt. 99-8,1992, s. 749–751 ( DOI 10.2307 / 2324242 , JSTOR 2324242 ).
-
(in) Ian G. Macdonald , Simetrik fonksiyonlar ve Hall polinomları , Oxford, Clarendon Press, Oxford University Press, col. "Oxford Matematiksel Monografları",1979, viii + 180 s. ( ISBN 0-19-853530-9 , Matematik İncelemeleri 84g: 05003 ) , s. 20.
-
(içinde) Dudley E. Littlewood , Grup karakterleri teorisi ve grupların matris temsilleri , Oxford, Oxford University Press ,1950, viii + 310 s. ( ISBN 0-8218-4067-3 ) , s. 84.
Şuna da bakın:
İlgili Makaleler
bibliyografya
- (tr) Jean-Pierre Tignol, Galois' cebirsel denklemler teorisi , Singapur, World Scientific ,2001, 333 s. ( ISBN 978-981-02-4541-2 , çevrimiçi okuyun )
- (tr) F. Bergeron, G. Labelle ve P. Leroux, Kombinatoryal türler ve ağaç benzeri yapılar , Cambridge, Cambridge University Press ,1998, 457 s. ( ISBN 978-0-521-57323-8 , çevrimiçi okuyun )
- (tr) Peter J. Cameron , Permütasyon Grupları , Cambridge , Cambridge University Press ,1999, 220 s. ( ISBN 978-0-521-65378-7 , çevrimiçi okuyun )
- (tr) David A. Cox , John Little et Don O'Shea , İdealler, Çeşitler ve Algoritmalar: hesaplamalı cebirsel geometri ve değişmeli cebire giriş , New York, Springer-Verlag ,2007, 3 e ed. ( ISBN 978-0-387-35651-8 , çevrimiçi okuyun )
-
(tr) David Eppstein ve Michael T. Goodrich (tr) , “Newton kimlikleri ve ters çevrilebilir Bloom filtreleri aracılığıyla gidiş-dönüş veri akışlarında alan açısından verimli dağınık tanımlama” , Algorithms and Data Structures , 10th International Workshop, WADS 2007 , Springer , kol. "Bilgisayar Bilimi Ders Notları" ( n o 4619),2007, s. 637-648, “ 0704.3313 ” , ücretsiz erişim metni, arXiv üzerinde .
- (tr) IG Macdonald , Simetrik fonksiyonlar ve Hall polinomları , New York, Oxford Science Publications. Clarendon Press, Oxford University Press, col. "Oxford Matematiksel Monografları",1995, İkinci baskı. ( ISBN 0-19-853489-2 , Matematik İncelemeleri 96h: 05207 ) , x + 475
- (tr) Richard P. Stanley , Enumerative Combinatorics , cilt. 2 [ baskıların detayı ] ( çevrimiçi sunum )
- (tr) Bernd Sturmfels , Değişmez Teoride Algoritmalar , New York, Springer-Verlag ,1992( ISBN 978-0-387-82445-1 )
- (tr) Alan Tucker, Applied Combinatorics , New York, Wiley ,1980, 5. baskı. , 476 s. ( ISBN 978-0-471-73507-6 )
Dış bağlantılar
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">