Skripta

jednak k ≤n, odkud již plyne, že k = n.
2: Nechť vektory v1,...,vs generují prostor V. Podle předpokladu má prostor V bázi,
tzn. musí být V negationslash= {o}. Pak lze vektory v1,...,vs přečíslovat tak, že v1,...,vi jsou
lineárně nezávislé a v1,...,vi,vj jsou lineárně závislé pro každé j s vlastností i rj (tj. jestliže větší z obou čísel předchází v daném pořadí číslu
menšímu).
Pořadí, v němž celkový počet inverzí je sudé číslo (resp. liché číslo), se nazývá sudé
pořadí (resp. liché pořadí). Hovoříme pak též o paritě pořadí.
Příklad 1.1.
Nechť n = 8. Potom:
1. pořadí (1,2,3,4,5,6,7,8) je sudé (celkový počet inverzí je 0),
2. pořadí (3,1,2,7,5,8,6,4) je liché (celkový počet inverzí je 9).
Celkový počet inverzí v daném konkrétním pořadí zřejmě nejrychleji zjistíme tak, že
bereme odleva jedno číslo po druhém a pro každé z nich spočítáme, kolik menších čísel stojí
za ním (napravo). Sečtením těchto hodnot pak dostaneme celkový počet inverzí v daném
pořadí.
Definice.
Nechť R = (r1,...,rn), S = (s1,...,sn) jsou dvě pořadí. Nechť existují indexy inegationslash= j tak,
že si = rj, sj = ri a dále rk = sk pro k negationslash= i,j. Potom řekneme, že pořadí S vzniklo
z pořadí R provedením jedné transpozice.
Poznámka.
Jinými slovy řečeno, provedení jedné transpozice znamená vzájemnou záměnu dvou růz-
ných prvků v daném pořadí, přičemž všechny ostatní prvky zůstávají na původním místě.
Věta 1.1.
Nechť n je pevné přirozené číslo. Pak platí:
1. z n prvků lze utvořit celkem n! různých pořadí,
2. všech n! pořadí z n prvků lze seřadit tak, že každé následující pořadí obdržíme z před-
cházejícího provedením jedné transpozice. Přitom lze vyjít z libovolného pořadí.
24
Důkaz.
Nejprve připomeňme, že symbol n! (čti „n faktoriálcsquotedblright) značí přirozené číslo definované:
n! = n·(n−1)· ··· ·2·1. Dokazovat budeme obě části věty najednou, a to matematickou
indukcí vzhledem k n.
α) Pro n = 1 obě tvrzení triviálně platí.
β) Předpokládejme, že obě tvrzení platí pro 1,...,n− 1, a budeme je dokazovat pro n.
Nechť (r1,...,rn) je libovolné pořadí z n prvků. Podle indukčního předpokladu je všech
pořadí, která mají na posledním místě prvek rn, celkem (n− 1)! a lze je seřadit tak, že
následující vznikne z předchozího provedením jedné transpozice. V posledním z těchto
pořadí proveďme transpozici prvků rn a ri (1 ≤ i ≤ n− 1) a stejnou úvahou jako výše
dostaneme (n−1)! pořadí s prvkemri na posledním místě. Takto vystřídáme na posledním
místě všech n prvků, čímž dostaneme všechna různá pořadí z n prvků, kterých je tedy
n·(n−1)! = n!, přičemž následující pořadí vzniklo vždy z předchozího provedením jedné
transpozice. squaresolid
Věta 1.2.
Provedení jedné transpozice změní paritu daného pořadí.
Důkaz.
Důkaz provedeme ve dvou krocích. Nejprve pro transpozici dvou sousedních prvků a
potom pro transpozici libovolných dvou různých prvků daného pořadí.
α) Nechť v pořadí R = (r1,...,ri,ri+1,...,rn) je t inverzí. Provedením transpozice
sousedních prvků ri a ri+1 dostaneme pořadí R′ = (r1,...,ri+1,ri,...,rn), v němž je buď
t−1, nebo t+ 1 inverzí (proč?). Tedy R′ má opačnou paritu než R.
β) Nechť R = (r1,...,ri,...,rj,...,rn) je dané pořadí. Provedením transpozice prvků
ri a rj dostaneme pořadí R′ = (r1,...,rj,...,ri,...,rn). Tuto transpozici však lze reali-
zovat postupným provedením (j −i) + (j −i− 1) = 2(j −i) − 1 transpozic sousedních
prvků. Ale číslo 2(j−i)−1 je liché, tzn. užitím α) dostáváme tvrzení. squaresolid
Věta 1.3.
Nechť n ≥ 2. Pak z celkového počtu n! různých pořadí z n prvků je n!2 pořadí sudých
a n!2 pořadí lichých.
Důkaz.
Tvrzení věty plyne ihned v vět 1.1. a 1.2. squaresolid
Definice.
Nechť M = {1,2,...,n} je konečná množina o n prvcích. Pak bijektivní zobrazení P
množiny M na sebe se nazývá permutace množiny M nebo krátce permutace.
Permutaci P, definovanou předpisem: P(it) = jt, pro t = 1,...,n, budeme zapisovat ve
tvaru dvouřádkové tabulky: parenleftbigg
i1 i2 ··· in
j1 j2 ··· jn
parenrightbigg
.
Poznámka.
Permutace množiny M je tedy bijekce M →M, kterou zapisujeme ve tvaru dvouřádkové
tabulky. Znamená to, že v horním i dolním řádku této tabulky musí být vždy nějaké
25
pořadí z n prvků. Zřejmě lze tutéž permutaci P zapsat v uvedeném tvaru celkem n! for-
málně různými způsoby (zaměníme-li pořadí sloupců v tabulce permutace). Všech těchto
n! zápisů permutace P je samozřejmě naprosto rovnocenných, i když nejčastěji budeme
permutaci zapisovat v tzv. základním tvaru:
parenleftbigg1 2 ··· n
k1 k2 ··· kn
parenrightbigg
. (1)
Příklad 1.2.
Pro n = 5 jsou:
parenleftbigg1 2 3 4 5
2 3 5 4 1
parenrightbigg
, resp.
parenleftbigg3 2 1 4 5
5 3 2 4 1
parenrightbigg
, resp.
parenleftbigg4 1 5 2 3
4 2 1 3 5
parenrightbigg
tři formálně různé zápisy téže permutace (z celkového počtu 5! = 120 možných zápisů
této jedné permutace).
Věta 1.4.
Počet různých permutací n-prvkové množiny je roven číslu n!.
Důkaz.
Zapíšeme-li každou permutaci v základním tvaru (1), pak různých permutací bude přesně
tolik, kolik bude různých pořadí v dolním řádku. Těch je však n!, podle věty 1.1.1. squaresolid
Definice.
PermutaceP se nazývá sudá permutace, resp. lichá permutace, jestliže součet počtu inverzí
v horním a dolním řádku tabulky permutace P je sudé číslo, resp. liché číslo. Hovoříme
pak též o paritě permutace.
Poznámka.
I když danou permutaci P můžeme zapsat n! formálně různými tabulkami, je předchozí
definice korektní, neboť při libovolném zápisu permutace P je parita horního a dolního
řádku (chápaných jako pořadí) buď vždy stejná, nebo vždy rozdílná. Tento fakt plyne
z toho, že při přechodu od jednoho zápisu permutace P k jinému provádíme totiž jistý
počet transpozic, a to současně v horním i dolním řádku.
Věta 1.5.
Nechť n ≥ 2. Pak z celkového počtu n! různých permutací n-prvkové množiny je n!2
permutací sudých a n!2 permutací lichých.
Důkaz.
Každou permutaci zapíšeme v základním tvaru:
parenleftbigg1 2 ··· n
k1 k2 ··· kn
parenrightbigg
.
Parita permutace je pak shodná s paritou pořadí v dolním řádku a věta plyne bezpro-
středně z věty 1.3. squaresolid
26
§2. Determinanty
Jedním ze základních pojmů celé moderní matematiky je pojem matice. Teorie matic
hraje ústřední úlohu v tzv. lineární algebře. Její výsledky se pak aplikují při řešení soustav
lineárních rovnic, při studiu vektorových prostorů a v celé řadě dalších odvětví nejenom
matematiky.
Definice.
Nechť T je číselné těleso, m, n jsou přirozená čísla. Pak obdélníkové schéma tvaru:
A =



a11 a12 ··· a1n
a21 a22 ··· a2n
... ... ... ...
am1 am2 ··· amn


, (1)
kde aij ∈T pro i = 1,...,m a j = 1,...,n, se nazývá matice typu m/n (nad tělesem T).
Označení: A = (aij) typu m/n. Čísla aij ∈T se nazývají prvky matice A.
Matice A = (aij) typu m/n a matice B = (bij) typu p/q jsou si rovny, jestliže jsou
stejného typu (tj. m = p ∧ n = q) a je-li aij = bij pro každé i,j.
Poznámka.
1. Předchozí definice matice je sice názorná, ale přísně vzato není zcela korektní, neboť
se v ní používá formálně nejasného a nepřesného pojmu „obdélníkové schémacsquotedblright (a je pak
nutné v ní hovořit o rovnosti dvou matic). Zcela přesně by bylo možné matici typu m/n
nad tělesem T definovat jakožto zobrazení:
f : {1,2,...,m}×{1,2,...,n}→T,
kde fparenleftbig(i,j)parenrightbig = aij. Při této definici by však většina tvrzení o maticích byla formálně
značně komplikovaná a nepřehledná. Ponecháme tedy definici matice tak, jak byla pů-
vodně uvedena (tj. vypisujeme vlastně funkční hodnoty uvedeného zobrazení f do onoho
„obdélníkového schématucsquotedblright).
2. Každý jednotlivý řádek matice A typu m/n nad tělesem T můžeme zřejmě uvažovat
jako uspořádanou n-tici čísel z tělesa T, tzn. jinak řečeno, jako vektor z vektorového
prostoru Tn. Má smysl pak hovořit o sčítání řádků matice, násobení řádku číslem z T,
lineární kombinaci řádků, lineární závislosti a nezávislosti řádků, atd., a to ve smyslu
uvedených operací, resp. pojmů tak, jak byly definovány ve vektorovém prostoru Tn.
Matici A lze pak též chápat jako uspořádanou m-tici vektorů z Tn.
Analogicky můžeme sloupce matice A chápat jako vektory z vektorového prostoru Tm
a provádět s nimi tytéž úvahy.
Definice.
Nechť A = (aij) je matice typu m/n nad T. Potom:
1. je-li aij = 0 pro každé i,j (tj. všechny prvky matice jsou rovny nule), matice se
nazývá nulová matice (typu m/n) a označuje se symbolem 0mn
2. je-li m = n (tj. počet řádků je roven počtu sloupců), matice A se nazývá čtvercová
matice řádu n
27
3. matice A′ typu n/m, která vznikne z matice A záměnou řádků za sloupce, tj.:
A′ =



a11 a21 ··· am1
a12 a22 ··· am2
... ... ... ...
a1n a2n ··· amn



se nazývá transponovaná matice k matici A.
Ve zbývající části tohoto paragrafu se budeme zabývat pouze čtvercovými maticemi
řádu n nad pevným číselným tělesem T. Pro tyto matice nejprve zavedeme následující
pojem.
Definice.
Nechť A = (aij) je čtvercová matice řádu n nad tělesem T. Pak determinant matice A je
číslo z tělesa T označené detA (nebo též |A|) a definované vztahem:
detA = summationtext
(j1,...,jn)
(−1)I(j1,...,jn) ·a1j1 ·a2j2 · ··· ·anjn,
kde I(j1,...,jn) značí celkový počet inverzí v permutaci:
parenleftbigg1 2 ··· n
j1 j2 ··· jn
parenrightbigg
použitých řádkových a sloupcových indexů. Sčítání se provádí přes všechna různá pořadí
(j1,...,jn) sloupcových indexů.
Výraz
(−1)I(j1,...,jn) ·a1j1 ·a2j2 · ··· ·anjn
se nazývá člen determinantu.
Poznámka.
Rozebereme-li si předchozí definici podrobněji, pak vidíme, že determinant detA je číslo
z T, které dostaneme sečtením celkem n! členů determinantu (viz věta 1.1.1.). Přitom
každý jednotlivý člen determinantu je součinem n prvků matice A vybraných tak, že
z každého řádku a každého sloupce je vybrán právě jeden prvek a tento součin je „opatřen
znaménkem + nebo −csquotedblright podle toho, zda permutace utvořená z řádkových a sloupcových
indexů vybraných n prvků je sudá nebo lichá.
Dále je třeba si uvědomit zásadní rozdíl mezi pojmem matice (tj. jakýmsi obdélníkovým,
resp. čtvercovým schématem) a pojmem determinantu matice (tj. pevným číslem z T).
Příklad 2.1.
Rozepišme si předchozí definici determinantu pro nejjednodušší případy, tj. n = 1,2,3.
n = 1: vextendsinglevextendsinglea11vextendsinglevextendsingle = a11 n = 2:
vextendsinglevextendsingle
vextendsinglevextendsinglea11 a12a
21 a22
vextendsinglevextendsingle
vextendsinglevextendsingle = a11 ·a22 −a12 ·a21
n = 3 :
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
a11 a12 a13
a21 a22 a23
a31 a32 a33
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle = a11 ·a22 ·a33 +a12 ·a23 ·a31 +a13 ·a21 ·a32 −−a
13 ·a22 ·a31 −a12 ·a21 ·a33 −a11 ·a23 ·a32 .
28
Je vidět, že výpočet determinantu matice pouze na základě definice by byl neúnosně
zdlouhavý a pracný, zejména pro větší n. Např. pro n = 10 by bylo nutno spočítat přes tři
a půl milionu desetičlenných součinů (neboť 10! = 3628800). Z tohoto důvodu uvedeme
nyní několik vět popisujících základní vlastnosti determinantů, které mnohdy výpočet
determinantu podstatně zjednoduší.
Všude v dalším v tomto paragrafu budeme symbolem A označovat čtvercovou matici
A = (aij) řádu n nad tělesem T.
Věta 2.1.
Transponováním matice A se hodnota determinantu nezmění, tj. detA′ = detA.
Důkaz.
Nechť (j1,j2,...,jn) je libovolné pořadí z n prvků. Pak součin a1j1 ·a2j2 · ··· ·anjn se
vyskytuje právě jednou v detA i detA′. Tento součin je v detA vynásoben číslem (−1)r,
resp. v detA′ číslem (−1)s, kde r, resp. s značí celkový počet inverzí v permutaci:
parenleftbigg1 2 ··· n
j1 j2 ··· jn
parenrightbigg
, resp.
parenleftbiggj
1 j2 ··· jn
1 2 ··· n
parenrightbigg
.
Zřejmě však r = s, odkud již plyne tvrzení. squaresolid
Věta 2.2.
Nechť prvky k-tého řádku matice A mají tvar:
ak1 = bk1 +ck1, ak2 = bk2 +ck2, ... akn = bkn +ckn
a nechť matice B, resp. C se liší od matice A pouze v prvcích k-tého řádku, přičemž
bk1,...,bkn je k-tý řádek matice B, resp. ck1,...,ckn je k-tý řádek matice C. Potom platí:
detA = detB + detC.
Schématicky zapsáno tedy platí:
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsingle
a11 ··· a1n
... ... ...
bk1 +ck1 ··· bkn +ckn
... ... ...
an1 ··· ann
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsingle
=
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsingle
a11 ··· a1n
... ... ...
bk1 ··· bkn
... ... ...
an1 ··· ann
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsingle
+
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsingle
a11 ··· a1n
... ... ...
ck1 ··· ckn
... ... ...
an1 ··· ann
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsinglevextendsingle
vextendsingle
.
Důkaz.
Tvrzení plyne přímo z definice determinantu, neboť pro každý člen determinantu detA
platí:
(−1)I(j1,...,jn) ·a1j1 · ··· ·(bkjk +ckjk)· ··· ·anjn =
= (−1)I(j1,...,jn) ·a1j1 · ··· ·bkjk · ··· ·anjn + (−1)I(j1,...,jn) ·a1j1 · ··· ·ckjk · ··· ·anjn .
squaresolid
Poznámka.
Předchozí větu lze zřejmě rozšířit pro libovolný konečný počet sčítanců v k-tém řádku
matice A (dokáže se pomocí matematické indukce).
29
Věta 2.3.
Nechť matice B vznikne z matice A:
1. záměnou dvou různých řádků. Potom je detB = −detA.
2. vynásobením jednoho řádku pevným číslem t∈T. Potom je detB = t·detA.
Důkaz.
1: Zaměňme v matici A k-tý řádek s r-tým řádkem, kde k negationslash= r. Pak součiny vyskytující
se v detA a detB zůstanou stejné, ale mají vždy opačná znaménka, protože permutace:
parenleftbigg1 ··· k ··· r ··· n
j1 ··· jk ··· jr ··· jn
parenrightbigg
a
parenleftbigg1 ··· k ··· r ··· n
j1 ··· jr ··· jk ··· jn
parenrightbigg
mají (podle věty 1.2.) různou paritu. Potom však detB = −detA.
2: Plyne přímo z definice determinantu, neboť vynásobíme-li v matici A např. k-tý řádek
prvkem t∈T, potom:
detB = summationtext
(j1,...,jn)
(−1)I(j1,...,jn) ·a1j1 · ··· ·t·akjk · ··· ·anjn =
= t· summationtext
(j1,...,jn)
(−1)I(j1,...,jn) ·a1j1 · ··· ·akjk · ··· ·anjn = t·detA.
squaresolid
Věta 2.4.
Nechť v matici A:
1. jeden řádek sestává ze samých nul. Potom je detA = 0.
2. dva různé řádky jsou shodné. Potom je detA = 0.
3. jeden řádek je násobkem jiného řádku. Potom je detA = 0.
4. jeden řádek je lineární kombinací ostatních řádků. Potom je detA = 0.
Důkaz.
1: Plyne přímo z definice determinantu. Každý člen detA je totiž roven nule, poněvadž
obsahuje nulu (a sice z toho řádku, který sestává ze samých nul).
2: Zaměníme-li ty dva řádky maticeA, které jsou shodné, pak maticeAse zřejmě nezmění.
Podle věty 2.3.1. však musí být detA = −detA, tj. 2·detA = 0, odkud však dostáváme,
že detA = 0.
3: Plyne přímo z věty 2.3.2. a z právě dokázané části 2.
4: Nechť např. k-tý řádek matice A je lineární kombinací ostatních řádků. Pak detA lze
podle poznámky za větou 2.2. vyjádřit jako součet (n− 1) determinantů, z nichž však
v každém je k-tý řádek násobkem nějakého jiného řádku. Podle části 3 této věty je však
každý z těchto (n−1) determinantů roven nule, a tedy detA = 0 + 0 +···+ 0 = 0. squaresolid
Věta 2.5.
Hodnota determinantu matice A se nezmění, jestliže:
1. k jednomu řádku matice A přičteme libovolný násobek jiného řádku
2. k jednomu řádku matice A přičteme libovolnou lineární kombinaci ostatních řádků
30
Důkaz.
1: Plyne bezprostředně z vět 2.2. a 2.4.3..
2: Plyne z poznámky za větou 2.2. a z věty 2.4.4.. squaresolid
Poznámka.
Z věty 2.1. plyne, že ke každé z následujících vět, tj. 2.2., 2.3. a 2.4. platí analogická věta,
kterou získáme tak, že v původní formulaci slovo „řádekcsquotedblright nahradíme slovem „sloupeccsquotedblright.
Například tedy platí tvrzení: „jestliže v matici A je jeden sloupec lineární kombinací
ostatních sloupců, potom je detA = 0csquotedblright, atd.
Tuto úvahu lze zřejmě uplatnit na každé tvrzení o determinantech matice, týkající
se řádků matice. Dostaneme tak stejné tvrzení, týkající se sloupců. Analogicky naopak
(tzn. z každého platného tvrzení o determinantech, týkajícího se sloupců dané matice,
dostaneme záměnou slova „sloupeccsquotedblright za slovo „řádekcsquotedblright platné tvrzení, týkající se řádků).
Větu 2.5. (a odpovídající větu pro sloupce) často využíváme při konkrétních výpočtech
determinantů, kdy se přičítáním vhodných násobků jedněch řádků (resp. sloupců) k jiným
řádkům (resp. sloupcům) snažíme matici upravit na takový tvar, z něhož již determinant
lehce spočítáme. Například, dojdeme-li k matici A tvaru:
A =




a11 a12 ··· a1,(n−1) a1n
0 a22 ··· a2,(n−1) a2n
... ... ... ... ...
0 0 ··· a(n−1),(n−1) a(n−1),n
0 0 ··· 0 ann




(tj. všude pod hlavní diagonálou jsou nuly), pak detA = a11 ·a22 · ··· ·ann, jak plyne
ihned z definice determinantu. Stejný výsledek (tzn. hodnota determinantu je rovna sou-
činu prvků v hlavní diagonále) dostaneme, jestliže v matici jsou samé nuly nad hlavní
diagonálou.
Ve zbývající části tohoto paragrafu pak odvodíme ještě jeden způsob jak zjednodušit
výpočet determinantu.
Definice.
Nechť A = (aij) je čtvercová matice řádu n. Nechť je zvoleno k jejích řádků a sloupců
(k