Множення матриць

Множе́ння ма́триць — це бінарна операція, яка використовуючи дві матриці, утворює нову матрицю, яка називається доб́утком ма́триць. Дійсні або комплексні числа множаться відповідно до правил елементарної арифметики. З іншого боку, матриці є масивами чисел, тому існують різні способи визначити добуток матриць. Таким чином, загалом термін «матричне множення» означає різні способи перемноження матриць. Ключовими особливостями будь-якого матричного множення є: кількість рядків і стовпців, в початкових матрицях, і правило, як елементи матриць утворюють нову матрицю.

Визначення

Нехай дано дві прямокутні матриці $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{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}}$

У загальному випадку, добуток матриць не є комутативною операцією. Приміром:

${\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 {BC} )=(\mathbf {AB} )\mathbf {C} ;$

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

Розподільна властивість, дистрибутивність щодо додавання:

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

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

Добуток матриці на одиничну матрицю $\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} \neq \mathbf {BA} .$

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

Найпростіші приклади комутуючих матриць:

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

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

$\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]\neq 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 Кох та ін. розглянули в своїх роботах алгоритми Штрассена і Копперсміта-Винограда в контексті теорії груп. Вони показали, що гіпотеза Штрассена справедлива, якщо виконується одна з гіпотез теорії груп.

Див. також

• Добуток Адамара
• Добуток Кронекера
• Basic Linear Algebra Subprograms
• Добуток Хатрі-Рао
• Торцевий добуток

Джерела

• Гантмахер Ф. Р. Теория матриц. — 5-е. — М: : Физматлит, 2010. — 559 с. — ISBN 5-9221-0524-8.(рос.)
• Ланкастер П. Теория матриц. — Москва : Наука, 1973. — 280 с.(рос.)
• Р.Хорн, Ч.Джонсон. Матричный анализ. — М: : Мир, 1989. — 653 с.(рос.)
• Корн Г., Корн Т. Довідник по математиці. — Москва : Наука, 1978. — С. 392-394.