2.5. Решение систем линейных уравнений

В последних главах мы видели, что некоторые задачи, возникающие в теории кодирования, могут быть сведены к решению систем линейных уравнений. Часто эти системы рассматриваются над двоичным полем. Однако в некоторых случаях приходится рассматривать другие поля, как, например, поле классов вычетов по модулю 5. Сложение и умножение в задаются таблицами

Рассматриваемые системы линейных уравнений могут быть записаны в виде

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

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

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

2.51. Определение, -матрица X имеет приведенную треугольную идемпотентную форму, если каждый ее элемент, расположенный ниже главной диагонали, равен нулю, каждый элемент главной диагонали равен нулю или единице, каждый элемент, в столбце которого имеется нуль главной диагонали или в строке которого имеется единица главной диагонали, равен нулю.

Следующая матрица является примером треугольной идемпотентной матрицы над :

В символической записи это означает, что если или 1, если если или если

Иначе, только если и либо либо Термин треугольный вытекает из требования при Термин идемпотентный объясняется следующей теоремой:

2.52. Теорема. Всякая квадратная матрица в приведенной треугольной идемпотентной форме удовлетворяет уравнению

Доказательство. Элемент отличен от нуля только тогда, когда элемент и отличен от нуля только тогда, когда или Поэтому произведение и равно нулю во всех случаях, кроме

Следовательно,

Если то если то любом случае и

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

Из этого результата следует простая характеристика вектор-строк удовлетворяющих уравнению В дальнейшем нам также понадобится характеристика вектор-строк удовлетворяющих уравнению Теорема формулируется следующим образом:

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

Доказательство. Если то Следовательно, если произвольная линейная комбинация строк матрицы то Аналогично, если то и Следовательно, если

линейная комбинация строк матрицы X, то удовлетворяет уравнению

Так как только ненулевые столбцы матрицы имеют на главной диагонали —1, то ранг матрицы равен дефекту Следовательно, линейные комбинации строк матрицы исчерпывают все решения уравнения Так как все ненулевые столбцы матрицы X имеют на главной диагонали 1, то ранг матрицы X равен дефекту матрицы Следовательно, линейные комбинации строк X исчерпывают все решения уравнения

Произведение каждой координаты вектора на соответствующий диагональный элемент матрицы равно нулю тогда и только тогда, когда нулевой координате соответствует нулевой столбец матрицы Так как каждый ненулевой столбец треугольной матрицы X имеет на главной диагонали единицу, то является линейной комбинацией строк матрицы X тогда и только тогда, когда каждому нулевому столбцу из X соответствует нулевая координата

Наконец, докажем теорему 2.54.

2.54. Теорема. Любая квадратная матрица с помощью операций над столбцами может быть приведена к треугольной идемпотентной форме.

Хотя существует несколько способов такого приведения, мы остановимся не на самом простом, а на наиболее просто реализуемом.

Рис. 2.20. Циклический сдвиг столбцов влево.

Рис. 2.21. Циклический сдвиг строк вверх.

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

Соответственно определим операцию «циклического сдвига столбцов влево» с помощью диаграммы, приведенной на рис. 2.20. Аналогично с помощью диаграммы на рис. 2.21 определим операцию «циклического сдвига строк вверх».

Бдительный читатель в этом месте должен насторожиться: допустимой является операция перестановки столбцов, а не строк. Однако рассматриваемая процедура использует операцию сдвига строк траз, так что в итоге строки располагаются в первоначальном порядке.

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

2.55. Алгоритм приведения матрицы (к треугольной идемпотентной форме). Процедура состоит из следующего базисного множества шагов, повторяющегося раз:

1. Не делать ничего, если верхний член первого столбца матрицы отличен от нуля. Если верхний член первого столбца равен нулю, то поменять местами первый столбец с самым левым столбцом, в котором верхний элемент отличен от нуля, а элемент главной диагонали равен нулю. Если такого столбца нет, то поменять местами первый столбец с самым левым столбцом, в котором верхний элемент и элемент главной диагонали отличны от нуля. Если и такого столбца нет (в этом случае верхняя строка является нулевой), то не делать ничего.

2. Разделить все члены первого стобца на верхний элемент. (Если этот элемент равен нулю, не делать ничего.)

3. Аннулировать верхние элементы всех столбцов, кроме первого, с помощью вычитания подходящего кратного первого столбца.

4. Сдвинуть циклически строки вверх, а столбцы влево.

В двоичном случае шаг 2 можно опустить. Каждый из остальных шагов выполняется в один временной цикл. Блок-схема для выполнения операции 1 объяснена на рис. 2.22 и 2.23, а для операции 3 — на рис. 2.24.

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

имеет вид

Рис. 2.22. Подробная блок-схема одной ячейки из рис. 2.23. Вход равен О тогдаи только тогда, когда верхняя координата наиболее левого столбца равна 1, а его диагональный элемент равен 0. Если в данном столбце в верхней позиции стоит 1, а на диагонали стоит 0, то выход полагается равным 1, в противном случае равно Вход равен 0 тогда и только тогда, когда все А равны 0 и ни один из более левых столбцов не имеет нулевой верхней координаты.

Если любой из сигналов А или В изменяет свое значение с 0 на 1, то в точках или С появляется соответственно сигнал 1 и выход принимает значение 1, указывающее на то, что данный столбец надо поменять местами с крайним левым столбцом.

Связи между столбцами показаны на рис. 2.23. Заметим, что распространение сигнала вдоль линий и изменение его с 0 на 1 затрагивает только столбец, который должен переставляться. Если элемент в верхнем левом углу равен 1, то этот сигнал всюду равен 1; если каждый элемент верхней строки равен 0, то и сигнал всюду равен 0. Обоим этим случаям соответствует отсутствие каких-либо перемен, и анализируемый столбец не надо переставлять с крайним левым столбцом.

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

(кликните для просмотра скана)

Проведем теперь следующий цикл основных преобразований. Во-первых, переставим первый и пятый столбцы:

Во-вторых, пронормируем первый столбец:

В-третьих, вычтем соответствующее кратное первого столбца из остальных столбцов:

Наконец, сдвинем строки вверх, а столбцы влево:

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

Начнем с матрицы

Переставим первый и шестой столбцы и пронормируем затем первый столбец:

Прибавляя затем первый столбец к седьмому и сдвигая строки и столбцы получаем

Таким образом, любая квадратная матрица может быть приведена к треугольной идемпотентной форме с помощью подходящих операций над столбцами, которые можно легко реализовать. Для двоичных -матриц эти операции над столбцами могут быть выполнены за временных циклов посредством схем, приведенных на рис. 2.20-2.24.

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

или

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

процедуры приведения циклический сдвиг строк относится лишь только к строкам матрицы Таким образом, при приведении квадратной матрицы X к треугольной идемпотентной форме X присоединенная строка преобразуется в строку которая, конечно, не имеет какого-либо специального вида, и все ее координаты могут быть ненулевыми.

Если строка содержит ненулевой элемент которому соответствует нулевой столбец приведенной матрицы X, то покомпонентное произведение этого столбца матрицы X и расширенного вектора равно

Это уравнение противоречиво. Ясно, что в этом случае исходная система уравнений и приведенная система не совместны.

Однако, если приведенная присоединенная строка содержит нуль в каждой координате, которой в матрице соответствует столбец с ненулевым диагональным числом, то всем нулевым столбцам матрицы X соответствуют нулевые координаты строки . В этом случае является линейной комбинацией строк матрицы X и удовлетворяет уравнению Следовательно, решение уравнения задается равенством Подытожим этот результат в виде теоремы 2.56.

2.56. Теорема. Пусть X — некоторая -матрица, -мерный вектор-строка. Тогда уравнение эквивалентно расширенному матричному уравнению Все решения этих уравнений могут быть получены следующим образом:

1) С помощью подходящих операций над столбцами расширенной матрицы X приводим ее к треугольному идемпотентному виду При этом присоединенная строка преобразуется в некоторую строку

2) Образуем матрицу вычитая единицы из элементов главной диагонали

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

2.57. Пример. Рассмотрим систему пяти двоичных уравнений с пятью неизвестными

Расширенная матрица равна

Для приведения этой матрицы к треугольной идемпотентной форме прибавим третий столбец ко всем остальным столбцам, а затем пятый столбец к третьему:

Интересно проиллюстрировать такой способ приведения с помощью схем, изображенных на рис. 2.22-2.24. Проведем более детальное вычисление:

(см. скан)

Ясно, что одним решением этой системы является 00101, а остальные семь решений получаются путем прибавления к нему любой линейной комбинации строк