Задача 18

Условие задачи

Пусть для любого $n$ имеет алгоритм обращения произвольной обратимой матрицы порядка $n$ не более чем за $cn^\alpha$ арифметических операций, где $\alpha$ и $c$ не зависят от $n$. Докажите, что в этом случае существует алгоритм умножения двух матриц порядка $n$ с числом операций не более $c_1 n^\alpha$, где $c_1$ не зависит от $n$.

Решение задачи

Пусть $A$ и $B$ — произвольные квадратные матрицы порядка $n$, произведение которых требуется вычислить.

Рассмотрим блочную матрицу порядка $3n$: $M = \begin{bmatrix} I & A & 0 \\ 0 & I & B \\ 0 & 0 & I \end{bmatrix}$, где $I$ — единичная матрица порядка $n$.

Согласно задаче 17, для любых квадратных матриц $A$ и $B$ одного порядка имеет место равенство: $\begin{bmatrix} I & A & 0 \\ 0 & I & B \\ 0 & 0 & I \end{bmatrix}^{-1} = \begin{bmatrix} I & -A & AB \\ 0 & I & -B \\ 0 & 0 & I \end{bmatrix}$.

Следовательно, произведение матриц $AB$ совпадает с правым верхним блоком матрицы $M^{-1}$.

По условию задачи существует алгоритм обращения матриц порядка $3n$, требующий не более $c \left(3n\right)^\alpha = c \cdot 3^\alpha \cdot n^\alpha$ арифметических операций. Применяя этот алгоритм к матрице $M$, мы вычисляем матрицу $M^{-1}$ и, в частности, получаем её правый верхний блок, равный $AB$.

Построение матрицы $M$ и извлечение блока $AB$ требуют не более конечного числа операций, пропорционального $n^2$, то есть не более $dn^2$ операций с некоторой константой $d$, не зависящей от $n$.

Таким образом, общее число арифметических операций, необходимых для вычисления произведения матриц $A$ и $B$, не превосходит $c \cdot 3^\alpha \cdot n^\alpha + dn^2$.

Заметим, что при обращении матрицы порядка n необходимо вычислить $n^2$ числовых элементов матрицы $A^{-1}$. Следовательно, число арифметических операций любого алгоритма обращения не может быть меньше $n^2$, откуда следует $\alpha \geqslant 2$.

Т.к. $\alpha \geqslant 2$, существует константа $c_1$, не зависящая от $n$, такая что $c \cdot 3^\alpha \cdot n^\alpha + dn^2 \leqslant c_1 n^\alpha$ (поскольку при $\alpha \geqslant 2$ выполнено неравенство $n^2 \leqslant n^\alpha$) для всех $n$.

Следовательно, существует алгоритм умножения двух матриц порядка n, требующий не более $c_1 n^\alpha$ арифметических операций, где $c_1$ не зависит от $n$. $\square$