1611672535-7205ee7fb92cecd63cdae109c575108c (Пожидаев - Лекции), страница 20

Говорят, что многочлены fi и fj допускаюткомпозицию, если (fi )C и (fj )C одновременно делятся на некоторыйодночлен g 6∈ F .Если fi , fj ∈ I допускают композицию, т. е. (fi )C = wq1 , (fj )C =wq2 , то рассмотрим их композицию, т. е. многочлен S(fi , fj ) = fi q2 −fj q1 ∈ I. Редуцируем S(fi , fj ) с помощью базиса к элементу S̄(fi , fj ).Если S̄(fi , fj ) = 0, то говорим, что композиция тривиальна, иначеприсоединяем S̄(fi , fj ) := fm+1 к базису f1 , . . . , fm .Упражнение. Если Н.О.Д.

(fC , gC ) = 1, то S(f, g) := f gC − gfCредуцируется к нулю при помощи f, g. В этом случае также говорим,что композиция f и g также тривиальна.Лемма 3. Пусть fi , i P= 1, . . . , s, имеет старший членsα1αnαn1...x.Тогдаеслиai x αf=n1i=1 λi fi и fC < x1 . . . xn , то f =Ps−1i=1 γi S(fi , fi+1 ), γi ∈ F .PsДоказательство. S(fi , fi+1 ) = afii − afi+1, f = i=1 λi fi = λ1 a1 ( af11 −i+1f2a2 )+ (λ1 a1 + λ2 a2 )( af22 −(λ1 a1 + . . .

+λs as )( afss ).f3a3 )+ . . . + (λ1 a1 + . . . + λs−1 as−1 )( afs−1−s−1fsas )+¤Теорема 1. Для любого набора f1 , . . . , fm ∈ F [x1 , . . . , xn ] послеприсоединения конечного числа нетривиальных композиций получимнабор, в котором все композиции тривиальны.§ 4. Системы алгебраических уравнений и базисы Грёбнера119Доказательство от противного. Если при редуцированииполучается бесконечное множество I нередуцируемых многочленов, торассмотрим идеал J, порождённый их старшими членами.

Выбираемв J конечное множество образующих m1 , . . . , mk . Пусть fi ∈ I такие,что (fi )C = mi , i = 1, . . . , k, и пусть T = {fi , i = 1, . . . , k}. Тогда длялюбого f ∈ I \ T старший член fC делится на (fi )C для некоторого i,т. е. редуцируется.¤Теорема 2 (Diamond Lemma).

Базис f1 , . . . , fm в I являетсябазисом Грёбнера ⇔ в базисе f1 , . . . , fm все композиции тривиальны.Доказательство. В одну сторону утверждение Pочевидно. Докажемв обратную. Достаточно показать, что f =hi fi для любогоf ∈ I, где старший член fC совпадает с (hk fk )C для некоторого k.От противного. Предположим, что fC < (hk fk )C для некоторого kи такое представление для f Pвыбрано так, что (hk fkP)C минимален.tmПусть hi = (hi )C +(hi )M и f = i=1 ((hi )C fi +(hi )M fi )+ i=t+1 hi fi , гдеα1αn(hi fi )C = ai x1 .

. . xn , для i = 1, . . . , t, k < t, ai ∈ F . По лемме 3 имеем:PtPt−1i=1 (hi )C fi =i=1 γi S((hi )C fi , (hi+1 )C fi+1 ). Так как (hi )C являютсямономами, то S((hi )C fi , (hi+1 )C fi+1 ) делится наP S(fi , fi+1 ). Так какS(fi , fi+1 ) редуцируется к нулю, то S(fi , fi+1)=gl fl и S(fi , fi+1 )C =Pgk fk для некоторого k. Следовательно, f =dl fl , где (di fi )C < (h1 f1 )Cдля любого i.

Противоречие.¤§ 4.Системы алгебраическихи базисы ГрёбнерауравненийВ данном параграфе всюду F = C.Теорема 1. Система S несовместна ⇔ базис Грёбнера идеала I(S)содержит ненулевую константу.Доказательство. Если 0 6= α ∈ I(S), то система несовместна. Еслисистема несовместна, то 1 ∈ I(S) по следствию 4 § 2. Следовательно,(fi )C делит 1 для некоторого fi из базиса.¤Из следствия 3 § 2 получаем следующую теорему.Теорема 2. S1 = {fi = 0, i = 1, . . .

, m} ∼ S2 = {gi = 0, i =1, . . . , k} ⇔ fi ∈ r((g1 , . . . , gk )), gj ∈ r((f1 , . . . , fm )) для любых i, j.¤Теорема 3. Число решений системы S конечно ⇔ базис Грёбнераидеала I(S) содержит такие элементы f1 , . . . , fn , что (fi )C = xki i .1207. Базисы ГрёбнераДоказательство. Пусть число решений системы конечно.Неизвестная x1 может принимать на множестве решений лишь конечноечисло значений α1 , . . . , αn1 . Многочлен f (x1 ) = (x1 −α1 ) . .

. (x1 −αn1 ) ≡ 0на множестве решений системы S. Следовательно, по теоремеГильберта о нулях существует k1 ∈ N такое, что f k1 ∈ I(S). Далее(f k1 )C = xn1 1 k1 . По определению базиса Грёбнера в этом базисесуществует такой f1 , что (f1 )C делит (f k1 )C , т.

е. является степеньюx1 . Аналогично и для остальных неизвестных.Обратно, если f1 , . . . , fn — такие элементы базиса Грёбнера, что(fi )C = xni i , то в силу порядка fn зависит только от xn , т. е. xn можетпринимать лишь конечное число значений. Аналогично fn−1 зависиттолько от xn и xn−1 и его старший член не равен нулю при любыхзначениях xn .

Следовательно, xn−1 принимает конечное число значенийи т. д.¤Предметный указательалгебра над полем, 51алгоритмЕвклида, 13базисГрёбнера, 117Жордана, 69идеала, 114идеала конечный, 114базисысингулярные, 104векторкорневой, 66нормированный, 83собственный, 57векторыортогональные, 85ортонормированные, 85весмногочлена, 31одночлена, 31высотавектора, 61делимость, 8делительнаибольший общий, 10дискриминант, 34длинавектора, 83дополнениеортогональное, 87дробьнесократимая, 19правильная, 19простейшая, 20заменанеизвестных, 105значениесобственное, 57идеалглавный, 7радикальный, 116индекснильпотентности, 61клеткаЖордана, 62кольцоглавных идеалов, 12евклидово, 12с разложением, 9факториальное, 9композиция, 118координаты вектора, 48коренькратный, 21многочлена, 21кратное121122Предметный указательнаименьшее общее, 11матрицаЖордана, 64клеточно-диагональная, 56нормальная, 90ортогональная, 91отображения, 48перехода, 49полураспавшаяся, 54симметрическая, 91унитарная, 91характеристическая, 52эрмитова, 91матрицыподобные, 52метод Ньютона, 45минорглавный, 109многообразиеаффинное алгебраическое, 115многочленминимальный, 59неприводимый, 8однородный, 29примитивный, 15симметрический, 29симметрическийэлементарный, 30характеристический, 52характеристическийпреобразования, 56множестваортогональные, 87множитель многочленакратный, 27неравенствоКоши — Буняковского, 83определительпреобразования, 56определитель Вандермонда, 36ортогонализация, 86подпространствоинвариантное, 54полеалгебраически замкнутое, 43разложения, 24преобразованиеиндуцированное, 55неотрицательное, 101нильпотентное, 61нормальное, 90ортогональное, 90положительное, 101симметрическое, 90сопряжённое, 88унитарное, 90эрмитово, 90проектирование, 47произведениескалярное, 81производнаямногочлена, 25многочлена кратная, 25пространстваизоморфные, 92пространствоевклидово, 81унитарное, 81радикалидеала, 116разложениена множители, 27полярное, 103рангформы, 106123расстояние, 84расширение поляалгебраическое, 25простое, 24результант, 38ряд Штурма, 46сигнатура, 108системауравненийалгебраических, 113конечная, 113системыэквивалентные, 113следматрицы, 52преобразования, 56содержание многочлена, 15спектр, 61степеньдроби, 19многочлена, 29одночлена, 29суммаортогональная, 87степенная, 34теоремаГамильтона — Кэли, 53Гильберта о нулях, 116Жордана, 65, 66, 71, 74Штурма, 46формадиагональная, 106квадратичная, 105нормальная, 106положительно определённая,110формулаЛейбница, 25функцияматрицы, 75цепочка, 69числосингулярное, 103элементалгебраический, 25неразложимый, 8простой, 8регулярный, 8элементыассоциированные, 8образующие, 114порождающие, 114Учебное изданиеПожидаев Александр Петрович,Сверчков Сергей Робертович,Шестаков Иван ПавловичЛЕКЦИИ ПО АЛГЕБРЕЧасть 2Учебное пособиеРедактор Е.

П. ВойтенкоПодписано в печать 30.10.2012Формат Уч.-изд. л. 7,8. Усл. печ. л. 7,2.Тираж 150 экз. Заказ №Редакционно-издательский центр НГУ.630090, Новосибирск-90, ул. Пирогова, 2..