6. УМНОЖЕНИЕ МАТРИЦ И СВЯЗАННЫЕ С НИМ ОПЕРАЦИИ

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

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

6.1. ОСНОВНЫЕ ПОНЯТИЯ

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

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

Заметим, что последнее свойство — существование обратного элемента относительно сложения — в замкнутом полукольце может не выполняться (разд. 5.6). А свойство 4 замкнутого полукольца — существование и единственность бесконечных сумм — не обязательно выполняется в кольце. Кольцо, в котором операция-коммутативна, называется коммутативным.

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

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

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

Введем важный класс колец матриц.

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

Лемма кольцо.

Доказательство. Элементарное упражнение.

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

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

Лемма 6.2. Пусть — отображение из что матрица

из где — левый верхний квадрант матрицы правый верхний квадрант, левый нижний, А 22— правый нижний. Тогда

Доказательство. Доказательство состоит в подстановке определяющих равенств для в определяющие равенства для а это элементарное упражнение.

Лемма 6.2 важна тем, что указывает возможность построения алгоритма умножения -матриц из алгоритмов умножения -матриц и -матриц. Мы воспользуемся ею в следующем разделе и построим асимптотически быстрый алгоритм умножения матриц. Здесь же подчеркнем тот факт, что алгоритм умножения -матриц будет не произвольным, а специально ориентированным на работу с Так как кольцо не коммутативно, даже если таково кольцо то этот алгоритм умножения -матриц не может предполагать коммутативности умножения -матриц. Но он может, разумеется, использовать любое из свойств кольца.

Определение. Пусть А будет -матрицей с элементами из некоторого поля. Матрицей обратной к А, называется такая -матрица, что

Легко показать, что если матрица А -1 существует, то она единственна и Кроме того,

Определение. Пусть А будет -матрицей. Определителем матрицы А называется сумма, взятая по всем перестановкам целых чисел от 1 до произведений

где если перестановка четная (т. е. ее можно получить из четным числом транспозиций), и если перестановка нечетная (получается нечетным числом транспозиций).

Легко показать, что каждая перестановка либо четна, либо нечетна (но не то и другое одновременно).

Пример 6.2. Пусть

Шесть перестановок чисел 1, 2, 3 таковы: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). Очевидно, перестановка (1, 2, 3) четна, ибо получается из себя с помощью транспозиций. Перестановка (2, 3, 1) четна, поскольку, переставляя 2 и 3 в (1, 2, 3), получаем (1, 3, 2), затем переставляем 1 и 2 и получаем (2, 3, 1). Аналогично (3, 1,2) — четная перестановка, а остальные три — нечетные. Таким образом,

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

Определение. -матрица называется верхней треугольной, если при и нижней треугольной, если

Умножение двух верхних треугольных матриц дает верхнюю треугольную матрицу. Аналогичное утверждение верно и для нижних треугольных матриц.

Лемма 6.3. Если А — квадратная верхняя или нижняя треугольная матрица, то

(a) равняется произведению элементов, стоящих на главной диагонали (т. е. )

(б) А невырожденна тогда и только тогда, когда все элементы на главной диагонали отличны от нуля.

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

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

Заметим, что определитель нормированной верхней треугольной или нижней треугольной матрицы равен 1.

Определение. Матрицей перестановки называется такая матрица из и 1, что в каждой строке и каждом столбце стоит ровно одна единица.

Определение. Подматрицей матрицы А называется матрица, получаемая вычеркиванием некоторых строк и столбцов матрицы А. Главной подматрицей -матрицы А называется квадратная подматрица матрицы состоящая из первых строк первых столбцов матрицы

Рангом матрицы называется размер ее наибольшей квадратной невырожденной подматрицы. Например, ранг -матрицы перестановки равен

Заметим, что если то Кроме того, если имеет строк и ранг то любые ее строк образуют матрицу ранга

Определение. Матрицей транспонированной к называют матрицу, получаемую перестановкой для всех