Násobení matic

Násobení matic nebo též maticové násobení je v matematice zobecnění násobení čísel na matice. Formálně se dá definovat jako binární operace nad množinou matic. Využívá se v matematice, fyzice a jejich aplikacích pro popis skládání lineárních zobrazení.

Formální definice

Pokud A je matice o rozměrech m × n a B je matice n × p, jejich součin $A \cdot B$ je matice s rozměry m × p definována vztahem

$(A\cdot B)_{ij} = \sum_{r=1}^n a_{ir}b_{rj} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{in}b_{nj}.$

pro všechny prvky (i , j) výsledné matice.

Prvek v i-tém řádku a j-tém sloupci výsledné matice lze také chápat jako skalární součin vektoru i-tého řádku první matice s vektorem j-tého sloupce druhé matice.

Tečka $\cdot$ se obvykle vynechává a píše se pouze $AB$.

Příklad výpočtu

Ilustrační obrázek

Definujme matice

$\mathbf{A}=\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ \end{pmatrix}, \ \mathbf{B}=\begin{pmatrix} 1 & 2 \\ 3 & 4 \\ 5 & 6 \\ \end{pmatrix}.$

Jejich součin je

$\mathbf{A}\cdot\mathbf{B}=\begin{pmatrix} (1 \cdot 1+2 \cdot 3+3 \cdot 5) & (1 \cdot 2+2 \cdot 4+3 \cdot 6)\\ (4 \cdot 1+5 \cdot 3+6 \cdot 5) & (4 \cdot 2+5 \cdot 4+6 \cdot 6)\\ \end{pmatrix}= \begin{pmatrix} 22 & 28\\ 49 & 64 \end{pmatrix}$

Vlastnosti

• Maticové násobení odpovídá skládání lineárních zobrazení, které matice reprezentují.
• Maticové násobení je distributivní vůči sčítání, t.j. $\mathbf{A}\cdot\left(\mathbf{B}+\mathbf{C}\right)= \mathbf{A}\cdot\mathbf{B}+\mathbf{A}\cdot\mathbf{C}$ pro všechny matice, pro které má rovnice smysl.
• Násobení reálných resp. komplexních matic je lineární vůči násobení reálným resp. komplexním číslem, t.j. $\mathbf{A} \cdot \left( c \mathbf{B} \right) = (c \mathbf{A}) \cdot \mathbf{B}=c(\mathbf{A}\cdot\mathbf{B})$ pokud má rovnice smysl.
• Matice vzhledem k součinu můžou být dělitelé nuly, t.j. součin dvou nenulových matic může být nulová matice.
• Maticové násobení není komutativní, tedy obecně $\mathbf{A} \cdot \mathbf{B} \neq\mathbf{B} \cdot \mathbf{A}$.
• Násobení matice $\mathbf{A}$ jednotkovou maticí $\mathbf{E}$ zprava i zleva je identické zobrazení, t.j. $\mathbf{E} \cdot \mathbf{A} = \mathbf{A} \cdot \mathbf{E} = \mathbf{A}$, pokud má rovnice smysl.
• Maticové násobení je asociativní, tedy $\mathbf{A} \cdot (\mathbf{B} \cdot \mathbf{C}) =(\mathbf{A} \cdot \mathbf{B}) \cdot \mathbf{C}$, pokud prvky matice jsou z asociativního okruhu (např reálná nebo komplexní čísla).
• Pro čtvercové matice platí $\det (\mathbf{A}\cdot\mathbf{B})=\det \mathbf{A}\,\det \mathbf{B}$, t.j. determinant součinu je součin determinantů.
• Transpozice součinu matic je součin transponovaných matic v opačném pořadí, t.j. ${(\mathbf{A} \cdot \mathbf{B})}^T = \mathbf{B}^T \cdot \mathbf{A}^T$
• Inverzní matice součinu regulárních matic je součin inverzních matic v opačném pořadí, t.j. ${(\mathbf{A} \cdot \mathbf{B})}^{-1} = \mathbf{B}^{-1} \cdot \mathbf{A}^{-1}$
• Hermiteovské sdružení součinu matic je součin hermitovsky sdružených matic v opačném pořadí, t.j. ${(\mathbf{A} \cdot \mathbf{B})}^+ = \mathbf{B}^+ \cdot \mathbf{A}^+$

Výpočetní náročnost

Výpočetní náročnost výše popsaného algoritmu je $O( n^3 ) \,\!$ (počítáme n² čísel; pro každé potřebujeme n násobení). 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í $O( n^{\log_2{7}} ) \approx O(n^{2.807})$. Nižší složitost u tohoto algoritmu však získáváme za cenu snížené numerické stability. Asymptoticky nejrychlejší ze známých algoritmů je Coppersmithův-Winogradův algoritmus ($O( n^{2.376} ) \,\!$), který je však použitelný až pro matice tak velkých řádů, že je nelze zpracovávat pomocí současných počítačů.

Teoreticky by se dala složitost ještě zmenšit, ale nikdy nemůže být menší než $O( n^2 ) \,\!$, neboť počítáme n² čísel.

Hledání nejkratší cesty v grafu

Faktická přesnost této části byla zpochybněna.

Podrobnější zdůvodnění najdete v diskusi. Neodstraňujte, prosíme, tuto zprávu, dokud nebudou pochybnosti vyřešeny.

---

Pro vkladatele šablony: Na diskusní stránce zdůvodněte vložení šablony.

Násobení matic s malou výpočetní složitostí lze využít i pro hledání nejkratší cesty v grafu z každého do každého vrcholu. To má v nejjednodušší podobě složitost $O( n^3 ) \,\!$.

Graf lze popsat maticí vzdáleností A. 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 B získat jako ($A^n$) kde n 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 log2(n) násobeních. Je-li použit pro násobení algoritmus se složitostí menší než $O( \frac{n^3}{\log_2(n)} ) \,\!$, složitost hledání cest se tímto postupem sníží.

Související články

• Strassenův algoritmus
• Součin
• Skalární součin, Vnitřní součin
• Vektorový součin, Dvojitý vektorový součin
• Smíšený součin
• Tenzorový součin, Vnější součin
• Hadamardův součin
• Matice

Externí odkazy

• Lineární algebra: algebra matic Aplikace, která násobí a sčítá matice zadané uživatelem a zobrazuje postup výpočtu.