Задача 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} \text{,}$$

где $I$ – единичная матрица порядка n. Согласно задаче 17, для любых квадратных матриц $A$ и $B$ одного порядка матрица $M$ обратима и

$$M^{-1} = \begin{bmatrix} I & -A & AB \\ 0 & I & -B \\ 0 & 0 & I \end{bmatrix} \text{.}$$

Видно, что произведение $AB$ совпадает с правым верхним блоком матрицы $M^{-1}$. Известно, что матрица $M$ обратима, а её обратная выписана явно, – а значит, к $M$ применим алгоритм обращения из условия, который работает с обратимыми матрицами.

По условию существует алгоритм обращения матриц порядка $3n$, требующий не более

$$c \left(3n\right)^\alpha = c \cdot 3^\alpha \cdot n^\alpha$$

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

Построение матрицы $M$ (заполнение $\left(3n\right)^2 = 9n^2$ клеток элементами $A$, $B$ и числами $0$, $1$) и извлечение блока $AB$ ($n^2$ элементов) требуют не более конечного числа операций, пропорционального $n^2$, то есть не более $dn^2$ операций с некоторой константой $d$, не зависящей от $n$. Таким образом, общее число операций, необходимых для вычисления $AB$, не превосходит

$$c \cdot 3^\alpha \cdot n^\alpha + dn^2 \ \text{.} \tag{1}$$

Оценим показатель $\alpha$. Возьмём произвольную обратимую матрицу порядка $n$: алгоритм обращения обязан выдать все $n^2$ элементов обратной матрицы. Каждая арифметическая операция вычисляет не более одного нового числа, а обратную (в худшем случае – но его и оцениваем) можно взять так, что все $n^2$ её элементов отличны и от исходных данных, и от чисел $0$, $1$; поэтому для получения этих $n^2$ чисел требуется не менее $n^2$ операций. Вместе с оценкой сверху $cn^\alpha$ это даёт

$$n^2 \leqslant cn^\alpha \quad \forall n: n \geqslant 1 \ \text{.}$$

Если бы было $\alpha < 2$, то отношение $\dfrac{n^2}{n^\alpha} = n^{2-\alpha}$ неограниченно росло бы с ростом $n$, что противоречит ограниченности $n^{2-\alpha} \leqslant c$. Значит $\alpha \geqslant 2$.

Поскольку $\alpha \geqslant 2$, при всех $n \geqslant 1$ выполнено $n^2 \leqslant n^\alpha$, и из $\left(1\right)$

$$c \cdot 3^\alpha \cdot n^\alpha + dn^2 \leqslant c \cdot 3^\alpha \cdot n^\alpha + dn^\alpha = \\ = \left(c \cdot 3^\alpha + d\right) n^\alpha \ \text{.}$$

Положив $c_1 = c \cdot 3^\alpha + d$ (константа, не зависящая от $n$), получаем алгоритм умножения двух матриц порядка $n$, требующий не более $c_1 n^\alpha$ арифметических операций. $\square$

Замечание. Условие считает именно арифметические операции. Сборка матрицы $M$ – это лишь расстановка уже готовых чисел (элементов $A$, $B$ и констант $0$, $1$) по клеткам, а извлечение блока $AB$ – считывание уже вычисленных чисел; ни то, ни другое не содержит ни одной арифметической операции. Поэтому число арифметических операций описанного алгоритма умножения в точности равно числу операций одного обращения матрицы порядка $3n$, то есть не превосходит

$$c \left(3n\right)^\alpha = c \cdot 3^\alpha \cdot n^\alpha = \left(c \cdot 3^\alpha\right) n ^ \alpha \ \text{.}$$

Тем самым сразу годится $c_1 = c \cdot 3^\alpha$ – без слагаемого $dn^2$ и без рассуждения о том, что $\alpha \geqslant 2$. Приведённое выше решение через $dn^2$ и оценку $\alpha \geqslant 2$ остаётся верным и работает даже в более широкой модели, где учитывают любые операции (включая пересылки данных); в ней член $dn^2$ уже не бесплатен, и неравенство $\alpha \geqslant 2$ становится необходимым, чтобы его поглотить.