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

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

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

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

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

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

Азначэнне

Няхай дадзены дзве прамавугольныя матрыцы $A$ і $B$ памеру $l\times m$ і $m\times n$ адпаведна:

$A=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1m}\\ a_{21}& a_{22}& \cdots & a_{2m}\\ ⋮& ⋮& \ddots & ⋮\\ a_{l1}& a_{l2}& \cdots & a_{lm}\end{array}\right],B=\left[\begin{array}{cccc}{b}_{11}& b_{12}& \cdots & b_{1n}\\ b_{21}& b_{22}& \cdots & b_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ b_{m1}& b_{m2}& \cdots & b_{mn}\end{array}\right].$

Тады матрыца $C$ памеру $l\times n$:

$C=\left[\begin{array}{cccc}{c}_{11}& c_{12}& \cdots & c_{1n}\\ c_{21}& c_{22}& \cdots & c_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ c_{l1}& c_{l2}& \cdots & c_{ln}\end{array}\right],$

у якой:

$c_{ij}=\sum _{r=1}^m{a}_{ir}{b}_{rj}(i=1,2,\dots l;j=1,2,\dots n).$

называецца іх здабыткам.

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

Такім чынам, з існавання здабытку $AB$ зусім не вынікае існаванне здабытку $BA$.

Ілюстрацыя

Здабытак матрыц AB складаецца з усіх магчымых камбінацый скалярных здабыткаў вектар-радкоў матрыцы A і вектар-слупкоў матрыцы B. Элемент матрыцы AB з індэксамі i, j ёсць скалярным здабыткам i-га вектар-радка матрыцы A і j-га вектар-слупка матрыцы B.

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

Значэнні на перасячэннях, пазначаных кружочкамі, будуць:

$\begin{array}{cc}{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}\\ 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{array}$

У агульным выпадку, здабытак матрыц не з’яўляецца камутатыўнай аперацыяй. Напрыклад:

$\stackrel{3\times 4\text{ matrix}}{\left[\begin{array}{cccc}\cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot \\ 1& 2& 3& 4\end{array}\right]}\stackrel{4\times 5\text{ matrix}}{\left[\begin{array}{ccccc}\cdot & \cdot & \cdot & a& \cdot \\ \cdot & \cdot & \cdot & b& \cdot \\ \cdot & \cdot & \cdot & c& \cdot \\ \cdot & \cdot & \cdot & d& \cdot \end{array}\right]}=\stackrel{3\times 5\text{ matrix}}{\left[\begin{array}{ccccc}\cdot & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & x_{3,4}& \cdot \end{array}\right]}$

Элемент $x_{3,4}$ здабытку матрыц, прыведзеных вышэй, вылічваецца наступным чынам

$x_{3,4}=(1,2,3,4)\cdot (a,b,c,d)=1\cdot a+2\cdot b+3\cdot c+4\cdot d$

Першая каардыната ў абазначэнні матрыцы абазначае радок, другая каардыната — слупок; гэты парадак выкарыстоўваецца як пры індэксацыі, так і пры абазначэнні памеру. Элемент $x_{ij}$ на перасячэнні радка $i$ і слупка $j$ выніковай матрыцы з’яўляецца скалярным здабыткам $i$-га радка першай матрыцы і $j$-га слупка другой матрыцы. Гэта тлумачыць чаму шырыня і вышыня множаных матрыц павінны супадаць: у адваротным выпадку скалярны здабытак не вызначаны.

Абмеркаванне

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

Апошняе натуральна ўводзіцца зыходзячы з таго, што пры раскладзе вектараў па базісе дзеяння (любога) лінейнага аператара A дае выражэнне кампанентаў вектара v' = Av:

$v{\text{'}}_i=\sum _j{A}_{ij}{v}_j$

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

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

Разгледзеўшы паслядоўнае дзеянне на вектар двух аператараў: спачатку A, а потым B (або пераўтварэнне базіса A, а затым пераўтварэнне базіса B), двойчы прымяніўшы нашу формулу, атрымаем:

$v^{\prime }{\text{'}}_i=\sum _j{B}_{ij}\sum _k{A}_{jk}{v}_k=\sum _j\sum _k{B}_{ij}{A}_{jk}{v}_k=\sum _k\sum _j(B_{ij}{A}_{jk})v_k,$

адкуль відаць, што кампазіцыі BA дзеяння лінейных аператараў A і B (або аналагічнай кампазіцыі пераўтварэнняў базіса) адпавядае матрыца, вылічаная па правілу здабытку адпаведных матрыц:

$(BA{)}_{ik}=\sum _j{B}_{ij}{A}_{jk}.$

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

Уласцівасці

Злучальная ўласцівасць, асацыятыўнасць:

$𝐀(𝐁𝐂)=(𝐀𝐁)𝐂;$

$\alpha (𝐀𝐁)=(\alpha 𝐀)𝐁=𝐀(\alpha 𝐁).$

Размеркавальная ўласцівасць, дыстрыбутыўнасць адносна складання:

$𝐀(𝐁+𝐂)=𝐀𝐁+𝐀𝐂;$

$(𝐀+𝐁)𝐂=𝐀𝐂+𝐁𝐂.$.

Здабытак матрыцы на адзінкавую матрыцу $𝐄$ адпаведнага парадку роўны самой матрыцы:

$𝐄𝐀=𝐀;$

$𝐀𝐄=𝐀.$

Здабытак матрыцы на нулявую матрыцу $\mathrm{𝟎}$ адпаведнага памеру роўны нулявой матрыцы:

$\mathrm{𝟎}𝐀=\mathrm{𝟎};$

$𝐀\mathrm{𝟎}=\mathrm{𝟎}.$

Калі $𝐀$ і $𝐁$ — квадратныя матрыцы аднаго і таго ж парадку, то здабытак матрыц валодае яшчэ шэрагам уласцівасцей.

Множанне матрыц у агульным выпадку некамутатыўна:

$𝐀𝐁\ne 𝐁𝐀.$

Калі $𝐀𝐁=𝐁𝐀$, то матрыцы $𝐀$ і $𝐁$ называюцца камутавальнымі паміж сабой.

Прасцейшыя прыклады камутавальных матрыц:

• любая квадратная матрыца — з самой сабой: $𝐀𝐀=𝐀𝐀={𝐀}^{\mathrm{𝟐}}$ (узвядзенне матрыцы ў квадрат);
• любая квадратная матрыца — з адзінкавай матрыцай таго ж парадку: $𝐀𝐄=𝐄𝐀=𝐀$;
• любая квадратная матрыца — з нулявой матрыцай таго ж парадку: $𝐀\mathrm{𝟎}=\mathrm{𝟎}𝐀=\mathrm{𝟎}$;
• любая нявыраджаная квадратная матрыца — са сваёй адваротнай матрыцай: $𝐀{𝐀}^{\mathbf{-}\mathrm{𝟏}}={𝐀}^{\mathbf{-}\mathrm{𝟏}}𝐀=𝐄$.

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

$\det (𝐀𝐁)=\det (𝐁𝐀)=\det 𝐀\cdot \det 𝐁;$

$\text{tr}(𝐀𝐁)=\text{tr}(𝐁𝐀).$

Адваротная матрыца

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

$A{A}^{-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)

Першы алгарытм хуткага множання вялікіх матрыц быў распрацаваны Фолькерам ШтрасенамШаблон:Source-ref у 1969 годзе. У аснове алгарытму ляжыць рэкурсіўная разбіўка матрыц на блокі 2×2. Штрасен даказаў, што матрыцы 2×2 можна некамутатыўна перамножыць з дапамогай сямі множанняў, таму на кожным этапе рэкурсіі выконваецца сем множанняў замест васьмі. У выніку асімптатычная складанасць гэтага алгарытму складае $O(n^{{\log }_{2}7})\approx O(n^{2.81})$. Недахопам гэтага метаду з’яўляецца большая складанасць праграмавання ў параўнанні са стандартным алгарытмам, слабая лікавая ўстойлівасць і большы аб’ём выкарыстанай памяці. Распрацаваны шэраг алгарытмаў на аснове метаду Штрасена, якія паляпшаюць лікавую ўстойлівасць, хуткасць па канстанце і іншыя яго характарыстыкі. Тым не менш, з-за прастаты алгарытм Штрасена застаецца адным з практычных алгарытмаў множання вялікіх матрыц. Штрасен таксама вылучыў наступную гіпотэзу Штрасена: для якой заўгодна малой $\epsilon >0$ існуе алгарытм, пры дастаткова вялікіх натуральных n гарантуе перамнажэнне дзвюх матрыц памеру $n\times n$ за $O(n^{2+\epsilon })$ аперацый.

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

Храналогія паляпшэння ацэнак паказчыка ступені ω для вылічальнай складанасці матрычнага множання $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+\epsilon })$ для любога $\epsilon$), калі выконваецца адна з гіпотэз тэорыі груп.

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

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

Матрыца Шаблон:Math памеру Шаблон:Math, узведзеная ў ступень, вызначаецца формулай

${𝐀}^k=\underset{k}{\underbrace{𝐀𝐀\cdots 𝐀}}$

і валодае наступнымі ўласцівасцямі (Шаблон:Math — некаторы скаляр):

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

${𝐀}^0=𝐄$

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

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

$(\lambda 𝐀{)}^k={\lambda }^k{𝐀}^k$

Вызначнік:

$\det ({𝐀}^k)=\det (𝐀{)}^k$

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

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

${𝐀}^k={\left(\begin{array}{cccc}{a}_{11}& 0& \cdots & 0\\ 0& a_{22}& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & a_{nn}\end{array}\right)}^k=\left(\begin{array}{cccc}{a}_{11}^k& 0& \cdots & 0\\ 0& a_{22}^k& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & a_{nn}^k\end{array}\right).$

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

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

Гл. таксама

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

Літаратура

• Шаблон:Кніга