5.3.2. Гауссово исключение и результанты в формах Брюно и Труда

Напомним, что для двух данных полиномов матрица соответствующая результанту в форме Брюно, равна

Мы хотим доказать, что если мы приведем к верхней треугольной форме пользуясь только преобразованиями строк, то последняя ненулевая строка матрицы даст нам коэффициенты полинома . Заметим, что в общем случае при преобразовании мы можем получить только но ни одного другого члена PRS, порожденной полиномами

Для доказательства главного результата прежде всего нам понадобится следующая

Лемма 5.3.1 (Laidacker, 1969). Пусть —полиномы, соответствующие строкам матриц (определенной выше) и соответственно, где — верхняя треугольная форма матрицы полученная из последней только преобразованиями строк. Если k — степень полинома соответствующего последней ненулевой строке матрицы , то не существует полиномов вида

степени, меньшей k, где — константа, .

Доказательство. В обеих матрицах, элементы первого столбца — это коэффициенты при степени элементы второго столбца - это коэффициенты при степени и т.д.

Из линейной алгебры нам известно, что множество линейных комбинаций вида (L), порожденных полиномами совпадает с множеством, порожденным полиномами , поэтому мы будем доказывать теорему для последнего множества.

Прежде всего заметим, что при теорема очевидным образом верна. Предположим теперь, что она неверна при Тогда существуют константы такие, что где Так как а также , то должно равняться нулю. Рассмотрим оставшееся выражение по тем же причинам, что и выше, мы заключаем, что для» , откуда следует, что — нулевой полином, что противоречит предположению.

Теорема 5.3.2 (Laidacker, 1969). В предположениях леммы 5.3.1 последняя ненулевая строка матрицы полученной из с помощью только преобразований строк, дает коэффициенты полинома

Локазательство. Пусть — элементы последней ненулевой строки матрицы в этом случае По построению мы видим, что любой полином вида может быть записан в виде где . Ясно, что также может быть записан в виде тогда, очевидно, откуда мы заключаем, что . Однако по лемме 5.3.1 не существует полиномов степени которые могут быть представлены в виде , а следовательно, наша теорема доказана.

Пример. Рассмотрим пару полиномов порождающую полную PRS. Тогда

Из последней строки матрицы мы заключаем, что эти два полинома взаимно просты. Заметим также, что в мы теряем

полином и оказывается, что мы получаем полиномиальный остаток, третью строку, соответствующую полиному

Однако если мы рассмотрим пару полиномов порождающую неполную PRS, то

и

Учитывая, что члены PRS, порожденной двумя данными выше полиномами, суть

мы видим, что из мы можем извлечь заключение только о

Очевидно, что форма Труди результанта по существу совпадает с формой Брюно, за исключением того, что нижнее множество строк попарно переставлено. Таким образом, теорема 5.3.2 остается верной в атом случае, и мы можем ожидать, что получим только заключение о наибольшем общем делителе двух полиномов (который будет дан со знаком ).

Пример. Рассмотрим пару полиномов, исследовавшихся в предыдущем примере. Прежде всего для мы имеем

Заметим, что в предпоследняя строка соответствует полиному , т.е. это кратное противоположного к остатку полинома. Подобным же образом последняя строка, — это наибольший общий делитель со знаком

Теперь для мы имеем

и

Заметим, что четыре последние строки матрицы соответствуют четырем полиномам, из которых только три последних принадлежат PRS, порожденной . Таким образом, , где — остаток от деления на — второй полиномиальный остаток — это со знаком

Из этого примера мы видим, что из так же как из мы мажем получить сведения только о наибольшем общем делителе двух полиномов. Однако в случае полных PRS из могут быть получены противоположные к полиномиальным остаткам.