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

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

Матрицы ${\displaystyle A}$ и ${\displaystyle B}$ могут быть перемножены, если они совместимы в том смысле, что число столбцов матрицы ${\displaystyle A}$ равно числу строк ${\displaystyle B}$.

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

Для квадратных матриц, помимо умножения, может быть введена операция возведения матрицы в степень и обратная матрица.

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

Определение[ | ]

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

${\displaystyle A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1m}\\a_{21}&a_{22}&\cdots &a_{2m}\\\vdots &\vdots &\ddots &\vdots \\a_{l1}&a_{l2}&\cdots &a_{lm}\end{bmatrix}},\;\;\;B={\begin{bmatrix}b_{11}&b_{12}&\cdots &b_{1n}\\b_{21}&b_{22}&\cdots &b_{2n}\\\vdots &\vdots &\ddots &\vdots \\b_{m1}&b_{m2}&\cdots &b_{mn}\end{bmatrix}}.}$

Тогда матрица ${\displaystyle C}$ размерностью ${\displaystyle l\times n}$:

${\displaystyle C={\begin{bmatrix}c_{11}&c_{12}&\cdots &c_{1n}\\c_{21}&c_{22}&\cdots &c_{2n}\\\vdots &\vdots &\ddots &\vdots \\c_{l1}&c_{l2}&\cdots &c_{ln}\end{bmatrix}},}$

в которой:

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

называется их произведением.

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

Таким образом, из существования произведения ${\displaystyle AB}$ вовсе не следует существование произведения ${\displaystyle BA.}$

Иллюстрация[ | ]

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

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

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

${\displaystyle {\begin{aligned}{\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{aligned}}}$

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

${\displaystyle {\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}}}}$

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

${\displaystyle 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}}$

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

Обсуждение[ | ]

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

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

${\displaystyle v'_{i}=\sum \limits _{j}A_{ij}v_{j}}$

То есть линейный оператор оказывается представлен матрицей, векторы — векторами-столбцами, а действие оператора на вектор — матричным умножением вектора-столбца слева на матрицу оператора (это частный случай матричного умножения, когда одна из матриц — вектор-столбец — имеет размер ${\displaystyle n\times 1}$).

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

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

${\displaystyle 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 (или аналогичной композиции преобразований базиса) соответствует матрица, вычисляемая по правилу произведения соответствующих матриц:

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

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

Свойства[ | ]

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

${\displaystyle \mathbf {A} (\mathbf {BC} )=(\mathbf {AB} )\mathbf {C} ;}$

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

Распределительное свойство, дистрибутивность относительно сложения:

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

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

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

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

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

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

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

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

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

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

${\displaystyle \mathbf {AB} \neq \mathbf {BA} .}$

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

Простейшие примеры коммутирующих матриц:

• любая квадратная матрица — с самой собой: ${\displaystyle \mathbf {AA} =\mathbf {AA} =\mathbf {A^{2}} }$ (возведение матрицы в квадрат);
• любая квадратная матрица — с единичной матрицей того же порядка: ${\displaystyle \mathbf {AE} =\mathbf {EA} =\mathbf {A} }$;
• любая квадратная матрица — с нулевой матрицей того же порядка: ${\displaystyle \mathbf {A0} =\mathbf {0A} =\mathbf {0} }$;
• любая невырожденная квадратная матрица — со своей обратной матрицей: ${\displaystyle \mathbf {AA^{-1}} =\mathbf {A^{-1}A} =\mathbf {E} }$.

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

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

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

Обратная матрица[ | ]

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

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

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

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

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

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

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

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

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

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

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

Хронология улучшения оценок показателя степени ω для вычислительной сложности матричного умножения ${\displaystyle O(n^{\omega })}$.

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

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

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

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

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

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

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

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

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

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

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

В 2003 Кох и др. рассмотрели в своих работах^[8] алгоритмы Штрассена и Копперсмита-Винограда в контексте теории групп. Они показали, что гипотеза Штрассена справедлива (т.е. минимальная сложность ограничена ${\displaystyle O(n^{2+\epsilon })}$ для любого ${\displaystyle \epsilon }$) , если выполняется одна из гипотез теории групп^[9].

Степени матриц[ | ]

Квадратные матрицы можно многократно умножать сами на себя так же, как обычные числа, так как у них одинаковое число строк и столбцов. Такое последовательное умножение можно назвать возведением матрицы в степень — это будет частный случай обычного умножения нескольких матриц. У прямоугольных матриц число строк и столбцов разное, поэтому их никогда нельзя возводить в степень. Матрица A размерности n × n, возведённая в степень, определяется формулой

${\displaystyle \mathbf {A} ^{k}=\underbrace {\mathbf {A} \mathbf {A} \cdots \mathbf {A} } _{k}}$

и обладает следующими свойствами (λ — некоторый скаляр):

Нулевая степень:

${\displaystyle \mathbf {A} ^{0}=\mathbf {E} }$

где E - единичная матрица. Это аналог того факта, что нулевая степень любого числа равна единице.

Умножение на скаляр:

${\displaystyle (\lambda \mathbf {A} )^{k}=\lambda ^{k}\mathbf {A} ^{k}}$

Определитель:

${\displaystyle \det(\mathbf {A} ^{k})=\det(\mathbf {A} )^{k}}$

Наивный способ вычисления степени матрицы — это умножать k раз матрицу A на результат предыдущего умножения, начиная с единичной матрицы, как это часто делают для скаляров. Для диагонализируемых матриц существует лучший метод, основанный на использовании спектрального разложения матрицы A. Ещё один метод, основанный на теореме Гамильтона — Кэли, строит более эффективное выражение для A^k, в котором в требуемую степень возводится скаляр, а не вся матрица.

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

${\displaystyle \mathbf {A} ^{k}={\begin{pmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}\end{pmatrix}}^{k}={\begin{pmatrix}a_{11}^{k}&0&\cdots &0\\0&a_{22}^{k}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}^{k}\end{pmatrix}}.}$

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

Используя умножение матриц и возведение матриц в степень, можно определить другие операции над матрицами. Например, матричная экспонента может быть определена через степенной ряд, матричный логарифм^[en] — как обратная к матричной экспоненте функция и так далее.

См. также[ | ]

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

Литература[ | ]

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

Примечания[ | ]