У математици, Њутнови идентитети, такође познати и као Жирар-Њутнове формуле, дају односе између два типа симетричних полинома, односно између сума степена и елементарних симетричних полинома. Вредновани у коренима моничног полинома у једној променљивој, они омогућавају изражавање сума -тих степена свих корена полинома (рачунајући са њиховом вишеструкошћу) преко коефицијената од , без стварног проналажења тих корена. Ове идентитете пронашао је Исак Њутн око 1666. године, очигледно не знајући за ранији рад (1629) Алберта Жирара. Имају примену у многим областима математике, укључујући теорију Галоа, теорију инваријанти, теорију група, комбинаторику, као и даље примене ван математике, укључујући општу теорију релативности.
Математички исказ
Формулација преко симетричних полинома Нека су променљиве, означимо за са -ту суму степена:
и за означимо са елементарни симетрични полином (односно, збир свих различитих производа различитих променљивих), тако да је
Тада се Њутнови идентитети могу исказати као
што важи за све , где је лева страна нула за .
Конкретно, за првих неколико вредности добија се:
Облик и валидност ових једначина не зависе од броја променљивих (иако тачка у којој лева страна постаје 0 зависи, наиме након -тог идентитета), што омогућава њихово исказивање као идентитета у прстену симетричних функција. У том прстену важи
и тако даље; овде леве стране никада не постају нула. Ове једначине омогућавају да се рекурзивно изразе преко ; да би се урадило обрнуто, оне се могу преписати као
У општем случају, имамо
што важи за све .
Такође, важи
за све .
Примена на корене полинома Полином са коренима може се развити као
где су коефицијенти горе дефинисани симетрични полиноми. Узевши у обзир суме степена корена
коефицијенти полинома са коренима могу се изразити рекурзивно преко сума степена као
Формулисање полинома на овај начин је корисно при коришћењу методе Делвса и Лајнеса за проналажење нула аналитичке функције.
Примена на карактеристични полином матрице Када је горњи полином карактеристични полином матрице (нарочито када је пратећа матрица полинома), корени су сопствене вредности матрице, рачунајући њихову алгебарску вишеструкост. За било који позитиван цео број , матрица има као сопствене вредности степене , а свака сопствена вредност од доприноси својом вишеструкошћу вишеструкости сопствене вредности од . Тада су коефицијенти карактеристичног полинома матрице дати елементарним симетричним полиномима у тим степенима . Посебно, збир , што је -та сума степена корена карактеристичног полинома од , дата је његовим трагом:
Њутнови идентитети сада повезују трагове степена са коефицијентима карактеристичног полинома од . Користећи их обрнуто да би се елементарни симетрични полиноми изразили преко сума степена, они се могу искористити за проналажење карактеристичног полинома израчунавањем само степена и њихових трагова.
Ово израчунавање захтева рачунање трагова степена матрице и решавање троугаоног система једначина. Оба се могу урадити у класи сложености NC (решавање троугаоног система може се урадити методом завади па владај). Стога се карактеристични полином матрице може израчунати у NC класи. Према Кејли-Хамилтоновој теореми, свака матрица задовољава свој карактеристични полином, а једноставна трансформација омогућава проналажење адјуговане матрице у NC класи.
Преуређивање израчунавања у ефикасан облик доводи до Фадејев-Леверијеовог алгоритма (1840), чију је брзу паралелну имплементацију развио Л. Чанки (1976). Његов недостатак је што захтева дељење целим бројевима, тако да поље генерално треба да има карактеристику 0.
Веза са теоријом Галоа За дато , елементарни симетрични полиноми за формирају алгебарску базу за простор симетричних полинома по : сваки полиномски израз по који је инваријантан под свим пермутацијама тих променљивих дат је полиномским изразом у тим елементарним симетричним полиномима, и тај израз је јединствен до на еквиваленцију полиномских израза. Ово је општа чињеница позната као Основна теорема симетричних полинома, а Њутнови идентитети пружају експлицитне формуле у случају симетричних полинома сума степена. Примењено на монични полином са свим коефицијентима посматраним као слободним параметрима, ово значи да се сваки симетрични полиномски израз у његовим коренима може изразити као полиномски израз само преко његових коефицијената, другим речима без потребе за познавањем корена. Ова чињеница такође произилази из општих разматрања у теорији Галоа (где се посматрају као елементи основног поља са коренима у проширењу поља чија их Галоа група пермутује у складу са пуном симетричном групом, а поље које је фиксно под свим елементима Галоа групе је основно поље).
Њутнови идентитети такође омогућавају изражавање елементарних симетричних полинома преко симетричних полинома сума степена, показујући да се сваки симетрични полином може изразити и преко сума степена. Заправо, првих сума степена такође формира алгебарску базу за простор симетричних полинома.
Сродни идентитети Постоји низ (породица) идентитета који су веома уско повезани са Њутновим идентитетима, иако их треба разликовати од њих.
Варијанта са комплетним хомогеним симетричним полиномима Означавајући са комплетни хомогени симетрични полином (односно, збир свих монома степена ), полиноми сума степена такође задовољавају идентитете сличне Њутновим идентитетима, али без знакова минус. Исказани као идентитети у прстену симетричних функција, они гласе
што важи за све . За разлику од Њутнових идентитета, леве стране не постају нула за велико , а десне стране садрже све више не-нултих чланова. За првих неколико вредности , важи
Изражавање елементарних симетричних полинома преко сума степена Као што је поменуто, Њутнови идентитети могу се користити за рекурзивно изражавање елементарних симетричних полинома преко сума степена. Ово захтева увођење целобројних именилаца, тако да се може урадити у прстену симетричних функција са рационалним коефицијентима:
и тако даље.Напомена, коефицијенти тежинских производа у збиру датом горњим идентитетом повезани су са M2 бројевима у Одељку 26.4 DLMF-а и/или коефицијентима укљученим у развоје Фа ди Брунове формуле. Општа формула може се згодно изразити као
где је комплетни експоненцијални Белов полином. Овај израз такође води до следећег идентитета за функције генератрисе:
Примењене на монични полином, ове формуле изражавају коефицијенте преко сума степена корена: свако заменити са , а свако са .
Изражавање комплетних хомогених симетричних полинома преко сума степена Аналогне релације које укључују комплетне хомогене симетричне полиноме могу се слично развити, дајући једначине
и тако даље, у којима се појављују само знакови плус. Преко комплетног Беловог полинома,
Ови изрази тачно одговарају полиномима индекса циклуса симетричних група, ако се суме степена тумаче као неодређене: коефицијент у изразу за било ког монома једнак је уделу свих пермутација од које имају фиксних тачака, циклуса дужине 2, …, и циклуса дужине . Експлицитно, овај коефицијент се може записати као где је ; ово је број пермутација које комутирају са било којом датом пермутацијом датог типа циклуса. Изрази за елементарне симетричне функције имају коефицијенте са истом апсолутном вредношћу, али са знаком једнаким знаку од , наиме .
То се може доказати разматрањем следећег индуктивног корака:
По аналогији са извођењем функције генератрисе од , такође можемо добити функцију генератрису од , преко сума степена, као:
Ова функција генератриса је дакле плетистички експоненцијал од .
Изражавање сума степена преко елементарних симетричних полинома Њутнови идентитети се такође могу користити за изражавање сума степена преко елементарних симетричних полинома, што не уводи имениоце:
Прве четири формуле добио је Алберт Жирар 1629. године (дакле, пре Њутна).
Општа формула (за све позитивне целе бројеве ) гласи:
Ово се згодно може исказати преко обичних Белових полинома као
или еквивалентно као функција генератриса:
што је аналогно Беловом полиномском експоненцијалном генератору датом у претходном пододељку.
Горња формула вишеструког сумирања може се доказати разматрањем следећег индуктивног корака:
Изражавање сума степена преко комплетних хомогених симетричних полинома Коначно, варијанта идентитета која укључује комплетне хомогене симетричне полиноме може се слично користити за изражавање сума степена преко њих:
и тако даље. Осим замене сваког одговарајућим , једина промена у односу на претходну породицу идентитета је у знаковима чланова, који у овом случају зависе само од броја присутних фактора: знак монома је . Посебно, горњи опис апсолутне вредности коефицијената важи и овде.
Општа формула (за све ненегативне целе бројеве ) гласи:
Изрази преко детерминанти Могу се добити експлицитне формуле за горње изразе у облику детерминанти, тако што се првих Њутнових идентитета (или њихових пандана за комплетне хомогене полиноме) посматрају као линеарне једначине у којима су елементарне симетричне функције познате, а суме степена непознате (или обрнуто), и примени се Крамерово правило за проналажење решења за коначну непознату. На пример, узимајући Њутнове идентитете у облику
сматрамо и за непознате, и решавамо за последњу, дајући
Решавање за уместо за је слично, као и аналогна израчунавања за комплетне хомогене симетричне полиноме; у сваком случају, детаљи су нешто сложенији од коначних резултата, који су (Macdonald 1979, стр. 20):
Треба приметити да коришћење детерминанти доводи до тога да формула за има додатне знаке минус у поређењу са оном за , док је ситуација за развијени облик дат раније супротна. Како је приметио (Littlewood 1950, стр. 84), формула за може се алтернативно добити узимањем перманенте матрице за уместо детерминанте, а генералније, израз за било који Шуров полином може се добити узимањем одговарајућег имананта ове матрице.
Извођење идентитета Сваки од Њутнових идентитета може се лако проверити помоћу елементарне алгебре; међутим, за њихову општу валидност потребан је доказ. Овде су наведена нека могућа извођења.
Докази помоћу функција генератриса Можемо приказати односе између , , и преко функција генератриса
E и H Једнакост коефицијената уз са обе стране једначине даје нам да
где користимо предност чињенице да је за , и где је Кронекер делта функција, која је 1 када је и 0 у супротном. То јест, збир на левој страни једнак је нули, осим у тривијалном случају када је .
E и P Једначина
даје нам
а једнакост коефицијената уз са обе стране те једначине даје
где смо искористили да је .
Други однос се може пронаћи вишеструким диференцирањем десне стране једначине
да бисмо добили њен Тејлоров ред око ; њен -ти члан једнак је .
H и P Убацивањем
у однос између и добијамо
а једнакост коефицијената уз са обе стране те једначине даје
Као телескопски збир идентитета симетричних функција Следеће извођење, дато у суштини у (Mead, 1992), формулисано је у прстену симетричних функција ради јасноће (сви идентитети су независни од броја променљивих). Фиксирајмо неко и дефинишимо симетричну функцију за као збир свих различитих монома степена добијених множењем једне променљиве степеноване на са различитих других променљивих (ово је мономна симетрична функција где је облик куке . Посебно важи ; за опис би одговарао опису , али је овај случај искључен јер овде мономи више немају ниједну истакнуту променљиву. Сви производи могу се изразити преко , при чему су први и последњи случај донекле посебни. Имамо
зато што сваки производ чланова на левој страни који укључује различите променљиве доприноси , док они где се променљива из већ јавља међу променљивама члана из доприносе , а сви чланови на десној страни добијају се тачно једном. За множимо са , што тривијално даје
Коначно, производ за даје доприносе као и за остале вредности , али преостали доприноси производе пута сваки моном од , јер било која од променљивих може доћи из фактора ; према томе