Pokroˇ cil´ a line´ arn´ı algebra 1
1. s´ erie
Matice pro v´ ypoˇ cet line´ arn´ıch rekurenc´ı (20 bod˚ u)
Na u ´vod si ve struˇcnosti popiˇsme, jak poˇc´ıtat Fibonacciho ˇc´ısla pomoc´ı umocˇ nov´an´ı matic; ve vˇetˇs´ıch podrobnostech pops´ ano na konci kapitoly 3.1 textu Pov´ıd´ an´ı o Line´ arn´ı algebˇre. Necht’ fn je n-t´e Fibonacciho ˇc´ıslo, definov´ano takto: f0 = 0,
f1 = 1,
fn+2 = fn+1 + fn .
Uvaˇzme matici A a vyn´ asobme j´ı zprava vektorem obsahuj´ıc´ı dvˇe po sobˇe jdouc´ı Fibonacciho ˇc´ısla: f fk + fk+1 1 1 fk+2 1 1 · k+1 = , = A= , fk 1 0 fk+1 1 0 fk+1 tedy n´asoben´ım A se posouv´ ame v posloupnosti Fibonacciho ˇc´ısel o jedna doprava. Proto plat´ı, ˇze f1 f1 fn+1 n · = A · = A · A · · · A , | {z } f0 f0 fn n-kr´ at
kde prvn´ı rovnost plat´ı d´ıky asociativitˇe. Nav´ıc An um´ıme spoˇc´ıtat v ˇcase O(log n).1 Zkus´ıme v´ yˇse uveden´ y postup zobecnit. M´ ame nˇejakou obecnou zadanou line´ arn´ı rekurentn´ı posloupnost. Nˇekolik prvn´ıch ˇclen˚ u x0 aˇz xk−1 je pevnˇe urˇceno. Kaˇzd´ y dalˇs´ı ˇclen je line´ arn´ı kombinace k pˇredch´azej´ıc´ıch ˇclen˚ u, tedy plat´ı xn+k = αk−1 xn+k−1 + αk−2 xn+k−2 + · · · + α1 xn+1 + α0 xn pro pevn´ a ˇc´ısla α0 aˇz αk−1 .
Pˇr´ıklad. Posloupnost m˚ uˇze m´ıt tˇreba urˇcen´e prvn´ı tˇri ˇcleny x0 = 1, x1 = 2, x2 = 3 a dalˇs´ı ˇcleny jsou urˇceny pˇredpisem xn+3 = xn+2 − xn+1 + 3xn . Zaˇc´atek posloupnosti vypad´ a takto: (1, 2, 3, 4, 7, 12, 17, 26, 45, . . .). ´ Uloha 1.1. Zobecnˇete postup v´ ypoˇctu pro obecnou line´ arn´ı rekurenci. Pro zadan´e k a koeficienty α0 , . . . , αk−1 popiˇste, jak se matice A zkonstruuje. Pochopitelnˇe tak´e dok´aˇzte, ˇze m´ a poˇzadov´an´e vlastnosti. T´ım pochop´ıte, jak jsme matici A pro Fibonacciho ˇc´ısla z´ıskali. N´ apovˇeda. Zkuste nejprve uvaˇzovat posloupnosti pro k = 2, tedy posloupnosti, kter´e z´avis´ı pouze na dvou pˇredch´azej´ıc´ıch ˇclenech. Pozn´ amka. Matice A je zaj´ımav´a, i kdyˇz nechceme zkonstruovat rychl´ y algoritmus. V l´etˇe si uk´aˇzeme, jak z n´ı lze vydolovat vzorec pro n-t´ y ˇclen line´ arn´ı rekurence. K tomu se budou hodit vlastn´ı ˇc´ısla matice A. Ta n´am umoˇzn´ı pˇrev´est matici do Jordanova tvaru, ve kter´em bude vzorec pˇr´ımo vidˇet.
2
Permutaˇ cn´ı matice (25 bod˚ u)
Permutace jiˇz zn´ ame z diskr´etn´ı matematiky. Permutace π je bijektivn´ı zobrazen´ı π : X → X, tedy r˚ uzn´ ym prvk˚ um z X pˇriˇrazujeme r˚ uzn´e prvky. Intuitivnˇe je permutace pouze nˇejak´e pˇreuspoˇr´ad´ an´ı prvk˚ u v X. N´ as budou zaj´ımat permutace mnoˇziny X = {1, 2, . . . , n}. Pro permutaci π je permutaˇcn´ı matice Pπ ˇctvercov´a matice n × n dan´ a pˇredpisem: ( 1 pro π(i) = j, (Pπ )ij = 0 jinak. 1
n 2 ate, zkuste si rozmyslet detaily. Vyuˇzijeme p˚ ulen´ı, nebot’ an = a 2 . Pokud tento algoritmus nezn´
1
Tedy je to nula-jedniˇckov´a matice, kter´a m´ a v kaˇzd´em ˇr´adku pˇresnˇe jednu jedniˇcku na pozici (i, π(i)). Pˇr´ıklad. Uk´aˇzeme si dva pˇr´ıklady. Pro n = 5 mˇejme permutace π pˇredpisem (v druh´em ˇr´ adku je zaps´ano, kam se ˇc´ısla zobrazuj´ı): 1 2 3 4 5 1 2 3 4 π= a σ= 2 3 1 5 4 3 1 2 5
a σ dan´e n´asleduj´ıc´ım 5 . 4
Tyto permutace maj´ı permutaˇcn´ı matice Pπ a Pσ (s vynechan´ ymi nulami): 1 1 1 1 . a Pσ = Pπ = 1 1 1 1 1 1 Pro permutaˇcn´ı matice vyˇreˇste n´asleduj´ıc´ı:
´ Uloha 2.1. Proˇc se permutaˇcn´ım matic´ım ˇr´ık´ a permutaˇcn´ı? Uvaˇzte, co permutaˇcn´ı matice prov´ad´ı s matic´ı A (pochopitelnˇe spr´ avn´e velikosti), pokud ji n´asob´ı zleva ˇci zprava. ´ Uloha 2.2. Permutaˇcn´ı matice stejn´e velikosti lze n´asobit. Pro libovoln´e n-prvkov´e permutace π a σ m´ a Pπ Pσ smysl. Ukaˇzte, ˇze souˇcin permutaˇcn´ıch matic je opˇet permutaˇcn´ı matice a objevte, v jak´em je vztahu k permutac´ım π a σ. ´ Uloha 2.3. Permutaˇcn´ı matice maj´ı plnou hodnost, rank(Pπ ) = n. Tedy vˇzdy existuje inverzn´ı matice. Zjistˇete pro libovolnou permutaci π, jak vypad´ a inverzn´ı matice Pπ−1 . ´ Uloha 2.4. Ukaˇzte, ˇze pro libovolnou permutaˇcn´ı matici Pπ existuje mocnina k ≥ 1, ˇze Pπk = In . Jak´a je nejmenˇs´ı moˇzn´ a hodnota k?
3
Matice Pascalova troj´ uheln´ıku (20 bod˚ u)
ˇ ast Pascalova troj´ C´ uheln´ıku m˚ uˇzeme zapsat do matice n × n tˇremi zp˚ usoby: Ln je doln´ı troju ´heln´ıkov´a matice, Un je horn´ı troj´ uheln´ıkov´a a Sn m´ a zapsan´ y Pascal˚ uv troj´ uheln´ık po diagon´ al´ach. Form´alnˇe, pokud ˇc´ıslujeme prvky matice od 0 do n − 1: i j i+j (Ln )i,j = , (Un )i,j = , (Sn )i,j = , j i i kde pochopitelnˇe ji = 0 pro nesmysln´e hodnoty j > i. Pˇr´ıklad. Napˇr´ıklad pro n = 5 vypadaj´ı matice takto (s vynechan´ ymi nulami): 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 1 2 3 4 5 , 1 3 6 L5 = U5 = S5 = 1 2 1 , 1 3 6 10 15 . 1 3 3 1 1 4 1 4 10 20 35 1 4 6 4 1 1 1 5 15 35 70
´ Uloha 3.1. Jak bude vypadat souˇcin L5 U5 ?
´ Uloha 3.2. Zobecnˇete z´ıskan´ y v´ ysledek a popiˇste souˇcin Ln Un . Pochopitelnˇe pokud odvod´ıte obecn´ y vztah, nemus´ıte ˇreˇsit pˇredchoz´ı u ´lohu. N´ apovˇeda. Zkuste objevit co nejv´ıc d˚ ukaz˚ u. Lze si souˇcin rozepsat form´ alnˇe pomoc´ı definice souˇcinu a vzpomenout si na sumy kombinaˇcn´ıch ˇc´ısel. Dalˇs´ı moˇzn´e ˇreˇsen´ı je prov´est Gaussovu eliminaci vznikl´e matice Ln Un a udˇelat jej´ı LDU dekompozici. Co budou asi matice L a U ? Za kaˇzd´ y r˚ uzn´ y d˚ ukaz budou dalˇs´ı body (r˚ uznost posuzuje cviˇc´ıc´ı :)).
2
Pokroˇ cil´ a line´ arn´ı algebra 4
2. s´ erie
Mocniny Jordanovy matice (20 bod˚ u)
Jordanova matice je blokov´ a diagon´ aln´ı matice sloˇzen´ a z ˇctvercov´ ych blok˚ u um´ıstˇen´ ych pod´el diagon´ aly, kter´e se naz´ yvaj´ı Jordanovy buˇ nky. Jordanova buˇ nka Jλ je matice, kter´a m´ a na diagon´ ale hodnotu λ, nad diagon´ alou prouˇzek jedniˇcek a zbytek matice je nulov´ y, pˇr´ıklad Jordanovy buˇ nky 5 × 5 je na obr´ azku vlevo. Jordanova matice je sloˇzena z blok˚ u um´ıstˇen´ ych na diagon´alu, a kaˇzd´ y blok je jedna Jordanova buˇ nka. Pˇr´ıklad Jordanovy matice je na obr´ azku vpravo.
Jλ1
λ 1 λ 1 λ 1 Jλ = λ 1 λ
J=
Jλ2 Jλ3 Jλ4
Jordanova vˇeta je jeden z fundament´aln´ıch v´ ysledk˚ u line´ arn´ı algebry a ˇr´ık´ a n´asleduj´ıc´ı: Vˇ eta (Jordanova norm´aln´ı forma). Pro kaˇzdou ˇctvercovou matici A existuje regul´ arn´ı matice S a Jordanova matice J, ˇze A = SJS −1 . Napˇr´ıklad pro matici A pro v´ ypoˇcet Fibonacciho ˇc´ısel z prvn´ıho u ´kolu (ˇci konce kapitoly 3.1 textu Pov´ıd´ an´ı o line´ arn´ı algebˇre) dost´ av´ame n´asleduj´ıc´ı na prvn´ı pohled odpudivou Jordanovu norm´aln´ı formu: √ √ 5+1 1 √ √ 1 + 5 √ √ − 1− 5 1+ 5 5 2 5 1 1 2 √ A= = 2 2 = SJS −1 . √ 1 0 1− 5 1 5 − 1 1 1 √ √ 2 5 2 5 Je velice uˇziteˇcn´e umˇet pro matici A spoˇc´ıtat jej´ı k-tou mocninu Ak , s t´ım jsme se uˇz setkali v prvn´ım u ´kolu pro v´ yˇse uvedenou A. Pˇresnˇe v takov´e situaci se hod´ı Jordanova vˇeta, kter´ a umoˇzn ˇuje Ak pˇresnˇe urˇcit. Plat´ı totiˇz: Ak = SJS −1 SJS 1− · · · SJS −1 = SJ k S −1 . Tedy v pˇr´ıpadˇe k-t´e mocniny staˇc´ı umocˇ novat pouze Jordanovu matici. Napˇr´ıklad m˚ uˇzete zkusit z v´ yˇse uveden´eho rozkladu vyvodit vzorec pro k-t´e Fibonacciho ˇc´ıslo 1 fk = √ 5
√ !k 1 1+ 5 −√ 2 5
√ !k 1− 5 . 2
C´ılem t´eto u ´lohy je zjistit, jak vypad´ a k-t´a mocnina Jordanovy matice. To lze samozˇrejmˇe spoˇc´ıtat pˇr´ımo z definice maticov´eho n´asoben´ı, i kdyˇz postup je to trochu pracn´ y. Uk´aˇzeme si trikov´ y v´ ypoˇcet zaloˇzen´ y na binomick´e vˇetˇe. Pro zaˇca´tek jedna ze z´akladn´ıch vlastnost´ı blokov´ ych diagon´ aln´ıch matic: ´ Uloha 4.1. Pˇredpokl´ adejme, ˇze um´ıme umocˇ novat Jordanovy buˇ nky, tedy zn´ ame Jλk . Urˇcete k k J v z´avislosti na Jλ . 1
4.1
Binomick´ a vˇ eta
Binomick´a vˇeta z kombinatoriky je n´asleduj´ıc´ı identita, kter´a plat´ı pro vˇsechna re´aln´a ˇc´ısla a a b a pˇrirozen´a ˇc´ısla k: n 0 n n 1 n−1 n 2 n−2 n n n 0 k n−1 1 (a + b) = a b + a b + a b + ··· + a b + a b . 0 1 2 n−1 n
Pˇresnˇe v t´eto podobˇe vˇsak binomick´a vˇeta pro matice fungovat nem˚ uˇze, totiˇz napˇr´ıklad: (A + B)(A + B) = A(A + B) + B(A + B) = A2 + AB + BA + B 2 .
Protoˇze souˇcin matic obecnˇe nekomutuje, neplat´ı obecnˇe rovnost (A + B)2 = A2 + 2AB + B 2 . Pokud se vˇsak AB = BA, binomick´a vˇeta plat´ı. Speci´alnˇe jsme uk´azali na cviˇcen´ıch, ˇze αIn komutuje s libovolnou matic´ı A. ˇ ´ Uloha 4.2. Cemu se rovn´a (A + αIn )k ?
4.2
Mocnina Jordanovy buˇ nky
Zb´ yv´ a vyˇreˇsit, jak vypad´ a k-t´ a mocnina Jordanovy buˇ nky Jλk . To udˇel´ame ve dvou kroc´ıch: ´ Uloha 4.3. Jak vypad´ a k-t´ a mocnina J k ? 0
N´ apovˇeda. Tady staˇc´ı postupovat z definice n´asoben´ı, ale v´ ysledek vyjde velice hezky. k ´ Uloha 4.4. Jak vypad´ a k-t´ a mocnina J ? λ
N´ apovˇeda. Vyuˇzijte binomickou vˇetu.
5
Matice s vzorem ˇ sachovnice (25 bod˚ u)
Na cviˇcen´ı jsme dok´azali, ˇze tˇr´ıdy U horn´ıch troj´ uheln´ıkov´ ych matic, L doln´ıch troj´ uheln´ıkov´ ych matic a D diagon´ aln´ıch matic jsou uzavˇren´e na sˇc´ıt´ an´ı, n´asoben´ı a inverze (pochopitelnˇe pouze pokud inverze existuj´ı). Tedy napˇr´ıklad pro A, B ∈ U plat´ı A + B ∈ U , AB ∈ U a A−1 ∈ U , pokud operace d´avaj´ı smysl. V t´eto u ´loze chceme zjistit, jestli nˇeco podobn´eho plat´ı pro dvˇe tˇr´ıdy matic Sˇℓ a Sˇs se ˇ ˇsachovnicov´ ym vzorem. Nejprve definujme tyto tˇr´ıdy. Ctvercov´ a matice A patˇr´ı do Sˇℓ , pr´avˇe kdyˇz (A)i,j = 0, kdykoliv i + j je lich´e. Podobnˇe ˇctvercov´a matice B patˇr´ı do Sˇs , pr´avˇe kdyˇz (B)i,j = 0, kdykoliv i + j je sud´e. Na ostatn´ı pol´ıˇcka matic neklademe ˇz´adn´e pˇredpoklady, tedy napˇr´ıklad nulov´a matice patˇr´ı do obou tˇr´ıd. Pˇr´ıklad. Nˇekolik pˇr´ıklad˚ u tˇechto matic (s vynechan´ ymi nulami mimo ˇsachovnicov´ y vzor): 1 4 0 0 0 1 1 4 2 1 3 17 1 . 3 2 , a , , 5 , 1 2 7 2 0 2 2 0 0 2 0 7 1 0 {z } {z } | | ˇ ˇ ∈ Sℓ ∈ Ss ´ Uloha 5.1. Rozhodnˇete, zda jsou tˇr´ıdy Sˇℓ a Sˇs uzavˇren´e na souˇcet. ´ Uloha 5.2. Rozhodnˇete, zda jsou tˇr´ıdy Sˇℓ a Sˇs uzavˇren´e na souˇcin? Jsou souˇciny matic z tˇechto tˇr´ıd v nˇejak´em dalˇs´ım vztahu; tˇreba pro AB, pokud A ∈ Sˇℓ a B ∈ Sˇs ? ´ Uloha 5.3. Rozhodnˇete, zda jsou tˇr´ıdy Sˇℓ a Sˇs uzavˇren´e na inverze (opˇet s pˇredpokladem, ˇze pro A inverzn´ı matice A−1 existuje)? Lze pro nˇekter´e rozmˇery s jistotou ˇr´ıct, ˇze matice nen´ı invertovateln´ a? N´ apovˇeda. Inverze se poˇc´ıt´ a pomoc´ı Gaussovy eliminace, kter´a pˇrevede tvar (A | In ) na tvar (In | A−1 ). Nelze nˇejak vhodnˇe vyuˇz´ıt vlastnost´ı ˇsachovnicov´eho vzoru? 2
Pokroˇ cil´ a line´ arn´ı algebra 6
3. s´ erie
Dedekindovy ˇ rezy (30 bod˚ u)
V t´eto u ´loze se pokus´ıme sezn´ amit s Dedekindov´ymi ˇrezy, pomoc´ı nichˇz zavedeme re´aln´a ˇc´ısla. Tuto konstrukci vymyslel a publikoval Dedekind v roce 1872. Poznamenejme, ˇze ve stejn´em roce Cantor publikoval alternativn´ı zaveden´ı re´aln´ ych ˇc´ısel jako limit Cauchyovsk´ ych posloupnost´ı. Samotnou konstrukci neprovedeme do nejmenˇs´ıch detail˚ u, ostatnˇe to by form´ alnˇe zabralo nˇekolik str´anek. Naˇs´ım c´ılem bude poznat, jak tyto ˇrezy funguj´ı a proˇc maj´ı vlastnosti, kter´e po re´aln´ ych ˇc´ısel poˇzadujeme. Tou nejkl´ıˇcovˇejˇs´ı vlastnost´ı bude existence suprema kaˇzd´e nepr´ azdn´e shora omezen´e mnoˇziny. Na zaˇc´atku m´ ame uspoˇr´ adan´e tˇeleso racion´ aln´ıch ˇc´ısel Q, kter´e splˇ nuje n´asleduj´ıc´ı vlastnosti: Sˇc´ıt´ an´ı a n´asoben´ı je komutativn´ı, asociativn´ı, existuj´ı inverzn´ı prvky a operace jsou sv´azan´e distributivitou, nav´ıc m´ ame definovan´e line´ arn´ı uspoˇr´ad´ an´ı (tedy tranzitivn´ı antisymetrickou relaci). Budeme cht´ıt toto tˇeleso rozˇs´ıˇrit, tedy vytvoˇrit tˇeleso re´aln´ ych ˇc´ısel R rozˇsiˇruj´ıc´ı Q, kter´e bude splˇ novat velice siln´ y axiom o supremu. Dalˇs´ı veled˚ uleˇzitou vlastnost´ı racion´ aln´ıch ˇc´ısel, kterou budeme potˇrebovat, je, ˇze jsou hust´e, tedy ˇze mezi kaˇzd´ ymi dvˇema racion´ aln´ımi ˇc´ısly je jedno dalˇs´ı. Form´alnˇe: Pokud a, b ∈ Q a a < b, potom existuje c ∈ Q, ˇze a < c < b.
6.1
Definice ˇ rezu
Budeme cht´ıt vyuˇz´ıt faktu, ˇze re´aln´ ych ˇc´ısel je pˇresnˇe tolik, kolik je podmnoˇzin racion´ aln´ıch ˇc´ısel. Tedy re´aln´a ˇc´ısla budeme reprezentovat jako podmnoˇziny racion´ aln´ıch ˇc´ısel. Ovˇsem ne ledajak´e podmnoˇziny, budeme uvaˇzovat pouze podmnoˇziny, kter´e jsou ˇrezy. ˇ α je podmnoˇzina Q, kter´ Rez a splˇ nuje tˇri podm´ınky: 1. α je nepr´ azdn´a a rozd´ıln´a od cel´eho Q, 2. pokud p ∈ α, q ∈ Q a q < p, potom i q ∈ α, 3. pokud p ∈ α, potom existuje r, ˇze p < r a r ∈ α. Prvn´ı podm´ınka ˇr´ık´ a, ˇze ˇrez je netrivi´aln´ı podmnoˇzina. Druh´a ˇr´ık´ a, ˇze ˇrez obsahuje s kaˇzd´ ym re´aln´ ym ˇc´ıslem i vˇsechna menˇs´ı. Tˇret´ı naopak ˇr´ık´ a, ˇze ˇrez neobsahuje nejvˇetˇs´ı racion´ aln´ı ˇc´ıslo. V dalˇs´ım textu budeme ˇreck´ ymi p´ısmeny α, β, γ, . . . oznaˇcovat ˇrezy a norm´aln´ımi p´ısmeny racion´ aln´ı ˇc´ısla. ´ Uloha 6.1. Pro lepˇs´ı sezn´ amen´ı s ˇrezy dokaˇzte: 1. Pokud p ∈ α a q ∈ / α, potom p < q, 2. Pokud r ∈ / α a r < s, potom i s ∈ / α. Pan Dedekind nebyl cukr´ aˇr, a tedy ˇrezy se nejmenuj´ı ˇrezy podle cukr´ arny. Tento n´azev dostaly, nebot’ odpov´ıdaj´ı rozˇr´ıznut´ı re´aln´e osy na dvˇe ˇc´asti. Re´ aln´e ˇc´ıslo r je reprezentov´ano ˇ reprezentuj´ıc´ı r jsou tak, ˇze vezmeme re´alnou osu a rozˇr´ızneme ji v bodˇe r na dvˇe ˇc´asti. Rez √ potom vˇsechna racion´ aln´ı ˇc´ısla menˇs´ı neˇz r. Napˇ y bude reprezentovat 2 bude √r´ıklad ˇrez, kter´ mnoˇzina vˇsech racion´ aln´ıch ˇc´ısel q menˇs´ıch neˇz 2 (tedy to jsou bud’ ˇc´ısla z´aporn´ a nebo ty, ˇze 2 q < 2). Tento ˇrez je naznaˇcen tuˇcnˇe na obr´ azku. 0
√
2
Abychom pomoc´ı ˇrez˚ u vytvoˇrili uspoˇr´adan´e tˇeleso re´aln´ ych ˇc´ısel, budeme muset udˇelat ˇctyˇri vˇeci: 1. Zadefinovat na ˇrezech uspoˇr´ ad´ an´ı, 2. zadefinovat operaci sˇc´ıt´ an´ı, 3. zadefinovat operaci n´asoben´ı a 1
4. uk´azat, ˇze v sobˇe obsahuj´ı racion´ aln´ı ˇc´ısla jako podtˇeleso. Pokud bychom chtˇeli definici ovˇeˇrit do vˇsech detail˚ u, museli bychom uk´azat, ˇze splˇ nuje vˇsechny axiomy uspoˇr´ adan´eho tˇelesa. Takov´ y d˚ ukaz by byl moc pracn´ y, a proto ovˇeˇr´ıme jenom nˇekter´e axiomy. I tak z´ısk´ ame dobr´ y n´ahled do toho, jak ˇrezy funguj´ı, d´ıky ˇcemuˇz by dok´az´an´ı ostatn´ıch vlastnost´ı uˇz nebylo obt´ıˇzn´e.
6.2
Uspoˇ r´ ad´ an´ı na ˇ rezech
ˇ Na ˇrezech nadefinujeme uspoˇr´ ad´ an´ı zcela pˇrirozenˇe. Rezy uspoˇr´ad´ ame inkluz´ı, tedy α ≺ β, pokud α ( β. 0
a ≺ b
´ Uloha 6.2. Dokaˇzte, ˇze pro kaˇzd´e dva ˇrezy nastane pr´avˇe jedna z moˇznost´ı α ≺ β, α = β nebo α ≻ β. ´ Uloha 6.3. Dokaˇzte, ˇze je uspoˇr´ ad´ an´ı tranzitivn´ı: Pro kaˇzd´e tˇri ˇrezy α, β, γ plat´ı, ˇze α ≺ β a β ≺ γ implikuje α ≺ γ. ´ Uloha 6.4. Ukaˇzte, ˇze plat´ı axiom o supremu. Tedy ukaˇzte, ˇze pro libovolnou nepr´ azdnou shora omezenou podmnoˇzinu ˇrez˚ u M existuje sup(M ), nejmenˇs´ı horn´ı z´avora mnoˇziny M . N´ apovˇeda. Uvaˇzte mnoˇzinu vˇsech horn´ıch z´avor, kaˇzd´ a z nich je ˇrez. Definujte sup(M ) jako pr˚ unik vˇsech horn´ıch z´avor. Budete muset uk´azat, ˇze sup(M ) je ˇrez a ˇze neexistuje ˇz´adn´ a menˇs´ı horn´ı z´avora.
6.3
Sˇ c´ıt´ an´ı ˇ rez˚ u
Pro dva ˇrezy α a β definujeme sˇc´ıt´ an´ı takto: α ⊕ β = {x + y | x ∈ α, y ∈ β}. Pokud chceme nˇeco dok´azat o sˇc´ıt´ ani ˇrez˚ u, potˇrebujeme vyuˇz´ıt vlastnost´ı sˇc´ıt´ an´ı v racion´ aln´ıch ˇc´ıslech. Jak by se dalo ˇcekat, struktura racion´ aln´ıch ˇc´ısel se pˇrenese i na ˇrezy. ´ Uloha 6.5. Dokaˇzte, ˇze sˇc´ıt´ an´ı ⊕ je komutativn´ı a asociativn´ı. Neutr´aln´ı prvek 0⋆ definujeme jako mnoˇzinu vˇsech z´aporn´ ych racion´ aln´ıch ˇc´ısel.1
´ Uloha 6.6. Dokaˇzte, ˇze 0⋆ je skuteˇcnˇe neutr´ aln´ı prvek v˚ uˇci operaci ⊕, tedy α ⊕ 0⋆ = α pro kaˇzd´ y ˇrez α. Definovat inverzn´ı prvek bude maliˇcko komplikovanˇejˇs´ı. Necht’ α je libovoln´ y ˇrez. Definujme (−α) = {p | p ∈ Q a ∃r > 0, ˇze −r − p ∈ / α}. Jin´ ymi slovy, p leˇz´ı v (−α), pokud nˇejak´e racion´ aln´ı ˇc´ıslo menˇs´ı neˇz −p neleˇz´ı v α. N´ asleduj´ıc´ı obr´ azek ilustruje definici. Mnoˇzina vˇsech −p z definice odpov´ıd´ a vˇsem vˇetˇs´ım racion´ aln´ım ” ˇc´ısl˚ um“ neˇz tˇem obsaˇzen´ ych v ˇrezu α. Mnoˇzina (−α) obsahuje racion´ aln´ı ˇc´ısla k nim opaˇcn´ a. −p (−α)
0
α
Korektnost definice dok´aˇzeme ve dvou kroc´ıch: ´ Uloha 6.7. Dokaˇzte, ˇze pro kaˇzd´ y ˇrez α je mnoˇzina (−α) ˇrez, tedy splˇ nuje podm´ınky (1) aˇz (3) z definice ˇrezu. ´ Uloha 6.8. Dokaˇzte pro kaˇzd´ y ˇrez α, ˇze (−α) je skuteˇcnˇe inverzn´ı prvek ke sˇc´ıt´ an´ı, tedy α + ⋆ (−α) = 0 . 1
Znaˇc´ıme s hvˇezdiˇckou, abychom odliˇsili od neutr´ aln´ıho prvku 0 ∈ Q.
2
6.4
N´ asoben´ı ˇ rez˚ u
Definovat n´asoben´ı je kv˚ uli znam´enku maliˇcko sloˇzitˇejˇs´ı neˇz definovat sˇc´ıt´ an´ı. Omez´ıme se proto ⋆ ⋆ ’ nejprve jenom na kladn´e ˇrezy. Necht α ≻ 0 a β ≻ 0 , potom definujeme α ⊙ β = {p | ∃r ∈ α, ∃s ∈ β, ˇze r ≥ 0 a p < rs}. ´ Uloha 6.9. Ukaˇzte, ˇze pro libovoln´e dva ˇrezy α ≻ 0⋆ a β ≻ 0⋆ je α ⊙ β ˇrez. Podobnˇe jako v´ yˇse, lze snadno uk´azat, ˇze n´asoben´ı splˇ nuje vˇsechny axiomy tˇelesa. Jako neutr´ aln´ı prvek 1⋆ se pouˇzije mnoˇzinˇe vˇsech racion´ aln´ıch ˇc´ısel menˇs´ıch neˇz jedna. Pro α ≻ 0⋆ se definuje inverzn´ı prvek jako o n /α . α−1 = p | p ≤ 0 nebo ∃r > 0, ˇze p1 − r ∈ Protoˇze vˇsak d˚ ukaz by byl hodnˇe podobn´ y v´ yˇse uveden´ ym d˚ ukaz˚ um pro sˇc´ıt´ an´ı, detaily si zde odpust´ıme. Dodefinovat n´asoben´ı pro vˇsechny ˇrezy je jednoduch´e. Pro libovoln´ y ˇrez α plat´ı, ˇze α ⊙ 0⋆ = ⋆ ⋆ 0 ⊙ α = 0 . D´ ale definujeme −((−α) ⊙ β), pokud α ≺ 0⋆ a β ≻ 0⋆ , (−α) ⊙ (−β), pokud α ≺ 0⋆ a β ≺ 0⋆ , α⊙β = −(α ⊙ (−β)), pokud α ≻ 0⋆ a β ≺ 0⋆ , α ⊙ β, jinak plat´ı p˚ uvodn´ı definice. Inverzn´ı prvky se dodefinuj´ı podobnˇe, pro α ≺ 0⋆ definujeme α−1 = (−((−α)−1 )). Opˇet vynech´ame detaily d˚ ukaz˚ u, ˇze n´asoben´ı splˇ nuje axiomy tˇelesa. ´ Uloha 6.10. Ukaˇzte, ˇze pro libovoln´e dva ˇrezy α a β je α ⊙ β ˇrez. T´ım je odvozen´ı t´emˇeˇr dokonˇceno. V´ıme, ˇze takto sestrojen´e ˇrezy tvoˇr´ı uspoˇr´adan´e tˇeleso, kter´e m´ a supremum pro libovolnou nepr´ azdnou shora omezenou mnoˇzinu.
6.5
Vnoˇ ren´ı racion´ aln´ıch ˇ c´ısel
Zb´ yv´ a dok´azat, ˇze vznikl´e tˇeleso obsahuje racion´ aln´ı ˇc´ısla jako podtˇeleso. Pro racion´ aln´ı ˇc´ıslo r ⋆ uvaˇzujme mnoˇzinu r definovanou takto: r⋆ = {p | p ∈ Q, p < r}. ´ Uloha 6.11. Pro libovoln´e racion´ aln´ı ˇc´ıslo r plat´ı, ˇze r⋆ je ˇrez. ´ Uloha 6.12. Sˇc´ıt´ an´ı ˇrez˚ u reprezentuj´ıc´ıch racion´ aln´ı ˇc´ısla odpov´ıd´ a sˇc´ıt´ an´ı racion´ aln´ıch ˇc´ısel, tedy pro libovoln´a dvˇe racion´ aln´ı ˇc´ısla r a s je r⋆ ⊕ s⋆ = (r + s)⋆ . Podobnˇe lze dok´azat, ˇze pro libovoln´a dvˇe racion´ aln´ı ˇc´ısla r a s plat´ı, ˇze r⋆ ⊙ s⋆ = (rs)⋆ a r⋆ ≺ s⋆ , pr´avˇe kdyˇz r < s. Z toho vypl´ yv´ a, ˇze kaˇzd´e racion´ aln´ı ˇc´ıslo r m˚ uˇzeme zidentifikovat s ˇrezem r⋆ .
6.6
Shrnut´ı
V t´eto u ´loze jsme popsali, jak pomoc´ı Dedekinov´ ych ˇrez˚ u zkonstruovat z uspoˇr´adan´eho tˇelesa (Q, +, ·, <) jin´e uspoˇr´ adan´e tˇeleso (R, ⊕, ⊙, ≺) splˇ nuj´ıc´ı axiom o supremu. Nav´ıc jsme uk´azali, ˇze lze tˇeleso Q vnoˇrit do novˇe zkonstruovan´eho tˇelesa R. 3
7
Jen jeden sinus? (25 bod˚ u)
ˇ aˇr urˇcitˇe dobˇre zn´ Cten´ a kˇrivku funkce sin x. V t´eto u ´loze se zamˇeˇr´ıme na posloupnost {sin n}∞ n=0 a jej´ı poˇc´ateˇcn´ı u ´sek. Uk´aˇzeme si, ˇze zmˇena mˇeˇr´ıtka m˚ uˇze m´ıt velk´ y vliv. Prvn´ıch deset ˇclen˚ u posloupnosti vypad´ a pˇresnˇe tak, jak ˇcten´aˇr oˇcek´av´a. 0
1
2
3
4
5
6
7
8
9
10
1
1
-1
-1 0
1
2
3
4
5
6
7
8
9
10
Pro prvn´ıch sto ˇclen˚ u vypad´ a obr´ azek mnohem chaotiˇctˇeji. Ostatnˇe to d´av´a smysl, protoˇze jsme hodnoty desetkr´at v´ıce nahustili vedle sebe, tedy jednotliv´e oblouˇcky funkce sin x zaˇcnou spl´ yvat. 0
10
20
30
40
50
60
70
80
90
100
1
1
-1
-1 0
10
20
30
40
50
60
70
80
90
100
Zkus´ıme tedy zobrazit prvn´ıch tis´ıc a prvn´ıch deset tis´ıc ˇclen˚ u, coˇz vytvoˇr´ı dva r˚ uzn´e pˇrekvapiv´e vzory. Pro tis´ıc ˇclen˚ u dost´ av´ame jak´ ysi vzor ˇsesti´ uheln´ık˚ u. Ty vid´ıme kv˚ uli naˇsemu vn´ım´an´ı, kter´e spojuje nesouvisej´ıc´ı vˇeci. Pro deset tis´ıc vˇsak dost´ av´ame jeˇstˇe pˇrekvapivˇejˇs´ı vzor, kter´ y v˚ ubec nevypad´a jako posloupnost; vid´ıme ˇradu sinusovek poloˇzen´ ych pˇres sebe. 0
100
200
300
400
500
600
700
800
900
1000
1
1
-1
-1 0
100
200
300
400
500
4
600
700
800
900
1000
0
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
1
1
-1
-1 0
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
Moˇzn´ a je pˇrekvapiv´e, ˇze se obr´ azky pro tis´ıc a deset tis´ıc bod˚ u tolik liˇs´ı. Zkuste se vˇsak na obr´ azek pro tis´ıc bod˚ u pod´ıvat ze strany a uvid´ıte posunut´e sinusovky. ´ Uloha 7.1. Vaˇs´ım u ´kolem je posledn´ı obr´ azek pochopit a vysvˇetlit. Proˇc na obr´ azku vid´ıme pˇres sebe poloˇzen´e sinusovky? Kolik tˇech sinusovek je a jakou maj´ı periodu? Proˇc obr´ azek vypad´ a symetricky kolem osy x? N´ apovˇeda. Co v´ıte o aproximaci ˇc´ısla π? M˚ uˇzete k analyzov´an´ı posloupnosti pouˇz´ıvat libovoln´ y matematick´ y software a zkusit l´epe pochopit, jak se hodnoty posloupnosti {sin n}∞ chovaj´ ı. n=1
8
Koneˇ cn´ a tˇ elesa existuj´ı jen pro mocniny prvoˇ c´ısla (40 bod˚ u)
V t´eto u ´loze si uk´aˇzeme ˇc´ast z d˚ ukazu n´asleduj´ıc´ı algebraick´e vˇety. Vˇ eta. Koneˇcn´e tˇeleso F ˇra ´du rˇ existuje, pr´ avˇe kdyˇz rˇ je mocnina prvoˇc´ısla pk . Dokonce plat´ı, ˇze koneˇcnˇe tˇeleso dan´eho ˇr´adu je urˇceno jednoznaˇcnˇe (aˇz na pˇrejmenov´an´ı prvk˚ u, kter´emu se odbornˇe ˇr´ık´ a isomorfismus). Tato vˇeta tedy opodstatˇ nuje oznaˇcen´ı GF(pk ), k nebot’ tˇeleso ˇr´ adu p je jednoznaˇcnˇe urˇcen´e. V d˚ ukazu uk´aˇzeme, ˇze kaˇzd´e takov´e tˇeleso je vysoce symetrick´ y objekt, kter´ y v sobˇe skr´ yv´ a vektorov´ y prostor. To je pomˇernˇe pˇrekvapiv´e, nebot’ v definici tˇelesa se vektorov´e prostory v˚ ubec nevyskytuj´ı a naopak ty se definuj´ı pomoc´ı tˇeles.
Co o tˇ elesech uˇ z zn´ ame . . . V samotn´em d˚ ukazu m˚ uˇzeme pouˇz´ıt pouze axiomy tˇelesa a jejich d˚ usledky! Pˇripomeˇ nme si, co ˇr´ıkaj´ı axiomy tˇelesa: • Tˇeleso je struktura s dvˇema operacemi – sˇc´ıt´ an´ım a n´asoben´ım. • Tˇeleso obsahuje dva speci´aln´ı prvky, neutr´ aln´ı prvek na sˇc´ıt´ an´ı (budeme znaˇcit 0) a neutr´aln´ı prvek na n´asoben´ı (znaˇc´ıme 1). • Z hlediska sˇc´ıt´ an´ı se tˇeleso chov´a jako grupa – m´ ame inverzn´ı prvky a neutr´ aln´ı prvek. • Z hlediska n´asoben´ı se tˇeleso bez 0 chov´a jako grupa – opˇet m´ ame inverze a neutr´ aln´ı prvek. • Nav´ıc operace sˇc´ıt´ an´ı a n´asoben´ı jsou dohromady sv´ azan´e distributivitou. Z axiom˚ u lze odvodit i dalˇs´ı vlastnosti tˇeles, nˇekter´e jsme jiˇz vidˇeli. • Neutr´aln´ı prvky 0 a 1 a inverze pro obˇe operace jsou urˇceny jednoznaˇcnˇe. Ostatnˇe to plat´ı obecnˇe i v grup´ ach. • Libovoln´ y n´asobek 0 je zase nula: a · 0 = 0. • Pokud a + b = a + c, potom b = c. • Podobnˇe pro n´asoben´ı a a 6= 0, pokud a · b = a · c, potom b = c. • Neexistuj´ı dvˇe nenulov´a ˇc´ısla a a b, ˇze a · b = 0. 5
Zp je podtˇ eleso F Na rozjezd vyˇreˇs´ıme tˇelesa s prvoˇc´ıselnou velikost´ı. Uvaˇzujme strukturu Zk tvoˇrenou ˇc´ısly 0, . . . , k − 1 a operacemi sˇc´ıtan´ı a n´asoben´ı definovan´ ymi jako zbytek po celoˇc´ıseln´em sˇc´ıt´ an´ı a n´asoben´ı. Pˇr´ıklad. Napˇr´ıklad pro Z4 a prvky a = 2 a b = 3 dostaneme, ˇze a + b = 1 a a · b = 2, nebot’ pˇresnˇe takov´e zbytky maj´ı ˇc´ısla 5 a 6 po dˇelen´ı 4. ´ Uloha 8.1. Dokaˇzte, ˇze Zp je tˇeleso, pr´avˇe kdyˇz p je prvoˇc´ıslo. N´ apovˇeda. Pokud p nen´ı prvoˇc´ıslo, nen´ı tˇeˇzk´e nal´ezt dvojici, kter´a poruˇsuje posledn´ı vlastnost. Pro prvoˇc´ısla to se sˇc´ıt´ an´ım bude docela jednoduch´e. Je vˇsak tˇreba pro kaˇzd´ y prvek a uk´azat, ˇze n´asoben´ı t´ımto prvkem je prost´e, tedy ˇze neexistuje dvˇe rozd´ıln´a ˇc´ısla b a c, aby a · b = a · c. Charakteristika tˇelesa je nejmenˇs´ı pˇrirozen´e ˇc´ıslo k takov´e, ˇze souˇcet k jedniˇcek 1+1+· · ·+1 = 0, pˇr´ıpadnˇe 0, pokud takov´e k neexistuje (tˇreba re´aln´a ˇc´ısla). ´ Uloha 8.2. Dokaˇzte, ˇze pro kaˇzd´e koneˇcn´e tˇeleso F je jeho charakteristika nˇejak´e prvoˇc´ıslo p. N´ apovˇeda. Ukaˇzte nejprve, ˇze charakteristika je nenulov´a. Pot´e zkuste dokazovat sporem. Kdyby charakteristika nebyla prvoˇc´ıseln´a, co by bylo ˇspatnˇe? Oznaˇcme souˇcet k jedniˇcek pomoc´ı k. V tˇelese tedy m´ ame prvky 0, . . . , p − 1. O dalˇs´ıch prvc´ıch zat´ım nic nev´ıme. ´ Uloha 8.3. Ukaˇzte, ˇze prvky 0, . . . , p − 1 tvoˇr´ı podtˇeleso totoˇzn´e Zp .
Zp 0 1 2 3 ··· p − 1
F
Coˇ ze? Tˇ eleso je vektorov´ y prostor? Nyn´ı vyuˇzijeme z´ıskan´e znalosti o tˇelesech a dokonˇc´ıme d˚ ukaz pˇrekvapiv´ ym u ´skokem, vˇsak posud’te sami. ´ Uloha 8.4. Dokaˇzte, ˇze kaˇzd´e koneˇcn´e tˇeleso F charakteristiky p je vektorov´ y prostor V nad tˇelesem Zp . Operace V definujeme takto: sˇc´ıt´ an´ı vektor˚ u odpov´ıd´ a sˇc´ıt´ an´ı v tˇelese a skal´arn´ı n´asoben´ı n´asoben´ım v tˇelese (protoˇze Zp je podtˇeleso F, lze to takto definovat). N´ apovˇeda. K tomu potˇrebujeme dok´azat, ˇze vznikl´a struktura splˇ nuje vˇsechny axiomy vektorov´eho prostoru. Neplyne to snadno z toho, ˇze F je tˇeleso? V´ıme, ˇze vektorov´e prostory tvoˇr´ı silnˇe pˇredurˇcenou strukturu, pojd’me toho tedy vyuˇz´ıt. Vektorov´ y prostor V m´ a totiˇz koneˇcnou dimenzi k. Podle Steinitzovy vˇety v´ıme, ˇze existuje nˇejak´ a b´aze b1 , . . . , bk . Sice v˚ ubec netuˇs´ıme, jak vypad´ a, ale to nebudeme potˇrebovat – staˇc´ı vˇedˇet, ˇze existuje. Bude se hodit jeˇstˇe jedno obecn´e tvrzen´ı o b´az´ıch a line´ arn´ıch kombinac´ıch. ´ Uloha 8.5. Dokaˇzte, ˇze pokud b1 , . . . , bk je b´aze vektorov´ eho prostoru, potom jej´ı r˚ uzn´e line´ arn´ı P P kombinace definuj´ı r˚ uzn´e vektory. Tedy dokaˇzte, ˇze ki=1 αi bi = ki=1 α ¯ i bi implikuje, ˇze αi = α ¯i.
Dokonˇ cen´ı d˚ ukazu A na z´avˇer sloˇzme oba poznatky dohromady. ´ Uloha 8.6. Dokaˇzte, ˇze kaˇzd´e koneˇcn´e tˇeleso F m´ a pk prvk˚ u. N´ apovˇeda. Kolik rozd´ıln´ ych line´ arn´ıch kombinac´ı vektor˚ u b1 , . . . , bk existuje? T´ım jsme uk´azali neexistenci koneˇcn´eho tˇelesa velikosti, kter´a nen´ı mocnina prvoˇc´ısla. Tak´e v´am pˇrijde trik hezk´ y? Pokud jste se dostali aˇz sem (a pˇr´ıpadnˇe vˇsechna tvrzen´ı po cestˇe dok´azali), m´ ate m˚ uj obdiv (a zaslouˇz´ıte si sv´e body :)). 6
