Опишем метод получения НДФС матрицы А. Сначала, методом Гаусса найдем какой-нибудь ненулевой минор матрицы А максимального порядка. Обозначим его через d. Отметим, числа 
являются делителями d.
Элементарными преобразованиями строк и столбцов приведем матрицу А к диагональному виду. При этом все операции будем делать по модулю d.
Запоминая элементарные преобразования со строками и столбцами в соответствующих матрицах, найдем матрицы Р и Q.
Поскольку 
являются делителями d, то, проводя все арифметические операции по модулю d, мы, тем не менее, построим НДФС матрицы А. При этом, элементарных преобразований потребуется, не больше, чем число итераций алгоритма Евклида, умноженного на k=min (m, n). Таким образом, общее число элементарных операций метода не более O(mn log d), или, учитывая неравенство Адамара 
, не более O(mnk log αk). При этом будут найдены унимодулярные матрицы Р и Q, удовлетворяющие равенству РАQ=S+dT, где Т — целочисленная матрица размерами mхn. Так как d — величина некоторого минора матрицы А, то 
можно представить как АВ, где В — целочисленная матрица размерами mхm и может быть найдена как решение системы линейных уравнений. Из равенства PAQ=S+dT вытекает S=PAQ-PAВ=РА(Q-В). В результате, кроме НДФС матрицы А мы нашли и унимодулярные матрицы Р и Q-В, приводящие к НДФС.
Сборник тестовых примеров и задач
План практических занятий.
