Кіріспе
Күштер қосындысы мен элементарлы симметриялық функциялар арасындағы қатынастар. Математикада Ньютонның өзіндіктері, сондай-ақ Жирард-Ньютон формулалары деп аталатын бұл қатынастар, симметриялық көпмүшелердің екі түрін – күштер қосындысын және элементарлы симметриялық көпмүшелерді байланыстырады. Бір айнымалыдағы мономиялық көпмүше түбірлерінде есептелгенде, олар P көпмүшесінің барлық түбірлерінің k-шы дәрежелерінің қосындысын (көбейтілісімен есептегенде) P көпмүшесінің коэффициенттері арқылы, тікелей түбірлерді табусыз көрсетуге мүмкіндік береді. Бұл өзіндіктерді Исаак Ньютон 1666 жыл шамасында тапқан, бірақ Альберт Жирардтың бұрынғы жұмысын (1629 жыл) білмеген көрінеді. Олар математиканың көптеген салаларында, соның ішінде Галуа теориясы, инварианттар теориясы, топтар теориясы, комбинаторика және математикадан тыс, мысалы, жалпы салыстырмалылық теориясында қолданылады.
In mathematics, Newton's identities, also known as the Girard–Newton formulae, give relations between two types of symmetric polynomials, namely between power sums and elementary symmetric polynomials. Evaluated at the roots of a monic polynomial P in one variable, they allow expressing the sums of the k th powers of all roots of P (counted with their multiplicity) in terms of the coefficients of P, without actually finding those roots. These identities were found by Isaac Newton around 1666, apparently in ignorance of earlier work (1629) by Albert Girard. They have applications in many areas of mathematics, including Galois theory, invariant theory, group theory, combinatorics, as well as further applications outside mathematics, including general relativity.
Матрицаның сипаттамалық көптік атауына қолдану
Жоғарыдағы полиномиал матрицаның сипаттамалық полиномиалы болғанда (әсіресе, егер ол полиномиалдың серік матрицасы болса), түбірлер матрицаның өзіндік мәндері болып табылады, олар алгебралық қиылысымен есептеледі. Кез келген оң бүтін сан үшін матрицаның өзіндік мәндері осы санның дәрежелері болып табылады, және матрицаның әрбір өзіндік мәні оның қиылысын осы дәрежелердің өзіндік мәнінің қиылысына қосады. Осыдан кейін, сипаттамалық полиномиалдың коэффициенттері осы дәрежелердегі элементарлы симметриялық полиномдар арқылы беріледі. Атап айтқанда, дәрежелердің қосындысы, яғни сипаттамалық полиномиалдың түбірлерінің n-ші дәрежелік қосындысы, оның ізбен беріледі: Ньютон теңдестіктері енді дәрежелердің іздерін сипаттамалық полиномиалдың коэффициенттерімен байланыстырады. Оларды кері бағытта қолданып, элементарлы симметриялық полиномдарды дәрежелік қосындылар арқылы өрнектеуге болады, бұл сипаттамалық полиномиалды тек дәрежелерді және олардың іздерін есептеу арқылы табуға мүмкіндік береді. Бұл есептеу үшін матрицалық дәрежелердің іздерін есептеу және үшбұрышты теңдеулер жүйесін шешу қажет. Екеуі де күрделілік класы NC-де орындалуы мүмкін (үшбұрышты жүйені бөліп-бағындыру әдісімен шешуге болады). Сондықтан матрицаның сипаттамалық полиномиалын NC класында есептеуге болады. Кейли-Гамильтон теоремасы бойынша, әрбір матрица өзінің сипаттамалық полиномиалын қанағаттандырады, ал қарапайым түрлендіру NC класында серік матрицаны табуға мүмкіндік береді. Есептеулерді тиімді түрде қайта құру Faddeev-LeVerrier алгоритміне (1840) әкеледі, оның жылдам параллельдік іске асырылуы L. Csanky (1976) еңбегіне байланысты. Оның кемшілігі - ол бүтін сандарға бөлуді талап етеді, сондықтан, әдетте, өрістің сипаттамасы 0 болуы керек.
The Newton identities now relate the traces of the powers to the coefficients of the characteristic polynomial of Using them in reverse to express the elementary symmetric polynomials in terms of the power sums, they can be used to find the characteristic polynomial by computing only the powers and their traces. This computation requires computing the traces of matrix powers and solving a triangular system of equations. Both can be done in complexity class NC (solving a triangular system can be done by divide and conquer). Therefore, characteristic polynomial of a matrix can be computed in NC. By the Cayley–Hamilton theorem, every matrix satisfies its characteristic polynomial, and a simple transformation allows to find the adjugate matrix in NC. Rearranging the computations into an efficient form leads to the Faddeev–LeVerrier algorithm (1840), a fast parallel implementation of it is due to L. Csanky (1976). Its disadvantage is that it requires division by integers, so in general the field should have characteristic 0.
Галуа теориясымен байланысы
Берілген n үшін, k = 1, ..., n үшін элементарлы симметриялық көпмүшелер ek(x1, ..., xn) x1, ..., xn айнымалыларындағы симметриялық көпмүшелер кеңістігінің алгебралық негізін құрайды: осы айнымалылардың барлық пермутацияларында өзгермейтін xi-дегі әрбір көпмүшелік өрнек сол элементарлы симметриялық көпмүшелер арқылы беріледі, және бұл өрнек көпмүшелік өрнектердің эквиваленттілігіне дейін бірегей. Бұл симметриялық көпмүшелердің негізгі теоремасы деп аталатын жалпы факт, ал Ньютонның теңдестіктері күштердің қосындысы симметриялық көпмүшелер жағдайында нақты формулаларды ұсынады. Барлық коэффициенттері ak еркін параметрлер ретінде қарастырылатын мономиялық көпмүшеге қолданғанда, бұл әрбір симметриялық көпмүшелік өрнек S(x1, ..., xn) оның түбірлерінде тек оның коэффициенттері арқылы, яғни түбірлерді білуді қажет етпей, P(a1, ..., an) түріндегі көпмүшелік өрнек ретінде өрнектеле алады. Бұл факт Галуа теориясындағы жалпы қарастырулардан да туындайды (ak-лар толық симметриялық топқа сәйкес оларды ауыстыратын кеңейту өрісінде түбірі бар базалық өрістің элементтері ретінде қарастырылады, ал Галуа тобының барлық элементтері бойынша бекітілген өріс базалық өріс болып табылады). Ньютонның теңдестіктері элементарлы симметриялық көпмүшелерді күштердің қосындысы симметриялық көпмүшелер арқылы өрнектеуге мүмкіндік береді, осылайша кез келген симметриялық көпмүше күштердің қосындысы түрінде де өрнектеле алады. Шындығында, алғашқы n күштердің қосындысы симметриялық көпмүшелер кеңістігінің алгебралық негізін құрайды.
Қатынасты сәйкестіктер
Ньютонның өрнектерінен ерекшеленетін, бірақ олармен тығыз байланысты бірнеше (өрнектер) тобы бар.
Элементарлы симметриялық көптіктерді күштер қосындысы түрінде көрсету
Жоғарыда айтылғандай, Ньютонның өзара байланыстары элементарлы симметриялық көпшелерді қуаттардың қосындысы арқылы рекурсивті түрде өрнектеуге қолданылуы мүмкін. Мұны істеу үшін бүтін сан бөлшектерін енгізу қажет, сондықтан оны рационалды коэффициенттері бар симметриялық функциялардың ΛQ сақинасында жасауға болады: және т.б. Жалпы формула мына түрде ыңғайлы жазылуы мүмкін:
and so forth. The general formula can be conveniently expressed as
where the Bn is the complete exponential Bell polynomial. This expression also leads to the following identity for generating functions:
Applied to a monic polynomial, these formulae express the coefficients in terms of the power sums of the roots: replace each ei by ai and each pk by sk.
мұнда Bn – толық экспоненциалды Белл көпшесі. Бұл өрнек сондай-ақ генераторлық функциялар үшін келесі тепе-теңдікке әкеледі:
and so forth. The general formula can be conveniently expressed as
where the Bn is the complete exponential Bell polynomial. This expression also leads to the following identity for generating functions:
Applied to a monic polynomial, these formulae express the coefficients in terms of the power sums of the roots: replace each ei by ai and each pk by sk.
Моник көпшеге қолданғанда, бұл формулалар коэффициенттерді түбірлердің қуаттарының қосындысы түрінде көрсетеді: әр ei-ді ai-мен және әр pk-ді sk-мен алмастырыңыз.
and so forth. The general formula can be conveniently expressed as
where the Bn is the complete exponential Bell polynomial. This expression also leads to the following identity for generating functions:
Applied to a monic polynomial, these formulae express the coefficients in terms of the power sums of the roots: replace each ei by ai and each pk by sk.
Бiрлiктiлiктердiң алынуы
Ньютонның әрбір өрнегі элементар алгебра арқылы оңай тексеріледі; бірақ, олардың жалпы жарамдылығын дәлелдеу қажет. Мүмкін болатын мынадай түсіндірулер.