Kapitola 10

Determinanty

Začneme pomocnou definicí.

Definice 10.1 Vzájemně jednoznačné zobrazení p : X → X nazýváme permutace na množině X. Je-li p permutace na množině X, pak inverzní zobrazení p^{−1} : X → X nazýváme inverzní permutace k permutaci p. Jsouli p, q dvě permutace na množině X, pak složené zobrazení, tj. permutaci, q ∘p : X → X nazýváme složení permutací p a q (v tomto pořadí). Identické zobrazení ı : X → X, pro které platí ı(x) = x pro každé x ∈ X, nazýváme identická permutace na množině X.

Zřejmě platí

• p ∘ ı = ı ∘ p = p pro každou permutaci p na množině X,

• p ∘ p^{−1} = p^{−1} ∘ p = ı pro každou permutaci p na množině X,

• r ∘ (q ∘ p) = (r ∘ q) ∘ p pro každé tři permutace p, q, r na množině X.

Budeme se zabývat výhradně permutacemi na množině {1, 2, …, n}. Množinu všech permutací na {1, 2, …, n} budeme nazývat grupa všech permutací na množině {1, 2, …, n} a budeme ji označovat S_{n}.

Permutace můžeme zapisovat různým způsobem. V případě permutací na konečné množině X = {1, 2, …, n} je můžeme zapsat pomocí tabulky. Do tabulky napíšeme do horního řádku čísla 1, 2, …, n a pod každé číslo i napíšeme hodnotu p(i). Tak například

p = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 3 & 5 & 2 & 9 & 4 & 1 & 8 & 7 & 6 \end{matrix} )

je permutace na množině {1, 2, …, 9}.

Pokud se domluvíme, že v horním řádku budeme psát čísla vždy ve stejném pořadí 1, 2, …, n, tak stačí zapsat pouze druhý řádek této tabulky (3, 5, 2, 9, 4, 1, 8, 7, 6).

Permutace můžeme zapisovat rovněž graficky. V rovině si zvolíme body 1, 2, …, n, a pokud permutace p zobrazuje prvek i do prvku j = p(i), pak nakreslíme šipku z bodu i do bodu j = p(i). Takovému obrázku říkáme graf permutace p. Graf permutace je charakterizován vlastnostmi

• z každého bodu i ∈ {1, 2, …, n} vychází právě jedna šipka, neboť hodnota p(i) je určena jednoznačně pro každý bod i ∈ {1, 2, …, n},

• do každého bodu j ∈ {1, 2, …, n} vede právě jedna šipka, neboť pro každý bod j ∈ {1, 2, …, n} existuje právě jeden bod i ∈ {1, 2, …, n} takový, že j = p(i).

Z grafu permutace je ihned vidět, že každá permutace se skládá z několika cyklů. Tak například uvedená permutace p na množině {1, 2, …, 9} se skládá ze dvou cyklů. Jeden je na bodech 1, 3, 2, 5, 4, 9, má délku 6, a druhý je na bodech 7, 8, má délku 2. Permutaci tak můžeme zapsat v cyklickém zápisu jako

p = (1, 3, 2, 5, 4, 9), (7, 8).

Každý bod z množiny {1, 2, …, 9} se zobrazí do bodu, který v zápisu následuje těsně za ním ve stejné závorce. Poslední bod v nějaké závorce se zobrazí do prvního bodu v téže závorce.

Pro obecnou permutaci p na nějaké konečné množině X najdeme cyklus obsahující bod i_{1} ∈ X tak, že postupně zapisujeme, kam se permutací p zobrazuje. Proto i_{2} = p(i_{1}), i_{3} = p(i_{2}), …, tj. i_{k+1} = p(i_{k}) pro libovolné k > 0. Protože je množina X konečná, musí se v posloupnosti i_{1}, i_{2}, … nějaký prvek opakovat. Označme k + 1 nejmenší index takový, že i_{k+1} se rovná některému z předcházejících prvků posloupnosti i_{1}, …, i_{k}. To znamená, že p(i_{k}) = i_{k+1} ∈ {i_{1}, …, i_{k}}. To znamená, že p(i_{k}) = i_{j} pro nějaké j ≤ k. Pokud by bylo j > 1, platilo by p(i_{k}) = p(i_{j−1}) = p_{j}. Protože i_{k+1} byl první prvek posloupnosti i_{1}, i_{2}, …, který se rovnal některému z předchozích prvků, bylo by i_{k} ≠ i_{j−1}, což je ve sporu se vzájemnou jednoznačností permutace p. Proto j = 1, tj. p(i_{k}) = i_{1}. Cyklus permutace p obsahující bod i_{1} se proto rovná (i_{1}, i_{2}, …, i_{k}). Počet jeho prvků, tj. číslo k, se nazývá délka tohoto cyklu. Je také dobré uvědomit si, že permutace p ∈ S_{n} se rovná identické permutaci ı právě když má všechny cykly délky 1.

Cyklický zápis rovněž popisuje permutaci p jednoznačně stejně jako tabulka nebo graf. Pokud jsou v permutaci nějaké cykly délky 1, tak je obvykle v cyklickém zápisu vynecháváme. V tom případě mluvíme o redukovaném cyklickém zápisu permutace. Tak například cyklický zápis permutace

q = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 1 & 2 & 4 & 5 & 6 & 7 & 8 & 3 & 9) \end{matrix} )

se rovná

q = (1), (2), (3, 4, 5, 6, 7, 8), (9)

a redukovaný cyklický zápis téže permutace q je

q = (3, 4, 5, 6, 7, 8).

V případě redukovaného cyklického zápisu musíme být předem domluveni, na jaké množině je permutace q definovaná.

Skládání permutací

Nejdříve si ukážeme, jak najít tabulku složené permutace q ∘ p, známe-li tabulky permutací p a q. Vezmeme například výše uvedené permutace p, q. Uděláme si tabulku o třech řádcích tak, že horní dva řádky budou tvořit tabulku permutace p a dolní dva řádky tabulku permutace q. Dostaneme tak

( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 3 & 5 & 2 & 9 & 4 & 1 & 8 & 7 & 6 \\ 4 & 6 & 2 & 9 & 5 & 1 & 3 & 8 & 7 \end{matrix} ) .

V každém sloupci máme pod prvkem i ve druhém řádku prvek p(i) a ve třetím řádku prvek q(p(i)). Tabulku složené permutace q ∘p nyní dostaneme tak, že vynecháme druhý řádek:

( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 4 & 6 & 2 & 9 & 5 & 1 & 3 & 8 & 7 \end{matrix} ) .

Také graf složení dvou permutací snadno získáme z grafů obou permutací. Pro obě permutace použijeme stejnou množinu bodů v rovině. Máme-li najít graf složené permutace q ∘ p najdeme napřed šipku v grafu p, která vede z bodu i do bodu p(i) a potom navážeme šipkou v grafu permutace q, která vede z bodu p(i) do bodu q(p(i)). V grafu složené permutace q ∘ p pak vede šipka z bodu i do bodu q ∘ p(i) = q(p(i)).

O něco složitější je najít cyklický zápis a redukovaný cyklický zápis složené permutace q ∘ p, známe-li odpovídající zápisy permutací p a q. Pro různé úlohy o permutacích je třeba zvolit vždy ten zápis, který je pro řešení příslušné úlohy nejvhodnější.

Definice 10.2 Permutace t ∈ S_{n} se nazývá transpozice, pokud má jeden cyklus délky 2 a ostatní cykly délky 1.

Pro zápis transpozic používáme nejčastěji redukovaný cyklický zápis t = (i, j).

Lemma 10.3 Každou permutaci p ∈ S_{n}, kde n ≥ 2, lze vyjádřit jako složení transpozic.

Důkaz. Budeme předpokládat, že p ≠ ı. V permutaci p tak existuje aspoň jeden cyklus délky aspoň 2. Označíme si jej (i_{1}, i_{2}, …, i_{k}). Složíme permutaci p s transpozicí (i_{1}, i_{2}). Dostaneme tak permutaci (i_{1}, i_{2}) ∘ p. V této složené permutaci se cyklus (i_{1}, i_{2}, …, i_{k}) rozpadne na dva cykly (i_{1}) a (i_{2}, …, i_{k}), a všechny ostatní cykly zůstanou beze změny.

V permutaci (i_{2}, i_{3}) ∘ (i_{1}, i_{2}) ∘ p se tak původní cyklus (i_{1}, i_{2}, …, i_{k}) rozpadne do tří cyklů (i_{1}), (i_{2}) a (i_{3}, …, i_{k}). Jednoduchou indukcí podle k tak dokážeme, že v permutaci

(i_{k−1}, i_{k}) ∘ (i_{k−2}, i_{k−1}) ∘ ⋯ ∘ (i_{1}, i_{2}) ∘ p

se původní cyklus (i_{1}, i_{2}, …, i_{k}) rozpadne na k cyklů délky 1 a všechny ostatní cykly permutace p zůstanou beze změny.

Opakujeme-li celý postup s dalším cyklem (j_{1}, …, j_{l}), dostaneme permutaci

(j_{l−1}, j_{l}) ∘ (j_{l−2}, j_{l−1}) ∘ ⋯ ∘ (j_{1}, j_{2}) ∘ (i_{k−1}, i_{k}) ∘ (i_{k_{2}}, i_{k−1}) ∘ ⋯ ∘ (i_{1}, i_{2}) ∘ p,

ve které se dva cykly (i_{1}, i_{2}, …, i_{k}) a (j_{1}, …, j_{l}) původní permutace p rozpadnou na cykly délky 1 a všechny ostatní cykly zůstávají beze změny. Postupně rozkládáme tímto způsobem další cykly permutace p na cykly délky 1, dokud nedostaneme identickou permutaci ı. Existují proto transpozice t_{1}, …, t_{m}, pro které platí

t_{m} ∘ ⋯ ∘ t_{1} ∘ p = ı.

Protože pro každou transpozici t platí t = t^{−1}, tj. t ∘ t = ı, můžeme poslední rovnost složit z transpozicí t_{m} zleva a dostaneme tak

t_{m−1} ∘ … ∘ t_{1} ∘ p = t_{m}.

Postupným skládáním s transpozicemi t_{m−1}, …, t_{1} zleva tak dostaneme rovnost

p = t_{1} ∘ t_{2} ∘ ⋯ ∘ t_{m},

což znamená, že jsme permutaci p vyjádřili jako složení transpozic. V případě identické permutace stačí vzít vyjádření ı = t ∘ t pro libovolnou transpozici t ∈ S_{n}. □

Lemma 10.4 Počet cyklů v permutaci p ∈ S_{n} a permutaci t ∘ p, kde t ∈ S_{n} je libovolná transpozice, se liší o 1. Rovněž počty cyklů v permutacích p a p ∘ t se liší o 1.

Důkaz. Označíme t = (i, j). Napřed budeme předpokládat, že prvky i, j leží ve stejném cyklu (i_{1}, …, i_{k}, j_{1}, …, j_{l}) permutace p a i = i_{1}, j = j_{1}. Pak platí, že v permutaci t ∘ p se tento cyklus rozpadne na dva cykly (i_{1}, …, i_{k}) a (j_{1}, …, j_{l}) a ostatní cykly zůstanou beze změny. Počet cyklů v permutaci t ∘ p je tak o 1 větší, než počet cyklů v permutaci p.

Jsou-li prvky i, j z různých cyklů (i = i_{1}, …, i_{k}) a (j = j_{1}, …, j_{l}) permutace p, potom ve složení t ∘ p se oba cykly propojí do jednoho cyklu (i_{1}, …, i_{k}, j_{1}, …, j_{l}) a ostatní cykly zůstanou beze změny, počet cyklů v permutaci t ∘ p je proto o 1 menší než počet cyklů v permutaci p.

Zcela stejně dokážeme, že také počet cyklů v permutaci p ∘ t se liší o 1 od počti cyklů v permutaci p. □

Lemma 10.5 Jsou-li p = t_{1} ∘ ⋯ ∘ t_{k} a p = u_{1} ∘ ⋯ ∘ u_{l} dvě různá vyjádření permutace p ∈ S_{n} jako složení transpozic, pak jsou obě čísla k, l buď současně sudá nebo jsou současně lichá.

Důkaz. Z rovnosti t_{1} ∘ ⋯ ∘ t_{k} = u_{1} ∘ ⋯ ∘ u_{l} dostaneme postupným skládáním s transpozicemi t_{1}, …, t_{k} zleva rovnost

t_{k} ∘ ⋯ ∘ t_{1} ∘ u_{1} ∘ ⋯ ∘ u_{l} = ı.

To znamená, že počet cyklů v obou permutacích ı a t_{k} ∘ ⋯ ∘ t_{1} ∘ u_{1} ∘ ⋯ ∘ u_{l} je stejný a rovná se n. Podle předchozího Tvrzení 10.4 se počet cyklů v jakékoliv permutaci změní o 1, pokud ji složíme s transpozicí. Proto musí být počet transpozic k + l ve složení t_{k} ∘ ⋯ ∘ t_{1} ∘ u_{1} ∘ ⋯ ∘ u_{l} sudý, a tedy jsou čísla k, l buď obě sudá nebo obě lichá. □

Definice 10.6 Permutace p ∈ S_{n} se nazývá sudá, pokud ji lze vyjádřit jako složení sudého počtu transpozic. Nazývá se lichá, pokud ji lze vyjádřit jako složení lichého počtu transpozic. Definujeme také znaménko permutace p jako 1, pokud je p sudá permutace, a jako −1, pokud je p lichá permutace. Znaménko permutace p označujeme jako sgn p.

Tvrzení 10.7 Složení dvou sudých permutací nebo dvou lichých permutací je sudá permutace. Složení sudé permutace s lichou (v jakémkoliv pořadí) je lichá permutace. Speciálně, pro každou permutaci p ∈ S_{n} a každou transpozici t ∈ S_{n} platí

sgn(t ∘ p) = sgn(p ∘ t) = −sgn p.

Důkaz. Plyne okamžitě z předchozího Tvrzení 10.5. Pokud p = t_{1}∘⋯∘t_{k} a q = u_{1} ∘ ⋯ ∘ u_{l}, pak q ∘ p = (u_{1} ∘ ⋯ ∘ u_{l}) ∘ (t_{1} ∘ ⋯ ∘ t_{k}), permutaci q ∘ p proto dostaneme jako složení k + l transpozic. □

Lemma 10.8 Je-li k počet cyklů permutace p ∈ S_{n}, pak sgn p = (−1)^{n−k}.

Důkaz. Permutaci p vyjádříme jako složení transpozic p = (t_{1}∘⋯∘t_{l})∘ı. Přidáním indentické permutace ı se složení nezmění. Identická permutace ı má n cyklů, zatímco permutace p má k cyklů. To znamená, že číslo l musí mít stejnou paritu jako číslo n − k (to znamená, že obě čísla musí být současně sudá nebo současně lichá). Z Definice 10.6 tak plyne

sgn p = (−1)^{l} = (−1)^{n−k}.

□

Cvičení 10.1 Dokažte, že permutace p ∈ S_{n} je sudá právě když má sudý počet cyklů sudé délky a je lichá právě když má lichý počet cyklů sudé délky.

Úloha 10.1 Charakterizace řešitelných a neřešitelných pozic u hry “15”.

Determinanty

Definice 10.9 Je-li A = (a_{ij}) čtvercová matice řádu n s prvky z tělesa T, pak definujeme determinant matice A jako číslo

det A = ∑_{p∈S_{n}} sgn p · a_{1p_{1}}a_{2p_{2}} ⋯ a_{np_{n}} ∈ T.

Determinant matice A označujeme rovněž |A|.

Pro zjednodušení zápisu jsme v definici determinantu použili označení p_{i} = p(i) pro i = 1, 2, …, n a p ∈ S_{n}.

Úloha 10.2 Spočítejte determinant matice řádu 2 a matice řádu 3. Spočítejte determinant horní trojúhelníkové matice.

Řešení. Matice řádu 2

A = ( \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} )

má determinant det A = a_{11}a_{22} − a_{12}a_{21}.

Matice řádu 3

B = ( \begin{matrix}b_{11} & b_{12} & b_{13} \\ b_{21} & b_{22} & b_{23} \\ b_{31} & b_{32} & b_{33} \end{matrix} )

má determinant

det B = b_{11}b_{22}b_{33} + b_{12}b_{23}b_{31} + b_{13}b_{21}b_{32}
−b_{11}b_{23}b_{32} − b_{12}b_{21}b_{33} − b_{13}b_{22}b_{31}.

Matice C = (c_{ij}) řádu n je horní trojúhelníková právě když c_{ij} = 0 kdykoliv i > j. V součtu definujícím detC dostaneme pro p = ı součin sgn ı · c_{11}c_{22} ⋯ c_{nn} = c_{11}c_{22} ⋯ c_{nn}. Ukážeme si, že pro jakoukoliv permutaci p ≠ ı je součin c_{1p_{1}}c_{2p_{2}} ⋯ c_{np_{n}} = 0. V permutaci p je aspoň jeden cyklus délky větší než 1. Ukážeme si, že v tomto cyklu existuje prvek j, pro který platí j > p(j), a tedy c_{jp_{j}} = 0. Má-li tento cyklus délku m ≥ 2 a jeli i = i_{1} nějaký prvek tohoto cyklu, pak všechny ostatní prvky můžeme vyjádřit induktivně jako i_{k+1} = p(i_{k}) pro k = 1, 2, …, m − 1. Kromě toho rovněž p(i_{m}) = i_{1}. Nemůže platit i_{1} < i_{2} < ⋯ < i_{m} < i_{1}. Proto existuje k ∈ {1, 2, …, m}, pro které platí i_{k} > p(i_{k}). Pro toto j = i_{k} pak platí c_{jp_{j}} = 0 a tedy sgn p·c_{1p_{1}}c_{2p_{2}} ⋯ c_{np_{n}} = 0. Všechny členy součtu definujícího determinant detC určené permutacemi p ≠ ı jsou tak rovné 0, proto

detC = c_{11}c_{22} ⋯ c_{nn}.

□

Absolutní hodnota determinantu reálné matice A = (a_{ij}) řádu 2 má jasný geometrický význam. Nakreslíme-li si v rovině dva vektory (a_{11}, a_{12}) a (a_{21}, a_{22}), a doplníme je na rovnoběžník, pak plocha tohto rovnoběžníku se rovná | detA| (spočtěte si to!). Číslo detA je kladné, pokud je úhel mezi vektory (a_{11}, a_{12}) a (a_{21}, a_{22}) měřený v kladném směru (tj. proti směru hodinových ručiček) menší než π a je záporný, pokud je tento úhel větší než π. Pokud se rovná tento úhel 0 nebo π, tj. jsou-li řádky matice A lineárně závislé, platí detA = 0, jak se můžete sami přesvědčit přímo z definice determinantu.

Podobný geometrický význam má rovněž determinant reálné matice B = (b_{ij}) řádu 3. Řádkové vektory b_{1} = (b_{11}, b_{12}, b_{13}), b_{2} = (b_{21}, b_{22}, b_{23}) a b_{3} = (b_{31}, b_{32}, b_{33}) určují v třídimenzionálním prostoru rovnoběžnostěn a jeho objem se rovná | detB|. Determinant detB je kladný, pokud je posloupnost vektorů b_{1}, b_{2}, b_{3} pravotočivá, tj. pokud umístíme pravou ruku tak, aby prsty ukazovaly od vektoru b_{1} k vektoru b_{2} ve směru, ve kterém je úhel mezi těmito vektory menší než π, pak palec ukazuje do poloprostoru, do kterého také míří vektor b_{3}. Deteminant detB je záporný, pokud palec ukazuje do opačného poloprostoru než kam míří vektor b_{3}, tj. pokud je posloupnost b_{1}, b_{2}, b_{3} levotočivá.

V případě reálných prostorů dimenze větší než 3 můžeme naopak pomocí determinantu definovat, kdy je posloupnost vektorů b_{1}, b_{2}, …, b_{n} pravotočivá nebo levotočivá, a co je to objem zobecněného rovnoběžnostěnu určeného vektory b_{1}, b_{2}, …, b_{n}.

Tvrzení 10.10 Pro každou čtvercovou matici A = (a_{ij}) řádu n platí

det A = det A^{T} .

Důkaz. Označme si transponovanou matici A^{T} = B = (b_{ij}). Pro libovolnou permutaci p = (p_{1}, p_{2} …, p_{n}) ∈ S_{n} (zápis tabulkou) je součin a_{1p_{1}}a_{1p_{2}} ⋯ a_{np_{n}} = b_{p_{1}1}b_{p_{2}2} ⋯ b_{p_{n}n}. Součin a_{1p_{2}}a_{1p_{2}} ⋯ a_{np_{n}} se při výpočtu detA vyskytuje se znaménkem sgn p, zatímco tentýž součin b_{p_{1}1}b_{p_{2}2} ⋯ b_{p_{n}n} odpovídá při výpočtu detB permutaci p^{−1} a má tedy znaménko sgn p^{−1} = sgn p. V součtech definujících detA a detB se tak vyskytují stejné součiny se stejným znaménkem, proto detA = detB = detA^{T}. □

Tvrzení 10.11 Má-li matice A řádu n dva stejné řádky, pak detA = 0.

Důkaz. Předpokládáme, že A_{i∗} = A_{j∗} pro i < j, tj. a_{ik} = a_{jk} pro k = 1, 2, …, n. Označme t = (i, j) transpozici, která prohazuje i-tý a j-tý řádek. Zvolíme libovolnou permutaci p ∈ S_{n} a podíváme se, jaké součiny v součtu definujícím detA určují permutace p a q = p ∘ (i, j) = p ∘ t. Platí q(i) = p(j), q(j) = p(i) a q(k) = p(k) pro k ≠ i, j. Permutace p určuje součin

sgn p · a_{1p_{1}} ⋯ a_{ip_{i}} ⋯ a_{jp_{j}} ⋯ a_{np_{n}},

zatímco permutace q = p ∘ t určuje součin

sgn q · a_{1q_{1}} ⋯ a_{iq_{i}} ⋯ a_{jq_{j}} ⋯ a_{nq_{n}} =
= sgn(p ∘ t) · a_{1q_{1}} ⋯ a_{iq_{i}} ⋯ a_{jq_{j}} ⋯ a_{nq_{n}} =
= −sgn p · a_{1p_{1}} ⋯ a_{ip_{j}} ⋯ a_{jp_{i}} ⋯ a_{np_{n}} =
= −sgn p · a_{1p_{1}} ⋯ a_{ip_{i}} ⋯ a_{jp_{j}} ⋯ a_{np_{n}}.

Je q = p ∘ t ≠ p neboť jedna z permutací p, q je sudá a druhá lichá podle Tvrzení 10.7. Součet součinů určených permutacemi p, q se tak rovná

sgn p · a_{1p_{1}} ⋯ a_{ip_{i}} ⋯ a_{jp_{j}} ⋯ a_{np_{n}} + sgn q · a_{1q_{1}} ⋯ a_{iq_{i}} ⋯ a_{jq_{j}} ⋯ a_{nq_{n}} = 0.

Celou množinu indexů, tj. symetrickou grupu S_{n}, rozložíme do disjunktních dvojic permutací {p, p∘t}. Tyto dvojice jsou skutečně disjunktní. Z rovnosti permutací p = r plyne rovnost p ∘ t = r ∘ t. Podobně z rovnosti p ∘ t = r ∘ t vyplývá p = (p ∘ t) ∘ t = (r ∘ t) ∘ t = r a rovnost p = r ∘ t platí právě když p∘t = (r ∘t)∘t = r. Pokud se tedy dvě dvojice {p, p∘t} a {r, r ∘t} protínají, musí se rovnat. Celý součet

∑_{p∈S_{n}} sgn p · a_{1p_{1}}a_{2p_{2}} ⋯ a_{np_{n}} ∈ T.

definující det A tak můžeme rozložit do neprotínajících se dvojic, z nichž součet každé dvojice se rovná 0. Proto také

detA = ∑_{p∈S_{n}} sgn p · a_{1p_{1}}a_{2p_{2}} ⋯ a_{np_{n}} ∈ T = 0.

□

Věta 10.12 Předpokládáme, že A = (a_{ij}) je čtvercová matice řádu n a B = (b_{ij}) je matice, kterou dostaneme z matice A nějakou elementární řádkovou úpravou, pak

• detB = − detA, pokud jsme B dostali z A prohozením dvou řádků,

• detB = c · detA, pokud jsme B dostali z A vynásobením některého řádku prvkem 0 ≠ c ∈ T,

• detB = detA, pokud jsme dostali B z A pomocí třetí elementární řádkové úpravy.

Důkaz. V případě první elementární úpravy platí B_{i∗} = A_{j∗} a B_{j∗} = A_{j∗} pro nějaké indexy i < j, a B_{k∗} = A_{k∗} pro k ≠ i, j. Porovnáme součin určený nějakou permutací p ∈ S_{n} v součtu definujícím detA a součin určený permutací q = p ∘ t v součtu definujícím detB. Stejně jako v důkazu předchozího tvrzení označuje t transpozici (i, j). Platí

sgn q · b_{1q_{1}} ⋯ b_{iq_{i}} ⋯ b_{jq_{j}} ⋯ b_{nq_{n}} = sgn(p ∘ t) · a_{1p_{1}} ⋯ a_{jp_{j}} ⋯ a_{ip_{i}} ⋯ a_{np_{n}} = = −sgn p · a_{1p_{1}} ⋯ a_{ip_{i}} ⋯ a_{jp_{j}} ⋯ a_{np_{n}}.

V součtech definujících detB a detA se tak vyskytují stejné součiny, ale s opačnými znaménky. Proto detB = − detA.

Pro důkaz druhého tvrzení si připomeňme, že v matici B platí B_{i∗} = cA_{i∗} pro nějaké i ∈ {1, 2, …, n}, a B_{k∗} = A_{k∗} pro k ≠ i. Platí proto b_{ij} = ca_{ij} a b_{kj} = a_{kj} pro libovolné j a k ≠ i. Permutace p ∈ S_{n} tak určuje v součtu definujícím detB součin

sgn p · b_{1p_{1}}b_{2p_{2}} ⋯ b_{ip_{i}} ⋯ b_{np_{n}} = sgn p · a_{1p_{1}}a_{2p_{2}} ⋯ ca_{ip_{i}} ⋯ a_{np_{n}} =
= c · sgn p · a_{1p_{1}}a_{2p_{2}} ⋯ a_{ip_{i}} ⋯ a_{np_{n}}.

Součin určený permutací p v definici detB tak dostaneme ze součinu určeného stejnou permutací p v definici detA vynásobením skalárem c. Protože to platí pro každou permutaci p ∈ S_{n}, dostáváme rovnost detB = c · detA.

Konečně třetí elementární úpravou k i-tému řádku matice A přičítáme c-násobek j-tého řádku. Budeme opět předpokládat i < j, případ i > j se dokáže zcela stejně. V tomto případě máme b_{ik} = a_{ik} + ca_{jk} pro každé k = 1, 2, …, n. Dále b_{lk} = a_{lk} pro každé l ≠ i a k ∈ {1, 2, …, n}. Permutace p ∈ S_{n} určuje v definici detB součin

b_{1p_{1}} ⋯ b_{ip_{i}} ⋯ b_{jp_{j}} ⋯ b_{np_{n}} = a_{1p_{1}} ⋯ (a_{ip_{i}} + ca_{jp_{i}}) ⋯ a_{jp_{j}} ⋯ a_{np_{n}} =
= a_{1p_{1}} ⋯ a_{ip_{i}} ⋯ a_{jp_{j}} ⋯ a_{np_{n}} + a_{1p_{1}} ⋯ (ca_{jp_{i}}) ⋯ a_{jp_{j}} ⋯ a_{np_{n}} =
= a_{1p_{1}} ⋯ a_{ip_{i}} ⋯ a_{jp_{j}} ⋯ a_{np_{n}} + c · a_{1p_{1}} ⋯ a_{jp_{i}} ⋯ a_{jp_{j}} ⋯ a_{np_{n}}.

První sčítanec v závěrečném součtu se rovná součinu určenému permutací p v detA, zatímco druhý sčítanec se rovná c-násobku součinu určeného permutací p v determinantu matice, jejíž i-tý řádek se rovná j-tému řádku. Taková matice má determinant rovný 0 podle Tvrzení 10.11. Proto

detB = ∑_{p∈S_{n}} sgn p · b_{1p_{1}} ⋯ b_{np_{n}} = ∑_{p∈S_{n}} sgn p · a_{1p_{1}} ⋯ a_{np_{n}} = detA.

□

Všimněte si, že v případě, kdy charakteristika tělesa T je různá od 2, plyne Tvrzení 10.11 z první části Věty 10.12. Jsou-li v matici A dva řádky – i-tý a j-tý – stejné, pak prohozením těchto dvou řádků dostaneme matici B = A. Podle první části Věty 10.12 platí detA = detB = − detA, tj. detA + detA = 0. Protože má těleso T charakteristiku různou od 2, plyne odtud detA = 0. Pouze v případě, kdy má těleso T charakteristiku rovnou 2, z rovnosti detA + detA = 0 nevyplývá detA = 0. V takovém případě je nutné použít Tvrzení 10.11.

Důsledek 10.13 Pro determinanty elementárních matic řádu n platí • detE_{ij} = −1,

• detE_{i}(c) = c,

• detE_{ij}(d) = 1.

Pro každou elementární matici E a libovolnou matici A téhož řádu n platí

detEB = detE · detB.

Důkaz. Každou elementární matici dostaneme z jednotkové matice I odpovídající elementární řádkovou úpravou. Protože detI = 1 neboť jednotková matice je horní trojúhelníková, plynou dodnoty determinantů všech elementárních matic z Věty 10.12.

Odtud rovněž plyne druhá část důsledku za využití Věty 10.12. □

Věta 10.14 Čtvercová matice A je regulární právě když detA ≠ 0.

Důkaz. Podle Důsledku 10.13 platí rovnost

det(EB) = detE · detB

pro každou elementární matici E a čtvercovou matici B stejného řádu n. Matici A převedeme Gaussovou eliminací pomocí elementárních řádkových úprav do matice D v řádkově odstupňovaném tvaru. To znamená, že existují elementární matice E_{1}, E_{2}, …, E_{k}, pro které platí D = E_{k} ⋯ E_{1}A. S využitím předchozí rovnosti dostáváme

detD = det(E_{k} ⋯ E_{1}A) = detE_{k} · det(E_{k−1} ⋯ E_{1}A) =
= detE_{k} · detE_{k−1} · det(E_{k−2} ⋯ E_{1}A) =
⋮
= detE_{k} · detE_{k−1} ⋯ detE_{1} · detA.

Determinanty elementárních matic jsou nenulové podle Důsledku 10.13, platí proto

detA ≠ 0 právě když detD ≠ 0.

Podle Věty 3.9 je matice A regulární právě když D neobsahuje žádný nulový řádek, což je právě když detD ≠ 0, neboť matice D je horní trojúhelníková matice, a to je podle právě dokázané ekvivalence právě když detA ≠ 0. □

Pomocí předchozí věty snadno dokážeme následující důležitou větu o součinu determinantů.

Věta 10.15 Pro každé dvě čtvercové matice A, B řádu n platí

det(AB) = detA · detB

Důkaz. Je-li matice A singulární, platí r(A) < n, a proto také podle Důsledku 6.20 r(AB) ≤ r(A) < n, součin AB je proto také singulární matice. Z rovnosti detA = 0 tak plyne det(AB) = 0 a dokazovaná rovnost det(AB) = detA · detB tak platí v případě, že A je singulární matice.

Pokud je A regulární matice, můžeme ji podle podle Tvrzení 3.12 vyjádřit jako součin elementárních matic A = E_{k} ⋯ E_{1}. Potom platí

det(AB) = det(E_{k} ⋯ E_{1}B) = detE_{k} ⋯ detE_{1} · detB =
= det(E_{k} ⋯ E_{1}) · detB = detA · detB.

□

Nyní se budeme věnovat základní metodě výpočtu determinantů – rozvoji determinantu podle řádku případně podle sloupce.

Definice 10.16 Je-li A = (a_{ij}) čtvercová matice řádu n, pak pro i, j ∈ {1, 2, …, n} označujeme M_{ij} čtvercovou matici řádu n − 1, kterou dostaneme z A vynecháním i-tého řádku a j-tého sloupce. Nazýváme ji minor matice A odpovídající místu (i, j). Číslo m_{ij} = (−1)^{i+j} detM_{ij} nazýváme kofaktor matice A určený místem (i, j). Matici M = (m_{ij}) nazýváme kofaktorová matice určená maticí A a transponovanou matici M^{T} nazýváme adjungovaná matice k matici A. Adjungovanou matici k matici A budeme označovat adjA.

Věta 10.17 Pro každou čtvercovou matici A = (a_{ij}) řádu n a každé i, j ∈ {1, 2, …, n} platí

• detA = a_{i1}m_{i1} + a_{i2}m_{i2} + ⋯ + a_{in}m_{in} = ∑_{k=1}^{n} a_{ik}m_{ik},

• detA = a_{1j}m_{1j} + a_{2j}m_{2j} + ⋯ + a_{nj}m_{nj} = ∑_{k=1}^{n} a_{kj}m_{kj}.

Důkaz. Dokážeme první z obou tvrzení o rozvoji determinantu podle itého řádku. Druhé tvrzení o rozvoji determinantu podle j-tého sloupce pak vyplyne z rozvoje podle j-tého řádku a z Tvrzení 10.10.

Začneme tím, že se podíváme na všechny součiny v součtu definujícím detA, které obsahují činitele a_{nn}. Tyto součiny jsou určené permutacemi p ∈ S_{n}, pro které platí p(n) = n. Každý takový součin má tvar

sgnp · a_{1p_{1}}a_{2p_{2}} ⋯ a_{n−1p_{n−1}}a_{nn}.

Součet všech těchto součinů se potom rovná

∑_{p(n)=n} sgnp·a_{1p_{1}}a_{2p_{2}} ⋯ a_{n−1p_{n−1}}a_{nn} = a_{nn}· ∑_{p(n)=n} sgnp·a_{1p_{1}}a_{2p_{2}} ⋯ a_{n−1p_{n−1}}.

Pokud každou permutaci p ∈ S_{n}, pro kterou platí p(n) = n, zúžíme na množinu {1, 2, …, n − 1}, dostaneme permutaci q ∈ S_{n−1}. Permutace q působí na množině, která má o jeden prvek méně, a sama má také o jeden cyklus méně, než permutace p. Proto sgnq = sgnp. Každou permutaci q ∈ S_{n−1} můžeme naopak jednoznačně rozšířit do permutace p ∈ S_{n} tak, že dodefinujeme p(n) = n. Každý člen sgnp · a_{1p_{1}}a_{2p_{2}} ⋯ a_{n−1p_{n−1}} v druhém součtu v poslední rovnosti se proto rovná sgnq · a_{1q_{1}}a_{2q_{2}} ⋯ a_{n−1q_{n−1}}, kde q je zúžení permutace p na množinu {1, 2, …, n − 1}. Druhá suma v poslední rovnosti se proto rovná

∑_{q∈S_{n−1}} sgnq · a_{1q_{1}}a_{2q_{2}} ⋯ a_{n−1q_{n−1}} = detM_{nn},

součet všech součinů v detA obsahujících prvek a_{nn} se tak rovná součinu a_{nn} · detM_{nn}.

Nyní se podíváme, jak vypadají všechny součiny v detA obsahující prvek a_{ij}. K tomu účelu postupně zaměníme i-tý řádek matice A s (i + 1)-ním řádkem, potom s (i+2)-hým řádkem, atd. až s n-tým řádkem. Dostaneme tak matici, jejíž n-tý řádek se rovná i-tému řádku matice A a pořadí ostatních řádků se nezměnilo. Speciálně, prvek na místě (n, j) nové matice se rovná a_{ij}.

Dále pokračujeme tak, že postupně prohazujeme j-tý sloupec s (j + 1)- ním sloupcem, pak s (j + 2)-hým sloupcem, a tak dále až nakonec s ntým sloupcem. Dostaneme tak nakonec matici B = (b_{ij}), pro kterou platí b_{nn} = a_{ij}, a dále minor N_{nn} matice B odpovídající místu (n, n) se rovná minoru M_{ij} matice A odpovídajícímu místu (i, j). Součet všech součinů v detB obsahujících prvek b_{nn} se podle předchozích dvou odstavců proto rovná b_{nn} · detN_{nn} = a_{ij} · detM_{ij}.

Matici B jsme dostali z matice A pomocí n − i + 1 elementárních řádkových úprav prvního druhu a dále pomocí n − j + 1 elementárních sloupcových úprav prvního druhu. Každá z těchto úprav mění znaménko detA podle Věty 10.12 a Tvrzení 10.10, platí proto

detB = (−1)^{2n−i−j−2} detA = (−1)^{i+j} detA.

Protože detA = (−1)^{i+j} detB, součet všech součinů v detA obsahujících prvek a_{ij} se proto rovná součtu všech součinů v detB obsahujících prvek b_{nn} = a_{ij} s koeficientem (−1)^{i+j} . Podle předchozího odstavce se tak součet všech součinů v detA obsahujících a_{ij} rovná

(−1)^{i+j} b_{nn} · detN_{nn} = a_{ij} · (−1)^{i+j} detM_{ij} = a_{ij}m_{ij},

kde m_{ij} je podle Definice 10.10 kofaktor matice A určený místem (i, j).

Protože v každém součinu v součtu definujícím detA se vyskytuje právě jeden prvek z i-tého řádku matice A, platí

detA = a_{i1}m_{i1}+a_{i2}m_{i2}+⋯+a_{in}m_{in} = ∑_{k=1}^{n} a_{ik}m_{ik} = ∑_{k=1}^{n}(−1)^{i+k} a_{ik} detM_{ik}.

□

Úloha 10.3 Spočítejte determinant Vandermondovy matice a rozhodněte, kdy je Vandermondova matice regulární.

Řešení. Označíme

V_{t_{0},t_{1},...,t_{n}} = | \begin{matrix}1 & t_{0} & t_{0}^{2} & ⋯ & t_{0}^{n} \\ 1 & t_{1} & t_{1}^{2} & ⋯ & t_{1}^{n} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 1 & t_{n} & t_{n}^{2} & ⋯ & t_{n}^{n} \end{matrix} |

determinant Vandermondovy matice řádu n určené prvky t_{0}, t_{1}, …, t_{n} ∈ T. Pokud se dva z prvků t_{0}, t_{1}, …, t_{n} rovnají, má Vandermondova matice dva stejné řádky a její determinant se proto rovná 0 podle Tvrzení 10.11. Budeme proto nadále předpokládat, že všechny prvky t_{0}, t_{1}, …, t_{n} jsou navzájem různé.

Napřed odečteme první řádek od všech ostatních. Determinant se podle Věty 10.12 nezmění, dostaneme tak

V_{t_{0},t_{1},...,t_{n}} = | \begin{matrix}1 & t_{0} & t_{0}^{2} & ⋯ & t_{0}^{n} \\ 0 & t_{1} − t_{0} & t_{1}^{2} − t_{0}^{2} & ⋯ & t_{1}^{n} − t_{0}^{n} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & t_{n} − t_{0} & t_{n}^{2} − t_{0}^{2} & ⋯ & t_{n}^{n} − t_{0}^{n} \end{matrix} | .

Nyní determinant rozvineme podle prvního sloupce a dostaneme vyjádření

V_{t_{0},t_{1},...,t_{n}} = | \begin{matrix}t_{1} − t_{0} & t_{1}^{2} − t_{0}^{2} & ⋯ & t_{1}^{n} − t_{0}^{n} \\ t_{2} − t_{0} & t_{2}^{2} − t_{0}^{2} & ⋯ & t_{2}^{n} − t_{0}^{n} \\ ⋮ & ⋮ & ... & ⋮ \\ t_{n} − t_{0} & t_{n}^{2} − t_{0}^{2} & ⋯ & t_{n}^{n} − t_{0}^{n} \end{matrix} | .

Dále použijeme známý algebraický rozklad

t_{i}^{j} − t_{0}^{j} = (t_{i} − t_{0})(t_{i}^{j−1} + t_{i}^{j−2}t_{0} + ⋯ t_{i}t_{0}^{j−2} + t_{0}^{j−1}) = (t_{i} − t_{0})c_{ij},

kde jsme pro jednoduchost označili

c_{ij} = t_{i}^{j−1} + t_{i}^{j−2}t_{0} + ⋯ t_{i}t_{0}^{j−2} + t_{0}^{j−1} = ∑_{k=0}^{j−1} t_{i}^{k}t_{0}^{j−1−k}.

Speciálně platí c_{i1} = 1 pro libovolné i = 1, …, n. S použitím tohoto označení dostáváme

V_{t_{0},t_{1},...,t_{n}} = | \begin{matrix}(t_{1} − t_{0})c_{11} & (t_{1} − t_{0})c_{12} & ⋯ & (t_{1} − t_{0})c_{1n} \\ (t_{2} − t_{0})c_{21} & (t_{2} − t_{0})c_{22} & ⋯ & (t_{2} − t_{0})c_{2n} \\ ⋮ & ⋮ & ... & ⋮ \\ (t_{n} − t_{0})c_{n1} & (t_{n} − t_{0})c_{n2} & ⋯ & (t_{n} − t_{0})c_{nn} \end{matrix} | .

Z i-tého řádku můžeme vytknout t_{i} − t_{0} pro každé i = 1, …, n a dosadit c_{i1} = 1, proto

V_{t_{0},t_{1},...,t_{n}} = ∏_{i=1}^{n}(t_{i} − t_{0}) | \begin{matrix}1 & c_{12} & ⋯ & c_{1n} \\ 1 & c_{22} & ⋯ & c_{2n} \\ ⋮ & ⋮ & ... & ⋮ \\ 1 & c_{n2} & ⋯ & c_{nn} \end{matrix} | .

Nyní c_{i2} = t_{i} + t_{0} pro každé i = 1, …, n. Pokud tedy odečteme od druhého sloupce t_{0}-násobek prvního sloupce, dostaneme

V_{t_{0},t_{1},...,t_{n}} = ∏_{i=1}^{n}(t_{i} − t_{0}) | \begin{matrix}1 & t_{1} & c_{13} & ⋯ & c_{1n} \\ 1 & t_{2} & c_{23} & ⋯ & c_{2n} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 1 & t_{n} & c_{n3} & ⋯ & c_{nn} \end{matrix} | .

Podobně c_{i3} = t_{i}^{2} −t_{i}t_{0}+t_{0}^{2} pro každé i = 1, …, n. Odečteme tedy od třetího sloupce t_{0}^{2}-násobek prvního sloupce a t_{0}-násobek druhého sloupce. Potom

V_{t_{0},t_{1},...,t_{n}} = ∏_{i=1}^{n}(t_{i} − t_{0}) | \begin{matrix}1 & t_{1} & t_{1}^{2} & c_{14} & ⋯ & c_{1n} \\ 1 & t_{2} & t_{2}^{2} & c_{24} & ⋯ & c_{2n} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 1 & t_{n} & t_{n}^{2} & c_{n4} & ⋯ & c_{nn} \end{matrix} | .

Postupně tak dostaneme

V_{t_{0},t_{1},...,t_{n}} = ∏_{i=1}^{n}(t_{i} − t_{0}) · V_{t_{1},...,t_{n}}

Poslední výraz je rekurentní formule, pomocí které již vypočítáme hodnotu V_{t_{0},t_{1},...,t_{n}} Vandermonodova determinantu řádu n + 1. Začneme hodnotami pro malá n.

V_{t_{0}} = 1, V_{t_{0},t_{1}} = t_{1} − t_{0}, V_{t_{0},t_{1},t_{2}} = (t_{2} − t_{0})(t_{2} − t_{1})(t_{1} − t_{0}).

Pokud induktivně předpokládáme, že

V_{t_{0},t_{1},...,t_{n−1}} = ∏_{{i>j \atop i,j=0,...,n−1}} (t_{i} − t_{j}),

potom pomocí již dokázané rekurentní formule dostaneme

V_{t_{0},t_{1},...,t_{n}} = (∏_{i=1}^{n}(t_{i} − t_{0}))V_{t_{1},...,t_{n}} = ∏_{i=1}^{n}(t_{i} − t_{0}) ∏_{{i>j \atop i,j=1,...,n}} (t_{i} − t_{j}) =

= ∏_{{i>j \atop i,j=0,...,n}} (t_{i} − t_{j}).

Tím je hodnota Vandermondova determinantu dokázána pomocí matematické indukce. Všimněte si, že rovnost

V_{t_{0},t_{1},...,t_{n}} = ∏_{{i>j \atop i,j=0,...,n}} (t_{i} − t_{j})

platí i v případě, kdy se dva z prvků t_{0}, t_{1}, …, t_{n} ∈ T rovnají. Vandermondova matice je tak regulární právě když jsou prvky t_{0}, t_{1}, …, t_{n} ∈ T navzájem různé. □

Tvrzení 10.18 Je-li A regulární matice, pak

A^{−1} = \frac{1}{detA} · adjA.

Důkaz. Adjungovaná matice adjA = (n_{ij}), kde n_{ij} = m_{ji}, minor matice A určený místem (j, i). V součinu A·adjA se prvek na místě (i, i) na hlavní diagonále rovná součtu

∑_{k=1}^{n} a_{ik}n_{ki} = ∑_{k=1}^{n} a_{ik}m_{ik} = detA

podle Věty 10.17. Prvek na místě (i, j) mimo hlavní diagonálu v součinu A · adjA, tj. pro i ≠ j, se rovná

∑_{k=1}^{n} a_{ik}n_{kj} = ∑_{k=1}^{n} a_{ik}m_{jk}.

Poslední součet se rovná rozvoji determinantu podle i-tého řádku v matici, kterou dostaneme z matice A nahrazením j-tého řádku A_{j∗} řádkem A_{i∗}. Minory m_{jk} pro k = 1, …, n se tak nezmění a nová matice má dva stejné řádky. Její determinant se proto rovná 0 podle Tvrzení 10.11. Proto platí rovněž

∑_{k=1}^{n} a_{ik}m_{jk} = 0.

Součin A · adjA má proto nenulové prvky pouze na hlavní diagonále, a ty se všechny rovnají detA. Platí tak A · adjA = detA · I_{n}, neboli

A^{−1} = \frac{1}{detA} · adjA.

□

A nakonec vzoreček pro řešení soustavy lineárních rovnic s regulární maticí. Tomuto vzorečku se říká Cramerovo pravidlo.

Tvrzení 10.19 Je-li Ax = b soustava n lineárních rovnic o n neznámých s regulární maticí A, pak pro j = 1, 2, …, n platí

x_{j} = \frac{detA_{j}}{detA} ,

kde A_{i} = [A_{∗1}| ⋯ |A_{∗j−1}|b|A_{∗j+1} | ⋯ |A_{∗n}] je matice, kterou dostaneme z matice A nahrazením i-tého sloupce sloupcem pravých stran b.

Důkaz. Soustava má jediné řešení x = A^{−1}b. Dosadíme za inverzní matici A^{−1} její vyjádření podle předchozí Věty 10.18

A^{−1} = \frac{1}{detA} · adjA.

Dostaneme tak rovnost

x = \frac{1}{detA} · adjA · b.

KAPITOLA 10. DETERMINANTY 18 Pro j-tou souřadnici řešení x = (x_{1}, …, x_{n})^{T} pak platí

x_{j} = \frac{1}{detA} · [adjA]_{j∗}b = \frac{1}{detA} · ∑_{k=1}^{n} m_{kj}b_{k},

kde b_{k} je k-tá souřadnice vektoru b pravých stran. Součet

∑_{k=1}^{n} b_{k}m_{kj}

je rozvojem podle j-tého sloupce determinantu matice A_{j}, kterou dostaneme z matice A nahrazením sloupce A_{∗j} vektorem pravých stran b. □