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

Г4 О 3 1 О О 2 4 2 2 3 1 0 0 3 3 2 4 4 4 1 0 0 0 1 0 0 0 0 0 0 0 0 3 2

0 0 0 0 0 1 0 .0 0 0 0 0 0 1.

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

Г1 О 3 1 О О 2-

1 2 2 3 1 0 0

2 3 2 4 4 4 1 0 0 0 1 0 0 0 0 0 0 0 0 3 2 О О О О ОИ О

0 0 0 0 00 1.

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

•1 О О О О О 01

1 2 4 2 1 0 3

2 3 1 2 4 4 2 0 0 0 1 0 0 0 0 0 0 0 0 3 2 0 0 0 0 0 1 0 0 0 0 0 0 0 1.

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

Г2 4 2 1 О 3 11

3 1 2 4 4 2 2 0 0 1 0 0 0 0 0 0 0 0 3 2 0 . 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1.

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

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

4 3 2 ООО ООО ООО

ООО 2 3 4 2 4 3 1 О О О О О

3 41 О О

0 О 3 2

L0 О О О О О и

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

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

Во многих интересных случаях приходится рассматривать систему т линейных уравнений с т неизвестными, имеющую вид ЪХ = и, а не ZX = О, где U - заданный иг-мерный вектор-строка, я X - заданная (т X т)-матрица. Для определения Z построим прежде всего расширенное матричное уравнение

(Z, -1]

= 0,

[Zq, Zj, . . . , Zm~i, - 1]

= [0,0, ...,0].

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

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

Если строка U содержит ненулевой элемент %, которому соот- i ветствует нулевой столбец приведенной матрицы X, то покомно-1 нентное произведение этого столбца матрицы X и расширенного! вектора Z равно

ZoO -Ь ZiO + ZaO + . . . + Zm-iO - 1 = - 0.

Это уравнение противоречиво. Ясно, что в этом случае исхода пая система уравнений [Z, - 1] =0 и приведенная систем {Z, -1] = О не совместны.

LU J , •

Однако, если приведенная присоединенная строка U содержи нуль в каждой координате, которой в матрице X - J соответствуе столбец с ненулевым диагональным числом, то всем нулевым столб цам матрицы X соответствуют нулевые координаты строки U, В это» случае U является линейной комбинацией строк матрицы X и удов летворяет уравнению tJX = U. Следовательно, решение уравнение

1Z, -и

== О задается равенством Z = 11. Подытожим это

результат в виде теоремы 2.56.

2.56. Теорема. Пусть X - некоторая (т X т)-матрица а V--т-мерный вектор-строка. Тогда уравнение ZX = U эквивалент

но расширенному матричному уравнению [Z, -1] =0. Вс решения этих уравнений могут быть получены следующим образол

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

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

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

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

гО О О О 0-11111

11111 = [00001]. 1 1110 L1 1 1 1 0-

lOi 1» •З, i]

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

ГО О О О ОТ 11111 11111 11110 11110 0 0 0 0 1

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

ГО О О О О-

0 0 10 0 0 0 10 0 0 0 0 0 1 0 0 0 0 1 0 0 10 1

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

Перестановка столбцов

Уточнение верхней строки

Циклические сдвиги строк и столбцов

Ясно, что одним решением этой системы является 00101, а остальные семь реше-i НИИ получаются путем прибавления к нему любой линейной комбинации строке 10000, 01100, 00011.

*2.6. Специальный метод решения систем уравнений, матрицы которых состоят почти сплошь из нулей

Если большинство из элементов (т х пг)-матрицы X равнс нулю, то для решения уравнения ZX = О более целесообразно! использовать специальные прямые методы. В качестве примера рассмотрим систему 10 двоичных уравнений с 10 неизвестными:!

= [0,0, о, ...,0].

Ненулевые элементы каждого столбца матрицы X выделяют подг множество координат вектора Z, сумма которых должна равняться!

2.6. Специальный метод решения систем уравнений нулю. В данном случав этими координатами являются

Рассмотрим сначала уравнения, содержащие не более двух неизвестных. Например, согласно уравнению с номером 3, Zg -j- Zg = О, так что Zg = Zg. Будем теперь координаты с большими значениями индексов заменять их выражением через координаты с меньшими значениями индексов и исключать координаты с большими значениями индексов из всех остальных уравнений. В данном случае, начиная с подстановки индекса 8 вместо индекса 9, получаем

Номер уравнения

Первметые

Отметка кружком координаты 9 в уравнении 3 указывает на то, что неизвестное Zg определяется теперь именно этим уравнением.

00000 00001 00001

01000

00001 00000 00010 00010 00001

00011

00000 00100 00100 00001 00001

00101