Множення матриць - одна з основних операцій над матрицями. Матриця, що отримується в результаті операції множення, називається твором матриць.


1. Визначення

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


2. Ілюстрація

Matrix multiplication diagram 2.svg

Добуток матриць 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 -Го стовпця другого матриці. Це пояснює чому ширина і висота множимо матриць повинні збігатися: в іншому випадку скалярний добуток не визначено.


3. Мотивування

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

Останнє природно вводиться виходячи з того, що при розкладанні векторів по базису дію (будь-якого) лінійного оператора A дає вираз компонент вектора v '= A v:

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}.

Певне таким чином твір матриць виявляється абсолютно природним і очевидно корисним (дає простий і універсальний спосіб обчислення композицій довільної кількості лінійних перетворень).


4. Властивості

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

\ 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} \ 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}).

5. Зворотний матриця

Квадратна матриця 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].


6. Алгоритми швидкого множення матриць

Складність обчислення добутку матриць за визначенням складає Θ (n 3), однак існують більш ефективні алгоритми [1], що застосовуються для великих матриць.

  • Алгоритм штрассе (1969)
    Перший алгоритм швидкого множення матриць був розроблений В. Штрассеном [2] в 1969. В основі алгоритму лежить рекурсивне розбиття матриць на блоки. На кожному етапі рекурсії виконується сім множень замість восьми. В результаті складність цього алгоритму складає O (n ^ {\ log_ {2} 7}) \ approx O (n ^ {2.807}) . Недоліком даного методу є велика складність програмування в порівнянні зі стандартним алгоритмом, чисельна нестійкість і великий обсяг використовуваної пам'яті.
    Розроблено велику кількість алгоритмів на основі методу штрассе, які покращують його чисельну стійкість і зменшують обсяг використовуваної пам'яті.
  • Алгоритм Пана (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] опублікували алгоритм, умножающий матриці зі складністю O (n 2.3727). [7] Цей алгоритм використовує ідеї, схожі з алгоритмом штрассе. На сьогоднішній день алгоритм Копперсміта-Винограда є найбільш асимптотично швидким, але він ефективний тільки на дуже великих матрицях і тому не застосовується.
  • Алгоритми з використанням теорії груп (2003)
    У 2003 Кох та ін розглянули у своїх роботах [8] алгоритми штрассе і Копперсміта-Винограда в контексті теорії груп. Вони показали можливість існування алгоритмів множення матриць із складністю Θ (n 2) [9].

Література

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

Примітки

  1. Кібернетичний збірник. Нова серія. Вип. 25. Сб статей 1983 - 1985 рр..: Пер. з англ. - М.: Мир, 1988 - В.Б. Алексс. Складність множення матриць. Огляд.
  2. Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969
  3. Pan V. Ya, Strassen's algorithm is not optimal - trilinear technique of aggregating uniting and canceling for constructing fast algorithms for matrix operations. - Proc. 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Mich., 1978
  4. Bini D., Capovani M., Lotti G., Romani F. - O (n ^ {2.7799}) complexity for approximate matrix multiplication. - Inform. Process. Lett., 1979
  5. Schonhage A. Partial and total matrix multiplication. - SIAM J. Comput., 1981
  6. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251-280, 1990.
  7. Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier - www.cs.berkeley.edu/ ~ virgi / matrixmult.pdf.
  8. Group-theoretic Algorithms for Matrix Multiplication - www.cs.caltech.edu/ ~ umans/papers/CKSU05.pdf
  9. Toward an Optimal Algorithm for Matrix Multiplication - www.siam.org/pdf/news/174.pdf