Множанне матрыц

**Мно́жанне ма́трыц** — адна з асноўных аперацый над матрыцамі. Матрыца, атрыманая ў выніку аперацыі множання, называецца **здабы́ткам ма́трыц**. Элементы новай матрыцы атрымліваюцца з элементаў старых матрыц у адпаведнасці з правіламі, праілюстраванымі ніжэй.

Матрыцы A і B могуць быць памножаны, калі яны **сумяшчальныя** ў тым сэнсе, што колькасць слупкоў матрыцы A роўная колькасці радкоў B.

Матрыцы маюць шматлікія алгебраічныя ўласцівасці множання, уласцівыя звычайным лікам, за выключэннем камутатыўнасці.

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

Паколькі матрыцы выкарыстоўваюцца для апісання, у прыватнасці, пераўтварэнняў матэматычных прастораў (паварот, адлюстраванне, расцяжэнне і іншыя), здабытак матрыц будзе апісваць кампазіцыю пераўтварэнняў.

## Азначэнне 
Няхай дадзены дзве прамавугольныя матрыцы A і B памеру l \times m і m \times n адпаведна:
: 
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}.

Тады матрыца C памеру l \times n:
: 
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},

у якой:
:  c_{ij} = \sum_{r=1}^m a_{ir}b_{rj} \;\;\; \left(i=1, 2, \ldots l;\; j=1, 2, \ldots n \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**' = *A***v**:
: v'_i = \sum\limits_j A_{ij} v_j

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

(Пераход да любога новага базіса пры змене каардынат прадстаўляецца цалкам аналагічным выразам, толькі 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} называюцца камутавальнымі паміж сабой.

Прасцейшыя прыклады камутавальных матрыц:
* любая квадратная матрыца — з самой сабой: \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 ] \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 годзе Пан прапанаваў свой метад множання матрыц, складанасць якога склала **Θ(n2.78041)**.
:* **Алгарытм Біні (1979)**
:: У 1979 годзе група італьянскіх навукоўцаў на чале з Біні распрацавала алгарытм множання матрыц з выкарыстаннем тэнзараў. Яго складанасць складае **Θ(n2.7799)**.
:* **Алгарытмы Шонхаге (1981)**
:: У 1981 годзе Шонхаге прадставіў метад, які працуе з хуткасцю **Θ(n2.695)**. Ацэнка атрымана з дапамогай падыходу, названага *частковым матрычным множаннем*. Пазней яму ўдалося атрымаць ацэнку **Θ(n2.6087)**.
:: Затым Шонхаге на базе *метаду прамых сум* атрымаў ацэнку складанасці **Θ(n2.548)**. Рамані змог панізіць ацэнку да **Θ(n2.5166)**, а Пан — да **Θ(n2.5161)**.
* **Алгарытм Каперсміта — Вінаграда (1990)**
: У 1990 годзе Копперсміт і Вінаград апублікавалі алгарытм, асімптатычная складанасць якога складала **O(n2.3755)**. Гэты алгарытм выкарыстоўвае ідэі, падобныя з алгарытмам Штрасена. На сённяшні дзень мадыфікацыі алгарытму Каперсміта—Вінаграда з’яўляюцца найбольш асімптатычна хуткімі. У апошняй мадыфікацыі (2024) складанасць алгарытму складае **O(n2.371552)**. Вядома, што шырокі клас мадыфікацый гэтага алгарытму ў прынцыпе не можа дасягнуць складанасці лепшай, чым **O(n2.3078)**. Алгарытм Копперсміта—Вінаграда эфектыўны толькі на матрыцах астранамічнага памеру і на практыцы прымяняцца не можа.
* **Сувязь з тэорыяй груп (2003)**
: У 2003 годзе Кох і інш. разгледзелі ў сваіх працах алгарытмы Штрасена і Каперсміта-Вінаграда ў кантэксце тэорыі груп. Яны паказалі, што гіпотэза Штрасена справядлівая (г. зн. мінімальная складанасць абмежаваная O(n^{2+\varepsilon}) для любога \varepsilon), калі выконваецца адна з гіпотэз тэорыі груп.

## Ступені матрыц 
Квадратныя матрыцы можна шмат разоў множыць самі на сябе гэтак жа, як звычайныя лікі, паколькі ў іх аднолькавая колькасць радкоў і слупкоў. Такое паслядоўнае множанне можна назваць **узвядзеннем матрыцы ў ступень** — гэта будзе прыватным выпадкам звычайнага множання некалькіх матрыц. У прамавугольных матрыц колькасць радкоў і слупкоў розная, таму іх *ніколі* нельга ўзводзіць у ступень.

Матрыца  памеру , узведзеная ў ступень, вызначаецца формулай
: \mathbf{A}^k = \underbrace{\mathbf{A}\mathbf{A}\cdots\mathbf{A}}_{k}
і валодае наступнымі ўласцівасцямі ( — некаторы скаляр):

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

: \mathbf{A}^0 = \mathbf{E}

дзе **E** — адзінкавая матрыца. Гэта аналаг таго факту, што нулявая ступень любога ліку роўная адзінцы.

**Множанне на скаляр:**

:  ( \lambda \mathbf{A} )^k = \lambda^k\mathbf{A}^k

**Вызначнік:**

:  \det(\mathbf{A}^k) = \det(\mathbf{A})^k 

Найбольш просты спосаб вылічэння ступені матрыцы — гэта множыць  разоў матрыцу  на вынік папярэдняга множання, пачынаючы з адзінкавай матрыцы, як гэта часта робяць для скаляраў. Для дыяганалізуемых матрыц існуе лепшы метад, заснаваны на выкарыстанні спектральнага раскладанне матрыцы . Яшчэ адзін метад, заснаваны на тэарэме Гамільтана — Кэлі, будуе больш эфектыўнае выражэнне для , у якім у патрабаваную ступень узводзіцца *скаляр*, а не ўся *матрыца''.

Асобны выпадак складаюць дыяганальныя матрыцы. Паколькі здабытак дыяганальных матрыц зводзіцца да множання адпаведных дыяганальных элементаў, то -ая ступень дыяганальнай матрыцы  складаецца з элементаў, узведзеных у патрабаваную ступень:
: 
  \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}.

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

Выкарыстоўваючы множанне матрыц і ўзвядзенне матрыц у ступень, можна вызначыць іншыя аперацыі над матрыцамі. Напрыклад, матрычная экспанента можа быць вызначана праз ступеневы рад, матрычны лагарыфм — як адваротная да матрычнай экспаненты функцыя і гэтак далей.

## Гл. таксама 
* Здабытак Кронекера
* Здабытак Адамара

## Літаратура 
* 

## Крыніцы 
Катэгорыя:Алгарытмы множання матрыц
Катэгорыя:Матрыцы
Катэгорыя:Лічбавыя метады лінейнай алгебры
Катэгорыя:Білінеарныя аператары