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

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

Матрыцы $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{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}$

То бок лінейны аператар аказваецца прадстаўлены матрыцай, вектары — вектарамі-слупкамі, а дзеянне аператара на вектар — матрычным множаннем вектара-слупка злева на матрыцу аператара (гэта прыватны выпадак матрычнага множання, калі адна з матрыц — вектар-слупок — мае памер $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 {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 })$ аперацый.

• Далейшыя паляпшэнні паказчыка ступені ω для хуткасці матрычнага множання

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

У далейшым ацэнкі хуткасці множання вялікіх матрыц шматразова паляпшаліся. Аднак гэтыя алгарытмы насілі тэарэтычны, галоўным чынам набліжаны характар. З-за неўстойлівасці алгарытмаў набліжанага множання ў цяперашні час яны не выкарыстоўваюцца на практыцы.

• Алгарытм Пана (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 годзе Копперсміт і Вінаград апублікавалі алгарытм, асімптатычная складанасць якога складала O(n^2.3755). Гэты алгарытм выкарыстоўвае ідэі, падобныя з алгарытмам Штрасена. На сённяшні дзень мадыфікацыі алгарытму Каперсміта—Вінаграда з’яўляюцца найбольш асімптатычна хуткімі. У апошняй мадыфікацыі (2024) складанасць алгарытму складае O(n^2.371552). Вядома, што шырокі клас мадыфікацый гэтага алгарытму ў прынцыпе не можа дасягнуць складанасці лепшай, чым O(n^2.3078). Алгарытм Копперсміта—Вінаграда эфектыўны толькі на матрыцах астранамічнага памеру і на практыцы прымяняцца не можа.

• Сувязь з тэорыяй груп (2003)

У 2003 годзе Кох і інш. разгледзелі ў сваіх працах алгарытмы Штрасена і Каперсміта-Вінаграда ў кантэксце тэорыі груп. Яны паказалі, што гіпотэза Штрасена справядлівая (г. зн. мінімальная складанасць абмежаваная $O(n^{2+\varepsilon })$ для любога $\varepsilon$), калі выконваецца адна з гіпотэз тэорыі груп.

Ступені матрыц

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

Матрыца A памеру n × n, узведзеная ў ступень, вызначаецца формулай

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

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

Асобны выпадак складаюць дыяганальныя матрыцы. Паколькі здабытак дыяганальных матрыц зводзіцца да множання адпаведных дыяганальных элементаў, то k-ая ступень дыяганальнай матрыцы A складаецца з элементаў, узведзеных у патрабаваную ступень:

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

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

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

Гл. таксама

• Здабытак Кронекера
• Здабытак Адамара

Літаратура

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