Kapitola 3

Počítání s maticemi

Matice stejného tvaru můžeme sčítat a násobit reálným číslem podobně jako vektory stejné dimenze.

Definice 3.1 Jsou-li A = (a_{ij}) a B = (b_{ij}) dvě matice stejného tvaru m×n, pak definujeme jejich součet jako matici A + B = (c_{ij}), kde c_{ij} = a_{ij} + b_{ij} pro libovolné indexy i = 1, 2, …, m a j = 1, 2, …, n.

Součin matice A a čísla k definujeme jako matici kA = (d_{ij}) tvaru m × n, kde d_{ij} = ka_{ij} pro libovolné indexy i, j.

Zavedeme si také označení 0_{m×n} pro nulovou matici tvaru m × n. Ta má všechny prvky rovné 0. Je-li tvar nulové matice zřejmý ze souvislostí, budeme ji značit pouze 0. Pro libovolnou matici A = (a_{ij}) tvaru m × n označujeme symbolem −A = (−a_{ij}) opačnou matici k matici A.

Cvičení 3.1 Matice A, B, C jsou stejného tvaru m × n, k, l jsou čísla. Dokažte následující vlastnosti sčítání matic a násobení matic číslem.

1. (A + B) + C = A + (B + C),

2. A + B = B + A,

3. A + 0 = A,

4. A + (−A) = 0,

5. (kl)A = k(lA),

6. k(A + B) = kA + kB,

7. (k + l)A = kA + lA, 8. 1A = A.

Následující definice je zobecněním vztahu mezi sloupcovým a řádkovým zápisem vektorů.

Definice 3.2 Transponovaná matice k matici A tvaru m × n je matice A^{T} = (b_{ij}) tvaru n × m, kde b_{ij} = a_{ji} pro libovolné indexy i = 1, 2, …, m a j = 1, 2, …, n.

Například

( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 8 & 5 \\ 2 & 3 & 4 & 5 & 6 \end{matrix} )^{T} = ( \begin{matrix}1 & 1 & 2 \\ 2 & 2 & 3 \\ 3 & 3 & 4 \\ 4 & 8 & 5 \\ 5 & 5 & 6 \end{matrix} ) .

Cvičení 3.2 Dokažte, že pro libovolné matice A, B stejného tvaru platí

• (A + B)^{T} = A^{T} + B^{T},

• (kA)^{T} = kA^{T},

• (A^{T})^{T} = A.

Dále zavedeme názvy pro několik speciálních typů matic. Je-li A = (a_{ij}) čtvercová matice řádu n, pak říkáme, že prvky a_{ii} pro i = 1, 2, …, n leží na hlavní diagonále matice A. Ostatní prvky a_{ij}, kde i ≠ j, leží mimo hlavní diagonálu.

Definice 3.3 Symbolem I_{n} budeme označovat čtvercovou matici (a_{ij}) řádu n, která má na hlavní diagonále samé prvky 1 a mimo hlavní diagonálu samé prvky 0:

I_{n} = ( \begin{matrix}1 & 0 & ⋯ & 0 \\ 0 & 1 & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & 1 \end{matrix} )

Tuto matici budeme nazývat jednotková matice řádu n.

Čtvercová matice B = (b_{ij}) se nazývá symetrická matice, jestliže platí b_{ij} = b_{ji} pro libovolné indexy i, j, tj. jestliže platí A^{T} = A.

Čtvercová matice B = (b_{ij}) se nazývá kososymetrická matice, jestliže platí b_{ij} = −b_{ji} pro libovolné indexy i, j, tj. platí-li A^{T} = −A.

Základní definicí této kapitoly je definice součinu matic.

Definice 3.4 Je-li A = (a_{ij}) matice tvaru m × n a B = (b_{jk}) matice tvaru n×p, pak definujeme součin matic AB = (c_{ik}) jako matici tvaru m×p, kde

c_{ik} = ∑_{j=1}^{n}a_{ij}b_{jk}.

Podle této definice můžeme násobit pouze takové dvojice matic, u kterých se počet sloupců první matice rovná počtu řádků druhé matice. Stejně jako v případě součtu matic tak ani součin matic není definován pro libovolné dvě matice.

Prvek na místě (i, k) součinu AB se rovná standardnímu skalárnímu součinu i-tého řádku matice A s j-tým sloupcem matice B. Neformální vyjádření pro způsob výpočtu součinu matic říká, že matice násobíme způsobem “řádek×sloupec”.

Cvičení 3.3 Spočítejte součin několika dvojic matic. Spočítejte oba součiny AB a BA pro nějaké dvě čtvercové matice stejného řádu. Je násobení matic komutativní, tj. platí AB = BA pro libovolné dvě matice A tvaru m × n a B tvaru n × m? Platí to pro libovolné dvě čtvercové matice řádu n?

Soustavu (2.1) tak nyní můžeme vyjádřit pomocí součinu matic ve tvaru

Ax = b,

kde A = (a_{ij}) je matice soustavy, b = (b_{1}, …, b_{m})^{T} je sloupcový vektor pravých stran a x = (x_{1}, …, x_{n})^{T} je sloupcový vektor neznámých.

Cvičení 3.4 Je-li A matice tvaru m × n, pak platí

I_{m}A = A = AI_{n}.

Dokažte.

Jakkoliv vypadá definice součinu matic na první pohled uměle, ve skutečnosti je přirozená a lze ji udůvodnit, skládáme-li zobrazení ve dvoudimenzionálním aritmetickém reálném vektorovém prostoru.

Úloha 3.1 Označme symbolem f zobrazení definované na prostoru R_{2} předpisem

f ( \begin{matrix}x \\ y \end{matrix} ) = ( \begin{matrix}ax + by \\ cx + dy \end{matrix} ) ,

kde a, b, c, d jsou reálná čísla. Podobně označíme g : R_{2} → R_{2} zobrazení definované předpisem

g ( \begin{matrix}x \\ y \end{matrix} ) = ( \begin{matrix}Ax + By \\ Cx + Dy \end{matrix} ) ,

kde A, B, C, D jsou také reálná čísla. Popište, jak vypadá složené zobrazení g ∘ f.

Řešení. Všimněte si, že předpis pro zobrazení f můžeme pomocí násobení matic vyjádřit následovně:

f ( \begin{matrix}x \\ y \end{matrix} ) = ( \begin{matrix}a & b \\ c & d \end{matrix} ) ( \begin{matrix}x \\ y \end{matrix} ) .

Lze říct, že

A = ( \begin{matrix}a & b \\ c & d \end{matrix} )

je matice zobrazení f. Podobně rovnost

g ( \begin{matrix}x \\ y \end{matrix} ) = ( \begin{matrix}A & B \\ C & D \end{matrix} ) ( \begin{matrix}x \\ y \end{matrix} )

ukazuje, že matici

B = ( \begin{matrix}A & B \\ C & D \end{matrix} )

můžeme považovat za matici zobrazení g.

Pokusíme se najít podobné maticové vyjádření pro složené zobrazení g ∘ f. Platí

(g ∘ f) ( \begin{matrix}x \\ y \end{matrix} ) = gf ( \begin{matrix}x \\ y \end{matrix} ) = g ( \begin{matrix}ax + by \\ cx + dy \end{matrix} ) =

= ( \begin{matrix}A(ax + by) + B(cx + dy) \\ C(ax + by) + D(cx + dy) \end{matrix} ) =

= ( \begin{matrix}(Aa + Bc)x + (Ab + Bd)y \\ (Ca + Dc)x + (Ay + Bd)y \end{matrix} ) =

= ( \begin{matrix}Aa + Bc & Ab + Bd \\ Ca + Dc & Cb + Dd \end{matrix} ) ( \begin{matrix}x \\ y \end{matrix} ) =

= (( \begin{matrix}A & B \\ C & D \end{matrix} ) ( \begin{matrix}a & b \\ c & d \end{matrix} )) ( \begin{matrix}x \\ y \end{matrix} ) .

Výpočet ukazuje, že matice složeného zobrazení g ∘ f se rovná součinu BA matic zobrazení g a f (v tomto pořadí). □

Následující cvičení udává, kolik aritmetických operací je třeba uskutečnit pro výpočet součinu matic.

Cvičení 3.5 Jsou-li A, B dvě čtvercové matice řádu n, pak pro výpočet součinu AB potřebujeme nejvýše

n^{3}  násobení/dělení, a
n^{3} − n^{2} sčítání/odčítání.

Násobení a sčítání matic mají řadu vlastností společných s násobením a sčítáním čísel.

Tvrzení 3.5 Jsou-li A = (a_{ij}), B = (b_{kl}) a C = (c_{uv}) matice, pak platí

• A(B + C) = AB + AC,

• (A + B)C = AC + BC,

• (AB)C = A(BC)

za předpokladu, že všechny součty a součiny matic v příslušné rovnosti existují.

Důkaz. Aby existovaly oba součty a všechny tři součiny v první rovnosti, musí být matice A tvaru m × n a obě matice B, C musí být tvaru n × p. Ukážeme, že čísla na stejném místě (i, k) v obou maticích A(B + C) a AB + AC jsou stejná.

Číslo na místě (j, k) v součtu B + C se rovná b_{jk} + c_{jk}. Prvek na místě (i, k) v součinu A(B + C) se proto rovná

∑_{j=1}^{n}a_{ij}(b_{jk} + c_{jk}) = ∑_{j=1}^{n}(a_{ij}b_{jk} + a_{ij}c_{jk}).

Prvek na místě (i, k) v součinu AB se rovná

∑_{i=1}^{n}a_{ij}b_{jk}

a prvek na místě (i, k) v součinu AC se rovná

∑_{i=1}^{n}a_{ij}c_{jk}.

Proto je prvek na místě (i, k) v součtu AB + AC rovný

∑_{i=1}^{n}a_{ij}b_{jk} + a_{ij}c_{jk}.

Prvky na stejných místech v maticích A(B+C) a AB+AC jsou shodné, což dokazuje první rovnost.

Všimněte si, že právě dokázaná distributivita násobení matic vzhledem k jejich sčítání je bezprostředním důsledkem distributivity násobení reálných čísel vzhledem k jejich sčítání.

Pokud jste si udělali celé Cvičení 3.3 tak víte, že násobení matic není komutativní. Druhá rovnost v Tvrzení 3.5 tak není důsledkem právě dokázané rovnosti a je nutné ji dokázat zvlášť. Dokažte si ji sami jako další cvičení.

V případě asociativity násobení matic musí být matice A tvaru m × n, B tvaru n × p a matice C musí být tvaru p × q. Součin AB má potom tvar m × p, jeho prvky si označíme

d_{ik} = ∑_{j=1}^{n}a_{ij}b_{jk}.

Prvek na místě (i, l) v součinu (AB)C se tak rovná

∑_{k=1}^{p} d_{ik}c_{kl} = ∑_{k=1}^{p}(∑_{j=1}^{n}a_{ij}b_{jk})c_{kl} = ∑_{k=1}^{p} ∑_{j=1}^{n}(a_{ij}b_{jk})c_{kl} = ∑_{j=1}^{n} ∑_{k=1}^{p} a_{ij}b_{jk}c_{kl}.

Poslední rovnost vyplývá z komutativity sčítání a asociativity násobení reálných čísel.

Matice BC = (e_{jl}) je tvaru n × q. Prvek e_{jl} má podle definice násobení matic vyjádření

e_{jl} = ∑_{k=1}^{q} b_{jk}c_{kl}.

Prvek na místě (i, l) v součinu A(BC) se tak rovná

∑_{j=1}^{n}a_{ij}e_{jl} = ∑_{j=1}^{n}a_{ij} ∑_{k=1}^{q} b_{jk}c_{kl} = ∑_{j=1}^{n} ∑_{k=1}^{q} a_{ij}(b_{jk}c_{kl}) = ∑_{j=1}^{n} ∑_{k=1}^{q} a_{ij}b_{jk}c_{kl}.

Tím je důkaz asociativity násobení dokončen. □

Další dvě cvičení se týkají transponovaných matic.

Cvičení 3.6 Matice A má tvar m × n a matice B má tvar n × p. Dokažte, že platí • (AB)^{T} = B^{T} A^{T}.

Změna pořadí matic v součinu B^{T} A^{T} je nutná kvůli tomu, aby je vůbec bylo možné násobit.

Cvičení 3.7 Dokažte, že pro každou matici A jsou součiny AA^{T} a A^{T} A symetrické matice. Musíte počítat jednotlivé prvky v těchto maticích?

Dříve, než se začneme zabývat strukturou součinu matic, uvedeme ještě jednu definici.

Definice 3.6 Jsou-li a a b_{1}, b_{2}, …, b_{k} vektory stejné dimenze n, pak říkáme, že vektor a je lineární kombinací vektorů b_{1}, b_{2}, …, b_{k}, jestliže

a = t_{1}b_{1} + t_{2}b_{2} + ⋯ + t_{k}b_{k}

pro nějaká čísla t_{1}, t_{2}, …, t_{k}. Těmto číslům říkáme koeficienty lineární kombinace. Skutečnost, že vektor a je lineární kombinací vektorů b_{1}, b_{2}, …, b_{k}, vyjadřujeme také slovy, že vektor a je lineárně závislý na vektorech b_{1}, b_{2}, …, b_{k}.

Vyřešit soustavu lineárních rovnic Ax = b znamená najít (všechna) vyjádření sloupce pravých stran jako lineární kombinace sloupců matice A.

Tvrzení 3.7 Jsou-li A = (a_{ij}) matice tvaru m × n a B = (b_{jk}) matice tvaru n × p, pak platí

• [AB]_{i∗} = A_{i∗}B = ∑_{j=1}^{n} a_{ij}B_{j∗} pro libovolné i = 1, 2, …, m,

• [AB]_{∗k} = AB_{∗k} = ∑_{j=1}^{n} b_{jk}A_{∗j} pro libovolné k = 1, 2, …, p.

První rovnost pro i-tý řádek součinu AB říká, že se rovná součinu i-tého řádku matice A s maticí B. Druhá rovnost pak říká, že je lineární kombinací řádků matice B s koeficienty v i-tém řádku matice A. Podobně k-tý sloupec v součinu AB se rovná součinu matice A s k-tým sloupcem matice B. Rovná se také lineární kombinaci sloupců matice A s koeficienty v k-tém sloupci matice B.

Důkaz. Dokážeme pouze vyjádření sloupců v součinu. Důkaz pro řádky je analogický.

Prvek na místě (i, k) v součinu AB, tj. i-tá souřadnice sloupcového vektoru [AB]_{∗k}, se rovná

∑_{j=1}^{n}a_{ij}b_{jk}.

Podobně i-tá souřadnice sloupcového vektoru AB_{∗k} se rovná

∑_{j=1}^{n}a_{ij}b_{jk}.

Nakonec i-tá souřadnice lineární kombinace b_{1k}A_{∗1} + b_{2k}A_{∗2} + ⋯ + b_{nk}A_{∗n} se rovná

∑_{j=1}^{n}b_{jk}a_{ij}.

Všechna tři čísla jsou stejná, proto se tři uvedená vyjádření pro k-tý sloupec součinu AB rovnají. □

Inverzní matice

Definice 3.8 Jsou-li A a B dvě čtvercové matice stejného řádu n, pak říkáme, že B je inverzní matice k matici A, jestliže platí

AB = I_{n}.

Pokud existuje inverzní matice k matici A, označujeme ji A^{−1}. Čtvercová matice A se nazývá regulární, jestliže existuje inverzní matice A^{−1}. V opačném případě se nazývá singulární.

Inverzní matice tedy může existovat pouze ke čtvercové matici. Jak zjistíme, jestli k dané čtvercové matici A = (a_{ij}) existuje inverzní matice A^{−1}? A pokud existuje, jak ji spočítáme? Těmito otázkami se budeme nyní zabývat.

Označíme symbolem e_{k} k-tý sloupec jednotkové matice I_{n} řádu n. Souřadnice vektoru e_{k} se rovnají 0 s výjimkou k-té souřadnice, která se rovná 1.

Pokud inverzní matice A^{−1} = (b_{jk}) k matici A existuje, musí její k-tý sloupec A_{∗k}^{−1} = (b_{1k}, b_{2k}, …, b_{nk})^{T} podle Tvrzení 3.7 splňovat rovnosti

e_{k} = [I_{n}]_{∗k} = [AA^{−1}]_{∗k} = AA_{∗k}^{−1} = ∑_{j=1}^{n}A_{∗j}b_{jk}.

To znamená, že k-tý sloupec A_{∗k}^{−1} inverzní matice A^{−1} je řešením soustavy n lineárních rovnic o n neznámých Ax = e_{k}. Abychom inverzní matici A^{−1} vypočítali, musíme vyřešit n soustav lineárních rovnic

Ax = e_{k} pro k = 1, …, n.

Protože mají soustavy stejnou matici A, můžeme je řešit všechny současně pomocí elementárních řádkových úprav matice

[A|I_{n}] = [A|e_{1}|e_{2}| ⋯ |e_{n}]

tvaru n × (2n).

Tuto matici převedeme pomocí elementárních řádkových úprav do řádkově odstupňovaného tvaru [E|B]. Matici E jsme tedy dostali pomocí elementárních řádkových úprav z matice A a podobně jsme dostali matici B pomocí elementárních řádkových úprav z jednotkové matice I_{n}. Protože jsou všechny elementární řádkové úpravy vratné, dostaneme také jednotkovou matici I_{n} zpět z matice B pomocí elementárních řádkových úprav. Matice I_{n} je v řádkově odstupňovaném tvaru (dokonce v redukovaném řádkově odstupňovaném tvaru) a neobsahuje žádný nulový řádek. Matice B má proto hodnost n. Speciálně tak matice B neobsahuje žádný nulový řádek.

Matice B tak obsahuje nějaký nenulový prvek c v posledním řádku. Nechť je v k-tém sloupci. Pomocí elementárních řádkových úprav dostaneme z matice [A|e_{k}] – rozšířené matice soustavy Ax = e_{k}, jejímž řešením je k-tý sloupec inverzní matice A^{−1} – matici [E|c], kde prvek v posledním řádku posledního sloupce c je c ≠ 0. Pokud inverzní matice A^{−1} existuje, musí být soustava Ax = e_{k} řešitelná. Matice E tak nemůže obsahovat žádný nulový řádek. Protože je v řádkově odstupňovaném tvaru a dostali jsme ji z A pomocí elementárních řádkových úprav, znamená to, že hodnost r(A) matice A se rovná n.

Dokázali jsme tak, že pokud inverzní matice A^{−1} existuje, musí platit r(A) = n. Naopak, pokud r(A) = n, má každá soustava Ax = e_{k} pro k = 1, …, n (jednoznačné) řešení podle Věty 2.7. Inverzní matice A^{−1} proto existuje. Tím jsme dokázali část následující věty.

Věta 3.9 Předpokládáme, že A je čtvercová matice řádu n. Potom je ekvivalentní

1. inverzní matice A^{−1} existuje, tj. matice A je regulární,

2. r(A) = n,

3. Gaussova-Jordanova eliminace převede matici A do matice I_{n},

4. homogenní soustava Ax = 0 má pouze triviální řešení x = 0.

Důkaz. Ekvivalenci 1 ⇔ 2 jsme dokázali před Větou 3.9.

2 ⇒ 3. Je-li hodnost r(A) = n, obsahuje každá matice E v řádkově odstupňovaném tvaru, kterou dostaneme z A pomocí elementárních řádkových úprav z matice A, celkem n pivotů, všechny sloupce jsou tedy bázové. Protože má n řádků, jsou také všechny řádky nenulové. Použijeme-li Gaussovu-Jordanovu eliminaci, jsou všechny pivoty v E rovné 1 a ostatní prvky matice E se rovnají 0. Matice E se proto rovná jednotkové matici I_{n}.

3 ⇒ 4. Pokud Gaussova-Jordanova eliminace převádí matici A do jednotkové matice I_{n}, převádí matici [A|0] – rozšířenou matici soustavy Ax = 0 – do matice [I_{n}|0]. Soustava Ax = 0 má proto pouze triviální řešení x_{i} = 0 pro i = 1, 2, …, n.

4 ⇒ 2. Má-li homogenní soustava Ax = 0 pouze triviální řešení, je r(A) = n podle Věty 2.5.

Tím je ekvivalence všech čtyř výroků dokázána. □

Z úvah před Větou 3.9 také přímo dostaneme algoritmus pro výpočet inverzní matice ke čtvercové matici A řádu n, pokud existuje, tj. pokud r(A) = n.

• Gaussovou-Jordanovou eliminací převedeme matici [A|I_{n}] do matice [I_{n}|B]. Potom A^{−1} = B.

V tom případě je totiž k-tý sloupec matice B řešením soustavy Ax = e_{k} pro k = 1, 2, …, n. Podle Tvrzení 3.7 tak platí

[AB]_{∗k} = AB_{∗k} = e_{k},

což znamená

AB = I_{n}.

Cvičení 3.8 Spočítejte inverzní matice k několika regulárním maticím. Napište program pro výpočet inverzní matice.

Spočítáme ještě, kolik operací vyžaduje výpočet inverzní matice algoritmem založeným na Gaussově-Jordanově eliminaci.

Tvrzení 3.10 Pro výpočet inverzní matice A^{−1} k regulární matici A řádu n Gaussovou-Jordanovou eliminací je třeba nejvýše

n^{3}  násobení/dělení, a
n^{3} − 2n^{2} + n sčítání/odčítání.

Důkaz. Podobně jako v důkazu Tvrzení 2.10 spočítáme, že první průběh hlavního cyklu Gaussovy-Jordanovy eliminace vyžaduje

n + (n − 1)n = n^{2}  násobení/dělení, a
(n − 1)(n − 1) = n^{2} − 2n + 1 sčítání/odčítání.

Nižší počet sčítání/odčítání vyplývá z toho, že všechny prvky v prvním sloupci matice I_{n} pod prvním řádkem se rovnají 0. Stejný počet operací je třeba při všech n průbězích hlavního cyklu Gaussovy-Jordanovy eliminace. Odtud ihned vyplývá celkový počet operací. □

Dokážeme si ještě následující užitečné tvrzení.

Tvrzení 3.11 Jsou-li A a B dvě čtvercové matice stejného řádu n, pak platí

AB = I_{n} právě když BA = I_{n}.

Důkaz. Je-li AB = I_{n}, pak pro libovolný nenulový vektor x dimenze n platí

A(Bx) = (AB)x = I_{n}x = x ≠ 0.

Musí proto platit Bx ≠ 0. Homogenní soustava Bx = 0 tak má pouze triviální řešení. Podle Věty 2.5 platí r(B) = n a podle Věty 3.9 je matice B regulární. Rovnost AB = I_{n} můžeme proto vynásobit zprava maticí B^{−1} inverzní k B. Dostaneme

A = AI_{n} = A(BB^{−1}) = (AB)B^{−1} = I_{n}B^{−1} = B^{−1}.

Proto BA = BB^{−1} = I_{n}.

Opačnou implikaci dokážeme naprosto stejně. □

Poslední tvrzení nám dovoluje “snadno” vyřešit soustavu Ax = b, pokud je matice soustavy A regulární. Stačí soustavu vynásobit zleva inverzní maticí A^{−1}. Dostaneme

x = I_{n}x = (A^{−1}A)x = A^{−1}(Ax) = A^{−1}b.

Soustava má proto (jediné) řešení A^{−1}b.

Pohled na Tvrzení 3.10 a Tvrzení 2.8 ukazuje, proč je toto vyjádření řešení soustavy Ax = b výhodné pouze pro teoretické zkoumání, nikoliv pro praktický výpočet řešení této soustavy. Výpočet součinu A^{−1}b vyžaduje

n^{2}  násobení/dělení, a
n(n − 1) sčítání/odčítání.

Celkem tak výpočet inverzní matice A^{−1} Gaussovou-Jordanovou metodou a součinu A^{−1}b potřebuje

n^{3} + n^{2} násobení/dělení, a
n^{3} − n^{2} sčítání/odčítání.

Tento výpočet tak vyžaduje zhruba trojnásobný počet operací a tedy trojnásobné množství času než přímý výpočet řešení pomocí Gaussovy eliminace a zpětné substituce.

Je také zajímavé všimnout si, že výpočet inverzní matice k regulární matici řádu n potřebuje zhruba stejně operací jako výpočet součinu dvou čtvercových matic řádu n. Na první pohled se zdá být výpočet inverzní matice mnohem náročnější.

Následující cvičení shrnuje základní vlastnosti inverzních matic. Snadno je dokážete za použití poznatků z této kapitoly.

Cvičení 3.9 Dokažte, že pro regulární matice A, B stejného řádu n platí

• (A^{−1})^{−1} = A,

• součin AB je také regulární matice,

• (AB)^{−1} = B^{−1}A^{−1},

• (A^{−1})^{T} = (A^{T})^{−1}.

Z druhého tvrzení ihned indukcí podle k snadno dokážete, že součin A_{1}A_{2} ⋯ A_{k} je regulární matice, jsou-li všechny matice A_{i} regulární a stejného řadu n. V tom případě

(A_{1}A_{2} ⋯ A_{k})^{−1} = A_{k}^{−1} ⋯ A_{2}^{−1}A_{1}^{−1}.

Čtvrté tvrzení pak znamená, že matice transponovaná k regulární matici je opět regulární, a že inverzní matici k A^{T} dostaneme jako matici transponovanou k A^{−1}.

Následující obtížnější cvičení vám ukáže, jak dobře jste část o inverzních maticích zvládli. Je v něm uvedeno mimo jiné, jak rychle spočítat inverzní matici k matici, kterou dostaneme z dané regulární matice A změnou jednoho prvku, pokud již známe inverzní matici A^{−1}.

Cvičení 3.10 Předpokládáme, že A = (a_{ij}) je regulární matice řádu n a e_{i} pro i = 1, 2, …, n je i-tý sloupcový vektor jednotkové matice I_{n}. Dokažte, že platí • součin αe_{i}e_{j}^{T} je čtvercová matice, která má všechny prvky nulové s

výjimkou prvku na místě (i, j), který se rovná číslu α,

• je-li B = A + αe_{i}e_{j}^{T}, tj. B se liší od A pouze v prvku na místě (i, j), ke kterému jsme přičetli číslo α, a označíme-li dále A^{−1} = (b_{ij}), pak

B^{−1} = (A + αe_{i}e_{j}^{T})^{−1} = A^{−1} − α\frac{[A^{−1}]_{∗i}[A^{−1}]_{∗j}}{1 + αb_{ji}},

pokud je číslo ve jmenovateli nenulové (jde o speciální případ tzv. Shermanovy-Morrisonovy formule),

• jsou-li c, d sloupcové vektory dimenze n takové, že číslo 1 + d^{T} c ≠ 0, pak

(I_{n} + cd^{T})^{−1} = I_{n} − \frac{cd^{T}}{1 + d^{T} c} ,

• je-li 1 + d^{T} A^{−1}c ≠ 0, pak platí

(A + cd^{T})^{−1} = A^{−1} − \frac{A^{−1}cd^{T} A^{−1}}{1 + d^{T} A^{−1}c}

(obecná Shermanova-Morrisonova formule),

• jsou-li C, D matice tvaru n × k takové, že inverzní matice k matici I^{k} + D^{T} A^{−1}C existuje, potom

(A + CD^{T})^{−1} = A^{−1}C(I^{k} + D^{T} A^{−1}C)^{−1}D^{T} A^{−1}

(tzv. Shermanova-Morrisonova-Woodburyho formule).

Elementární matice V Tvrzení 3.7 jsme ukázali, že každý řádek součinu AB je lineární kombinací řádků matice B. Nyní si ukážeme, že můžeme efekt elementární řádkové úpravy matice B docílit také tím, že matici B vynásobíme zleva vhodnou regulární maticí.

Elementární matice 1. druhu je čtvercová matice E_{ij} = (a_{uv}) řádu m, kde a_{ij} = a_{ji} = 1 pro nějaké indexy i ≠ j, dále a_{kk} = 1 pro všechna k ≠ i, j. Všechny ostatní prvky matice E_{ij} se rovnají 0.

Podívejme se, jak vypadají řádky v součinu matic E_{ij}B, kde B je libovolná matice tvaru m × n. V i-tém řádku matice E_{ij} je jediný nenulový prvek a to na místě (i, j). Podle první části Tvrzení 3.7 se i-tý řádek součinu E_{ij}B rovná

[E_{ij}]_{i∗}B = ∑_{k=1}^{m} a_{ik}B_{k∗}.

Protože v i-tém řádku matice E_{ij} je jediný nenulový prvek a_{ij} = 1, rovná se i-tý řádek součinu E_{ij}B j-tému řádku B_{j∗} matice B.

Podobně ukážeme, že se j-tý řádek součinu E_{ij}B rovná i-tému řádku matice B. Pokud je k ≠ i, j, je v k-tém řádku matice E_{ij} jediný nenulový prvek a_{kk} = 1 na hlavní diagonále. Proto se k-tý řádek součinu E_{ij}B rovná k-tému řádku B_{k∗} matice B. Součin E_{ij}B tak dostaneme z matice B první elementární řádkovou úpravou prohazující i-tý a j-tý řádek matice B.

Elementární matice 2. druhu je čtvercová matice E_{i}(d) = (a_{uv}) řádu m, která má nenulové prvky pouze na hlavní diagonále, prvek a_{ii} = d ≠ 0, a prvky a_{kk} = 1 pro k ≠ i. Podobně jako v případě elementární matice 1. druhu snadno ověříme, že součin E_{i}(d)B dostaneme z matice B tak, že vynásobíme i-tý řádek číslem d, tedy druhou elementární řádkovou úpravou.

Je-li i ≠ j, pak elementární matice 3. druhu je čtvercová matice E_{ji}(d) = (a_{uv}) řádu m, která má na hlavní diagonále prvky rovné 1, a mimo hlavní diagonálu je jediný (případně) nenulový prvek d na místě (j, i). V součinu E_{ji}(d)B se potom j-tý řádek rovná lineární kombinaci dE_{i∗} +E_{j∗}, tj. součtu d-násobku i-tého řádku s j-tým řádkem matice B. Všechny ostatní řádky matice E_{ji}(d)B se rovnají příslušným řádkům matice B. Součin E_{ji}(d)B dostaneme z matice B třetí elementární řádkovou úpravou.

Pokud v elementární matici 1. druhu E_{ij} prohodíme i-tý a j-tý řádek, dostaneme jednotkovou matici I_{m}. Matice E_{ij} má proto hodnost m a podle Věty 3.9 je regulární.

Podobně také z elementární matice 2. druhu E_{i}(d) dostaneme jednotkovou matici I_{m} elementární řádkovou úpravou, při které vynásobíme i-tý řádek číslem d^{−1} ≠ 0. Matice E_{i}(d) je proto také regulární.

A nakonec, z matice E_{ji}(d) dostaneme jednotkovou matici I_{m} tak, že od j-tého řádku odečteme d-násobek i-tého řádku. Dokázali jsme tak první část následujícího tvrzení.

Tvrzení 3.12 Platí, že

• elementární matice všech tří druhů jsou regulární,

• inverzní matice k elementární matici je také elementární matice,

• čtvercová matice P řádu m je regulární právě když ji lze vyjádřit jako součin elementárních matic, • matici A tvaru m × n dostaneme z matice B téhož tvaru posloup-

ností elementárních řádkových úprav právě když A = PB pro nějakou regulární matici řádu m.

Důkaz. Přímým výpočtem ověříme, že E_{ij}^{−1} = E_{ij}, E_{i}(d)^{−1} = E_{i}(d^{−1}) a E_{ji}(d)^{−1} = E_{ji}(−d).

Součin elementárních matic je regulární podle Cvičení 3.9, protože každá elementární matice je regulární podle první části tohoto tvrzení.

Je-li naopak matice P regulární, má podle Věty 3.9 hodnost m. Pomocí elementárních řádkových úprav ji proto můžeme převést do jednotkové matice I_{m}. To znamená, že existují elementární matice E_{1}, E_{2}, …, E_{k} takové, že

E_{k} ⋯ E_{2}E_{1}P = I_{m}.

Protože je každá elementární matice regulární, postupným násobením poslední rovnosti inverzními maticemi E_{l}^{−1} dostaneme rovnost

P = E_{1}^{−1}E_{2}^{−1} ⋯ E_{k}^{−1}I_{m} = E_{1}^{−1}E_{2}^{−1} ⋯ E_{k}^{−1}.

Inverzní matice k libovolné elementární matici je opět elementární podle druhé části tohoto tvrzení, poslední rovnost je tak vyjádřením regulární matice P ve tvaru součinu elementárních matic.

Pokud dostaneme matici A z matice B pomocí posloupnosti elementárních úprav, platí

A = E_{k} ⋯ E_{2}E_{1}B.

pro nějaké elementární matice E_{1}, …, E_{k}. Podle druhé části tohoto tvrzení je matice P = E_{k} ⋯ E_{2}E_{1} regulární.

Naopak, je-li A = PB pro nějakou regulární matici P, vyjádříme podle třetí části tohoto tvrzení matici P jako součin elementárních matic P = F_{l} ⋯ F_{1}. Potom

A = PB = F_{l} ⋯ F_{1}B.

Matici A tak dostaneme z matice B posloupností elementárních řádkových úprav. □

Co se stane, když vynásobíme matici A tvaru m×n nějakou elementární maticí E řádu n zprava? Podle druhé části Tvrzení 3.7 víme, že k-tý sloupec v součinu AE je lineární kombinací sloupců matice A s koeficienty z k-tého sloupce matice E.

Součin AE_{ij} tak dostaneme z matice A prohozením i-tého a j-tého sloupce matice A. Součin AE_{i}(d) dostaneme z matice A vynásobením itého sloupce číslem d. A konečně matici AE_{ji}(d) dostaneme z matice A tak, že k i-tému sloupci přičteme d-násobek j-tého sloupce. Násobit matici A zprava elementárními maticemi je totéž jako provádět elementární sloupcové úpravy matice A.

Pomocí elementárních řádkových úprav můžeme danou matici A tvaru m×n zjednodušit do redukovaného řádkově odstupňovaného tvaru E_{A}. Pro další zjednodušení musíme použít elementární sloupcové úpravy. Jak moc můžeme matici A dále zjednodušit říká následující tvrzení. Ještě dříve si ale řekneme, co je to blokový tvar matice.

Je-li A matice tvaru m × n, a m, n ≥ 2, můžeme řádky matice rozdělit na prvních r řádků a zbylých n−r řádků, je-li 0 < r < m. Podobně můžeme rozdělit sloupce matice na prvních s sloupců a zbylých n − s sloupců. Celá matice A se tak rozpadne do čtyř matic

A = ( \begin{matrix}B & C \\ D & E \end{matrix} ) ,

kde B je matice tvaru r ×s, C je matice tvaru r ×(n−s), D je matice tvaru (m − r) × s a konečně E je matice tvaru (m − r) × (n − s). Tento blokový tvar matic budeme v dalším využívat.

Tvrzení 3.13 Je-li A matice tvaru m × n a její hodnost r(A) = r, pak ji můžeme pomocí elementárních řádkových a sloupcových úprav převést do matice

N_{r} = ( \begin{matrix}I_{r} & 0_{r×(n−r)} \\ 0_{(m−r)×r)} & 0_{(m−r)×(n−r)} \end{matrix} ) ,

která obsahuje přesně r prvků rovných 1 a ostatní prvky se rovnají 0. Existují tedy regulární matice P řádu m a Q řádu n tak, že PAQ = N_{r}.

Důkaz. Matici A převedem pomocí elementárních řádkových úprav do redukovaného řádkově odstupňovaného tvaru E_{A} (Gaussovou-Jordanovou eliminací).

První nenulový prvek v prvním řádku je pivot 1, který se nachází řekněme v j-tém sloupci. Odečítáním vhodných násobků j-tého sloupce od dalších sloupců můžeme vynulovat všechny ostatní prvky v prvním řádku. Zůstane v něm pouze jeden nenulový prvek – pivot 1.

Totéž opakujeme s druhým řádkem. Jeho pivot 1 se nachází řekněme v k-tém sloupci, k > j. V k-tém sloupci je pivot 1 jediný nenulový prvek. Odečítáním vhodných násobků k-tého sloupce od dalších sloupců vynulujeme všechny ostatní prvky v druhém řádku. Prvky v prvním řádku se nezmění, protože prvek v k-tém sloupci a prvním řádku (na místě (1, k)) se rovná 0.

Pokračujeme třetím řádkem, atd. se všemi nenulovými řádky matice E_{A}. Po skončení těchto elementárních řádkových úprav dostaneme matici, která má v prvních r řádcích jediný nenulový prvek 1 a všechny ostatní řádky jsou nulové. Tato matice má také přesně r nenulových sloupců. Jsou to bázové sloupce matice E_{A}. V každém z těchto bázových sloupců je jediný nenulový prvek 1 na místech pivotů matice E_{A}.

Pivot v prvním řádku přesuneme na místo (1, 1) do prvního sloupce prohozením prvního a j-tého sloupce. Podobně prohozením druhého a ktého sloupce dostaneme pivot 1 v druhém řádku na místo (2, 2), atd.

Podle poslední části Tvrzení 3.12 existuje regulární matice P tak, že PA = E_{A}. Skutečnost, že posloupnost elementárních sloupcových úprav můžeme vyjádřit pomocí násobení regulární maticí zprava plyne rovněž z poslední části Tvrzení 3.12, které použijeme na transponované matice. □

O maticích N_{r} říkáme, že jsou v normálním tvaru pro hodnost.

Cvičení 3.11 Najděte pro nějakou matici A regulární matice P a Q takové, že platí PAQ = N_{r}, kde r = r(A).

Tvrzení 3.13 říká, že každou matici A můžeme převést pomocí elementárních řádkových a sloupcových úprav do matice N_{r}, kde r je hodnost matice A. Neříká ale, že neexistuje jiná posloupnost elementárních řádkových a sloupcových úprav, která převede matici A do jiné matice N_{s} v normáln ím tvaru pro hodnost. Tuto možnost vylučuje druhá část následujícího tvrzení.

Tvrzení 3.14 Pro matice A, N_{r} a N_{s} tvaru m × n platí

• jsou-li N_{r} a N_{s} matice v normálním tvaru pro hodnost a PN_{r}Q = N_{s} pro nějaké regulární matice P a Q, pak r = s,

• pokud P_{1}AQ_{1} = N_{r} a P_{2}AQ_{2} = N_{s} jsou v normálním tvaru pro hodnost a P_{1}, Q_{1}, P_{2}, Q_{2} jsou regulární matice, pak r = s.

Důkaz. Z rovnosti PN_{r}Q = N_{s} vyplývá rovnost PN_{r} = N_{s}Q^{−1}. Hodnost matice PN_{r} se proto rovná hodnosti matice N_{s}Q^{−1}. Z Tvrzení 3.7 a podoby matice N_{r} dostáváme, že prvních r sloupců matice PN_{r} se rovná prvním r sloupcům matice P a zbývající sloupce matice PN_{r} jsou nulové:

PN_{r} = [P_{∗1}|P_{∗2}| ⋯ |P_{∗r}|0_{m×(n−r)} ].

Matice P je regulární, Gaussovou-Jordanovou eliminací ji proto převedeme do jednotkové matice I_{m} podle Věty 3.9. Přesně stejné elementární řádkové úpravy proto převedou matici PN_{r} do matice, která má prvních r sloupců shodných s prvními r sloupci jednotkové matice I_{m} a zbylých n − r sloupců jsou nulové sloupce. Proto r(PN_{r}) = r.

V součinu N_{s}Q^{−1} se podle téhož Tvrzení 3.7 prvních s řádků rovná prvním s řádkům matice Q^{−1} a ostatní řádky matice N_{s}Q^{−1} jsou nulové. Proto je hodnost r(N_{s}Q^{−1}) ≤ s, neboť v každém nenulovém řádku matice N_{s}Q^{−1} je nejvýše jeden pivot. Tím jsme dokázali nerovnost r = r(PN_{r}) = r(N_{s}Q^{−1}) ≤ s.

Z rovnosti PN_{r}Q = N_{s} také vyplývá rovnost P^{−1}N_{s}Q^{−1} = N_{r}. Z právě dokončené části důkazu tak rovněž vyplývá s ≤ r. Proto r = s.

Abychom dokázali druhou část tvrzení, vyjádříme matici A dvěma různými způsoby

P_{1}^{−1}N_{r}Q_{1}^{−1} = A = P_{2}^{−1}N_{s}Q_{2}^{−1},

a tedy

(P_{2}P_{1}^{−1})N_{r}(Q_{1}^{−1}Q_{2}) = N_{s}.

Protože jsou součiny P_{2}P_{1}^{−1} a Q_{1}^{−1}Q_{2} regulární podle Cvičení 3.9, vyplývá z první části tvrzení rovnost r = s. □

Důsledkem Tvrzení 3.14 je následující důležitá věta.

Věta 3.15 Pro každou matici A platí

r(A) = r(A^{T}),

tj. hodnost matice A se rovná hodnosti matice k ní transponované.

Důkaz. Označme r(A) = r a r(A^{T}) = s. Podle Tvrzení 3.13 existují regulární matice P_{1} a Q_{1}, pro které platí

P_{1}AQ_{1} = N_{r},

a regulární matice P_{2} a Q_{2}, pro které platí

P_{2}A^{T} Q_{2} = N_{s}.

Pokud první z těchto rovností transponujeme, dostaneme

Q_{1}^{T}A^{T} P_{1}^{T} = N_{r}^{T} .

Protože obě matice N_{s} a N_{r}^{T} jsou v normálním tvaru pro hodnost, vyplývá z druhé části předchozího Tvrzení 3.14, že r = s. □

Hodnost matice A najdeme pomocí elementárních řádkových úprav matice A. Říká se jí proto také řádková hodnost matice A. Hodnost transponované matice A^{T} najdeme pomocí elementárních řádkových úprav matice A^{T}, tj. pomocí elementárních sloupcových úprav matice A. Hodnost transponované matice A^{T} se proto také často nazývá sloupcová hodnost matice A. Poslední Větu 3.15 proto můžeme také vyjádřit slovy: řádková a sloupcová hodnost každé matice se rovnají. Jiný důkaz této důležité věty si ukážeme později. Bude založený na následujícím tvrzení.

Vynásobit matici A regulární maticí P zleva je totéž, jako udělat posloupnost elementárních řádkových úprav matice A. Elementární řádkové úpravy zachovávají lineární vztahy mezi sloupci matic v následujícím smyslu.

Tvrzení 3.16 Jsou-li A a B matice stejného tvaru m × n a B = PA pro nějakou regulární matici P, pak platí

A_{∗k} = ∑_{i≠k}c_{i}A_{∗i} právě když B_{∗k} = ∑_{i≠k}c_{i}B_{∗i}.

Důkaz. Platí-li

A_{∗k} = ∑_{i≠k}c_{i}A_{∗i},

vynásobíme tuto rovnost zleva maticí P. Dostaneme podle Tvrzení 3.7

B_{∗k} = [PA]_{∗k} = PA_{∗k} = P ∑_{i≠k}c_{i}A_{∗i} = ∑_{i≠k}Pc_{i}A_{∗i} =
= ∑_{i≠k}c_{i}PA_{∗i} = ∑_{i≠k}c_{i}[PA]_{∗i} = ∑_{i≠k}c_{i}B_{∗i}.

Naopak, platí-li

B_{∗k} = ∑_{i≠k}c_{i}B_{∗i},

vynásobíme tuto rovnost zleva inverzní maticí P^{−1} a postupujeme zcela stejně neboť A = P^{−1}B. □

LU faktorizace

Nyní se budeme zabývat řešením několika soustav n lineárních rovnic o n neznámých Ax = b_{1}, Ax = b_{2}, Ax = b_{3}, …, kde A je regulární matice řádu n a b_{1}, b_{2}, b_{3}, … jsou různé vektory pravých stran. Všechny soustavy tak mají jednoznačné řešení podle Věty 3.9 a Věty 2.7. Každou soustavu můžeme vyřešit zvlášť tím, že rozšířenou matici soustavy [A|b_{p}] převedeme Gaussovou eliminací do matice [E|c_{p}] v řádkově odstupňovaném tvaru, a následnou zpětnou substitucí. Při těchto výpočtech mnoho operací opakujeme. Jde o ty operace, kterými společnou matici všech soustav A převádíme do řádkově odstupňovaného tvaru E.

Vyřešíme-li první soustavu Ax = b_{1}, získáme tím znalost matice E. Ta nám ale při řešení další soustavy Ax = b_{2} příliš nepomůže. Neznáme totiž vektor c_{2} – poslední sloupec matice [E|c_{2}]. Ten závisí spíš na tom, jak probíhá výpočet matice E, jakými elementárními řádkovými úpravami ji z matice A dostaneme. Stejné elementární řádkové úpravy potom převedou sloupcový vektor b_{2} do vektoru c_{2}. Potřebujeme najít způsob, jak uchovat informaci o průběhu Gaussovy eliminace, nikoliv pouze o jejím výsledku. Rozklad matice A v součin dvou vhodných matic LU je způsob uchování potřebné informace o průběhu Gaussovy eliminace. Název LU faktorizace pochází z anglických slov lower (dolní) a upper (horní). A slova dolní a horní objasňuje následující definice.

Definice 3.17 Čtvercová matice A = (a_{ij}) řádu n se nazývá dolní trojúhelníková matice, pokud a_{ij} = 0 pro i < j, tj. pokud se prvek a_{ij} nachází nad hlavní diagonálou.

Matice A se nazývá horní trojúhelníková matice, pokud a_{ij} = 0 pro i > j, tj. pokud se prvek a_{ij} nachází pod hlavní diagonálou.

Pro začátek hledání matic L a U budeme navíc předpokládat, že v průběhu Gaussovy eliminace použité na matici A se nikdy na místě pro pivot neobjeví číslo 0. Tento předpoklad znamená, že při Gaussově eliminaci nemusíme použít první elementární řádkovou úpravu prohazující dva řádky. Vystačíme pouze se třetími elementárními řádkovými úpravami, při kterých postupně vždy odečítáme násobky nějakého řádku od všech řádků pod ním. Těmto elementárním řádkovým úpravám odpovídá násobení zleva elementárními maticemi třetího druhu E_{ji}(l) pro j > i.

Podíváme se, jaké elementární řádkové úpravy potřebujeme k tomu, abychom vynulovali všechny prvky v prvním sloupci matice A pod pivotem a_{11} ≠ 0. K tomu potřebujeme pro j = 2, …, n odečíst od j-tého řádku l_{j1}- násobek prvního řádku, kde l_{j1} = a_{j1}a_{11}^{−1}. Tohoto efektu dosáhneme podle Tvrzení 3.7 tak, že matici A vynásobíme zleva maticí

T_{1} = ( \begin{matrix}1 & 0 & 0 & ⋯ & 0 \\ −l_{21} & 1 & 0 & ⋯ & 0 \\ −l_{31} & 0 & 1 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ −l_{m1} & 0 & 0 & ⋯ & 1 \end{matrix} ) .

Po prvním průběhu hlavního cyklu Gaussovy eliminace tak dostaneme matici

T_{1}A = ( \begin{matrix}a_{11} & a_{12} & a_{13} & ⋯ & a_{1n} \\ 0 & b_{22} & b_{23} & ⋯ & b_{2n} \\ 0 & b_{32} & b_{33} & ⋯ & b_{3n} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & b_{n2} & b_{n3} & ⋯ & b_{nn} \end{matrix} ) .

Podle našeho předpokladu je prvek na místě pro druhý pivot b_{22} ≠ 0. Gaussova eliminace tedy pokračuje tím, že postupně odečítáme l_{j2}-násobky druhého řádku od všech řádků pod ním, kde koeficient l_{j2} = b_{j2}b_{22}^{−1} pro j = 3, …, n. Efekt druhého průběhu hlavního cyklu Gaussovy eliminace dosáhneme tak, že matici T_{1}A vynásobíme zleva maticí

T_{2} = ( \begin{matrix}1 & 0 & 0 & ⋯ & 0 \\ 0 & 1 & 0 & ⋯ & 0 \\ 0 & −l_{32} & 1 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & −l_{n2} & 0 & ⋯ & 1 \end{matrix} ) .

Po dvou průbězích hlavního cyklu Gaussovy eliminace tak dostaneme matici

T_{2}T_{1}A = ( \begin{matrix}a_{11} & a_{12} & a_{13} & ⋯ & a_{1n} \\ 0 & b_{22} & b_{23} & ⋯ & b_{2n} \\ 0 & 0 & c_{33} & ⋯ & c_{3n} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & c_{n3} & ⋯ & c_{nn} \end{matrix} ) .

Opět c_{33} ≠ 0 a pokračujeme vynulováním všech prvků matice T_{2}T_{1}A pod pivotem c_{33}. Efekt k-tého cyklu Gaussovy eliminace dosáhneme pro k = 1, 2, … n − 1 vynásobením dosud vypočítané matice zleva maticí

T_{k} = ( \begin{matrix}1 & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ 0 & 1 & ⋯ & 0 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & 1 & 0 & ⋯ & 0 \\ 0 & 0 & ⋯ & −l_{k+1,k} & 1 & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & −l_{nk} & 0 & ⋯ & 1 \end{matrix} ) ,

kde −l_{m,k} je násobek k-tého řádku, který přičítáme k m-tému řádku pro m = k + 1, …, n.

Po skončení Gaussovy eliminace tak dostaneme matici

T_{n−1} ⋯ T_{2}T_{1}A = E.

Protože matice E je v řádkově odstupňovaném tvaru (a čtvercová), je horní trojúhelníková. Nadále ji tedy budeme značit U = (u_{ij}). Dostáváme tak rovnost

A = T_{1}^{−1}T_{2}^{−1} ⋯ T_{n−1}^{−1}U.

Přímým výpočtem zjistíme, že

T_{k}^{−1} = ( \begin{matrix}1 & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ 0 & 1 & ⋯ & 0 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & 1 & 0 & ⋯ & 0 \\ 0 & 0 & ⋯ & l_{k+1,k} & 1 & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & l_{nk} & 0 & ⋯ & 1 \end{matrix} )

pro k = 1, 2, …, n − 1. A dalším přímým výpočtem najdeme součin

T_{1}^{−1}T_{2}^{−1} ⋯ T_{n−1}^{−1} = ( \begin{matrix}1 & 0 & 0 & ⋯ & 0 \\ l_{21} & 1 & 0 & ⋯ & 0 \\ l_{31} & l_{32} & 1 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ l_{n1} & l_{n2} & l_{n3} & ⋯ & 1 \end{matrix} ) .

Matice T_{1}^{−1}T_{2}^{−1} ⋯ T_{n−1}^{−1} je tedy dolní trojúhelníková a označíme ji proto L. Dostáváme tak rozklad A = LU. Tomuto rozkladu říkáme LU faktorizace matice A. Důležité je podívat se na podobu matice L. Jakou roli hraje prvek l_{ij}, pro i > j, při výpočtu matice U = E Gaussovou eliminací? Po j −1 průbězích hlavního cyklu Gaussovy eliminace jsme dostali matici T_{j−1} ⋯ T_{1}A. Při j-tém průběhu Gaussovy eliminace vynulujeme prvek na místě (i, j) tím, že od i-tého řádku odečteme l_{ij}-násobek j-tého řádku. Číslo l_{ij} je tedy to číslo, které používáme při vynulování prvku na místě (i, j). Prvky matice L proto nemusíme zvlášť počítat, vypočítáme je při Gaussově eliminaci.

Cvičení 3.12 Najděte LU faktorizaci několika matic, pro které LU faktorizace existuje. Napište program pro výpočet LU faktorizace matice.

Možná někoho z vás napadlo, jak dobře uchovávat informace o poloze čísel l_{ij}. Když třetí elementární řádkovou úpravou vynulujeme prvek na místě (i, j), zapíšeme si koeficient l_{ij} na místo (i, j) jiným typem písma, nebo jej zakroužkujeme, aby bylo jasné, že jde o prvek matice L a nikoliv matice U. Následující úloha ukazuje tento postup.

Úloha 3.2 Najděte LU faktorizaci matice

A = ( \begin{matrix}2 & 2 & 2 \\ 4 & 7 & 7 \\ 6 & 18 & 22 \end{matrix} ) .

Řešení. Počítáme Gaussovu eliminaci matice A. Prvky l_{ij} zapisujeme na příslušná místa tučně:

A = ( \begin{matrix}2 & 2 & 2 \\ 4 & 7 & 7 \\ 6 & 18 & 22 \end{matrix} ) ∼ ( \begin{matrix}2 & 2 & 2 \\ 2 & 3 & 3 \\ 3 & 12 & 16 \end{matrix} ) ∼ ( \begin{matrix}2 & 2 & 2 \\ 2 & 3 & 3 \\ 3 & 4 & 4 \end{matrix} ) .

Proto A = LU pro

L = ( \begin{matrix}1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 4 & 1 \end{matrix} ) a U = ( \begin{matrix}2 & 2 & 2 \\ 0 & 3 & 3 \\ 0 & 0 & 4 \end{matrix} ) .

□

Pokud již známe LU faktorizaci A = LU, můžeme poměrně snadno vyřešit libovolnou soustavu Ax = b. Přepíšeme ji do tvaru

Ax = L(Ux) = b

a označíme y = Ux. Řešení soustavy Ax = b se tak rozpadne na řešení dvou soustav

Ly = b a Ux = y.

Obě soustavy snadno vyřešíme vzhledem k tomu, že obě matice L a U jsou trojúhelníkové. Soustavu Ly = b, tj.

( \begin{matrix}1 & 0 & 0 & ⋯ & 0 \\ l_{21} & 1 & 0 & ⋯ & 0 \\ l_{31} & l_{32} & 1 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ l_{n1} & l_{n2} & l_{n3} & ⋯ & 1 \end{matrix} ) ( y_{1} ; y_{2} ; y_{3} ; ⋮ ; y_{n} ) = ( b_{1} ; b_{2} ; b_{3} ; ⋮ ; b_{n} )

přímou substitucí

y_{1} = b_{1}, y_{2} = b_{2} − l_{21}y_{1}, y_{3} = b_{3} − l_{31}y_{1} − l_{32}y_{2}, atd.

Obecně můžeme řešení soustavy Ly = b vyjádřit ve tvaru

y_{1} = b_{1} a y_{i} = b_{i} − ∑_{k=1}^{i−1} l_{ik}y_{k} pro i = 2, 3, …, n.

Pokud již známe řešení y soustavy Ly = b, najdeme řešení soustavy Ux = y standardní zpětnou substitucí. Označíme-li U = (u_{ij})

x_{n} = \frac{y_{n}}{u_{nn}} , a x_{i} = \frac{1}{u_{ii}} (y_{i} − ∑_{k=i+1}^{n} u_{ik}x_{k}) pro i = n − 1, n − 2, …, 1.

Můžete si sami spočítat, že pokud již známe LU faktorizaci A = LU, pak řešení soustavy Ax = b tímto způsobem vyžaduje n^{2} násobení/dělení a n^{2} − n sčítání/odečítání. Pokud bychom měli řešit pouze jednu soustavu Ax = b, není využití LU faktorizace žádnou velkou výhodou. Pokud ale máme později řešit další soustavu Ax = c s jinou pravou stranou, pomůže nám znalost LU faktorizace urychlit řešení.

Cvičení 3.13 Najděte nějakou soustavu Ax = b, kterou lze vyřešit pouze pomocí třetích elementárních řádkových úprav. Během řešení soustavy Gaussovou eliminací najděte LU faktorizaci matice A. S její pomocí vyřešte několik dalších soustav Ax = c.

Cvičení 3.14 Vypočítejte inverzní matici A^{−1} k regulární matici A řádu n tak, že najdete řešení n soustav Ax = e_{i} pro i = 1, 2, …, n pomocí LU faktorizace matice A. Srovnejte počet operací, které jsou k tomuto výpočtu potřeba, s počtem operací při výpočtu pomocí Gaussovy-Jordanovy eliminace.

Cvičení 3.15 Dokažte, že pokud pro čtvercovou matici A řádu n platí A = LU a

• matice L = (l_{ij}) je dolní trojúhelníková, matice U = (u_{ij}) je horní trojúhelníková, obě řádu n,

• l_{ii} = 1 a u_{ii} ≠ 0 pro i = 1, 2, …, n,

pak jsou matice L a U určené maticí A jednoznačně.

Ne každá regulární matice má LU faktorizaci. Snadno si ověříte, že neexistuje nenulové číslo u_{11}, pro které platí

( \begin{matrix}0 & 1 \\ 1 & 1 \end{matrix} ) = ( \begin{matrix}1 & 0 \\ l_{21} & 1 \end{matrix} ) ( \begin{matrix}u_{11} & u_{12} \\ 0 & u_{22} \end{matrix} ) .

Následující cvičení je dost obtížné. Pokud je zkusíte a nezvládnete, můžete najít řešení v části 3.10. v Meyerově učebnici na webu.

Cvičení 3.16 Dokažte, že následující tři tvrzení jsou ekvivalentní:

• regulární matice A = (a_{ij}) řádu n má LU faktorizaci ve smyslu předchozího cvičení,

• v průběhu Gaussovy eliminace použité na matici A se na místě pro pivot nikdy neobjeví číslo 0, tj. Gaussova eliminace vystačí pouze se třetí elementární řádkovou úpravou,

• každá matice

( \begin{matrix}a_{11} & a_{12} & ⋯ & a_{1k} \\ a_{21} & a_{22} & ⋯ & a_{2k} \\ ⋮ & ⋮ & ... & ⋮ \\ a_{k1} & a_{k2} & ⋯ & a_{kk} \end{matrix} )

je regulární pro k = 1, 2, …, n.

Nyní si ukážeme, jak rozložit regulární matici, která nemá LU faktorizaci, v součin tří matic – dolní trojúhelníkové matice, horní trojúhelníkové matice a nějaké matice, které říkáme permutační.

Definice 3.18 Čtvercová matice P řádu n se nazývá permutační, můžemeli ji vyjádřit jako součin elementárních matic prvního druhu a řádu n.

Každá permutační matice je tedy regulární, neboť je součinem elementárních matic, které regulární jsou.

Ještě si ukážeme vyjádření matice

T_{k} = ( \begin{matrix}1 & 0 & ⋯ & 0 & 0 & ⋯ & 0 \\ 0 & 1 & ⋯ & 0 & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & 1 & 0 & ⋯ & 0 \\ 0 & 0 & ⋯ & −l_{k+1,k} & 1 & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & −l_{nk} & 0 & ⋯ & 1 \end{matrix} ) ,

se kterým se lépe počítá. Označíme

c_{k} = ( 0 ; 0 ; ⋮ ; 0 ; l_{k+1,k} ; l_{k+2,k} ; ⋮ ; l_{nk} )

a ještě připomeneme, že symbolem e_{k} označujeme k-tý sloupcový vektor jednotkové matice I_{n}. Přímým výpočtem potom ověříme, že platí

T_{k} = I_{n} − c_{k}e_{k}^{T} .

Maticím, které můžeme vyjádřit v tomto tvaru, budeme říkat elementární dolní trojúhelníkové matice. Připomeňme ještě, že symbolem E_{k+i,k+j} označujeme elementární matici prvního druhu. Pro tuto matici platí rovnost e_{k}^{T} E_{k+i,k+j} = e_{k}^{T}, jak si rovněž snadno ověříme přímým výpočtem. Vzhledem k tomu, že také platí E_{k+i,k+j}^{2} = I_{n}, dostáváme

E_{k+i,k+j} T_{k}E_{k+i,k+j} = E_{k+i,k+j} (I_{n} − c_{k}e_{k}^{T})E_{k+i,k+j} =
= E_{k+i,k+j}^{2} − E_{k+i,k+j} c_{k}e_{k}^{T} E_{k+i,k+j} = I_{n} − (E_{k+i,k+j} c_{k})e_{k}^{T} .

Označíme si \overline{c}_{k} = E_{k+i,k+j} c_{k}. Potom se matice

\overline{T}_{k} = E_{k+i,k+j} T_{k}E_{k+i,k+j} = I_{n} − \overline{c}_{k}e_{k}^{T}

liší od matice T_{k} pouze tím, že jsou v ní prohozené prvky l_{k+i,k} a l_{k+j,k} . Je to rovněž elementární dolní trojúhelníková matice.

Po této přípravě se můžeme vrátit k problému, jak se vypořádat se situací, kdy po proběhnutí k hlavních cyklů Gaussovy eliminace dostaneme v matici T_{k} ⋯ T_{1}A na místě (k + 1, k + 1) pro k + 1-ní pivot číslo 0. Nyní musíme použít první elementární úpravu prohazující k + 1-ní řádek s k + jtým řádkem pro nějaké j > 1. Příslušnou elementární matici prvního druhu si označíme E = E_{k+1,k+j} . Vzhledem k tomu, že E^{2} = I_{n} tak dostaneme matici

ET_{k} ⋯ T_{1}A = ET_{k}E^{2}T_{k−1}E^{2} ⋯ E^{2}T_{1}E^{2}A =
= (ET_{k}E)(ET_{k−1}E) ⋯ (ET_{1}E)EA =
= \overline{T}_{k}\overline{T}_{k−1} ⋯ \overline{T}_{1}EA.

Každou z elementárních dolních trojúhelníkových matic \overline{T}_{p}, p = 1, …, k dostaneme z matice T_{p} tak, že v ní prohodíme prvky na místech (k + 1, p) a (k+j, p). Součin \overline{T}_{k}\overline{T}_{k−1} ⋯ \overline{T}_{1} se proto od součinu T_{k} ⋯ T_{1} liší tím, že jsme v prvních k sloupcích prohodili prvky, které se nacházejí v (k+1)-ním řádku a (k + j)-tém řádku. Není to elementární řádková úprava !! Neprohazujeme totiž celý (k + 1)-ní řádek s celým (k + j)-tým řádkem. Prohazujeme pouze ty prvky z obou řádků, které odpovídají multiplikátorům l_{uv}.

Poslední výpočet ukazuje, že efekt první elementární řádkové úpravy na matici ET_{k} ⋯ T_{1}A dosáhneme také tak, že tuto elementární řádkovou úpravu uděláme pouze na matici A a součin elementárních dolních trojúhelníkových matic T_{k} ⋯ T_{1} nahradíme součinem jiných elementárních trojúhelníkových matic \overline{T}_{k}\overline{T}_{k−1} ⋯ \overline{T}_{1}.

Pokud tedy v průběhu Gaussovy eliminace musíme několikrát použít první elementární řádkovou úpravu, kterým odpovídají elementární matice prvního druhu E_{1}, …, E_{r}, pak výsledkem Gaussovy eliminace bude horní trojúhelníková matice

U = T̃_{n−1} T̃_{n−2} ⋯ T̃_{1}(E_{r} ⋯ E_{1})A.

Součin dolních elementárních trojúhelníkových matic L = T̃_{n−1} T̃_{n−2} ⋯ T̃_{1} je dolní trojúhelníková matice Součin elementárních matic prvního druhu P = E_{r} ⋯ E_{1} je permutační matice. Dostáváme tak rozklad

PA = (T̃_{1}^{−1} T̃_{2}^{−1} ⋯ T̃_{n−1}^{−1})U

Protože inverzní matice k elementárním dolním trojúhelníkovým maticím T̃_{k} = I_{n} − c̃_{k}e_{k}^{T} se rovnají T̃_{k}^{−1} = I_{n} + c̃_{k}e_{k}^{T}, jsou rovněž elementární dolní trojúhelníkové. Jejich součin L = T̃_{1}^{−1} T̃_{2}^{−1} ⋯ T̃_{n−1}^{−1} je proto dolní trojúhelníková matice.

Dostáváme tak LU faktorizaci PA = LU matice PA místo matice A, jejíž LU faktorizace nemusí existovat. Praktický postup nalezení permutační matice P a LU faktorizace PA = LU si ukážeme v následující úloze. Zdůvodnění správnosti postupu je podobné jako v případě matic, pro které přímo existuje LU faktorizace.

Úloha 3.3 Použijte parciální pivotaci na matici

A = ( \begin{matrix}1 & 2 & −3 & 4 \\ 4 & 8 & 12 & −8 \\ 2 & 3 & 2 & 1 \\ −3 & −1 & 1 & −4 \end{matrix} )

a najděte LU faktorizaci PA = LU, kde P je příslušná permutační matice.

Řešení. Multiplikátory l_{uv} budeme opět vyznačovat tučně. Abychom po skončení výpočtu mohli rekostruovat matici P, přidáme si k matici A kontrolní “sloupec pravých stran” p, který tvoří různá čísla. Provádíme-li v průběhu Gaussovy eliminace první elementární řádkovou úpravu, prohazujeme nejen prvky příslušné matice, ale i multiplikátory, které si píšeme na příslušná místa stejně jako jsme to dělali v předchozí úloze.

[A|b] = ( \begin{matrix}1 & 2 & −3 & 4 & 1 \\ 4 & 8 & 12 & −8 & 2 \\ 2 & 3 & 2 & 1 & 3 \\ −3 & −1 & 1 & −4 & 4 \end{matrix} ) ∼ ( \begin{matrix}4 & 8 & 12 & −8 & 2 \\ 1 & 2 & −3 & 4 & 1 \\ 2 & 3 & 2 & 1 & 3 \\ −3 & −1 & 1 & −4 & 4 \end{matrix} ) ∼

∼ ( \begin{matrix}4 & 8 & 12 & −8 & 2 \\ 1/4 & 0 & −6 & 6 & 1 \\ 1/2 & −1 & −4 & 5 & 3 \\ −3/4 & 5 & 10 & −10 & 4 \end{matrix} ) ∼ ( \begin{matrix}4 & 8 & 12 & −8 & 2 \\ −3/4 & 5 & 10 & −10 & 4 \\ 1/2 & −1 & −4 & 5 & 3 \\ 1/4 & 0 & −6 & 6 & 1 \end{matrix} ) ∼

∼ ( \begin{matrix}4 & 8 & 12 & −8 & 2 \\ −3/4 & 5 & 10 & −10 & 4 \\ 1/2 & −1/5 & −2 & 3 & 3 \\ 1/4 & 0 & −6 & 6 & 1 \end{matrix} ) ∼ ( \begin{matrix}4 & 8 & 12 & −8 & 2 \\ −3/4 & 5 & 10 & −10 & 4 \\ 1/4 & 0 & −6 & 6 & 1 \\ 1/2 & −1/5 & −2 & 3 & 3 \end{matrix} )

∼ ( \begin{matrix}4 & 8 & 12 & −8 & 2 \\ −3/4 & 5 & 10 & −10 & 4 \\ 1/4 & 0 & −6 & 6 & 1 \\ 1/2 & −1/5 & 1/3 & 1 & 3 \end{matrix} ) .

Proto

L = ( \begin{matrix}1 & 0 & 0 & 0 \\ −3/4 & 1 & 0 & 0 \\ 1/4 & 0 & 1 & 0 \\ 1/2 & −1/5 & 1/3 & 1 \end{matrix} ) , U = ( \begin{matrix}4 & 8 & 12 & −8 \\ 0 & 5 & 10 & −10 \\ 0 & 0 & −6 & 6 \\ 0 & 0 & 0 & 1 \end{matrix} )

a

P = ( \begin{matrix}0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{matrix} ) .

□

Máme-li nyní řešit soustavu Ax = b, u které neexistuje LU faktorizace matice soustavy A, najdeme postupem z předchozí úloha permutační matici P a LU faktorizaci PA = LU. Potom místo soustavy Ax = b řešíme ekvivalentní (ekvivalentní proto, že P je regulární matice) soustavu PAx = Pb.

A protože matice PA nové soustavy už má LU faktorizaci, můžeme použít dříve uvedený postup.

Cvičení 3.17 Zvolte nějakou soustavu Ax = b, jejíž matice A je regulární, ale nemá LU faktorizaci. Najděte matici P, pro kterou má součin PA LU faktorizaci, najděte ji a vyřešte původní soustavu pro několik různých pravých stran b.

Strassenův algoritmus pro rychlé násobení matic

Počátkem šedesátých let minulého století dostal ruský matematik Karacuba nápad, jak urychlit násobení čísel. Jeho nápad je velmi jednoduchý. Máme-li vynásobit dvě n-místná čísla x, y vyjádřená v soustavě o základu β, napíšeme si je ve tvaru

x = aβ^{n/2} + b, y = cβ^{n/2} + d.

Po vynásobení dostaneme

x · y = (aβ^{n/2} + b)(cβ^{n/2} + d) = acβ^{n} + (ad + bc)β^{n/2} + bd.

Pro výpočet součinu tak potřebujeme čtyři násobení a jedno sčítání. Součiny ac, ad, bc a bd jsou součiny n/2-místných čísel, která můžeme vynásobit stejně, atd.

Karacubův algoritmus spočívá v tom, že místo čtyř součinů ac, ad, bc, bd spočítáme pouze tři součiny ac, bd a (a − b)(d − c). Potom platí

x · y = (aβ^{n/2} + b)(cβ^{n/2} + d) = acβ^{n} + [(a − b)(d − c) + bd + ac]β_{n_{2}} + bd.

Stejný součin tak spočítáme pomocí 3 násobení a 4 sčítání/odčítání. Jednotlivé součiny počítáme stejným způsobem. Pro dostatečně velká n (v literatuře se obvykle uvádí n ≥ 500) převáží zmenšení počtu násobení nad zvětšeným počtem sčítání/odčítání a Karacubův algoritmus začne být rychlejší.

O několik let později Volker Strassen přišel na to, jak podobným způsobem urychlit násobení velkých matic. Máme-li vynásobit dvě matice

( \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} ) ( \begin{matrix}b_{11} & b_{12} \\ b_{21} & b_{22} \end{matrix} ) ,

a postupujeme-li podle definice, potřebujeme 8 násobení a 4 sčítání. Strassen ukázal postup, jak vystačit pouze se 7 násobeními a 15 sčítáními/odčítáními.

Počítal napřed součty

s_{1} = a_{21} + a_{22}, t_{1} = b_{12} − b_{11},
s_{2} = s_{1} − a_{11}, t_{2} = b_{22} − t_{1},
s_{3} = a_{11} − a_{21}, t_{3} = b_{22} − b_{21},
s_{4} = a_{12} − s_{2}, t_{4} = t_{2} − b_{21}.

Poté spočítal 7 součinů

p_{1} = a_{11}b_{11}, p_{5} = s_{1}t_{1},
p_{2} = a_{12}b_{21}, p_{6} = s_{2}t_{2},
p_{3} = s_{4}b_{22}, p_{7} = s_{3}t_{3}.
p_{4} = a_{22}t_{4},

A nakonec opět sčítal

u_{1} = p_{1} + p_{2}, u_{5} = u_{4} + p_{3},
u_{2} = p_{1} + p_{6}, u_{6} = u_{3} − p_{4},
u_{3} = u_{2} + p_{7}, u_{7} = u_{3} + p_{5}.
u_{4} = u_{2} + p_{5},

Potom mu vyšlo

( \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} ) ( \begin{matrix}b_{11} & b_{12} \\ b_{21} & b_{22} \end{matrix} ) = ( \begin{matrix}u_{1} & u_{5} \\ u_{6} & u_{7} \end{matrix} ) .

Máme-li vynásobit dvě čtvercové matice A, B řádu n = 2^{k}, rozdělíme si každou na čtyři čtvercové matice řádu n/2 a vynásobíme je předchozím postupem

A = ( \begin{matrix}A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} ) , B = ( \begin{matrix}B_{11} & B_{12} \\ B_{21} & B_{22} \end{matrix} ) .

Každý ze 7 součinů matic polovičního řádu n/2, které potřebujeme, opět spočítáme Strassenovým algoritmem, atd. Lze ukázat, že Strassenův algoritmus vyžaduje celkem n^{log_{2} 7} ≈ n^{2,807} násobení za cenu podstatného zvýšení počtu sčítání/odčítání. Pozdější vylepšení Strassenova algoritmu dokázala snížit počet násobení až na n^{2,376}. Někteří matematici vyjadřují domněnku, že lze počet násobení snížit dokonce až na n^{2}, nikdo to ale dosud nedokázal. Praktické experimenty ukazují, že algoritmy Strassenova typu jsou rychlejší než klasický algoritmus vyžadující n^{3} násobení, již pro násobení matic řádu 100.

Strassenův algoritmus vyvolal v sedmdesátých letech minulého století velký zájem o hledání “rychlých” algoritmů pro řešení nejrůznějších úloh.