6.3. ОБРАЩЕНИЕ МАТРИЦ

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

Лемма 6.5. Пусть матрица А разбита так:

Предположим, что существует Обозначим через А и допустим, что существует. Тогда

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

откуда

Лемму 6.5 нельзя применять ко всем невырожденным матрицам. Например, -матрица перестановки А, у которой если в противном случае, невырожденна, но для любой главной подматрицы Ли. Тем не менее лемма 6.5 применима ко всем невырожденным нижним и верхним треугольным матрицам.

Лемма 6.6. Если А — невырожденная верхняя (нижняя) треугольная матрица, то матрицы и А из леммы 6.5 обратимы и являются верхними (нижними) треугольными.

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

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

Доказательство. Докажем теорему для случая, когда степень числа 2. Очевидно, что в противном случае можно вложить в матрицу вида

является степенью числа 2. Тем самым, увеличив постоянную с не более чем в 8 раз, мы установим наш результат для произвольного

Если степень числа 2, можно разбить на четыре -подматрицы и рекурсивно применить формулу (6.3). Заметим, что так что Следовательно, для обращения треугольных матриц и А требуется времени, для двух нетривиальных умножений еще времени и, для того чтобы поставить минус в правом верхнем углу, еще операций. Из условия теоремы и неравенства выводим, что Таким образом,

Легко доказать, что из (6.4) следует