Умножение матриц

Умноже́ние ма́триц — одна из основных операций над матрицами. Матрица, получаемая в результате операции умножения, называется произведе́нием ма́триц.

Определение

Пусть даны две прямоугольные матрицы $A$ и $B$ размерности $m \times n$ и $n \times q$ соответственно:

$A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix},\;\;\; B = \begin{bmatrix} b_{11} & b_{12} & \cdots & b_{1q} \\ b_{21} & b_{22} & \cdots & b_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \cdots & b_{nq} \end{bmatrix}.$

Тогда матрица $C$ размерностью $m \times q$ называется их произведением:

$C = \begin{bmatrix} c_{11} & c_{12} & \cdots & c_{1q} \\ c_{21} & c_{22} & \cdots & c_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \cdots & c_{mq} \end{bmatrix},$

где:

$c_{ij} = \sum_{r=1}^n a_{ir}b_{rj} \;\;\; \left(i=1, 2, \ldots m;\; j=1, 2, \ldots q \right).$

Операция умножения двух матриц выполнима только в том случае, если число столбцов в первом сомножителе равно числу строк во втором; в этом случае говорят, что форма матриц согласована. В частности, умножение всегда выполнимо, если оба сомножителя — квадратные матрицы одного и того же порядка.

Следует заметить, что из существования произведения $AB$ вовсе не следует существование произведения $BA.$

Иллюстрация

Произведение матриц AB состоит из всех возможных комбинаций скалярных произведений строк матрицы A и столбцов матрицы B. Элемент матрицы AB с индексами i, j есть скалярное произведение i-ой строки матрицы A и j-го столбца матрицы B.

Иллюстрация справа демонстрирует вычисление произведения двух матриц A и B, она показывает как каждые пересечения в произведении матриц соответствуют строкам матрицы A и столбцам матрицы B. Размер результирующей матрицы всегда максимально возможный, то есть для каждой строки матрицы A и столбца матрицы B есть всегда соответствующее пересечение в произведении матрицы.

Значения на пересечениях отмеченных кружочками будут:

$\begin{align} {\color{Red}x_{1,2}} &= (a_{1,1}, a_{1,2})\cdot(b_{1,2}, b_{2,2}) \\ &= a_{1,1}b_{1,2} + a_{1,2}b_{2,2} \\ {\color{Blue}x_{3,3}} &= (a_{3,1}, a_{3,2})\cdot(b_{1,3}, b_{2,3}) \\ &= a_{3,1}b_{1,3} + a_{3,2}b_{2,3} \end{align}$

В общем случае, произведение матриц не является коммутативной операцией. К примеру:

$\overset{3\times 4 \text{ matrix}}{\begin{bmatrix} \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot \\ \color{Blue} 1 & \color{Blue} 2 & \color{Blue} 3 & \color{Blue} 4 \\ \end{bmatrix}} \overset{4\times 5\text{ matrix}}{\begin{bmatrix} \cdot & \cdot & \cdot & \color{Red}a & \cdot \\ \cdot & \cdot & \cdot & \color{Red}b & \cdot \\ \cdot & \cdot & \cdot & \color{Red}c & \cdot \\ \cdot & \cdot & \cdot & \color{Red}d & \cdot \\ \end{bmatrix}} = \overset{3\times 5\text{ matrix}}{ \begin{bmatrix} \cdot & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & x_{3,4} & \cdot \\ \end{bmatrix}}$

Элемент $x_{3,4}$ произведения матриц приведённых выше вычисляется следующим образом

$x_{3,4} = ({\color{Blue}1}, {\color{Blue}2}, {\color{Blue}3}, {\color{Blue}4})\cdot ({\color{Red}a}, {\color{Red}b}, {\color{Red}c}, {\color{Red}d}) = {\color{Blue} 1}\cdot{\color{Red} a} +{\color{Blue} 2}\cdot{\color{Red} b} +{\color{Blue} 3}\cdot{\color{Red} c} +{\color{Blue} 4}\cdot{\color{Red} d}$

Первая координата в обозначении матрицы обозначает строку, вторая координата — столбец; этот порядок используют как при индексации, так и при обозначении размера. Элемент $x_{{\color{Blue}i}{\color{Red}j}}$ на пересечении строки $i$ и столбца $j$ результирующей матрицы является скалярным произведением $i$-й строки первой матрицы и $j$-го столбца второй матрицы. Это объясняет почему ширина и высота умножаемых матриц должны совпадать: в противном случае скалярное произведение не определено.

Мотивация

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

Последнее естественно вводится исходя из того, что при разложении векторов по базису действие (любого) линейного оператора A дает выражение компонент вектора v' = Av:

$v'_i = \sum\limits_j A_{ij} v_j$

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

(Равно переход к любому новому базису при смене координат представляется полностью аналогичным выражением, только $v'_i$ в этом случае уже не компоненты нового вектора в старом базисе, а компоненты старого вектора в новом базисе; при этом $A_{ij}$ - элементы матрицы перехода к новому базису).

Далее, рассмотрев последовательное действие на вектор двух операторов: сначала A, а потом B (или преобразование базиса A, а затем преобразование базиса B), имеем, дважды применив нашу формулу:

$v''_i = \sum\limits_j B_{ij}\sum\limits_k A_{jk} v_k = \sum\limits_j \sum\limits_k B_{ij} A_{jk} v_k = \sum\limits_k \sum\limits_j (B_{ij} A_{jk}) v_k,$

откуда видно, что композиции BA действия линейных операторов A и B (или аналогичной композиции преобразований базиса) соответствует матрица, вычисляемая по рецепту произведения соответствующих матриц:

$(BA)_{ik} = \sum\limits_j B_{ij} A_{jk}.$

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

Свойства

Сочетательное свойство:

$\mathbf{A} ( \mathbf{B C} ) = ( \mathbf{A B} ) \mathbf{C};$

$\alpha (\mathbf{AB}) = (\alpha\mathbf{A}) \mathbf{B} = \mathbf{A}(\alpha\mathbf{B}).$

Распределительное свойство:

$\mathbf{A} ( \mathbf{B} + \mathbf{C} ) = \mathbf{A B} + \mathbf{AC};$

$( \mathbf{A} + \mathbf{B} ) \mathbf{C} = \mathbf{A C} + \mathbf{B C}.$.

Произведение матрицы на единичную матрицу $\mathbf{E}$ подходящего порядка равно самой матрице:

$\mathbf{EA} = \mathbf{A};$

$\mathbf{AE} = \mathbf{A}.$

Произведение матрицы на нулевую матрицу $\mathbf{0}$ подходящей размерности равно нулевой матрице:

$\mathbf{0A} = \mathbf{0};$

$\mathbf{A0} = \mathbf{0}.$

Если $\mathbf{A}$ и $\mathbf{B}$ — квадратные матрицы одного и того же порядка, то произведение матриц обладает ещё рядом свойств.

Умножение матриц в целом некоммутативно:

$\mathbf{AB} \ne \mathbf{BA}.$

Если $\mathbf{AB} = \mathbf{BA}$, то матрицы $\mathbf{A}$ и $\mathbf{B}$ называются перестановочными или коммутирующими между собой.

Определитель и след произведения не зависят от порядка умножения матриц:

$\det(\mathbf{AB}) = \det(\mathbf{BA}) = \det \mathbf{A} \cdot \det\mathbf{B};$

$\mbox{tr}(\mathbf{AB}) = \mbox{tr}(\mathbf{BA}).$

Обратная матрица

Квадратная матрица $A$ называется неособенной (невырожденной), если она имеет единственную обратную матрицу $A^{-1}$ такую, что выполняется условие:

$\! AA^{-1} = A^{-1}A = E.$

В противном случае матрица $A$ называется особенной (вырожденной).

Матрица $A = \left [ a_{ik} \right]$ порядка $n$ является невырожденной в том и только в том случае, если $\det A = \det \left [ a_{ik} \right ] \ne 0;$ в этом случае $A^{-1}$ есть квадратная матрица того же порядка $n:$

$A^{-1} = \left [ a_{ik} \right ]^{-1} = \left [ \frac{A_{ki}}{\det A} \right ],$

где $A_{ik}$ — алгебраическое дополнение элемента $a_{ik}$ в определителе $\det \left [ a_{ik} \right ].$

Алгоритмы быстрого перемножения матриц

Сложность вычисления произведения матриц по определению составляет $\ O(n^3)$, однако существуют более эффективные алгоритмы, применяющиеся для больших матриц. Вопрос о предельной скорости умножения больших матриц, также как и вопрос о построении наиболее быстрых и устойчивых практических алгоритмов умножения больших матриц остается одной из нерешенных проблем линейной алгебры.

• Алгоритм Штрассена (1969)

Первый алгоритм быстрого умножения больших матриц был разработан Фолькером Штрассеном в 1969. В основе алгоритма лежит рекурсивное разбиение матриц на блоки 2Х2. Штрассен доказал, что матрицы 2Х2 можно некоммутативно перемножить с помощью семи умножений, поэтому на каждом этапе рекурсии выполняется семь умножений вместо восьми. В результате асимптотическая сложность этого алгоритма составляет $O( n^{\log_{2}7}) \approx O(n^{2.81})$. Недостатком данного метода является бо́льшая сложность программирования по сравнению со стандартным алгоритмом, слабая численная устойчивость и больший объём используемой памяти. Разработан ряд алгоритмов на основе метода Штрассена, которые улучшают численную устойчивость, скорость по константе и другие его характеристики. Тем не менее, в силу простоты алгоритм Штрассена остается одним из практических алгоритмов умножения больших матриц. Штрассен также выдвинул следующую гипотезу Штрассена: для сколь угодно малого $\varepsilon > 0$ существует алгоритм, при достаточно больших натуральных n гарантирующий перемножение двух матриц размера $n \times n$ за $O(n^{2+\varepsilon})$ операций.

• Дальнейшие улучшения показателя степени ω для скорости матричного умножения

Хронология улучшения оценок показателя степени ω для скорости матричного умножения.

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

• Алгоритм Пана (1978)

В 1978 Пан предложил свой метод умножения матриц, сложность которого составила Θ(n^2.78041).

• Алгоритм Бини (1979)

В 1979 группа итальянских учёных во главе с Бини разработала алгоритм умножения матриц с использованием тензоров. Его сложность составляет Θ(n^2.7799).

• Алгоритмы Шёнхаге (1981)

В 1981 Шёнхаге представил метод, работающий со скоростью Θ(n^2.695). Оценка получена с помощью подхода,названного частичным матричным умножением. Позже ему удалось получить оценку Θ(n^2.6087).

Затем Шёнхаге на базе метода прямых сумм получил оценку сложности Θ(n^2.548). Романи сумел понизить оценку до Θ(n^2.5166), а Пан — до Θ(n^2.5161).

• Алгоритм Копперсмита — Винограда (1990)

В 1990 Копперсмит и Виноград опубликовали алгоритм, который в модификации Вильямс Василевской 2011 года умножает матрицы со скоростью O(n^2.3727). Этот алгоритм использует идеи, схожие с алгоритмом Штрассена. На сегодняшний день модификации алгоритма Копперсмита-Винограда являются наиболее асимптотически быстрыми. Но тот факт, что полученные улучшения ничтожны, позволяет говорить о существовании "барьера Копперсмита-Винограда" в асимптотических оценках скорости алгоритмов. Алгоритм Копперсмита-Винограда эффективен только на матрицах астрономического размера и на практике применяться не может.

• Связь с теорией групп (2003)

В 2003 Кох и др. рассмотрели в своих работах алгоритмы Штрассена и Копперсмита-Винограда в контексте теории групп. Они показали, что гипотеза Штрассена справедлива, если выполняется одна из гипотез теории групп.

См. также

• Произведение Кронекера

Литература

• Корн Г., Корн Т. Алгебра матриц и матричное исчисление // Справочник по математике. — 4-е издание. — М: Наука, 1978. — С. 392—394..