Zobrazení zdroje stránky Násobení matic

[[Soubor:Matrix multiplication diagram.svg|Pro součin matic musí být počet sloupců v první matici roven počtu řádků ve druhé matici. Výsledná matice má počet řádků první matice a počet sloupců druhé matice.|náhled]]
'''Součin matic'''<ref>{{Citace monografie
 | titul = Slovník školské matematiky
 | vydavatel = SPN
 | místo = Praha
 | rok = 1981
 | počet_stran = 240
}}</ref><ref name=norma>{{Citace normy
| označení = ČSN EN ISO 80000-2 (011300)
| název = Veličiny a jednotky - Část 2: Matematika
| vydal = Česká agentura pro standardizaci
| url = https://csnonline.agentura-cas.cz/Detailnormy.aspx?k=511177
| datum vydání = 2020-11-01
}}</ref> hovorově též '''maticové násobení''' (neplést se [[násobení skalárem|skalárním násobkem matice]]) je v [[matematika|matematice]] zobecnění [[násobení|součinu]] [[číslo|čísel]] na [[matice]]. Formálně se dá definovat jako [[binární operace]] na  [[matice|maticích]] odpovídajících typů. Využívá se v [[matematika|matematice]], [[fyzika|fyzice]] a jejich aplikacích, obvykle pro popis '''skládání [[lineární zobrazení|lineárních zobrazení]]'''.

Speciálním případem násobení matic je součin matice typu <math>m\times n</math> a vektoru braného jako [[matice]] o typu <math>n\times 1</math> ([[sloupcový vektor]]). Tento součin lze interpretovat jako aplikaci lineárního zobrazení reprezentovaného [[Transformační matice|transformační maticí]] na vektor.

== Formální definice ==
Pokud je <math>\boldsymbol A</math> [[matice]] typu <math>m\times n</math> a <math>\boldsymbol B</math> je matice typu <math>n\times p</math>, jejich '''součin''' <math>\boldsymbol A \cdot \boldsymbol B</math> je matice typu <math>m\times p</math> definovaná vztahem

:<math> (\boldsymbol A\cdot \boldsymbol B)_{ij} = \sum_{k=1}^n a_{ik}b_{kj} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{in}b_{nj}. </math>

pro všechny prvky výsledné matice indexované <math>i\in\{1,\dots,m\}</math> a <math>j\in\{1,\dots,p\}</math>.

Ve většině případů jsou prvky matice čísla, ale mohou to být jakékoli druhy matematických objektů, pro které je definováno sčítání a násobení, které jsou [[asociativní operace|asociativní]] a takové, že sčítání je [[komutativní operace|komutativní]] a násobení je [[distributivní operace|distributivní]] s ohledem na sčítání, typicky prvky nějakého [[Těleso (algebra)|tělesa]]. Prvky mohou být dokonce samotné matice ([[bloková matice]]).

U reálných matic lze prvek v <math>i</math>-tém řádku a <math>j</math>-tém sloupci výsledné matice lze také chápat jako standardní [[skalární součin]] vektoru <math>i</math>-tého řádku první matice s vektorem <math>j</math>-tého sloupce druhé matice.

Tečka <math>\cdot</math> se v součinu vynechává a píše se pouze <math>\boldsymbol{AB}</math>.<ref name=norma/>

== Ukázka výpočtu ==
[[File:MatrixMultiplication.png|thumb|300px|Schéma součinu <math>\boldsymbol{A}\boldsymbol{B}</math> dvou matic <math>\boldsymbol{A}</math> a <math>\boldsymbol{B}</math>.]]
Součin matic <math>
\boldsymbol{A}=
\begin{pmatrix}
\color{blue}1 & \color{blue}2 & \color{blue}3 \\
\color{orange}4 & \color{orange}5 & \color{orange}6 \\
\end{pmatrix}</math> a <math>
\boldsymbol{B}=
\begin{pmatrix}
\color{red}1 & \color{green}2  \\
\color{red}3 & \color{green}4  \\
\color{red}5 & \color{green}6 \\
\end{pmatrix}</math> je
:<math>
\boldsymbol{AB}=\begin{pmatrix}
({\color{blue}1} \cdot {\color{red}1}+{\color{blue}2} \cdot {\color{red}3}+{\color{blue}3} \cdot {\color{red}5}) & ({\color{blue}1} \cdot {\color{green}2}+{\color{blue}2} \cdot {\color{green}4}+{\color{blue}3} \cdot {\color{green}6})\\
({\color{orange}4} \cdot {\color{red}1}+{\color{orange}5} \cdot {\color{red}3}+{\color{orange}6} \cdot {\color{red}5}) & ({\color{orange}4} \cdot {\color{green}2}+{\color{orange}5} \cdot {\color{green}4}+{\color{orange}6} \cdot {\color{green}6})\\
\end{pmatrix}=
\begin{pmatrix}
22 & 28\\
49 & 64
\end{pmatrix}
</math>

Prvky matice <math>\boldsymbol A</math> zůstávají v řádcích tak, jak jsou, a prvky v matici <math>\boldsymbol B</math> se rozmístí opět do levého a pravého sloupce.

== Použití ==

Historicky bylo násobení matic zavedeno pro usnadnění a objasnění výpočtů v [[lineární algebra|lineární algebře]]. Tento silný vztah mezi maticovým součinem a lineární algebrou zůstává je fundamentální  v celé matematice, stejně jako ve [[fyzika|fyzice]], [[chemie|chemii]], [[inženýrství]] a [[informatika|informatice]].

===Soustavy lineárních rovnic===
Obecný tvar [[soustava lineárních rovnic|soustavy lineárních rovnic]] je
:<math>
\begin{array}{rcr}
a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n &=& b_1 \\
a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n &=& b_2 \\
&\vdots& \\
a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n &=& b_m \\
\end{array}
</math>

Při použití stejné notace jako výše je zápis soustavy ekvivalentní jednoduché maticové [[rovnice|rovnici]]
:<math>\boldsymbol{Ax}=\boldsymbol b</math>.

===Lineární zobrazení===
Pokud má [[vektorový prostor]] konečnou [[báze (lineární algebra)|bázi]], každý z jeho vektorů je jednoznačně reprezentován konečnou [[posloupnost (matematika)|posloupností]] skalárů, nazývanou [[vektor souřadnic]], tvořenou [[Soustava souřadnic|souřadnicemi]] vektoru vzhledem k bázi. Tyto vektory souřadnic tvoří další vektorový prostor, který je [[izomorfismus|izomorfní]] původnímu vektorovému prostoru. Vektor souřadnic je běžně zapisován jako ''sloupcový vektor'', což je matice pouze s jedním sloupcem. Sloupcový vektor pak představuje jak souřadnicový vektor, tak i vektor původního vektorového prostoru.

[[Lineární zobrazení]] <math>A</math> prostoru dimenze <math>n</math> do vektorového prostoru dimenze <math>m</math> převádí sloupcový vektor
:<math>\boldsymbol x=\begin{pmatrix}x_1 \\ x_2 \\ \vdots \\ x_n\end{pmatrix}</math>
na sloupcový vektor
:<math>\boldsymbol y= A(\boldsymbol x)= \begin{pmatrix}a_{11}x_1+\cdots + a_{1n}x_n\\ a_{21}x_1+\cdots + a_{2n}x_n \\ \vdots \\ a_{m1}x_1+\cdots + a_{mn}x_n\end{pmatrix}.</math>
Lineární zobrazení <math>A</math> je proto definováno maticí
:<math>\boldsymbol{A}=\begin{pmatrix}
 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{pmatrix}, </math>
a zobrazuje sloupcový vektor <math>\boldsymbol x</math> na maticový součin
:<math>\boldsymbol y = \boldsymbol {Ax}</math>.

Je-li <math>B</math> další lineární zobrazení z předchozího vektorového prostoru dimenze <math>m</math>, do vektorového prostoru dimenze <math>p</math>, pak jej lze reprezentovat maticí <math>\boldsymbol B</math> řádu <math>p\times m</math>. Přímý výpočet ukazuje, že matice [[skládání funkcí|složeného zobrazení]] <math>B\circ A</math> je rovna součinu <math>\boldsymbol {BA}</math>. Obecný vzorec <math>(B\circ A)(\boldsymbol x) = B(A(\boldsymbol x))</math>, který definuje složené zobrazení, je jedním z specifických případů asociativity maticového součinu:
:<math>(\boldsymbol{BA})\boldsymbol x = \boldsymbol{B}(\boldsymbol {Ax}) = \boldsymbol{BAx}.</math>

====Geometrické rotace====
Při použití systému [[kartézské souřadnice|kartézských souřadnic]] v euklidovské rovině je [[rotace (geometrie)|rotace]] o úhel <math>\alpha</math> kolem počátku (počátek odpovídá [[nulový vektor|nulovému vektoru]]) lineární zobrazení. Přesněji,
<math display="block"> 
\begin{pmatrix} 
x' \\ 
y' 
\end{pmatrix} =
\begin{pmatrix} 
\cos \alpha & - \sin \alpha \\ 
\sin \alpha & \cos \alpha 
\end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix},</math>
kde výchozí bod <math>(x,y)</math> i jeho obraz <math>(x',y')</math> jsou zapsány jako sloupcové vektory.

Složení rotací o úhel <math>\alpha</math> a pak o úhel <math>\beta</math> odpovídá maticovému součinu
<math display="block">
\begin{pmatrix} 
\cos \beta & - \sin \beta \\ 
\sin \beta & \cos \beta 
\end{pmatrix}
\begin{pmatrix} 
\cos \alpha & - \sin \alpha \\ 
\sin \alpha & \cos \alpha 
\end{pmatrix}
= 
\begin{pmatrix} 
\cos \beta \cos \alpha - \sin \beta \sin \alpha & - \cos \beta \sin \alpha - \sin \beta \cos \alpha \\
\sin \beta \cos \alpha + \cos \beta \sin \alpha & - \sin \beta \sin \alpha + \cos \beta \cos \alpha 
\end{pmatrix}
=
\begin{pmatrix} 
\cos (\alpha+\beta) & - \sin(\alpha+\beta) \\ \sin(\alpha+\beta) & \cos(\alpha+\beta) \end{pmatrix},
</math>
ve druhé rovnosti jsou použity [[Goniometrická funkce|součtové vzorce]]. Výsledné složení odpovídá rotaci o úhel <math>\alpha+\beta</math>, jak lze očekávat.

===Skalární součin, bilineární forma a seskvilineární forma ===
Standardní [[skalární součin]] dvou reálných sloupcových vektorů lze zapsat maticovým součinem
:<math>\boldsymbol x^\mathsf T \boldsymbol y,</math>
kde <math>\boldsymbol x^\mathsf T</math> je [[řádkový vektor]] získaný pomocí [[transpozice matice|transpozice]] <math>\boldsymbol x</math>. (Výsledná matice <math>1\times 1</math> je zde ztotožněna se svým jediným prvkem.)

Obecněji lze jakoukoli [[bilineární forma|bilineární formu]] ve vektorovém prostoru konečného rozměru vyjádřit jako maticový součin
:<math>\boldsymbol x^\mathsf T \boldsymbol {Ay},</math>
a jakoukoliv [[seskvilineární forma|seskvilineární formu]] lze vyjádřit jako
:<math>\boldsymbol x^{\mathsf H} \boldsymbol {Ay},</math>
kde <math>\boldsymbol x^{\mathsf H}</math> je [[Hermitovská transpozice|hermitovsky sdružený]] vektor k vektoru <math>\boldsymbol x</math>.

====Alokace zdrojů v ekonomii====
[[File:Mmult factory svg.svg|thumb|400px|Výpočet prvku v levém dolním rohu součinu <math>\boldsymbol{AB}</math>  odpovídá všem možným cestám (zvýrazněné) od suroviny <math>b_4</math> ke konečnému výrobku <math>f_1</math> v grafu toku výroby.]]
Jako příklad si představme fiktivní továrnu, která používá 4 druhy surovin <math>b_1, b_2, b_3, b_4</math> k výrobě 3 meziproduktů, <math>m_1, m_2, m_3</math>, které se následně používají k výrobě 3 druhů výrobků, <math>f_1, f_2, f_3</math>. 

Matice <math>
\boldsymbol{A} = 
\begin{pmatrix} 
1 & 0 & 1 \\ 
2 & 1 & 1 \\ 
0 & 1 & 1 \\ 
1 & 1 & 2 \\ 
\end{pmatrix}
</math> &nbsp; a &nbsp; <math>\boldsymbol{B} = 
\begin{pmatrix}
1 & 2 & 1 \\ 
2 & 3 & 1 \\ 
4 & 2 & 2 \\ 
\end{pmatrix}
</math> udávají množství surovin potřebných pro výrobu meziproduktů, respektive množství meziproduktů potřebných pro výsledné výrobky. Například k výrobě jednoho meziproduktu <math>m_1</math> je třeba jedna jednotka suroviny <math>b_1</math>, dvě jednotky <math>b_2</math>, žádné <math>b_3</math> a jedna jednotka <math>b_4</math>, což odpovídá prvnímu sloupci matice <math>\boldsymbol{A}</math>.

Součin <math>\boldsymbol{AB} = \begin{pmatrix} 5 & 4 & 3 \\ 8 & 9 & 5 \\\ 6 & 5 & 3 \\ 11 & 9 & 6 \\ \end{pmatrix} </math> pak přímo udává množství surovin potřebných pro výrobu jednotlivých výrobků. Například prvek v levém dolním rohu <math>\boldsymbol{AB}</math> je vypočítán jako <math>1 \cdot 1 + 1 \cdot 2 + 2 \cdot 4 = 11</math>, což odpovídá tomu, že <math>11</math> jednotek <math>b_4</math> je potřeba k výrobě jednoho výrobku <math>f_1</math>. Jmenovitě jedna jednotka <math>b_4</math> je třeba pro <math>m_1</math>, 2 pro <math>m_2</math> a <math>4</math> pro každý ze dvou meziproduktů <math>m_3</math>, které jsou potřeba pro  jeden kus <math>f_1</math>, viz obrázek.

Aby bylo možné vyrobit např. 100 výrobků <math>f_1</math>, 80 <math>f_2</math> a 60 <math>f_3</math>, lze potřebné množství surovin vypočítat jako
:<math>(\boldsymbol{AB})
\begin{pmatrix} 100 \\ 80 \\ 60 \\ \end{pmatrix} = \begin{pmatrix} 1000 \\ 1820 \\ 1180 \\ 2180 
\end{pmatrix} ,</math>
tj. <math>1000</math> jednotek <math>b_1</math>, <math>1820</math> jednotek <math>b_2</math>, <math>1180</math> jednotek <math>b_3</math> a <math>2180</math> jednotek <math>b_4</math>.Matice součinu <math>\boldsymbol{AB}</math> může být použita k výpočtu množství surovin i pro jiné počty výrobků.<ref>{{cite book | isbn=3-446-18668-9 | author=Peter Stingl | title=Mathematik für Fachhochschulen &ndash; Technik und Informatik | location=[[Mnichov|Munich]] | publisher=[[Carl Hanser Verlag]] | edition=5th | year=1996 | language=German }} Zde: příklad 5.4.10, s.205-206</ref>

== Vlastnosti ==
Rovnosti uvedené v následujících odstavcích platí, pokud mají výsledky operací smysl.

* Součin matice <math>\boldsymbol{A}</math> s [[jednotková matice|jednotkovou maticí]] <math>\mathbf{I}</math> zprava i zleva má za výsledek matici <math>\boldsymbol{A}</math>, tj. <math>\mathbf{I} \boldsymbol{A} = \boldsymbol{A}  \mathbf{I} = \boldsymbol{A}</math>.
* Maticový součin je [[asociativita|asociativní]], tedy <math>\boldsymbol{A}  (\boldsymbol{B}  \boldsymbol{C}) =(\boldsymbol{A}  \boldsymbol{B})  \boldsymbol{C}</math>.
* Maticový součin není [[komutativita|komutativní]], tedy existují příklady matic, pro něž platí <math>\boldsymbol{AB} \neq\boldsymbol{BA}</math>.
* Maticový součin je [[distributivita|distributivní]] vůči [[sčítání]], tj. <math>\boldsymbol{A}\left(\boldsymbol{B}+\boldsymbol{C}\right)= \boldsymbol{AB}+\boldsymbol{AC}</math>.
* Maticový součin je [[linearita|lineární]] vůči [[násobení skalárem]] (typicky [[reálné číslo|reálné]] nebo [[komplexní číslo]]), tj. <math>\boldsymbol{A}  \left( c \boldsymbol{B} \right) = (c \boldsymbol{A})  \boldsymbol{B}=c(\boldsymbol{A}\boldsymbol{B})</math>.
* Matice vzhledem k součinu mohou být dělitelé nuly, tj. součin dvou nenulových matic může být [[nulová matice]], například
:<math>
\begin{pmatrix}
1 & 1 \\
2 & 2
\end{pmatrix}
\begin{pmatrix}
-3 \\
3
\end{pmatrix}
=
\begin{pmatrix}
0 \\
0
\end{pmatrix}
</math>.
* Součin matic <math>\boldsymbol A</math> typu <math>m \times n</math> a <math>\boldsymbol B</math> typu <math>n \times p</math> lze vyjádřit jako
:<math>\boldsymbol{AB}=\boldsymbol a_1\boldsymbol b_1^\mathsf T+\boldsymbol a_2\boldsymbol b_2^\mathsf T+\cdots+\boldsymbol a_n\boldsymbol b_n^\mathsf T</math>,</br>kde <math>\boldsymbol a_1,\boldsymbol a_2,\dots, \boldsymbol a_n</math> jsou sloupce matice <math>\boldsymbol A</math> a <math>\boldsymbol b_1^\mathsf T,\boldsymbol b_2^\mathsf T,\dots, \boldsymbol b_n^\mathsf T</math> řádky matice <math>\boldsymbol B</math>. (Neboli <math>\boldsymbol b_1,\boldsymbol b_2,\dots, \boldsymbol b_n</math> jsou sloupce <math>\boldsymbol B^\mathsf T</math>.) Zde každý sčítanec <math>\boldsymbol a_i\boldsymbol b_i^\mathsf T</math> je matice typu <math>m \times p</math>, protože sloupcové vektory odpovídají maticím o jednom sloupci.
* [[transpozice matice|Transpozice]] součinu matic je součin transponovaných matic v opačném pořadí, tj. <math>{(\boldsymbol{AB})}^{\mathsf T} = \boldsymbol{B}^{\mathsf T} \boldsymbol{A}^{\mathsf T}</math>
* [[Inverzní matice]] součinu regulárních matic je součin inverzních matic v opačném pořadí, tj. <math>{(\boldsymbol{AB})}^{-1} = \boldsymbol{B}^{-1} \boldsymbol{A}^{-1}</math>
* [[Hermitovská transpozice|Hermitovské sdružení]] ([[Hermitovská matice|hermitovská]] transpozice) součinu matic je součin matic hermitovsky sdružených v opačném pořadí, tj. <math>{(\boldsymbol{AB})}^{\mathsf H} = \boldsymbol{B}^{\mathsf H}  \boldsymbol{A}^{\mathsf H}</math>
* Maticový součin odpovídá skládání [[lineární zobrazení|lineárních zobrazení]], které matice reprezentují.

== Součiny čtvercových matic ==

=== Mocniny matice ===

Čtvercovou matici lze umocnit na jakoukoli [[Umocňování|nezápornou celočíselnou mocninu]] tím, že ji opakovaně násobíme stejným způsobem jako u běžných čísel, konkrétně
:<math>\boldsymbol{A}^0 = \mathbf{I},</math>
:<math>\boldsymbol{A}^1 = \boldsymbol{A},</math>
:<math>\boldsymbol{A}^k = \underbrace{\boldsymbol{A}\boldsymbol{A}\cdots\boldsymbol{A}}_{k\text{ krát}}.</math>

Výpočet <math>k</math>-té mocniny matice potřebuje <math>k-1</math> maticových součinů, pokud se provádí triviálním algoritmem (opakované násobení). Protože to může být velmi časově náročné, obecně se dává přednost použití umocňování pomocí druhé mocniny, které vyžaduje nejvýše <math> \log_2 k</math> maticových součinů, a je tedy mnohem efektivnější.

Snadným případem umocňování je [[diagonální matice]]. Protože součin diagonálních matic se rovná prostému vynásobení odpovídajících diagonálních prvků dohromady, získáme <math>k</math>-tou mocninu diagonální matice  umocněním prvků na diagonále na <math>k</math>-tou:
:<math>
  \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}.
</math>

=== Regulární a singulární matice ===

Označme <math>\mathcal M_n(R)</math> množinu [[čtvercová matice|čtvercových matic]] řádu <math>n</math> s prvky z [[okruh (algebra)|okruhu]] <math>R</math>, což je v praxi často [[těleso (algebra)|těleso]].

V <math>\mathcal M_n(R)</math> je součin definován pro každou dvojici matic. Toto dělá z <math>\mathcal M_n(R)</math> [[okruh (algebra)|okruh]], který má [[jednotková matice|jednotkovou matici]] <math>\mathbf{I}</math> za [[neutrální prvek]].

Pokud je <math>n > 1</math>, mnoho matic nemá [[inverzní prvek]] vůči násobení, např. [[nulová matice]]. Pokud  inverzní prvek existuje, značí se <math>\boldsymbol{A}^{-1}</math> a nazývá se [[inverzní matice]] k matici <math>\boldsymbol A</math>. Splňuje: 
:<math> \boldsymbol{A}\boldsymbol{A}^{-1} = \boldsymbol{A}^{-1}\boldsymbol{A} = \mathbf{I}. </math>
Matice, která má inverzi, je [[regulární matice]], někdy též ''invertibilní matice''. Pokud inverzní matici nemá, nazývá se [[singulární matice]].

Součin matic <math>\boldsymbol{AB}</math> je regulární, právě když je každý z [[Činitel|činitelů]] <math>\boldsymbol A</math> i <math>\boldsymbol B</math> regulární. V tomto případě platí

:<math>(\boldsymbol{AB})^{-1} = \boldsymbol{B}^{-1}\boldsymbol{A}^{-1}.</math>

=== Determinant součinu ===

[[determinant matice|Determinant]] součinu čtvercových  matic je součin jejich determinantů.
:<math>\det (\boldsymbol{AB})=\det (\boldsymbol{BA})=\det \boldsymbol{A}\,\det \boldsymbol{B}</math>.

Tento vztah platí kdykoli je <math>R</math> [[komutativní|komutativní okruh]], jmenovitě i v [[těleso (algebra)|tělesech]]. 

== Výpočetní složitost ==
[[Asymptotická složitost|Výpočetní složitost]] výše popsaného [[algoritmus|algoritmu]] je <math>O(n^3) </math> (počítáme <math>n^2</math> čísel; pro každé potřebujeme <math>2n-1</math> aritmetických operací). Existují však algoritmy s nižší složitostí vhodné pro matice vyšších řádů. Nejpoužívanější z nich je [[Strassenův algoritmus]] se složitostí <math>O( n^{\log_2{7}}) \approx O(n^{2.807})</math>. Nižší složitost u tohoto algoritmu však získáváme za cenu snížené [[Stabilita numerické metody|numerické stability]]. Asymptoticky nejrychlejší ze známých algoritmů je [[Coppersmithův-Winogradův algoritmus]] (<math>O( n^{2.376} )</math>), který je však použitelný až pro matice tak velkých řádů, že je nelze zpracovávat pomocí současných počítačů<ref name="rob2005">Robinson, Sara (2005), "[http://www.siam.org/pdf/news/174.pdf Toward an Optimal Algorithm for Matrix Multiplication] {{Wayback|url=http://www.siam.org/pdf/news/174.pdf |date=20100331095603 }}", ''SIAM News'' '''38''' (9)<span class="printonly">, http://www.siam.org/pdf/news/174.pdf {{Wayback|url=http://www.siam.org/pdf/news/174.pdf |date=20100331095603 }}</span></ref>.

Teoreticky by se dala složitost ještě snížit, ale nikdy nemůže být menší než <math>O( n^2 )</math>, protože je třeba spočítat <math>n^2</math> čísel.

=== Hledání nejkratší cesty v grafu ===
Algoritmy pro násobení matic s malou výpočetní složitostí lze využít i pro hledání nejkratší [[Cesta (graf)|cesty]] v [[Graf (teorie grafů)|grafu]] z každého do každého vrcholu. To má v nejjednodušší podobě složitost <math>O( n^3)</math>. V tomto případě se však nepoužívá zde popsané násobení matic, ale upravená verze, kde je místo [[sčítání]] výběr nejmenšího prvku a místo [[násobení]] sčítání, proto nelze použít například [[Strassenův algoritmus]], který využívá operaci [[odčítání]] jako inverzní operaci ke sčítání, která k operaci <math>\min</math> není.

Graf lze popsat maticí vzdáleností <math>\boldsymbol{A}</math>. Pokud je pro výpočty operace sčítání dvou čísel definována jako jejich minimum, a místo násobení se použije sčítání, je možno matici nejkratších cest <math>\boldsymbol{B}</math> získat jako (<math>\boldsymbol A^n</math>) kde <math>n</math> je řád matice vzdáleností. Při reálném výpočtu není třeba cyklicky násobit původní maticí, ale vždy se vynásobí vzniklé výsledky - nejkratší cesty jsou získány po <math>\log_2(n)</math> násobeních. Je-li použit pro násobení algoritmus se složitostí menší než <math>O\biggl(\frac{n^3}{\log_2(n)}\biggr)</math>, složitost hledání cest se tímto postupem sníží.

== Odkazy ==
=== Reference ===
{{Překlad|en|Matrix multiplication|1140750080}}
<references/>

=== Literatura ===
*{{Citace monografie
 | příjmení = Bärtsch
 | jméno = Hans-Jochen
 | titul = Matematické vzorce
 | vydavatel = Academia
 | místo = Praha
 | rok = 2006
 | počet_stran = 832
 | kapitola = Matice
 | strany = 180–198
 | isbn = 80-200-1448-9
}}
* {{Citace monografie
| příjmení = Bečvář
| jméno = Jindřich
| titul = Lineární algebra
| vydání = 1
| vydavatel = Matfyzpress
| místo = Praha
| rok vydání = 2019
| počet_stran = 436
| isbn = 978-80-7378-392-1
}}
* {{Citace monografie
| příjmení = Hladík
| jméno = Milan
| titul = Lineární algebra (nejen) pro informatiky
| vydání = 1
| vydavatel = Matfyzpress
| místo = Praha
| rok vydání = 2019
| počet_stran = 328
| strany = 39
| isbn = 978-80-7378-378-5
}}
* {{Citace elektronické monografie
 | příjmení = Olšák
 | jméno = Petr
 | titul = Lineární algebra
 | url = http://petr.olsak.net/ftp/olsak/linal/linal.pdf
 | místo = Praha
 | datum vydání = 2007
 | datum přístupu = 2023-02-20
}}
* {{Citace elektronické monografie
 | příjmení1 = Motl
 | jméno1 = Luboš
 | příjmení2 = Zahradník
 | jméno2 = Miloš
 | titul = Pěstujeme lineární algebru
 | url = https://matematika.cuni.cz/zahradnik-pla.html
 | datum přístupu = 2023-02-20
 }}

=== Související články ===
* [[Hadamardův součin]]
* [[Skalární součin]], [[Vnitřní součin]]
* [[Smíšený součin]]
* [[Strassenův algoritmus]]
* [[Tenzorový součin]], [[Vnější součin]]
* [[Vektorový součin]], [[Dvojitý vektorový součin]]

=== Externí odkazy ===
* {{Commonscat}}
* [http://www.umat.feec.vutbr.cz/~novakm/algebra_matic/cz Lineární algebra: algebra matic] {{Wayback|url=http://www.umat.feec.vutbr.cz/~novakm/algebra_matic/cz |date=20090216132819 }} Aplikace, která násobí a sčítá matice zadané uživatelem a zobrazuje postup výpočtu.

{{Autoritní data}}

{{Portály|Matematika}}

[[Kategorie:Teorie matic]]
[[Kategorie:Binární operace]]
[[Kategorie:Bilineární zobrazení]]