7.5. Связь с матричными методами декодирования
Предыдущие методы вычисления величин по величинам
относятся к прямым методам решения системы линейных уравнений. Вместо ключевого уравнения
можно записать эквивалентное ему матричное уравнение
Это уравнение надо решить относительно
если известны
Сначала мы определим
из уравнения
которое эквивалентно уравнению
Эти уравнения можно решать с помощью описанной в разд. 2.5 стандартной редукции матриц. Такой метод требует значительно большего числа вычислений и большего объема памяти, чем метод производящих функций, и, как видно из разд. 7.1-7.4, эти матрицы, вообще говоря, вводить нецелесообразно.
Тем не менее мы покажем, в какой связи находятся матричные методы и алгоритм 7.4. Для предыдущей системы
-матрица
и
где
Если
то
Если
, то
. Следовательно, если
, то
где
Значит, если
, то
для
Но если
Таким образом,
тогда и только тогда, когда
для всех
злачит,
невырожденная матрица.
Так как матрица
невырожденна, то ранг
равен рангу произведения матриц
Столбцы матрицы
имеют вид
или, с учетом структуры матрицы
вид
где
Если
то
так что
. С другой стороны, если
то
так что
(Номер первой ненулевой координаты вектора
равен
Отсюда следует, что
— треугольная матрица с нулями над главной диагональю; каждый ее элемент на главной диагонали равен нулю или единице, а через нули главной диагонали проходят нулевые