7.5. Связь с матричными методами декодирования

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

Это уравнение надо решить относительно если известны Сначала мы определим из уравнения

которое эквивалентно уравнению

Эти уравнения можно решать с помощью описанной в разд. 2.5 стандартной редукции матриц. Такой метод требует значительно большего числа вычислений и большего объема памяти, чем метод производящих функций, и, как видно из разд. 7.1-7.4, эти матрицы, вообще говоря, вводить нецелесообразно.

Тем не менее мы покажем, в какой связи находятся матричные методы и алгоритм 7.4. Для предыдущей системы -матрица

из коэффициентов при неизвестных имеет вид

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

Вопрос о вырожденности матриц можно решить с помощью следующей теоремы:

7.51. Теорема.

Доказательство. Для определим многочлены

Так как тогда и только тогда, когда то для

Сопоставим каждому многочлену -мерный вектор-столбец

Введем теперь -матрицу столбцы которой совпадают с векторами

Мы утверждаем, что эта матрица невырожденна. Действительно, если линейная комбинация ее столбцов равна нулю, то

и

где

Если то Если , то . Следовательно, если , то

где Значит, если , то для Но если

Таким образом, тогда и только тогда, когда для всех злачит, невырожденная матрица.

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

столбцы. Нуль-подпространство матрицы является линейной оболочкой столбцов ранговое пространство натянуто на столбцы матрицы для которых Дефект матрицы Ли равен дефекту а последний в свою очередь равен числу таких что или

Из алгоритма 7.4 вытекает, что

Очевидно, что монотонная неубывающая функция аргумента и что только тогда, когда

Следующее замечание состоит в том, что отрезок целых чисел для которых к, не должен иметь пропусков. Действительно, если к для

Если

В этом случае дефект равен

С другой стороны, при существует такое что если то

В этом случае дефект равен . Значит,

Это эквивалентно теореме 7.51