Алгебра. Лекция 29

32:00 Всё правильно говорит, но есть неочевидные места. То что нули портятся понятно, неочевидно почему элемент f через какое-то время будет делиться на d`. Виктор Александрович не рассмотрел особый случай матрицы 2x2 и ещё надо какие-то слова сказать для общего случая матрицы nxn. Как мы поступаем со второй строкой, у которой в первой позиции (в первом столбце) стоит испорченный ноль.
Рассмотрим случай матрицы 2x2.
( a e )
( g f )
Утверждение 1) Если уже сделано два и более обнулений и d` делит ненулевой элемент матрицы на побочной диагонали, тогда d` делит и a22 (элемент f).
Доказательство. Рассмотрим возможные шаги обнуления с номерами хотя бы два.
( x y ) ( d 0 ) __ ( d` fy )
( −g/d` d/d`) ( g f ) __ ( 0 f(d/d`) )
и
( d e ) ( x −e/d`) __ ( d` 0 )
( 0 f ) ( y d/d`) __ ( fy f(d/d`) )
Пусть d`|fy. Так как d` не делит y, то d`|f и f=k∙d`. Тогда a22=f(d/d`)=k∙d, но d=m∙d`, поэтому d`|a22 и d`|f.
Замечание. Вообще после первого шага обнуления ненулевые элементы в матрице 2x2 отличные от d являются элементами идеала (e, f) или (g, f) и сами порождают тот же самый идеал.
Утверждение 2) Последовательно обнуляя элементы на побочной диагонали можно получить d` общий делитель (наибольший общий делитель) остальных элементов матрицы, в частности на d` будет делиться элемент a22 (элемент f).
Доказательство.
1 случай) Пусть на первом шаге d=НОД(a, g) делит остальные элементы матрицы. Почему d=НОД( a, g, e, f )? Очевидно, что после первого шага обнуления ненулевые элементы e`,f` идеала (e, f) порождают тот же самый идеал, потому что невырожденное обратимое преобразование 2x2 нод двух соседних элементов матрицы не меняет. Тоже самое верно и в случае, когда один из элементов был равен нулю, т.е. e=0 ( или g=0 для случая d=НОД(a, e) ). Проверьте, что это так. Поэтому если d делит их нод, значит он НОД всех элементов матрицы. Действительно, обозначим один из элементов n∙q, а другой m∙q, элемент q=нод(e, f) задаёт идеал (e, f)=(q), при этом из сохранения нодов следует, что у n, m нет общих делителей и q=нод(e`, f`), поэтому d делит q. Если изначально e=0, то e`, f` могут оказаться отличными от нуля, в этом случае q=нод(e`, f`)=f.
2 случай) На каком-то не первом шаге d`=НОД(d, e^) делит элемент на побочной диагонали, тогда по утверждению 1) он делит и a22 (элемент идеала (e, f) ). Почему d`=НОД( a, g, e, f )? Очевидно, что после второго и далее шага d`

2 случай) На каком-то не первом шаге d`=НОД(d, e^) делит элемент на побочной диагонали, тогда по утверждению 1) он делит и a22 (элемент идеала (e, f) ). Почему d`=НОД( a, g, e, f )? Очевидно, что после второго и далее шага d` меньше d, т. е. элемент d убывает, на первом шаге может не поменяться, когда соседний элемент на него делится. Из за убывания d мы через некоторое время должны попасть в случай 1) с e=0 или g=0.

Общий случай матрицы nxn. Как мы поступаем со второй строкой, у которой в первой позиции (в первом столбце) стоит испорченный ноль. В первой позиции a21 стоит испорченный ноль и предположительно вся вторая строка у нас не была преобразована. Случай 1) испорченный ноль a21 делится на d, тогда мы его обнуляем прибавив первую строчку, после чего прибавляем к первой вторую строчку и обнуляем все элементы матрицами 2x2, тем самым преобразовываем все элементы второй строчки для получения НОД. Ноль a21 опять может испортиться, тогда если a21 не делится на d, то мы его снова обнуляем. Случай 2) Испорченный ноль a21 не делится на d, тогда мы его обнуляем, портится ноль a12, его мы тоже обнуляем методом, который зависит от того делится ли a12 на d или нет, дальше как в случае 1) преобразовываем все элементы второй строчки прибавив их к первой и обнулив. В конечном итоге у нас в позиции a31 скорее всего будет лежать испорченный ноль, который мы обнуляем, если он не делится на d. Этот алгоритм работает для матриц nxn c n хотя бы 3, случай 2x2 надо разбирать отдельно.

51:30 В первой строке найдём минимальный элемент по норме и поставим в позицию a11, потом тоже самое сделаем с первым столбцом. У нас в позиции a11 будет стоять элемент с наименьшей нормой среди элементов строчки и столбца. Выполняя деление с остатком на a11 при помощи алгоритма Евклида a1j=q1j∙a11+r1j и ai1=qi1∙a11+ri1 и применяя элементарные трансвекции можно в первой строчке и первом столбце получить остатки от деления r1j и ri1, которые все по норме будут меньше ||a11||. Повторяем процедуру, ищем опять минимальный элемент, ставим его в позицию a11 и получаем остатки от деления r`1j и r`i1. В конечном итоге в позиции a11 мы получим НОД всех элементов строки и столбца, после чего элементарными трансвекциями мы можем обнулить все элементы под a11 и справа от него, если они до этого не были нулевые. Следующим шагом прибавляем к первой строчке i-ую и повторяя алгоритм получаем нод a11 и всех элементов этой строчки. Прибавляя строчку за строчкой мы можем получить в позиции a11 нод всех элементов матрицы, при этом под a11 и справа от него будут стоять нулю. По индукции повторяем тоже самое с элементом в позиции a22.

51:30 В первой строке найдём минимальный элемент по норме и поставим в позицию a11, потом тоже самое сделаем с первым столбцом. У нас в позиции a11 будет стоять элемент с наименьшей нормой среди элементов строчки и столбца. Выполняя деление с остатком на a11 при помощи алгоритма Евклида a1j=q1j∙a11+r1j и ai1=qi1∙a11+ri1 и применяя элементарные трансвекции можно в первой строчке и первом столбце получить остатки от деления r1j и ri1, которые все по норме будут меньше ||a11||. Повторяем процедуру, ищем опять минимальный элемент, ставим его в позицию a11 и получаем остатки от деления r`1j и r`i1. В конечном итоге в позиции a11 мы получим НОД всех элементов строки и столбца, после чего элементарными трансвекциями мы можем обнулить все элементы под a11 и справа от него, если они до этого не были нулевые. Следующим шагом прибавляем к первой строчке i-ую и повторяя алгоритм получаем нод a11 и всех элементов этой строчки. Прибавляя строчку за строчкой мы можем получить в позиции a11 нод всех элементов матрицы, при этом под a11 и справа от него будут стоять нулю. По индукции повторяем тоже самое с элементом в позиции a22.