Lineární algebra a geometrie III Doc. RNDr. Martin Čadek, CSc. Bc. Lukáš Vokřínek, PhD. 26. října 2019 Obsah Úvod 2 Sylabus přednášky 2 1 Afinní a projektivní prostory 3 2 Polyedry a lineární programování 12 3 Nadkvadriky v afinním a projektivním prostoru 23 4 Metrická klasifikace nadkvadrik 30 5 Mooreova Penroseova pseudoinverze 42 6 Multilineární algebra 48 7 Tenzorový součin 56 8 Symetrické a antisymetrické tenzory 67 9 Determinanty, objemy a orientace 77 10 Smithův normální tvar celočíselných matic 87 11 Smithův normální tvar polynomiálních matic 94 1 Úvod Obsah skript je zřejmý z následujícího podrobného sylabu. Většina kapitol kromě teoretického výkladu obsahuje vyřešené příklady a na konci kontrolní otázky a úlohy k samostatnému procvičení. Rádi bychom poděkovali Richardu Lastoveckému, který značnou část textu přepsal v L^TfrjXu a opatřil úlohami k samostatnému řešení. Místa označená jednou hvězdičkou „*" považujeme za těžká a jejich studium doporučujeme pouze studentům usilujícím o lepší známku. Místa označená dvěma hvězdičkami „**" jsou ještě náročnější. Části označené „cv" se dělaly na cvičení a „nd" se nedělaly vůbec. Martin Čadek & Lukáš Vokřínek Sylabus přednášky 1. Afinní a projektivní prostory: afinní prostor, komplexifikace vektorového a afinního prostoru, projektivní prostor, projektivní rozšíření afinního prostoru. 2. Nadkvadriky v afinním a projektivním prostoru: nadkvadriky v afinním a projektivním prostoru, vztah projektivních nadkvadrik a bilineárních forem a jejich klasifikace, klasifikace afinních nadkvadrik. 3. Metrická klasifikace nadkvadrik: polárně sdružené body vzhledem k nadkvadrice, střed nadkvadriky, hlavní směry, hlavní nadroviny, vrcholy nadkvadriky, metrická klasifikace nadkvadrik. 4. Mooreova Penroseova pseudoinverze: Mooreova-Penroseova pseudoinverze, singulární hodnoty, singulární rozklad, aproximace řešení soustavy lineárních rovnic, lineární regrese. 5. Multilineární algebra: faktorový prostor, multilineární zobrazení, duální prostor, duální báze, duální zobrazení, dualita a podprostory, báze prostoru multilineárních forem. 6. Tenzorový součin: tenzorový součin a jeho univerzální vlastnost, asociativita, komutati-vita a další vlastnosti tenzorového součinu, vztah tenzorového součinu a prostoru lineárních zobrazení, tenzorová algebra vektorového prostoru, souřadnice tenzorů při změně báze. 7. Symetrické a antisymetrické tenzory: symetrické tenzory, symetrická algebra vektorového prostoru a její báze, antisymetrické tenzory, vnější algebra vektorového prostoru a její báze, vztah vnější mocniny a determinantu. 8. Determinanty, objemy a orientace: antisymetrické formy a objemy, orientace, objem v Eukleidovském prostoru, geometrie v rovině a prostoru, kvaterniony a jejich vztah ke geometrii v prostoru. 9. Smithův normální tvar celočíselných matic: celočíselné matice a jejich Smithův normální tvar, prezentace konečně generovaných komutativních grup, klasifikace konečně generovaných komutativních grup. 10. Smithův normální tvar polynomiálních matic: polynomiální matice a jejich Smithův normální tvar, K[A]-moduly a jejich vztah k operátorům na vektorových prostorech, kanonická prezentace operátorů na Kn, racionální kanonický tvar, Cayleyho-Hamiltonova věta, Jordánův kanonický tvar. 2 1. Afinní a projektivní prostory Začněme s krátkou motivací. Naším cílem bude studium kuželoseček a jejich více-rozměrných analogií, kvadrik a nadkvadrik. Na kuželosečky se dá pohlížet dvěma způsoby - geometricky jako na množiny bodů, které splňují nějakou kvadratickou rovnici a algebraicky jako na tuto rovnici samotnou. Klasifikace kuželoseček pak spočívá v nalezení jistých kanonických tvarů - geometricky to znamená, že po posunutí a otočení každá kuželosečka vypadá jako elipsa, hyperbola, parabola, atd. a algebraicky pak to, že po jisté vhodné lineární substituci rovnice kuželosečky vypadá nějakým specifickým způsobem. Aby byly tyto dva pohledy ekvivalentní, je potřeba uvažovat „komplexně", neboť například x2 + y2 = —1 a x2 = —1 není možné převést na sebe, nicméně mají tyto rovnice totožnou množinu řešení, totiž prázdnou. Pokud bychom uvažovali i komplexní řešení, budou se jejich množiny chovat geometricky jinak. Kromě komplexních bodů bude ještě výhodné přidat k naší rovině „body v nekonečnu". Například by mělo být zřejmé, že střed elipsy hraje zásadní roli (elipsa je podle něj symetrická). Představme si nyní, že jeden konec elipsy držíme na místě a druhý konec táhneme směrem od prvního - střed se bude vzdalovat poloviční rychlostí. V limitním případě, kdy pohyblivý konec elipsy zmizí v nekonečnu, stane se z elipsy parabola a ta již střed mít nebude, protože jsme jej také přesunuli do nekonečna. Nicméně, tento bod v nekonečnu je stále v jistém smyslu středem paraboly a je vhodné jej mít k dispozici. O něco jednodušší příklad je dvojice různoběžných přímek, jejichž průsečík přesunujeme do nekonečna. Pokud budeme vhodnou dvojici bodů držet na místě, stane se v limitním případě z dvojice různoběžných přímek dvojice rovnoběžných přímek. Pokud budeme uvažovat i body v nekonečnu, přímky se budou stále protínat (tak, jak se nám zdá, že se koleje v dálce protínají). V dalším tedy obohatíme rovinu (obecněji afinní prostor) o komplexní body a později o body v nekonečnu. Mluvíme o komplexním a projektivním rozšíření. 1.1. Komplexifikace reálného vektorového prostoru Nechť V je reálný vektorový prostor. Jeho komplexním rozšířením (komplexifikací) je komplexní vektorový prostor Vc s nosnou množinou V x V, na které je definováno sčítání a násobení komplexním číslem takto: (v,w) + (v',w') = (v + v', w + w') (a + ib)(v,w) = (av — bw, bv + aw) Není těžké dokázat, že jde skutečně o vektorový prostor nad C s nulovým prvkem (0,0). (Dobrou motivací je způsob, jakým se konstruují komplexní čísla jako dvojice reálných čísel.) Vektory v £ V ztotožníme s prvky (v,0) £ Vc a budeme tak V považovat za podmnožinu prostoru Vc. Platí (v, w) = (v, 0) + i(w, 0) = v + iw Poznámka. Poněkud abstraktní, ale velice užitečné pozorování je následující univerzální vlastnost: každé M-lineární zobrazení p: V —> W do komplexního vektorového prostoru W se jednoznačně rozšiřuje na C-lineární zobrazení íp: Vc —> W, nutně dané předpisem p{v + iw) = p{v) + ip{w) = p{v) + ip{w). To, že je vskutku C-lineární se ověří snadno (stačí zachovávání násobení i). 3 1. Afínní a projektivní prostory Věta 1.1. Každá báze (ei, ..., en) prostoru V je bází prostoru V . cv Důkaz. Nechť u + iv £ Vc je libovolný vektor. Chceme ukázat, že existují jediná komplexní čísla Zk = a,k + ibk taková, že u + iv = ziei H-----h znen = (ai + ibi)ei H-----h (an + ibn)en. Porovnáním reálných a imaginárních částí dostáváme ekvivalentní soustavu u = a\e\ H-----\-anen, v = b\e\ H-----h&nen. Tato soustava má jediné řešení: a\. je fc-tá souřadnice u a je fc-tá souřadnice □ Příklad. Komplexní rozšíření vektorového prostoru Wl je izomorfní s Cn. Nejlépe se to vidí pomocí předchozí poznámky a věty: inkluze W1 —> Cn se rozšiřuje na (Mn)c —> Cn, které posílá bázový vektor na bázový vektor a je tedy isomorfismem. cv Příklad. Dokažte, že komplexní rozšíření prostoru polynomů s reálnými koeficienty je izomorfní s prostorem polynomů s komplexními koeficienty C[x]. Definice 1.2. Nechť tp: V —> W je lineární zobrazení mezi reálnými vektorovými prostory. Komplexní rozšíření ipc: Vc —> Wc je zobrazení definované předpisem ipC(v + iw) = if(v) + i(p(w). Toto zobrazení je opět lineární. Věta 1.3. Je-li A matice lineárního zobrazeníip: V —> W v bázích a a f3, pak ipc: Vc —> Wc má v bázích a a (3 opět matici zobrazení A. cv Důkaz. Nechť a = (ei,..., en), (3 = (ei,..., em). Matice A = (a^) je definována takto: k Pro (pc platí k (fC(ej) = ip(ej) = y^ějdij. i=i Tedy ( O +v, bijekce a můžeme tedy ztotožnit S s vektorovým prostorem Dir S. Důležité je ale mít na paměti, že tato identifikace závisí na volbě počátku. Každá jiná identifikace se však liší pouze o translaci, v i—> PÔ + v. Naopak, každý vektorový prostor V lze chápat jako afinní prostor se zaměřením V tím, že počátek „zapomeneme", tj. požadované zobrazení V x V —> V bude sčítání ve V. Definice 1.5. Báze afinního prostoru S je {n + l)-tice (O, e±, ..., en), kde O G S je bod (počátek) a (ei, ..., en) je báze vektorového prostoru V. Souřadnice bodu A G S v této bázi je (n + l)-tice skalárů (1, x\, ..., xn)T taková, že /1\ xi A = O + xiei H-----h xnen = (O, ei, ..., en) Souřadnice vektoru v G Dir S v této bázi je (n + l)-tice skalárů (0, x±, , xn)T taková, že v = x\e\ H-----h Xne^ (O, ei, ..., en) • /0\ Alternativně zapisujeme souřadnice bodů [x±,..., xn] = (1, x\,..., xn)T a souřadnice vektorů (xi,..., xn) = (0, xi,..., xn)T. Příklad. Kařdý afinní podprostor vektorového prostoru je afinní prostor. Příklad. Standardním afinním prostorem dimenze n budeme rozumět prostor An = {{l,x1,...,xn)£Kn+1} = {{x0,x1,...,xn) GKn+1 |x0 = l}. Vzhledem k předchozí diskuzi lze An považovat za „prostor souřadnic". Konkrétně, báze afinního prostoru S zadává izomorfismus An —> S daný násobením zleva řádkem (O, e±, ..., en) Inverzní zobrazení S —> An pak přiřazuje každému bodu jeho souřadnice. V afinním prostoru můžeme definovat afinní kombinace: jsou-li Aq, ... ,An G S body a xq, ..., xn G K čísla taková, že xq + • • • + xn = 1, položíme x0A0 + ■■■ + xnAn = P + x0PA0 + ■■■+ xnPAn G S, cv kde P G S je libovolně zvolený bod. Snadno se ukáže, že výsledek na této volbě nezávisí. Příklad. Prostorem barycentrických souřadnic dimenze n budeme rozumět prostor {(x0,x1, ...,xn) G xq H-----h xr. !}• 5 1. Afínní a projektivní prostory Stejně jako izomorfismy An — S odpovídají bázím S, izomorfismy Bn = S odpovídají bodovým bázím, tj. (n + l)-ticím bodů Eq, ..., En takovým, že každý bod A lze jednoznačně vyjádřit jako A = xqEq + • • - + xnEn, xq + • • • +xn = 1. Koeficienty x i nazýváme bary centrické souřadnice bodu A. Nechť S je afinní prostor, jehož zaměření V je reálný vektorový prostor. Komplexním rozšířením (komplexifikací) afinního prostoru S je množina 5C = S x V s operací + : SC xVC ^ SC definovanou předpisem (A, u) + (v, w) = (A + v, u + w). Jednoduše se dá ověřit, že takto definovaná operace má všechny vlastnosti z definice afinního prostoru, např. vlastnost (3) je splněna, protože rovnice (A,u) + (v,w) = (B,t) má jediné řešení (v, w) = (ÄÉ, t — u). Bod A G S ztotožníme s bodem (A, 0) G 5C a budeme tak opět chápat S jako podmnožinu 5C. Pro každý bod (A,u) G 5C pak platí (A, u) = (A, 0) + (0, u) = A + iu. cv Příklad. Je-li T C S afinní podprostor s parametrickým popisem {P + Mi + • • • + tkvk | íi,..., tk G M}, pak Tc je afinní podprostor v 5C s parametrickým popisem {P + Mi H-----h ífc^fc | íi,.. •,ífc e C}. cv Příklad. Je-li T = {x G Mn | Ar = 6} afinní podprostor všech reálných řešení soustavy rovnic Ax = b, pak = {x G Cn | = 6} je prostorem všech komplexních řešení téže soustavy. Definice 1.6. Zobrazení tp: S —> T mezi afinními prostory se nazývá afinní, jestliže existuje lineární zobrazení tp: Dir S —> Dir T takové, že T je afinní zobrazení mezi reálnými afinními prostory. Jeho komplexní rozšíření pc: 5C —> je definováno předpisem pc(A + iu) = p{Á) + ip(u), kde p je indukované lineární zobrazení. cv Zobrazení pc je opět afinní s indukovaným lineárním zobrazením pc = pc. 6 1. Afínní a projektivní prostory 1.3. Projektivní prostor Nechť V je {n + l)-rozměrný vektorový prostor nad tělesem K (obvykle K = M nebo C). Definice 1.8. Množinu V (V) všech jednorozměrných podprostorů vektorového prostoru V nazveme n-rozměrným projektivním prostorem nad K. Vektorový prostor V se nazývá aritmetickým základem projektivního prostoru V (V). Prvky projektivního prostoru se nazývají body. Každý nenulový vektor v G V \ {0} určuje jednorozměrný podprostor [v] = {kv G V | k G K} G P(F); vektor u se nazývá aritmetickým zástupcem bodu [u]. Zjevně každý jiný aritmetický zástupce je nenulovým násobkem v a můžeme tedy alternativně V (V) chápat jako rozklad (V \ {0}) / ~ podle relace ekvivalence v ~ kv, k G Kx. Příklad. Standardním projektivním prostorem dimenze n budeme rozumět Vn = "P(Kn+1). K popisu bodů budeme používat označení {xq : • • • : xn) = [(x0, ■ ■ .,xn)]. Jedna z možných názorných představ o projektivním prostoru s aritmetickým základem Mn+1 je založena na pozorování, že každá přímka v Mn+1 protne sféru Sn = {(x0,... ,xn) G Rn+1 \x2Q + • • • + xl = 1} právě ve dvou bodech. Tedy Vn je Sn, kde „ztotožníme" protilehlé body. O něco lépe představitelná je identifikace bodů na okraji hemisféry. Takto lze podmnožiny projektivního prostoru v omezené míře i namalovat, viz přednášky. Poznámka. Na přednášce jsem měl delší odbočku ohledně ploch, orientace, atd. Konkrétně jsem mluvil o Riemannovských plochách, Móbiově pásku, Kleinově láhvi a projektivním prostoru. Libovolná baze ql — (^o? • • • > ^n) vektorového prostoru V zádava identifikaci V —y IKn^ a následně V (V) ^> Vn, [v] i—> [(v)a]. O obrazu bodu [v] budeme hovořit jako o jeho homogenních souřadnicích. Konkrétně, je-li (v)a = (xq, ... ,xn), jsou homogenní souřadnice [v] rovny {x$ : • • • : xn) a tyto nezávisí na volbě aritmetického základu v. 1.4. Projektivní podprostory Jednorozměrné podprostory v {k + l)-rozměrném podprostorů W C V tvoří fc-rozměrný projektivní podprostor V(W) v projektivním prostoru V (V). Jednorozměrný projektivní podprostor se nazývá projektivní přímka. Příklad. Každé dvě přímky p, q v v2 mají společný bod. V aritmetickém základu K3 přímkám p a q odpovídají podprostory U a V dimenze 2. Protože dim U n V = dim U + dim V - dim(ř7 + V) a dim(č7 + V) < 3, je dimč7 n V > 1. Tedy p D q obsahuje alespoň jeden bod projektivního prostoru 7*2- 7 1. Afínní a projektivní prostory Nechť V(W) C Vn je fc-rozměrný projektivní podprostor, zadaný {k + l)-rozměrným podprostorem W C Kn+1 popsaným homogenní soustavou rovnic Ax = 0. Stejná soustava rovnic pak popisuje homogenní souřadnice bodů projektivního prostoru V(W), tj. ViW) = {[x] | Ax = 0}. 1.5. Kolineace Nechť V (V) a V(W) jsou dva projektivní prostory dimenze n. Zobrazení <í>: V (V) —> V(W) se nazývá kolineace, jestliže existuje lineární izomorŕismus p: V —> W takový, že = [<^)] pro všechna u G F. Píšeme <£ = [ Vn tvoří grupu, kterou budeme značit PGL(Vn). cv Poznámka. Analogicky k situaci ve vektorových a afinních prostorech existuje pojem báze projektivního prostoru - konkrétně geometrická báze je (n + 2)-tice bodů tvaru [eo], • • •, [en], [eo + • • • + en] pro nějakou bázi aritmetického základu. Platí, že kolineace je jednoznačně určena tím, kam posílá bázi a tu může poslat na libovolnou jinou bázi. Viz cvičení. 1.6. Afinní prostor jako podmnožina projektivního prostoru Nyní se k afinnímu prostoru pokusíme přidat body v nekonečnu. Názornou představu o tomto procesu si můžeme učinit tím, že afinní prostor budeme vnímat jako rovinu nad níž se nachází pozorovatel (jako když se díváme na podlahu). Pak když pozorujeme svět kolem sebe tak vidíme jednak body této roviny a jednak body na horizontu1. Body na horizontu mají speciální význam, odpovídají směrům v rovině - například každé dvě rovnoběžné přímky v rovině se protínají na horizontu přesně v bodě odpovídajícím jejich společnému směru, atd. Pokusíme se nyní tuto situaci popsat obecně. Nechť V (V) je n-rozměrný projektivní prostor s aritmetickým základem V. Nechť J\í C V je afinní nadrovina neprocházející počátkem. Pro každý bod X G V (V) nastane právě jedna z následujících dvou možností: • X n J\í = 0, potom X G V(BiľJ\í) nebo • X n J\í 7^ 0, potom je tímto průnikem jediný bod. Naopak, každým bodem A G J\í prochází jediný jednorozměrný podprostor X G V (V). Dostáváme tak identifikaci J\í = V (V) \ V(DiľJ\í). Definujme nevlastní prostor afinního prostoru S jako v(S) = V(DiľS). Můžeme potom psát V (V) =MUv{M). O bodech z J\í (lépe řečeno jednorozměrných podprostorech V protínajících J\í) budeme hovořit jako o vlastních boáech a o bodech v(ftf) jako o nevlastních boáech nebo také směrech. Toto rozdělení samozřejmě závisí na volbě nadroviny J\í (ve skutečnosti pouze na Dir J\í). V této situaci mluvíme o projektivním prostoru V (V) jako o projektivním rozšíření afinního prostoru J\í a značíme jej J\í = V (V). 1Body nad horizontem budeme ignorovat. Důvodem je, že naše vnímání je založené na polopřímkách, zatímco projektivní prostor na přímkách a v projektivním vnímání jsou tedy body nad horizontem zároveň body roviny vyskytující se týmž směrem za pozorovatelem. 8 1. Afínní a projektivní prostory Příklad. Zabývejme se příkladem M = An C Kn+1, tj. standardním afinním prostorem dimenze n. Potom bod (1, x±,..., xn) G An ztotožňujeme s vlastním bodem (1 : x\ : • • • : xn) a zbylé body Vn jsou tvaru (0 : x\ : • • • : xn) a leží v u(An). Zejména Vn = An. ** Poznámka. Přesuňme se nyní do situace, kdy máme zadaný abstraktní afinní prostor S a chceme definovat jeho projektivní rozšíření. Podle předchozího výkladu je vhodné S vložit do nějakého vektorového prostoru V jako afinní nadrovinu neprocházející počátkem. K tomu, abychom tento vektorový prostor definovali, předpokládejme prvně, že takové vložení máme a popišme V pouze pomocí S. Nechť P G S je libovolný bod (o kterém můžeme uvažovat jako o počátku). Zjevně platí V = [P]©Dir S (jsou to podprostory komplementární dimenze s nulovým průnikem, protože S neprochází počátkem), a proto můžeme obecný vektor u G V psát jednoznačně jako u = tP+v, kde í£lai)É Dir S. Zřejmě tedy máme bijekci K x Dir S = V, (t, v) i—> tP + v. Mohli bychom tedy definovat ľ = Kx Dir S, bijekce z předchozího odstavce ale bohužel závisí na volbě počátku P. Pokusme se nyní této závislosti zbavit a uvažujme tedy jinou volbou počátku Q a počítejme Zřejmě tedy platí tP + v = sQ + w, právě když s = íav = sPQ + w. Je-li nyní S libovolný afinní prostor, uvážíme na K x S x Dir S relaci ekvivalence, jejíž třídy [(i, P, v)] budeme značit íP + ti a budeme tedy požadovat tP + v = sQ + w, právě když platí s = t a v — w = sPCj. Potom lze na vzniklém rozkladu V(S) = (Ix5x Dir 5)/~ zavést strukturu vektorového prostoru (platí tP+v = tO + (t()P+v) a položíme (tO +v) + (sO+w) = (i + s)0 + (v + w)). Bod A £ S ztotožníme s vektorem 1A + 0 G V(S) a tímto způsobem budeme chápat S jako nadrovinu ve V(S). Dostáváme tak projektivní rozšíření S = V{V{S)). cv Cvičení. Popište projektivní přímku procházející dvěma vlastními body; vlastním a nevlastním bodem (řešte stejným způsobem). 1.7. Projektivní rozšíření afinních podprostorů Nechť T C S je afinní podprostor. Naším cílem bude zkonstruovat projektivní podprostor tak, že T bude projektivním rozšířením T. Předpokládejme tedy, že S C V jako afinní nadrovina a pokusme se najít vektorový podprostor W C V, v němž bude T ležet jako afinní nadrovina. Protože T C S neprochází počátkem, stačí za W zvolit lineární obal T, který je zjevně W = {0} * T (spojení počátku a T - to je afinní podprostor obsahující počátek, tj. vektorový podprostor). Pro dimenzi platí dimVF = dim{0} + 1 + dimT = dimT + 1, takže v něm vsktuktu leží T jako afinní nadrovina neprocházející počátkem. Můžeme tedy psát T = V(W) a jedná se o projektivní podprostor S - hovoříme o projektivním rozšíření afinního podprostorů. Z konstrukce vidíme, že se jedná o nejmenší projektivní podprostor S obsahující T. Z předchozí sekce víme, že T = T U v(T) a tedy T obsahuje krom bodů z T také směry v zaměření DirT. To podává uspokojivé vysvětlení, proč (a kde!) se protínají rovnoběžné přímky. Zabývejme se nyní početním aspektem. Nechť je T zadán soustavou (nehomogenních) lineárních rovnic b + Ax = 0. Tu můžeme vhodně zapsat jako (b | Áj í—\ = 0. Protože jsou 9 1. Afínní a projektivní prostory tedy body T dány soustavou (6|A)^=0, *0 = 1, je zjevně T afinní nadrovinou ve vektorovém podprostoru zadaném první (homogenní) sou- stavou rovnic = 0 (speciálně je třeba vyřešit případ, že by původní soustava neměla řešení2). Podívejme se na tento podprostor poněkud elementárněji: platí X = {x$ : x\ : • • • : xn) £ T, právě když xq 7^ 0 a X = (1 : x\/xq : • • • : xn/xo) = (1, x±/xq, ..., xn/xo) 6 T, tj. právě když xq 7^ 0 a b + A(xi/x0,.. •, xn/xQ)T = 0. Přenásobením xq 7^ 0 dostáváme ekvivalentní podmínku 6x0 + A(xi,..., xn)T = (b\ A) (x0,xi,xn)T = 0. Dostaneme tedy popis projektivního rozšíření T tak, že do soustavy zadávající T dosadíme (1, x\/xq, ..., xn/xo) = (xq : x\ : ••• : xn), přenásobením xq z ní uděláme opět lineární soustavu a zapomeneme na podmínku xq 7^ 0 (tím přesně přidáme nevlastní body - navíc je jasné, že tyto přidané body budou právě ty s xq = 0, tj. řešení homogenizované soustavy). 1.8. Vztah afinních zobrazení, lineárních zobrazení a kolineací Zabývejme se vztahem afinních zobrazení Am —> An a lineárních zobrazení Km+1 —> Kn+1. Zjevně, každé lineární zobrazení T: Km+1 —> Kn+1 s vlastností T(Am) C An dává po zúžení afinní zobrazení tp: Am —> -An. Budeme-li T psát blokově tvaru (1 + n) x (1 + m), pak T(1) = (k c\(l\ = (k + cx\( 1 \ \x J \b AJ\xJ \b + Ax) \b + Ax) a je vidět, že musí platit k = 1, c = 0. Naopak, nechť tp je afinní zobrazení. Potom * 0 = * (í) + ^ (x) = (ô) + (ax) = (6 + Ax) ' pokud vezmeme za b souřadnice p{eo) a za A matici p ve standardních bázích. Proto je tp zúžením lineárního zobrazení s maticí T = (5 ^) • Na cvičení ukážeme, že, je-li kolineace <í> reprezentována dvěma lineárními izomorfismy p, ip, pak platí ip = kip. Díky předchozí analýze je pak jednoduché vidět, že každá kolineace je reprezentována maximálně jedním afinním zobrazením a tento případ nastane, právě když <í> zachovává rozklad na vlastní a nevlastní podprostory. Ve výsledku tedy lze říct, že afinní zobrazení jsou kolineace zachovávající rozklad An = An U u(An). 2V takovém případě je T = 0 a tedy podle naší definice je T = 0. Z druhého pohledu je pak T = 0 s netriviálním zaměřením daném řešeními příslušně homogenní soustavy a T = T U u (T) = V(DirT). 10 1. Afínní a projektivní prostory Kontrolní otázky 1. Nechť V je reálny vektorový prostor. Definujte jeho komplexifikaci Vc. Ukažte na příkladu V = reálných polynomů stupně nejvýše 2. Co je Vc v tomto případě? 2. Vyslovte definici afinního prostoru a afinního zobrazení. Demonstrujte na několika příkladech. 3. Co jsou body projektivního prostoru Vnl Co jsou přímky v Vnl Mají každé dvě projektivní přímky v V3 neprázdný průnik? 4. Vysvětlete projektivní rozšíření afinní roviny a2 na projektivní prostor 7*2- Představujte si a2 jako rovinu v M3 zadanou v souřadnicích rovnicí xq = 1. Co jsou v tomto případě nevlastní body? Příklady k procvičení 1. Ke komplexnímu vektorovému prostoru V lze definovat konjugovaný prostor V takto: množinově V = V, sčítání vektorů je stejné jako ve V a násobení skalárem 0 definujeme předpisem (a + ib) 0 u = (a — ib) ■ u. Dokažte, že V je komplexní vektorový prostor. 2. Ke komplexnímu vektorovému prostoru V lze definovat jeho realifikaci VK takto: množinově VK = V, sčítání vektorů je stejné jako ve V a násobení reálným číslem je stejné. Nechť (ei,..., en) je báze V. Najděte nějakou bázi VK. [Řešení: Např. (ei,..., en,iei,..., ien).] 3. Dokažte, že pro reálný vektorový prostor V platí (Vcf ~v®v. 4. Dokažte, že pro komplexní vektorový prostor V platí (VR)C ~v®v. 5. Nechť íp: V —> W je lineární zobrazení mezi komplexními vektorovými prostory. Zobrazením tp je indukováno zobrazení Dokažte, že ip^ je lineární zobrazení mezi reálnými vektorovými prostory. 6. Jsou-li v prostorech V a W z předchozího příkladu zvoleny báze a = (e±,... ,en) a (3 = (ei,..., em), můžeme najít matice A a B takové, že matice zobrazení {ip)pa = A + iB. Zvolme v prostoru VK bázi aK = (ei,..., en,iei,... ,ien) a v prostoru WK bázi /3K = (ei,..., em, ie±,..., iem). Dokažte, že matice zobrazení 0 pro stejné třídy funkcí. V dalším nás bude nejvíce zajímat případ lineárních nerovnic ax+/3 > 0, kde používáme značení a G (Mn)*, (3 G M. Z tohoto pohledu neumíme rozlišit mezi množinou tří bodů v rovině a trojúhelníkem mající tyto tři body za vrcholy, protože tyto množiny splňují přesně tytéž lineární nerovnice -to si lze snadno rozmyslet, když si uvědomíme, že množina řešení nerovnice je polorovina, a že tyto dvě množiny leží ve stejných polorovinách (přesněji pokud v nějaké polorovině leží trojice bodů, bude v ní automaticky ležet i celý trojúhelník). Přitom trojúhelník je v jistém smyslu speciální, protože to je celá množina řešení jistého systému nerovnic. Situace se snadno popíše pomocí tzv. Galoisovy konexe. Zásadní výsledek, i když velmi snadný, je, že vždy dostáváme bijekci mezi množinami řešení na straně jedné a množinami vztahů na straně druhé. Tato dualita bude v našem výkladu hrát zásadní roli a lze ji velice hezky ilustrovat na předchozím příkladu. Viděli jsem, že pokud tři body patří do množiny řešení systému lineárních nerovnic, bude tam ležet i celý trojúhelník jimi "generovaný". Naopak trojúhelník lze zadat třemi nerovnicemi vyjadřujícími náležitost do tří polorovin určených jednotlivými hranami trojúhelníka. Samozřejmě bude trojúhelník splňovat také spoustu dalších nerovnic, ale ty budou opět "generovány" těmi zmíněnými třemi. Trojúhelník tedy lze zadat třemi body nebo třemi nerovnicemi. Ve vyšších dimenzích už tyto počty nebudou totožné, ale vždy bude platit, že daný útvar lze zadat konečným počtem bodů, právě když jej lze zadat konečným počtem lineárních nerovnic a takovéto útvary budeme nazývat polyedry. Zabývejme se nyní krátce tím, jak vypadají polyedry dimenze 2. S výjimkou celé roviny se jedná o mnohoúhelníky s tím, že některé vrcholy můžou ležet "v nekonečnu"; například (konvexní) úhel je trojúhelník mající dva vrcholy v nekonečnu. Jestliže k rovině přidáme body v nekonečnu (půjde o jisté projektivní rozšíření), můžeme pak s body v nekonečnu nakládat stejně jako s ostatními body a situace se stane homogenní; po pravdě se opravdu stanou definující rovnice homogenní, jak časem uvidíme. Protože je tato homogenní situace výrazně jednodušší, začneme prvně s ní a budeme tedy zkoumat podmnožiny W1 skrze homogenní lineární nerovnice, které tato podmnožina splňuje. Začneme s Galoisovou konexí, která je sice poměrně snadným pojmem, ale bude i přesto velmi užitečná. Definice 2.1. Galoisova konexe je dvojice zobrazení F: A < > B :G mezi uspořádanými množinami A, B, splňující: 12 2. Polyedry a lineární programování • a < a' =4> Fa > Fa', • b Gb', • a < GFa, • b < FGb. První dvě podmínky říkají, že obě F, G obrací uspořádání, pro vysvětlení zbylých dvou budeme prvky v obrazu G nazývat G-uzavřené a prvky v obrazu F pak F-uzavřené. Pro a G A je GFa tedy G-uzavřený, nyní ukážeme, že je dokonce nejmenší G-uzavřený nad a: nechť tedy a < Gb, pak b < FGb < Fa a nakonec a < GFa < Gb. Budeme tedy říkat, že GFa je G-uzávěr a, složení GF budeme nazývat uzáverový operátor a zejména vidíme, že a je G-uzavřený, právě když GFa = a. Lemma 2.2. Galoisova konexe se zužuje na bijekci mezi G-uzavřenými a F-uzavřenými prvky. □ 2.1. Polyedrální kužely Prvně se budeme zabývat homogenní situací, tedy homogenními lineárními nerovnicemi. Uvažme následující Galoisovu konexi (—)°: {podmnožiny U} < 1 {podmnožiny U*} :( —)° posílající podmnožinu X C U na množinu všech homogenních lineárních nerovnic, které tato podmnožina splňuje, přesněji 1° = {a G U* I Vx G X: ax > 0} Zobrazení v opačném směru je definováno zcela analogicky: přiřadí systému A lineárních nerovnic množinu řešení tohoto systému, A° = {x G U I Va G A: ax > 0}. Evidentně (—)°-uzavřené podmnožiny, tj. prvky obrazu ( —)°, jsou právě množiny řešení systémů homogenních lineárních rovnic a ( —)°-uzávěr množiny X je pak množina X°° řešení systému všech homogenních nerovnic, které X splňuje. O něco přehledněji je množina řešení jedné nerovnice poloprostor procházející počátkem a X°° je tedy průnik všech poloprostorů procházejících počátkem, ve kterých X leží. Následující tvrzení poměrně snadno charakterizuje ( —)°-uzavřené množiny, v dalším jej ale nebudeme používat. Tvrzení 2.3. Podmnožina X C U je ( —)° -uzavřená, právě když je X uzavřená na nezáporné lineární kombinace a zároveň uzavřená ve smyslu topologie? 3Zjevně každá množina řešení A0 je uzavřený konvexní kužel (například je to průnik poloprostorů 0 13 2. Polyedry a lineárni programování Množinám uzavřeným na nezáporné lineární kombinace budeme říkat konvexní kužely. Definujme coneX = {t\Xi + ■ ■ ■ +tnxn \ n > 0, X{ G X, ti > 0}, tj. množinu všech nezáporných lineárních kombinací prvků (pro n = 0 dostaneme 0 G coneX). Množina X je tedy konvexní kužel, pokud X = cone X. Podle předchozího tvrzení se Galoisova konexe zužuje na bijekci {uzavřené konvexní kužely v U} = {uzavřené konvexní kužely v U*}, v dalším nás ale budou zajímat jen ty konvexní kužely, které jsou v nějakém smyslu konečné a které budou zjevně (—)°-uzavřené. Definujme %-kužel jakožto množinu tvaru A° pro libovolnou konečnou množinu A, tedy jakožto množinu řešení konečného systému homogenních lineárních nerovnic. Definujme dále V-kužel jakožto množinu tvaru X°° pro nějakou konečnou množinu X; jedná se tedy o nejmenší (—)°-uzavřenou množinu obsahující X a je tedy v jistém smyslu generovaná konečnou množinou X - následující věta tuto situaci popíše konkrétně. Evidentntě pak dostáváme zúžením Galoisovy korespondence bijekce {V-kužely v U} 2á {^-kužely v U*} {^-kužely v U} 2á {V-kužely v U*} Věta 2.4. Následující podmínky jsou ekvivalentní: 1. C je V-kužel, 2. C = coneX pro nějakou konečnou množinu X, 3. C = X°° pro nějakou konečnou množinu X, tj. C je Tí-kužel. Množinám tohoto tvaru budeme říkat polyedrální kužely. Pro důkaz bude zcela zásadní tzv. Motzkinova eleminace, kterou lze teoreticky použít i k řešení soustavy nerovnic - konkrétně ji lze použít k rozhodování, zda daný systém má nějaké řešení. Uvažujme soustavu homogenních lineárních nerovnic bt + Ax > 0 v proměnných t, xi,..., xn jako soustavu nerovnic v jedné proměnné t a považujme tedy x±,..., xn za parametry. Budeme zkoumat, kdy má tato soustava řešení. Jednotlivé nerovnice v systému rozdělíme podle koeficientu fy: fyt + CLiX > 0 Pokud fy = 0, je tato nerovnice ekvivalentní cijX > 0. Pokud (3^ > 0, je tato nerovnice ekvivalenntí t > — a/t/Ä • x. Pokud fy < 0, je tato nerovnice ekvivalenntí t < —ai/fy ■ x. Zjevně lze systém skládající se z posledních dvou typů nerovnic vyřešit vzhledem k t, právě když každá horní mez je větší nebo rovna každé dolní mezi, tj. -ai/fy ■ x > -ak/f3k ■ x nebo ekvivalentně ( 0. (v opačném případě by vzdálenost x + tx od u byla pro malé t > 0 menší než vzdálenost žodu), takže a G X0, přitom au = (x — u, u) < (x — u, x) = 1/2 ■ ^ | (tx — u,ťx — u) = 0 (v opačném případě by vzdálenost tx od u byla pro t blízko 1 menší než vzdálenost x od u), takže u nesplňuje au > 0 a tedy u £ X"". 14 2. Polyedry a lineární programování Společně s nerovnicemi prvního typu, tj. cijX > 0, dostáváme soustavu A'x > 0, pro níž platí: pro každou volbu parametru x má původní soustava bt + Ax > 0 nějaké řešení t, právě když platí A'x > 0. Symbolicky: 3t:bt + Ax>0 <3> A'x > 0. Poslední formulace říká, že lze Motzkinovu eliminaci považovat za tzv. eliminaci (existenčních) kvantifikátorů, protože pro danou formuli s existenčním kvantifikátorem najdeme ekvivalentní formuli bez kvantifikátoru, přičemž iterací lze samozřejmě odstranit libovolný konečný počet existenčních kvantifikátorů. Důkaz. Prvně ukážeme 2 =4> 3. Nechť tedy X = {x±,... ,Xk}, pak coneX je zjevně množina těch x, které splňují formuli 3ti ■ ■ ■ 3tk: x = t±xi + • • • + tfcXfc, ti > 0,..., t k > 0 Protože je však tato formule ekvivalentní formuli Ax > 0 díky Motzkinově eliminaci, jedná se o %-kužel. Nyní ukážeme 1 => 2, přesněji pro konečnou množinu X dokážeme X°° = coneX. Protože je X°° nejmenší množina tvaru A° obsahující X, stačí ukázat, že coneX splňuje totéž. Podle právě dokázané implikace 2 =4> 3 je coneX tvaru A° (navíc pro konečnou množinu A). Zároveň je každá množina tvaru A° uzavřená na nezáporné lineární kombinace, takže pokud obsahuje X, musí obsahovat i coneX a tím pádem je coneX nejmenší. Implikace 3 1 je jednoduchou aplikací duality a již dokázané implikace 1 2 3, totiž C je %-kužel C° je V-kužel => C° je %-kužel C je V-kužel. □ Důsledek 2.5 (Farkasovo lemma pro kužely). Nechi C: Ax > 0 je polyedrální kužel. Pak C splňuje lineární nerovnici cx > 0, právě když je tato nezápornou lineární kombinací generujících nerovnic, tj. c = y A pro nějaké y > 0. Důkaz. Podle předpokladu platí C = A°, kde A nyní bereme jako množinu řádků matice A, tedy jako podmnožinu A C U*. Jestliže C splňuje cx > 0, pak c G C° = A°° = coneA, protože je A konečná. To ale přesně znamená, že c je nezápornou lineární kombinací řádků matice A. □ 2.2. Polyedry Uvažujme U jako podprostor {1} x U C M x U se souřadnicemi t na M a x na U, tedy jako podprostor {t = 1}. Zjevně řešení systému b + Ax > 0 jsou právě průniky {bt + Ax > 0} n {t = 1} polyedrálních kuželů s nadrovinou {t = 1}. Takovým podmnožinám budeme říkat polyedry. Zabývejme se nyní podrobněji zobrazením {kužely v M x U} —> {polyedry v U} daným právě průnikem s {t = 1}. Označme pro jednoduchost C\ = C n {t = 1}, v dalším budeme potřebovat také Co = C D {t = 0}. Je-li polyedr P obrazem kuželu C, pak zřejmě P = Ci C C, takže P°° C C a následně P c (P°°)! c Ci 15 2. Polyedry a lineárni programování a protože P = C\, dostáváme P = (P°°)i. Máme tedy přirozeného kandidáta na inverzní zobrazení, totiž P i—> P°°. Zřejmě kužely tohoto tvaru budou obsaženy v t > 0, protože celý prostor {t = 1} je v tomto poloprostoru obsažen. Navíc, pokud P 7^ 0, není P°° zcela obsažen v {t = 0}. Budeme tedy říkat, že kužel C je kladný, pokud C C {t > 0}, C % {t = 0}. Ve zbylém případě P = 0 je pak P°° = 0. Kladným kuželům společně s nulovým budeme říkat nezáporné. Věta 2.6. Zobrazení C *—> C\ je bijekce {nezáporné kužely ulx U} —> {polyedry v U} s inverzí P i—> P°°. Důkaz. Již jsme ukázali, že pro polyedr P platí P = (P°°)i, zbývá tedy dokázat C = pro nezáporné kužely C. Protože se jedná o ( —)°-uzavřené množiny, je toto ekvivalentní C° = C\, přičemž implikace =4> je triviální. Nechť tedy cx > 0 platí na C\ a ukážeme, že platí i na C. Protože každý prvek C s t > 0 je kladným násobkem prvku z C\ bude nerovnice cx > 0 pro takové prvky splněna a zbývá vyřešit případ v G Co- Nechť xq £ Ci je libovolný bod. Pak xq + Xv G Ci pro libovolné A > 0 a musí tedy platit c(xq + Xv) > 0 pro libovolné A > 0 a tedy jistě cv > 0, takže v také splňuje uvažovanou nerovnici. □ Nyní vysvětlíme, jak popsat polyedry pomocí V-kuželů. Protože je V-kužel obsažen v t > 0, můžeme jeho generující vektory psát jako (1, x i) nebo (0, Vj). Jejich nezáporná kombinace leží v {t = 1}, právě když je tvaru Aixi H-----h Xkxk + ii^i H-----h íz«z, kde Ai + • • • + Afc = 1 a všechny koeficienty jsou nezáporné. Jedná se tedy o součet konvexního obalu convjxi,... ,xk} bodů a konvexního kužele conej^i,... ,vi} vektorů. Druhá množina je pak zároveň průnikem s {t = 0} a lze ji tedy považovat za "zaměření" polyedru. Poznámka. Podmnožina conv X = {Xixi H-----h XkXk \X\-\-----h Afc = 1, A« > 0} je nejmenší konvexní podmnožina obsahující X, tj. nejmenší podmnožina uzavřená na konvexní kombinace (nezáporné se součtem koeficientů 1). Platí totiž, že konvexní kombinace konvexních kombinací je opět konvexní. Navíc lze každou takovou dostat iterováním konvexní kombinace pro dva prvky, kde Xx + py = x + p{y — x) jsou přesně body úsečky xy, protože p G [0,1], takže podmnožina je konvexní, právě když s každými dvěma body obsahuje i příslušnou úsečku. Uvažujme nyní kladný polyedrální kužel C: Ax > bt. Průnikem s {t = 1} tak dostaneme polyedr P: Ax > b. Naopak, každá neprázdná množina tohoto tvaru dostaneme jako C\ pro kladný kužel C: Ax > bt, t > 0. Díky jednoznačnosti platí P°° = C a tedy nerovnice, které P splňuje jsou právě nezáporné lineární kombinace Ax > bt, 0 > —t, což můžeme díky t = 1 přepsat jako nezáporné lineární kombinace Ax >b,0x> -1, tedy lineární nerovnice, které P splňuje jsou právě nezáporné kombinace generujících nerovnic a triviální nerovnice 0 > — 1. 16 2. Polyedry a lineární programování Tvrzení 2.7 (Farkasovo lemma pro polyedry). Polyedr P: Ax > b je prázdný, tj. soustava Ax > b nemá řešení, právě když nezápornou lineární kombinací nerovnic z Ax > b lze vyrobit 0 > 1. Důkaz. Soustava nemá řešení, právě když kužel C: Ax > bt má prázdný průnik s {t = 1}, tj. právě když leží v 0 > t. To je ale právě když je 0 > t nezápornou lineární kombinací nerovnic z Ax > bt. Tvrzení se dostane dosazením t = 1. □ 2.3. Afinní obal polyedru Lemma 2.8. Nechi P: Ax > b je neprázdný polyedr. Pak jsou následující podmínky ekvivalentní: 1. P nesplňuje žádnou netriviální rovnici. 2. P nesplňuje žádnou netriviální nerovnici z Ax > b jako rovnici. 3. Existuje bod P splňující všechny netriviální nerovnice v Ax > b ostře. Zjevně první podmínka znamená, že P neleží v žádném vlastním afinním podprostoru, tedy že afinní obal P je celý prostor U. V takovém případě řekneme, že dimenze P je rovna dimenzi U. Body z podmínky 3 nazveme vnitřní body polyedru P, takže budeme říkat, že P je polyedr s neprázdným vnitřkem. Obecně lze uvažovat P uvnitř svého afinního obalu, kde podmínky již splněny budou (některé nerovnice se po zúžení na afinní obal stanou triviálními) a dimenze P je pak rovna dimenzi tohoto afinního obalu. Vnitřní body P chápaného jako podmnožinu svém afinním obalu nazveme relativně vnitřní. Snadno se ukáže, že každý bod je relativně vnitřním bodem právě jedné stěny (a každá neprázdná stěna má nějaký relativně vnitřní bod), totiž stěny určené všemi nerovnicemi z Ax > b, které jsou v daném bodě splněné jako rovnice. Ostatní jsou splněny ostře, takže podle lemmatu je bod relativně vnitřním bodem této stěny. Je tedy každý polyedr disjunktním sjednocením relativních vnitřků stěn. Důkaz. Budeme předpokládat, že všechny nerovnice v Ax > b jsou netriviální. Implikace 1 =4> 2 je zřejmá. Pro implikaci 2 =4> 3 předpokládáme, že každá nerovnice ajX > /3j systému Ax > b je v nějakém bodě x;t £ P splněna ostře. Potom barycentrum \x\ + • • • + \xk bude všechny nerovnice splňovat ostře. Zbývá 3 1. Budeme ekvivalentně dokazovat, že žádná netriviální nerovnice není na P splněna jako rovnice. Uvažme tedy nerovnici cx > S, která je splněna na P a musí tedy být nezápornou lineární kombinací nerovnic z Ax > b, Ox > —1. Pokud je navíc netriviální, musí být nějaký koeficient nenulový. Každý bod splňující jednotlivé nerovnice ostře, jehož existence je zaručena podle 3, bude splňovat ostře i nerovnici cx > S a tato nerovnice tedy nemůže být na P splněna jako rovnice. □ 2.4. Stěny polyedrů Nechť cx > S je lineární nerovnice, kterou polyedr P splňuje. Potom průnik P s podprostorem cx = S nazveme stěnou polyedru P. Dva speciální případy nerovnic, které P splňuje jsou Ox > —1, Ox > 0, které odpovídají stěnám 0, P. 17 2. Polyedry a lineárni programování Nechť nyní P: Ax > b. Již víme, že cx > S platí na P, právě když je nezápornou lineární kombinací nerovnic ze systému Ax > b a Ox > — 1. Jestliže má být průnik polyedru P s podprostorem cx = S neprázdný, jistě nebude poslední nerovnice v kombinaci vystupovat. Navíc pokud cx > S je kombinací, ve které vystupují s nenulovými koeficienty právě řádky o-íX > fy, řekněme s koeficienty Aj > 0, pak pro libovolné x £ P platí cx = S 4^ Ví : diX = fii (jinak by musela platit pro nějaké i nerovnost a^x > /3« a protože je nerovnice brána s kladným koeficientem, bylo by i cx > 5). Je tedy obecná stěna dána tím, že některé z nerovnic systému Ax > b nahradíme rovnicemi. Lemma 2.9. Nechi P: Ax > b je polyedr s neprázdným vnitřkem. Předpokládejme, že žádná nerovnice systému Ax > b není nadbytečná (tj. důsledkem zbylých nerovnic). Potom přiřazení {nerovnice systému Ax > b} —> {stěny P kodimenze 1}, posílající nerovnici ax > (3 na stěnu P n {ax = /3}, je bijekce. Důkaz. Prvně ukážeme, že je zobrazení dobře definované, tedy že pro každou nerovnici ax > (3 systému je příslušná stěna kodimenze 1, tedy že má uvnitř nadroviny {ax = /3} neprázdný vnitřek. Označme podsoustavu vzniklou odstraněním nerovnice jako A'x > b'. Protože má P neprázdný vnitřek, existuje z splňující A'z > b', az > (3. Protože není naše nerovnice nadbytečná, musí existovat bod y splňující A'y > b', ay < (3. Vhodnou kombinací y, z s kladnými koeficienty dostaneme bod x splňující A'x > b', ax = /3, jedná se tedy o vnitřní bod stěny P n {ax = /3}. Každá stěna je dána nahrazením některých nerovnic systému příslušnými rovnicemi. Pokud by byly alespoň dvě, příslušný afinní prostor by měl kodimenzi alespoň dvě a stěna by nemohla mít kodimenzi 1. Je tedy zobrazení surjektivní. Každá stěna kodimenze 1 má jako afinní obal afinní nadrovinu a protože má P neprázdný vnitřek, leží P právě v jednom poloprostoru určeném touto nadrovinou. Je tedy nerovnice zadávající stěnu určena jednoznačně až na kladný násobek. Díky nenadbytečnosti je v systému maximálně jedna taková nerovnice. Je tedy zobrazení injektivní. □ Z důkazu je navíc zřejmé, že nenadbytečné nerovnice jsou jednoznačné až na kladný násobek (formulace analogického výsledku pro polyedry s prázdným vnitřkem je výrazně složitější). Důsledek 2.10. Minimální (tj. minimální neprázdné) stěny jsou afinní podprostory. Je-li polyedr P: Ax > b, jsou minimální stěny tvaru {A'x = b'}, kde A'x > b' je podsystém Ax > b. Důkaz. Každá stěna je dána nahrazením některých nerovnic systému příslušnými rovnicemi. Označme podprostor určený těmito rovnicemi U' C U. Pokud je stěna minimální, musí být zbylé nerovnice triviální na U', jinak by existovala nějaká nenadbytečná a ta by určovala nějakou stěnu. Jestliže jsou však ostatní nerovnice nadbytečné, je celé U' stěnou. Navíc vidíme, že je U' prostor řešení systému rovnic určeného podsystémem Ax > b. Poznamenejme, že z toho, že další nerovnice musí být na U' triviální, snadno plyne, že každá minimální stěna má zaměření {Ax = 0}, zejména je tedy stejné pro všechny minimální stěny. □ 18 2. Polyedry a lineární programování Polyedr, jehož minimální stěny jsou body se nazývá bodovaný a jeho minimální stěny se nazývají vrcholy. Samozřejmě každý neprázdný polyedr obsahuje nějakou minimální stěnu, zejména každý neprázdný bodovaný polyedr obsahuje vrchol. Vrcholy jsou dány jako řešení (některých) systémů n nezávislých rovnic A'x = b' jako v důsledku. Příklad. Každý polyedr {Ax = b, x > 0} je bodovaný, protože neobsahuje přímku. Vrcholy jsou {Ax = b, z = 0}, kde z jsou některé souřadnice x; ne každá volba určuje vrchol. Pokud má systém Ax = b nezávislé řádky, můžeme souřadnice brát tak, že systém Ax = b, z = 0 má n řádků a hodnost n. Jsou tedy vrcholy popsány (obecně nejednoznačné) některými {n — k)-prvkovými podmnožinami M C {l,...,n}, kde k je hodnost matice A. To nám výrazně zjednoduší počítání s vrcholy. Poznámka. Polytop je polyedr tvaru P = conv J pro X konečnou množinu bodů. Platí, že prvky X, které nejsou nadbytečné, jsou právě vrcholy P: Díky nenadbytečnosti y ^ conv(X \ {y}). Existuje tedy nějaká nerovnice cx > S, která je splněna na conv(X \ {y}), ale nikoliv na y, tj. cy < S. Potom cx > cy je nerovnice, kterou splňuje P, a přitom příslušná stěna P n {cx = cy} je tvořena právě bodem y, takže se jedná o vrchol. Naopak pokud by vrchol y, zadaný nerovnicí cx > S, byl kombinací zbylých vrcholů polyedru, musely by tyto také ležet na opěrné nadrovině cx = S, takže by příslušná stěna obsahovala víc bodů a nejednalo by se o vrchol. Nenadbytečné generující body tedy odpovídají vrcholům, nenadbytečné generující nerovnice odpovídají stěnám - pěkný příklad duality. 2.5. Úloha lineárního programování Jde o úlohu minimalizovat (nebo maximalizovat) lineární funkci cx na polyedru P: Ax > b. Úlohu budeme zapisovat Stejný zápis samozřejmě značí minimální hodnotu této funkce, nám však půjde o to najít bod x £ P, v němž minimum nastává. Poznamenejme, že z vyjádření P = conv J + coneV a z linearity funkce cx vyplývá, že obraz cP C M je opět polyedr, tedy uzavřený interval. Máme tři možnosti - buď je obraz prázdný, to nastane právě když je P prázdný, nebo je zdola neomezený nebo má minimum S. V posledním případě je množina všech bodů ve kterých nastává minimum {cx = S} D P a jedná se tedy o (neprázdnou) stěnu polyedru, neboť cx > S na P. Pokud je polyedr P bodovaný, nastává minimum nutně v nějakém vrcholu. Toho využívá metoda pro nalezení optima, tzv. simplexová metoda. Uvedeme dva speciální případy, které jsou ekvivalentní úloze v obecném tvaru, ale zároveň jsou velmi důežité - jednak kvůli dualitě a jednak kvůli simplexové metodě. Následující typy úloh jsou ekvivalentní: Tím je myšleno, že pro každou úlohu prvního typu umíme sestrojit úlohu druhého typu, z jejíhož řešení umíme vyrobit řešení v původní úloze, atd. Ukážeme nyní tedy redukce prvního typu na druhý a druhého na třetí. V opačných směrech není potřeba úlohu měnit, protože se minjcx | Ax > b}. minjcx minjcx minjcx Ax > b} Ax > b, x > 0} Ax = b, x > 0} 19 2. Polyedry a lineárni programování jedná o postupně speciálnější tvary. Pro úlohu minjcx | Ax > b} nahradíme neznámý vektor x rozdílem dvou nezáporných vektorů, x = x+ — X-, kde tedy > 0. Dostaneme tak úlohu minjcx | Ax > b} ~ min{cx+ — cx_ | Ax+ — Ax_ > b, x+, x_ > 0} druhého typu, řešení původní úlohy se dostane jako x = x+ — X-. Pro úlohu minjcx | Ax > b,x > 0} zavedeme substituci s = Ax — b > 0, čímž nerovnici Ax > b nahradíme rovnicí Ax — s = b, kde tedy s > 0 (tzv. přebytek). Dostaneme tak úlohu minjcx | Ax > b, x > 0} ~ minjcx | Ax — s = b, x, s > 0} třetího typu, řešení původní úlohy se dostane zapomenutím s. 2.6. Dualita v lineárním programování Nejjednodušší je: minjcx | Ax > b} lze popsat jako největší dolní závoru, přičemž S je dolní závora, pokud Ax > b =ŕ cx > S, takže podle Farkasova lemmatu to nastane, právě když je cx > S nezápornou lineární kombinací Ax > b (také bychom mohli použít Ox > —1, tím bychom ale dostali menší dolní závoru, takže ignorování této nerovnice maximum nezmění). minjcx | Ax > b} = max{S \ 3y > 0: c = y A, S = yb} = max{yb \ c = y A, y > 0} Duálně samozřejmě minjcx | Ax = b, x > 0} = max{yb \ c > yA}. Uveďme ještě symetričtější verzi pro prostřední typ úlohy lineárního programování: minjcx | Ax > b, x > 0} = max{S \ 3y > 03z > 0: c = y A + zE, S = yb + ^0} = max{yb \ 3z > 0: c = y A + z, y > 0} = max{yb \ c > y A, y > 0} (přitom lze elementárně vidět, že každé yb je menší nebo rovno každému cx, takže stejná nerovnost bude platit i pro maximum a minimum: yb < y{Ax) = {yA)x < cx). 2.7. Simplexová metoda Prvně uveďme metody, které sice fungují, ale nejsou příliš efektivní. Zaprvé lze Motzkinovou eliminací popsat obraz P při zobrazení cx, tj. popsat množinu {S | 3x: cx = S, Ax = b, x > 0}. Bude se jednat o interval a jeho minimum je právě minimum úlohy. K němu pak lze opět Motzkinovou eliminací nalézt nějaké řešení. Druhou metodou je prvně sestavit seznam všech vrcholů a poté porovnat funkční hodnoty v nich. K tomu lze použít popis vrcholů jakožto řešení soustav Ax = b, z = 0, kde z je nějaká podmnožina proměnných x, viz níže. Budeme předpokládat úlohu ve tvaru minjcx | Ax = b, x > 0}, kde o soustavě rovnic Ax = b budeme navíc předpokládat, že jsou z ní odstraněny nadbytečné rovnice, takže její hodnot je rovna počtu řádků k. Položme n = k + l, tedy l je dimenze podprostoru {Ax = b}. 20 2. Polyedry a lineární programování Vrcholy polyedru P: Ax = b, x > 0 budeme popisovat množinou indexů, pro které xí = 0. Pišme souhrnně tyto proměnné jako z a zbylé proměnné jako y. Protože předpokládáme, že podprostor {Ax = b, z = 0} má dimenzi 0 (jedná se o vrchol) a soustava Ax = b má lineárně nezávislé řádky, můžeme případným zredukováním proměnných z dosáhnout toho, že je těchto právě l a tedy proměnných v y je právě k. Soustavu Ax = b pak lze upravit do ekvivalentního tvaru y + Az = b, tj. rozřešit ji vzhledem k proměnným y, konkrétně y = b — Az. V takovém případě je vrcholem právě (y,z) = (6,0). Pak lze ale také lineární funkci cx na podprostoru Ax = b napsat pouze v proměnných z (dosazením y = b — Az). Lemma 2.11. Pokud má vyjádření cx pomocí z všechny koeficienty nezáporné, je vrchol (6, 0) bodem, ve kterém nastává minimum. Předpokládejme tedy dále, že koeficient u zq je záporný, označme zbylé proměnné z'', pak pro zq > 0, z' = 0 dostaneme bod s menší funkční hodnotou. Uvažme tedy přímku {Ax = b, z' = 0}. Ta protíná polyedr P v hraně, jejímž jedním vrcholem je bod (6, 0). Každá nerovnice y i > 0 zadává omezující podmínku na zq: y + aqzq + A z = b vzhledem k z' = 0 dává yi + onqzq = /3j, tedy Pokud aiq ií 0, nedává tato rovnice na zq žádné omezení shora, budeme tedy v dalším uvažovat pouze ty rovnice s ctiq > 0, kdy tato rovnice je ekvivalentní zq < fiijaiq. Lemma 2.12. Pokud jsou všechna ctiq < 0, je hrana neomezená a funkce cx podél ní klesá, takže nenabývá minima. Předpokládáme tedy, že nějaké ctiq > 0 a mezi nimi vyberme index p, pro který je poměr /3p/apq minimální. Pak druhým vrcholem hrany je zq = /3p/apq a tedy yp = 0. Dostaneme tedy nový vrchol tak, že v proměnných y nahradíme yp za zq. Obě volby indexů p, q jsou nejednoznačné. Pokud bude v každém kroku /3 > 0, hodnota se vždy zmenší a vzhledem ke konečnému počtu vrcholů se algoritmus zastaví. Toto nastane pro nedegenerované polyedry, tj. polyedry, ve kterých se v každém vrcholu potkává právě l stěn, tj. v každém vrcholu je nulových právě l souřadnic. Tato situace je obecná ve smyslu, že libovolně malou změnou pravé strany b lze dosáhnout nedegenerovanosti. V případě degenerovaného polyedru je třeba opatrnosti při výběru proměnných, jinak může dojít k zacyklení - v každém kroku měníme proměnné popisující vrchol, ale vlastní vrchol se nemění, přičemž po nějaké době opět dospějeme k téže množině proměnných. K zacyklení nedojde při použití tzv. Blandova pravidla, které říká, že máme volit q nejmenší možné a v rámci této volby také p nejmenší možné. Důkaz nezacyklení zde uvádět nebudeme. 2.8. Nalezení vrcholu Na započetí výpočtu je potřeba nalézt vrchol polyedru P: Ax = b, x > 0. To se nám podaří následující metodou. Případným vynásobením některých rovnic systému koeficientem — 1 můžeme předpokládat b > 0. Přidejme umělé proměnné t > 0 a uvažme pomocnou úlohu min{lí | Ax +1 = b, x > 0, t > 0}, 21 2. Polyedry a lineárni programování ve které li = íi + • • • +1 k je součet pomocných proměnných (tj. 1 reprezentuje řádek složený ze samých jedniček). Zjevně minimum takové úlohy bude existovat, protože je hodnota funkce zdola omezena nulou a pomocný polyedr obsahuje vrchol (x, i) = (0, b) zadaný rovnicemi x = 0. Protože pro pomocnou úlohu máme počáteční vrchol, můžeme na ni aplikovat simplexovou metodu. V případě, že nalezneme minimum větší než nula, dostaneme P = 0, v případě, že minimum bude nula, dostaneme bod polyedru P. Případnými dodatečnými kroky můžeme dosáhnout toho, že příslušný pomocný vrchol bude zadán rovnicemi z = 0, i = 0, kde z je tvořen některými z proměnných x jako předtím, takže se jedná také o vrchol polyedru P. 22 3. Nadkvadriky v afinním a projektivním prostoru 3.1. Definice nadkvadriky v reálném afinním prostoru Uvažujme reálný afinní prostor S s bází (O, e\, ..., en), pro jednoduchost můžeme předpokládat S = A n se standardní bazi. Nadkvadrikou v An rozumíme množinu Q C An všech bodů, jejichž souřadnice v dané bázi splňují rovnici n n ^ ciíjXiXj + 2 ^ aíOxí + aoo = 0, i,j=l i=l kde a,ij = a,ji G M a aspoň jedno 7^ 0 pro i, j G {1,..., n}. Nadkvadriky v A2 se nazývají kuželosečky, nadkvadriky v ^,3 kvadriky. Mnohé rovnice výše uvedeného typu (např. x\ + x\ + 1 = 0) nemají v reálném oboru řešení. Proto je výhodné místo s nadkvadrikami v An pracovat s nadkvadrikami v komplexním rozšíření Aft. Poznámka. Za chvíli uvidíme, že tato definice nezávisí na souřadnicích a ve skutečnosti lze provést ve vektorovém obalu afinního prostoru pomocí symetrické bilineární formy. 3.2. Definice nakvadriky v komplexním rozšíření afinního prostoru Uvažujme komplexní rozšíření Aft reálného afinního prostoru. Nechť (O, e±, ..., en) je nějaká báze An. Nadkvadrikou v A^ rozumíme množinu Q C A^ všech bodů, jejichž souřadnice v dané bázi splňují rovnici n n ^ ciíjXiXj + 2 ^ ai0Xi + a0o = 0, i,j=l i=l kde a,ij = a jí G M a aspoň jedno 7^ 0 pro i, j G {1,..., n}. Pro nadkvadriky v afinním prostoru chceme definovat takové pojmy jako střed, tečná nadrovina, asymptotická nadrovina, a to nejlépe v řeči koeficientů a^, aby nalezení těchto objektů bylo početně co nejjednodušší. To se nám podaří celkem snadno, když od afinního prostoru přejdeme k jeho projektivnímu rozšíření a od kvadriky Q C A% C A% k jejímu rozšíření Q C A%- Popišme nyní nadkvadriku Q v homogenních souřadnicích A%- Nechť tedy X = (xq : x\ : • • • : xn) G A%- Potom tento bod leží na Q, právě když X je vlastní, tj. xq 7^ 0 a pak X = (1 ~. — : • • • : ^IL), a navíc platí n n aij--- + 2 } ai0--h a00 = 0. . J x0 x0 ^—' x0 Po vynásobení xq 7^ 0 dostáváme ekvivalentní rovnici ^ aíjXiXj + 2 ^ ai0XiX0 + aoo^o = °- i,j = l i=l Množinu všech bodů A^, jejichž homogenní souřadnice splňují výše uvedenou rovnici, nazveme projektivním rozšířením nadkvadriky Q a budeme ji označovat Q. Množina Q může obsahovat i nevlastní body z v{A^) o souřadnicích (0 : x\ : ■ ■ ■ : xn). 23 3. Nadkvadriky v afínním a projektivním prostoru Položíme-li aoi = ciíq a A = (a^-)" -=0, je A nenulová symetrická matice typu (n+1) x (n+1). Výše uvedenou rovnici můžeme psát ve tvaru n i,j=0 Symetrická matice A definuje reálnou bilineární formu / na aritmetickém základu projektivního prostoru An předpisem n f(x> y) = 5ľ ai3xíV3 = xTAy- i,j=0 Blok matice A příslušný kladným indexům i > 0, j > 0 budeme označovat A, odpovídá kvadratické části původní rovnice. 3.3. Definice nadkvadriky v projektivním prostoru Nechť V (V) je reálný projektivní prostor dimenze n. Nechť / je nenulová reálná symetrická bilineární forma na V. Nadkvadrika Q v projektivním prostoru V{VC) je množina bodů [v] G V{VC), pro které f(v,v)=0. V souřadnicovém vyjádření v nějaké bázi V jde o řešení rovnice n X j^X — ^ Cl'íjOC'íOCj — 0, i,j=0 kde clíj = a jí G M a clíj 7^ 0 pro nějaké Důležitým aspektem je homogennost této rovnice, díky níž platnost této rovnice nezávisí na volbě reprezentanta. Poznámka. Nechť Q C je afinní nadkvadrika. Pak množina Q je nejmenší projektivní nadkvadrika, která obsahuje Q. Toto tvrzení není zcela triviální a přenecháváme jej čtenáři k věření. Lemma 3.1. Nadkvadrika Q v je rozšířením nějaké kvadriky v Aft právě tehdy, když existuje nějaký nevlastní bod X G u{A^), který v Q neleží. Důkaz. Nechť je projektivní nadkvadrika Q C zadána symetrickou bilineární formou / s maticí A. Potom Q není rozšířením afinní nadkvadriky, právě když je blok A nulový, tj. právě když je zúžení / na nevlastní podprostor nulové. To je ale právě tedhy, když je rovnice f(x,x) = 0 splněna pro všechny nevlastní body X = [x] G u{A^). □ 3.4. Vztah mezi nadkvadrikami a symetrickými bilineárními formami Nechť K,n je množina všech nadkvadrik v V^, nechť Bn je množina všech symetrických bi-lineárních forem na aritmetickém základu Mn+1. Protože se jedná o vektorový prostor, můžeme uvažovat příslušný projektivní prostor V{Bn) = {Bn \ {0})/~. Zobrazení ip: £>n \ {0} —> K.n, definované předpisem p(f) = {[x] G \ f(x,x) = 0}, indukuje zobrazení íp: V{Bn) —> fCn. 24 3. Nadkvadriky v afínním a projektivním prostoru Věta 3.2. Zobrazení tp: V{Bn) —> fCn je bijekce. Důkaz. Z definice existuje ke každé nadkvadrice příslušná bilineární symetrická forma, tedy íp je surjektivní zobrazení. Chceme dokázat, že je také injektivní, to znamená, že zadávají-li dvě bilineární symetrické formy / a g tutéž kvadriku, pak g = k ■ f pro nějaké k G M. Vezměme u G Mn+1 takové, že f (u, u) 7^ 0. Protože f a g zadávají tutéž kvadriku, je také g(u,u) 7^ 0. Můžeme proto psát g(u,u) = kf(u,u) pro nějaké 0 7^ k G M. Vezměme nyní libovolné v G Cn+1. Potom výrazy f (tu + v, tu + v) = t2 f (u, u) + 2tf(u, v) + f (v, v) g (tu + v,tu + v) = t2g(u, u) + 2tg(u, v) + g(v, v), chápané jako polynomy druhého stupně v proměnné t, mají podle předpokladů stejné kořeny íl, Í2- Z algebry víme, že koeficienty polynomů stejného stupně (v našem případě 2) a se stejnými kořeny musí být úměrné, proto ze vztahu g(u, u) = kf(u, u) plyne g(v, v) = k f (v, v). Protože vektor v byl volen libovolně, platí g = k ■ f. □ Poznámka. Podobné tvrzení platí také pro afinní nadkvadriky, konkrétně dvě kvadratické rovnice q(x) = 0, r(x) = 0 zadávají stejnou nadkvadriku, tj. mají stejnou množinu řešení, právě když r = k ■ q pro nějaké k G Mx. Důkaz se provede stejně jako v projektivním případě, jen je potřeba zvolit u nevlastní; pak se stejně ukáže, že g(x,x) = kf(x,x) pro x = (1, xi,..., xn) vlastní. To je ale přesně rovnice r(x) = kq(x). 3.5. Klasifikace nadkvadrik v projektivním prostoru Věta 3.3. Nechi Q C je naákvaárika. Potom v Mn+1 existuje báze, v níž je naákvaárika áva imaginární boáy áva reálné boáy ávojný boá imaginární regulární kuželosečka reálná regulární kuželosečka ávojice imaginárních přímek ávojice reálných přímek ávojnásobná přímka imaginární regulární kvaárika nepřímková regulární kvaárika přímková regulární kvaárika imaginární kuželová plocha reálná kuželová plocha imaginární ávojice rovin reálná ávojice rovin popsána právě jeánou z rovnic (a) pro n = 1 (b) pro n = 2 X0 + x2 = 0 x0 — x\ = 0 -y-. 2 x0 = 0 x0 + x\ + x2 = 0 x0 + x\ -y-. 2 x2 = 0 x0 + x2 = 0 x0 — x\ = 0 -y-. 2 x0 = 0 (c) pro n = 3 -y-. 2 x0 + x\ + x2 + x2 = 0 -y-. 2 x0 + x\ + x2 -x2 = 0 x0 + x2 — X2, — x3 = 0 x0 + x\ + x2 = 0 -y-. 2 x0 + x\ -y-. 2 x2 = 0 -y-. 2 x0 + x\ = 0 x0 — x\ = 0 25 3. Nadkvadriky v afínním a projektivním prostoru Xq = O dvojnásobná rovina Důkaz. Každá nadkvadrika je určena nějakou reálnou symetrickou bilineární formou / na aritmetickém základu Mn+1. Pro tuto formu lze nalézt vhodnou bázi Mn+1, v níž má / diagonální tvar s koeficienty ±1 nebo 0 na diagonále. Případným vynásobením číslem —1 dostaneme rovnici tvaru 2 i i 2 2 2 _ f\ Xq "T • • • T" Xp ' xp+q kde p, q > 0, p + l>q&p + q C je lineárni zobrazení, je buď im f (x, —) = 0 nebo C. Dále dimker f (x, —) = n + 1 — dimim/(x, —), což dává tvrzení lemmatu. □ Příklad (a). V P^ uvažujme kvadriku 2 i 2 2 2 _ r\ X-y ~\~ — U. Polárně sdružené body k bodu [(1,1, 0, y/2)\ mají homogenní souřadnice (y±,y2,2/3,2/4) a tvoří rovinu 0 = /((l, 1,0, y/2), (2/1,2/2,2/3,2/4)) = 2/1 +2/2 - VŽy4. 30 4. Metrická klasifíkace nadkvadrik Příklad (b). V uvažujme kuželosečku Polárně sdružené body k bodu [(0,0,1)] jsou všechny body "P^, neboť pro jejich homogenní souřadnice (2/1,2/2,2/3) platí 0 • 2/1 + 0 • 2/2 = 0. Definice 4.3. Bod [x] G V% se nazývá regulárním bodem vzhledem k nadkvadrice Q, jestliže množina polárně sdružených bodů k [x] je nadrovina v V^. Tato nadrovina se nazývá polární nadrovina (v "Pfp stručně polára). Definice 4.4. Bod [x] G V% se nazývá singulárním bodem nadkvadriky Q, jestliže množina polárně sdružených bodů k [x] je celý prostor V^ - (Speciálně platí [x] G Q.) Definice 4.5. Nadkvadrika Q v se nazývá regulární, jsou-li všechny její body regulární. Nadkvadrika se nazývá singulární, obsahuje-li nějaký singulární bod. nd Lemma 4.6. Nadkvadrika Q C je regulární právě tehdy, když hodnost symetrické matice A, která ji definuje v souřadnicích, je rovna n + 1. nd Důkaz. Hodnost A je rovna n + 1 právě tehdy, když xTA 7^ 0 pro každé x 7^ 0. To je ale ekvivalentní tomu, že existuje y 7^ 0 takové, že xTAy 7^ 0, neboli bod [x] je regulární. □ Lemma 4.7. Jestliže Q C je regulární nadkvadrika, pak součet dimenzí podprostoru U a jeho polárního doplňku je vždy n — 1 a platí = U. Říkáme, že to jsou podprostory komplementární dimenze. Důkaz. Pokud má aritmetický základ IÁ bázi (uq, ..., u^), pak jeho polární komplement má aritmetický základ popsaný soustavou d+1 rovnic f(uo, —) = ••• = f(ud, —) = 0. Tyto rovnice jsou lineárně nezávislé, protože jejich kombinace /(xqUq + • • • + x^u^, —) je nulová pouze pro xquq + • • • + XdUd = 0, tj. xq = ■ ■ ■ = Xd = 0, díky regularitě Q. Proto má aritmetický základ dimenzi n — d a v součtu pak mají U a dimenzi d + (n — d — 1) = n — 1. Druhé tvrzení plyne z prvního, protože zřejmě platí U C (ř/*)* a oba podprostory mají stejnou dimenzi. □ Lemma 4.8. Nechť Q C je nadkvadrika se singulárním bodem X. Jestliže Y 7^ X je dalším bodem nadkvadriky Q, pak v Q leží celá přímka XY*. Důkaz. Pro aritmetické zástupce x, y bodů X a Y a bilineární formu /, která definuje nad-kvadriku Q, platí f(x,x) = 0 a f(x,y) = 0, neboť [x] = X je singulární bod, a f(y,y) = 0, neboť [y] = Y G Q. Potom f(ax + by, ax + by) = a2f(x, x) + 2abf(x, y) + b2f(y, y) = 0. Tedy [ax + by] e Q. □ Speciální případ, kdy singulární bod [v] G v{A^) je nevlastní, má následující geometrickou interpretaci: s každým bodem Y G Q obsahuje nadkvadrika Q i celou přímku procházející Y se směrovým vektorem v. 31 4. Metrická klasifíkace nadkvadrik 4.2. Tečná nadrovina Na základě předchozí motivace můžeme vyslovit následující definici. Definice 4.9. Tečná nadrovina nadkvadriky Q C v regulárním bodě X 6 Q je polární nadrovina k X. Věta 4.10. Nadrovina r v je tečnou nadrovinou k nadkvadrice Q v regulárním bodě X £ Q právě tehdy, když tCQ nebo r CiQ je singulární kvadrika v r se singulárním bodem X. Důkaz. Nechť r je tečná nadrovina v bodě X = [x], r = {[y] \ f(x,y) = 0}. Pak Q flr = {[y] 6 r | f(y,y) = 0} a máme dvě možnosti - buď je zúžení / na aritmetický základ r nulové, pak je r C Q, nebo nenulové, pak je Q n r opět nadkvadrika a přímo podle definice je X její singulární bod Q. Opačný směr je analogický. □ Důsledek 4.11. Přímka p je tečnou ke kuželosečce Q právě tehdy, když p C Q nebo p(~]Q je jednobodová množina (čítaje nevlastní body, viz případ osy paraboly nebo přímky mající směr asymptoty hyperboly). □ Příklad. Najděte tečnu kuželosečky Q v bodě IeQ. Q:8xl+ 4Xlx2 + bx22 + 16xi + 4x2 - 28 = 0, X = [0; 2] Řešení. Daná kuželosečka je zadána v afinní rovině. Rozšíříme ji prvně na projektivní rovinu. V této rovině je bilineární forma kuželosečky Q f(x, y) = Sxiyi + 2xiy2 + 2x2yi + 5x2y2 + 8xiy0 + 8x0yi + 2x2y0 + 2x0y2 - 28x0y0. Bod X má homogenní souřadnice x\ = 0, x2 = 2, a?o = 1. Jeho dosazením do f(x,y) získáme rovnici tečny v homogenních souřadnicích: 12yi + 12y2 - 24y0 = 0. V afinní rovině je tečnou vedenou bodem X ke kuželosečce Q přímka 2/1+2/2-2 = 0. o Příklad. Bodem X 0 Q veďte tečnu ke kuželosečce Q. Q:2x\- 4xix2 + x2 - 2xx + 6x2 - 3 = 0, X = [3; 4] Řešení. Kuželosečku Q zadanou v afinní rovině rozšíříme na kuželosečku Q v projektivní rovině. Příslušná bilineární forma pro Q je f(x, y) = 2x\y\ - 2x\y2 - 2x2y\ + x2y2 - xiy0 - x0yi + 3x2y0 + 3x0y2 - 3x0y0. Nechť T = (to,ti,t2) je bodem dotyku hledané tečny. Tedy T £ Q a T a X jsou polárně sdružené. To vede na rovnice 2t\ - 4txt2 + t\ - 2íií0 + 6í2ío -3ÍQ = 0 -3íi + í2 + 6í0 = 0 32 4. Metrická klasifíkace nadkvadrik Dosazením 12 = 3íi + 6ío do první rovnice dostaneme -t\ - 3Íq + 4íií0 = 0. Položíme íq = 1 a, řešíme rovnici -t\ + 4íi - 3 = 0. Řešení íi = 3 a 1 vede k bodům T\ = (1, 3, 3) a T2 = (1,1, —3). Hledané tečny jsou potom x\ — 3 = 0 a 7a; 1 — 2a?2 — 13 = 0. o 4.3. Střed nadkvadriky v afinním prostoru V tomto paragrafu budeme pracovat s nadkvadrikou Q v afinním prostoru Aft a s jejím projektivním rozšířením Q v A%- Body z Q \ Q nazýváme nevlastní body nadkvadriky Q. Obecně pak o bodech z v{A^) budeme hovořit jako o směrech. Definice 4.12. Bod S G A% se nazývá střed nadkvadriky Q, jestliže je polárně sdružen se všemi nevlastními body. Poznámka. Střed může být vlastní i nevlastní bod v A%- Následující věta říká, že vlastní střed má právě ty vlastnosti, které po středu v geometrii požadujeme. Věta 4.13. Bod S G Aft je středem nadkvadriky Q právě tehdy, když Q je středově souměrná podle S. Důkaz. Nechť s G Cn+1 je aritmetický zástupce středu nadkvadriky S G Aft C A%- Potom pro všechny vektory v ze zaměření afinního prostoru Aft platí f(s, v) = 0. Odtud dostáváme f(s +tv,s+ tv) = f(s, s) + 2f(s, v)t + f (v, v)t2 = f(s, s) + f (v, v)t2. Tato rovnice v proměnné t má buď nekonečně mnoho řešení (oba koeficienty jsou nulové), žádné řešení (pouze kvadratický je nulový) nebo právě dvě řešení t = ±ío- V každém případě je množina řešení symetrická podle počátku a proto Q symetrická podle S. ** V opačném směru je potřeba ještě uvážit jednu možnost symetricky rozložených řešení, konkrétně jediné řešení t = 0, kdy lineární člen nemusí být nulový. Potom bude nulový kvadratický člen, tj. f (v, v) = 0. Protože je ale zúžení bilineární formy / na nevlastní podprostor Dir„4n nenulové, existuje báze (ei,..., en) taková, že /(e^, e^) 7^ 0, jak se snadno ukáže. Podle předchozího tak musí platit f(s, e^) = 0 a proto je S polárně sdružený s [ej] a tím pádem se všemi nevlastními body. □ Výpočet středu. Chceme-li najít středy S nadkvadriky Q zadané v homogenních souřadnicích A% bilineární symetrickou formou f(x, x) = xTAx, řešíme soustavu ai0s0 + ansi + ... + ai„sn = 0 dnOSQ + aniSi + ... + annsn = 0 Ta vznikne ze vztahu 0 = f(x, s) = xTAs postupným dosazením Chceme-li najít vlastní střed, pokládáme sq = 1, ideálně pak převedeme členy ajoso na pravou stranu. (Pro výpočet nevlastního středu bychom položili sq =0.) 33 4. Metrická klasifíkace nadkvadrik Lemma 4.14. Regulární nadkvadrika má právě jeden (vlastní nebo nevlastní) střed. Důkaz. To plyne buď z lemmatu o dimenzích polárních duálů (střed je polární duál nevlastní nadroviny, která má dimenzi n — 1) nebo z předchozího popisu výpočtu. □ Příklad. Najděte středy kuželosečky Q (vlastní i nevlastní). Q: 4xix2 + 3x22 + 6xi + 12x2 - 36 = 0 Řešení. Bilineární forma pro kuželosečku Q je f(x, y) = 2xiy2 + 2x2yi + 3x2y2 + 3xiy0 + 3x0yi + 6x2y0 + 6x0y2 - 36x0y0- Rovnice pro střed S = (yo> 2/i> 2/2) jsou 2y2 + 3y0 = 0 2yi + 3y2 + 6y0 = 0 Pro yo = l dostaneme jediné řešení S = ( — f, —|, 1)- Pro y0 = 0 dostame yi = y2 = 0, což nedává v projektivní rovině žádný bod. Daná kuželosečka má tedy vlastní střed S = [— |, — |] a nemá žádný nevlastní střed. o Příklad. Najděte středy kvadriky Q (vlastní i nevlastní). Q: x\ + xix2 + 2x2 — X3 — 2 = 0 Řešení. Bilineární forma pro kvadriku Q je 2f(x, y) = 2xiyi + xiy2 + x2yi + 4x2y2 - x3y0 - 2:0^3 - 4x0y0- Soustava rovnic pro střed S = (2/0)2/1)2/2)2/3) Je 22/1 +2/2 =0 2/1 + 4y2 =0 -2/0 = 0 Tato soustava nemá řešení pro í/o 7^ 0. Pro í/o = 0 má řešení (0,0,0,i). Tedy daná kvadrika nemá vlastní střed a má jeden nevlastní střed o homogenních souřadnicích (0, 0, 0,1). o 4.4. Eukleidovský afinní prostor Řekneme, že afinní prostor S je Eukleidovský, jestliže je na DirS zadán skalární součin. Standardní Eukleidovský prostor £n dimenze n je standardní afinní prostor An vybavený stadardním skalárním součinem ((0,xi,... ,xn), (0,yi,... ,2/n)) = xiyi H-----\-xnyn. Skalární součin bodů nebudeme uvažovat, protože geometricky nedává smysl. V této části budeme nadkvadriky uvažovat v komplexním rozšíření £^ a v jeho projektivním rozšíření Tyto nadkvadriky budeme popisovat nyní pouze v souřadnicích reálných ortonormálních bází (O, e±,..., en) v £n. To znamená, že O G £n a (e±,..., en) tvoří ortonormální bázi Dir £n. Říkáme, že směry [u] a [v] jsou kolmé, jestliže uli). Jak již bylo řečeno, kolmost vlastních bodů nedává geometricky smysl. 34 4. Metrická klasifíkace nadkvadrik 4.5. Hlavní směry Směr [u] zadaný reálným vektorem u G Dir£n se nazývá hlavní směr nadkvadriky Q, jestliže všechny k němu kolmé směry v Dir £^ jsou s ním polárně sdružené. Jinými slovy: Je-li nadkvadrika Q popsána bilineární formou /, pak pro všechny v G Dir£^, iilw platí f(u,v)=0. Nechť (O, ei,..., en) je nějaká ortonormální báze v £n. Nechť A = (clíj)™'-_0 je matice bilineární formy / na Mn+1. Nechť A je matice bilineární formy / zúžené na Dir£n v bázi (ei,...,en), tj. A = (aij)?j=1. Věta 4.15. Nenulový vektoru G Dir£n určuje hlavní směr nadkvadriky Q právě tehdy, když je vlastním vektorem lineárního zobrazení zadaného maticí A. Důkaz. Lineární zobrazení Dir £^ —> Dir £^ zadané maticí A označme opět A. Nechť u / 0 určuje hlavní směr. Potom 0 = f(u,v) = (Äu, v) pro všechna uli). Proto Au G (u^)^ = [u], tj. Au = Xu. Nechť obráceně u 7^ 0 je vlastním vektorem zobrazení A, tj. Au = Xu. Pro všechna ulu pak platí f(u,v) = (Au,v) = (Xu,v) = X(u,v) = 0. Tedy u určuje hlavní směr. □ Z důkazu je zároveň vidět, že pro normovaný vektor u zadávající hlavní směr platí f(u, u) = X(u,u) = X. V ortonormální bázi složené z vlastních vektorů tedy bude A diagonální s vlastními čísly na diagonále (to by nebyla pravda bez normovanosti!). Důsledek 4.16. Ke každé nadkvadrice Q v £^ existuje ortonormální báze v Dir£n, jejíž vektory určují hlavní směry nadkvadriky Q. Důkaz. K symetrické reálné matici A existuje ortonormální báze tvořená reálnými vlastními vektory. □ Definice 4.17. Vlastní čísla matice A se nazývají hlavní čísla nadkvadriky Q. Tato čísla nejsou určena jednoznačně, ale pouze až na společný násobek, je tedy jednoznačný jejich poměr (Ai : • • • : An), který lze chápat jako prvek projektivního prostoru V(M.n) (protože vlastní čísla symetrických matic jsou reálná). 4.6. Nadkvadriky a symetrie Již dříve jsme podali definici středu nadkvadriky v afinním prostoru. K této definici jsme nepotřebovali skalární součin. O symetrii nadkvadriky vzhledem k nadrovině však můžeme mluvit pouze tehdy, když máme na zaměření afinního prostoru zadán skalární součin. Definice 4.18. Nadrovina r v £n se nazývá hlavní nadrovinou nadkvadriky Q, jestliže je buď • polární nadrovinou k regulárnímu hlavnímu směru nadkvadriky Q C £C nebo • kolmou nadrovinou k singulárnímu hlavnímu směru nadkvadriky Q C £^. 35 4. Metrická klasifíkace nadkvadrik Osová nadrovina pro n = 2 se nazývá osová přímka nebo osa. Poznamenejme, že i v prvním případě je hlavní nadrovina kolmá k danému hlavnímu směru [u] - ten je totiž polárně sdružen s [u]^ a to je tedy zaměření této hlavní nadroviny. Poznámka. V dalším ukážeme, že hlavní nadroviny Q jsou osovými nadrovinami Q; obrácené tvrzení platí až na drobnou výjimku také a nebudeme proto mezi těmito pojmy rozlišovat. Příklad. Uvažujme parabolu xf+2x2 = 0 ve standardní ortonormální bázi vl2 = £2. Matice A je 0 1\ 0 1 0 v 0 0/ A Matice A = ^ ^ jj j má vlastní čísla 1 a 0 s vlastními vektory (1,0) a (0,1). Ty určují hlavní směry a jsou regulárními nevlastními body o homogenních souřadnicích (0 : 1 : 0) a (0:0: 1). Polára k (0 : 1 : 0) v je dána rovnici x1 = 0. Polára k (0 : 0 : 1) v £2 je dána rovnicí xQ = 0. Tedy v £2 má parabola pouze jedinou osovou přímku x1 = 0. Příklad. Uvažujme dvojici reálných rovnoběžek x\ - 1 = 0 ve standardní ortonormální bázi M = £0. Matice H 0 0 1 0 \o 0 0/ A 1 0 0 0 Vlastní čísla matice A jsou 1 a 0 s vlastními vektory (1,0) a (0,1). Ty určují 2 hlavní směry o homogenních souřadnicích (0 : 1 : 0) a (0 : 0 : 1). (0 : 1 : 0) je regulární nevlastní bod. Polára k němu je x1 = 0. (0 : 0 : 1) je singulární nevlastní bod. Všechny přímky kolmé na (0,1) v £2 jsou X2 = c, kde c je nějaká konstanta. Daná kuželosečka má tedy osové přímky x\ = 0 a X2 = c, c G M. Věta 4.19. Nechi r je hlavní nadrovina Q v £^. Pak je Q symetrická podle t. Důkaz. Nechť r je osová nadrovina v £n k hlavnímu směru [u] a nechť 5ět. Potom [s + íu] G Q, právě když 0 = f(s + tu, s + tu) = f(s, s) + 2f(s, u)t + /(u, u)í2 = f(s, s) + /(u, u)t2 a opět kořeny tohoto polynomu v proměnné t jsou symetricky rozložené okolo 0, tedy Q je symetrická podle r. □ Definice 4.20. Průsečnice dvou osových rovin kvadriky Q se nazývá osová přímka nebo osa kvadriky Q. Body průniku osové přímky s kvadrikou se nazývají vrcholy. 36 4. Metrická klasifíkace nadkvadrik 4.7. Metrická klasifikace kuželoseček a kvadrik Klasifikaci provedeme indukcí. Předpokládejme prvně, že existuje singulární směr a označme JeJ [en], kde en je normovaný. Zvolme libovolnou vlastní nadrovinu r kolmou na en; podle klasifikace v dimenzi n — 1 existuje ortonormální afinní báze (V, e±,..., en_i), v níž má Q D t kanonický tvar. Doplňme tuto bázi vektorem en do ortonormální afinní báze An a zkoumejme matici nadkvadriky v této bázi. Protože byl [en] singulární, je tato stejná jako pro QDt, pouze doplněná nulovým řádkem a nulovým sloupcem. Zejména, rovnice Q je totožná s rovnicí QDt. Budeme tedy v dalším předpokládat, že žádný singulární směr neexistuje. Poznamenejme ještě krátce, že v případě singulárního vlastního bodu je celá nadkvadrika kuželem a klasifikace se redukuje na (metrickou) projektivní klasifikaci nadkvadrik. Nechť je nejdříve Q středová a zvolme střed S za počátek. Dále zvolme ortonormální bázi (ei,..., en) zaměření Dir £n složenou z vektorů reprezentujících hlavní směry. To je možné díky ortonormální diagonalizovatelnosti symetrických bilineárních forem. V bázi (S, e±,..., en) má Q matici 0 • • °\ 0 Ai 0 0 An/ jelikož platí: /(e^e,) = 0, i / j, protože jsou [e^] hlavní směry; f(S,ei) = 0, protože je S střed. Ve skutečnosti je au = f = (Aej,ej) = (Aje^ej) = Aj, protože |ej| = 1, a aoo = f(S,S). V nestředovém případě se stačí omezit na regulární nadkvadriky, protože vlastní singulární bod by byl tím spíše vlastním středem. Díky regularitě je (u(£^))^ nularozměrný, označme jeho jediný bod [en] a předpokládejme opět en normovaný. Zkoumejme nyní kolmý doplněk [en]^ C v(£n). To je projektivní podprostor dimenze n — 2 a proto má jeho polární doplněk dimenzi 1, přičemž průnik tohoto doplňku s [en]* = v(£n) je ([enj^ + fen])* = (u(^n ))* = [en], takže doplněk obsahuje krom [en] ještě vlastní přímku o, tzv. osu nadkvadriky Q. Protože není o tečná k [en] (neleží v [en]* = u(£^)), je průnik Qn o regulárni a obsahuje tedy krom [en] i druhý bod V, nutně vlastní, který zvolíme za počátek. Zvolíme libovolnou ortonormální bázi zaměření složenou z vektorů zadávajících hlavní směry, přičemž cn bude aritmeticky zástupce středu (hlavního směru příslušného hlavnímu číslu 0). Nadkvadrika Q pak bude mít matici /o 0 0 p\ 0 Ai 0 ••• 0 0 0 '• An_i 0 \p 0 0 0/ Z výpočetního hlediska je dobré si zapamatovat, že i v singulárním případě se regulární střed dostane jako střed kolmý na všechny singulární směry. Osa je pak přímka mající směr tohoto regulárního středu polárně sdružená se všemi hlavními směry odpovídajícími nenulovým hlavním číslům (stačí spočítat jediný takový bod, protože směr již známe). Dostáváme tak následující klasifikační větu. Věta 4.21. Pro každou nadkvadriku Q v £^ lze najít takovou ortonormální bázi (O, e±,..., en), že v jejích souřadnicích má Q právě jednu z rovnic 37 4. Metrická klasifíkace nadkvadrik (a) pro n = 1,2,3 — +1 = 0 a následující kužel (b) pro n = 2, 3 ^ -i = o xi = 0 + + + 1 = 0 1 = o 1 = o + 2x2 = O a následující kužele Oil) \°í2, ct\ (c) pro n ■ 'xi ai 'xi ,ai 'xi ai 'xi ai + + + + + X2 CL2 Xi ai 'xi\2 _ ÍX2 ai) \a2 a následující kužele Oil J \Oí2j \OS3, O O + (^ť + ^V + i = o 1 = o + 1 = 0 1 = o + 2x3 = O + 2x3 = O O O dvojice imaginárních bodů/přímek/rovin dvojice reálnych bodů/přímek/rovin dvojnásobný bod/přímka/rovina imaginární elipsa/imaginární eliptický válec reálná elipsa/reálný eliptický válec hyperbola/hyperbolický válec parabola/parabolický válec imaginární různoběžné přímky/roviny reálné různoběžné přímky/roviny imaginární elipsoid reálný elipsoid dvoudílný (nepřímkový) hyperboloid jednodílný (přímkový) hyperboloid eliptický paraboloid hyperbolický paraboloid imaginární kuželová plocha reálná kuželová plocha xi\ / X2 \ _ I X3_ ,Oíi) \a2/ Pro koeficienty platí clí > O, cti > O, přičemž koeficienty cti jsou určeny až na násobek; jinými 38 4. Metrická klasifíkace nadkvadrik slovy, hraje roli pouze poměr (a± : • • • : an). Příklad. Najděte hlavní směry, osové rovin, osové přímky, vrcholy a kanonickou rovnici ve vhodné bázi kvadriky x\ — 4x2 + 6x1X3 + x2 + 4xi + 16x2 — 4x3 — 16 = 0. Rešení. Matice Vlastní čísla Ai, A2, A3 matice A jsou kořeny charakteristického polynomu det(A - XE) = -A3 - 2A2 + 16A + 32. Tyto kořeny, pokud jsou celočíselné, musí dělit absolutní člen 32. Tak zjistíme, že Ai = -2, A2 = 4, A3 = -4. Odpovídající vlastní vektory u{ jsou řešeními soustavy (A — XíE)uí = 0. Dostáváme ui = (1, 0,-1), U2 = (1, 0,1) a 113 = (0,1, 0). Osové roviny má kvadrika 3 a jsou to roviny polární k u±, 112 a u%. x\ — X3 — 2 = 0 x\ + x3 = 0 x2 - 2 = 0 Osové přímky jsou opět tři a jejich popis je dán výběrem 2 z předchozích 3 rovnic. Průnik všech tří osových rovin je jediný bod S = (1, 2,-1). Ten je středem kvadriky. Parametrické vyjádření os je potom následující: 01: (l,2,-l)+í(0,l,0) 02: (1,2,-1) +t(l,0,l) o3: (1,2,-1) +t(l,0,-l) Z parametrického vyjádření osy o\ dosadíme do rovnice kvadriky a pro parametr t dostaneme kvadratickou rovnici t2 — 1 =0. Vrcholy na ose íi jsou tedy A = (1, 3, — 1) a B = (1,1, —1). Z parametrického vyjádření osy o2 dostaneme kvadratickou rovnici 2í2 + l = 0. Na o2 tedy kl + ^2 i, 2, (1 &i 2 2 ') ^1 -1-4) leží dva komplexně sdružené vrcholy E Konečně pro osu 03 dostaneme opět rovnici t2 a D = (0,2,0). Z popisu os a reálných vrcholů vyplývá, že daná kvadrika je jednodílný hyperboloid. V bázi 1 = 0, která dává vrcholy C = (2, 2, —2) S, vi platí ^(1,0, -1), V2 U3 budeme mít souřadnice y±, y2, 7/3, pro které 39 4. Metrická klasifíkace nadkvadrik Tedy v homogenních souřadnicích x\ w Tedy rovnice kvadriky v souřadnicích y je /l 0 o o\ 1 2 v-1 -±- 0 0 0 1 1 1 n V2 V2 u/ /ž/o\ íyo\ = p ž/i ž/2 ž/2 Via/ W yPTAPy = 0, kde A f-16 2 8 -2\ 2 1 0 3 8 0-4 0 V "2 3 0 1 / PTAP í4 0 0 o\ 0 -2 0 0 0 0 4 0 Vo 0 0 -V Rovnice v nových souřadnicích je -2^+4^-4^ + 4 = 0. Kontrolní otázky 1. Podejte definici hlavních směrů a vysvětlete, kterou větu použijete k jejich výpočtu. 2. Jak se liší hlavní čísla regulárních kvadrik? 3. Kolik osových (hlavních) rovin mají jednotlivé kvadriky? (Použijte jejich metrickou klasifikaci.) 4. Napište kanonické rovnice kvadrik s 1, 2, 4, 6 a nekonečně mnoha reálnými vrcholy. 5. Zvolte si nějakou kvadriku a popište všechny její symetrie. Příklady k procvičení 1. Určete hlavní čísla a hlavní směry nadkvadriky, její střed a její kanonickou rovnici v příslušné ortonormální bázi. (a) 3xf + 10xix2 + 3x^ - 2xx - 14x2 13 [Řešení: Ai 8, A2 -2, Ul = ( i i v/2' v/2 0 V &2 ), u2 = 'v/2' ^), S = [2;-l], hyperbola *?-^ = l] (b) 7x\ + 6xix2 - x\ + 28xi + 12x2 + 28 = 0 v £■ [Řešení: Ai = 8, A2 = různoběžky x\ — ^ = 0] 2' Ul = (^o'Ä}' U2 Tu' 10 ; -2;0], 40 4. Metrická klasifíkace nadkvadrik (c) 9xj + 12xiX2 + Ax22 - 24xi - 16x2 + 3 = O v £2 [Řešení: Ax = 13, A2 = O, Ul = (7^,7=), u2 = (-* = ,--3 = ), S = [2í; 3 - 2í], rovnoběžky x\ = 1] (d) xf+X2+ 5x| — 6x1X2 — 2x1X3 + 2x2X3 — 6x1 + 6x2 — 6x3 + 9 = 0 v £3 ■73' ~73' 112 = ^_Vě' Vě' Vě' [Řešení: Ai = 3, A2 = 6, A3 = -2, «i = (-^=,—75,-75), «2 _ ' 1 1 2 u3 ^73' 73' ^' ^ = ^' —^' ~^' re^m^ kuželová plocha + x?, — ^ =0] (e) 5xf + 8x2 + 5x| + 4xiX2 — 8x1X3 + 4x2X3 — 27 = 0 v £ 3 ln 1 \ „ _ í 1 4 1 \ „. _ / 2 1 2^ [Rešení: Ai,2 = 9, A3 = 0, Ul = (75, 0, -^), ^2 = (575, 575, 575), ^3 = (-3, 3, -3 S* = [0; 0; 0], reálná eliptická válcová plocha -j- + = 1] (f) xf - 2x2 + xi + 4xiX2 - 8x1x3 - 4x2x3 - 14xi - 4X2 + 14x3 + 16 = 0 v £3 [Řešení: Ai,2 = -3, A3 = 6, Ul = (-^,--|,0), u2 = (^, ^, ^), u3 = 1 1 (|, |, — |), S* = [1; 1; —1], reálná kuželová plocha %^ + ^ — x| = 0.] (g) 2xf + 5x2 + 2x\ — 2x\x2 — 4xix3 + 2x2x3 + 2xx - 10x2 - 2x3 - 1 = 0 v £3 [Řešení: Ai = 6, A2 = 3, A3 = 0, Ul = (-J=,--J=), u2 = 2 u3 = (75, 0, 75), S = [í; 2; í], reálná eliptická válcová plocha x\ + ^ = 1-] (h) xf + x^ - 2xix2 + 2xi + 2x2 - 2^2^:3 - 8 = 0 v £3 [Řešení: Ax = 2, A2,3 = 0, Ul = (75,-75,0), u2 = (7575,0), u3 = (0,0,1), nestředová, parabolická válcová plocha x\ + 2x3 = 0.] 2. Určete osové nadroviny a vrcholy nadkvadrik z příkladu (1). [Řešení: (a) Osy 01: xi + x2 = 1, o2: x\ - x2 = 3, vrcholy Vi,2 = [2 ± 75; -1 T 75] příslušné k 01, F3,4 = [2 ± ^; -1 ± &\ příslušné k o2; (b) Osy xi + x2 = -6, xi - 3x2 = -2, vrcholy V\ = [-§, -|] k 01, V2 = [-2; 0] k o2; (c) Osa 3xi + 2x2 = 4, nevlastní vrchol určený zaměřením osy (-2,3,0); (d) Osové roviny o\: x\ — x2 + X3 = 3, o2: x\ — x2 — 2x3 = 0, V je lineární zobrazení mezi Eukleidovskými prostory. Zabývejme se otázkou, zda existuje inverzní zobrazení a v případě, že neexistuje, otázkou, jak blízko se k inverzi můžeme přiblížit. Nechť tedy ip:V^-U]e libovolné zobrazení a zkoumejme složení ipp a píp. Zřejmě je ipp = 0 na ker p a nejlepší, co můžeme očekávat, je, že bude toto složení rovno identitě na nějakém doplňku ker U se nazývá Mooreova-Penroseova pseudoinverze lineárního zobrazení p: U —> V, jestliže • ipíp = id na (keip)^ a • iptp = id na (keiip)^. Protože na ~keip je vždy ipp = 0, je první podmínka ekvivalentní tomu, že ipp je kolmá projekce na (keip)^. Lemma 5.2. Pro Mooreovu-Penroseovu pseudoinverzi platíimp = (keiip)^. Důkaz. Podle druhé podmínky z definice platí (ker xp)1- C im p, ukážeme nyní opačnou inkluzi. Prvně si uvědomme, že platí pipp = p - na ker (ker p)^ značí, že je nulové na komplementu (i~mp)^ a jeho komponenta v ker im p existuje jediná, dostáváme jednoduše následující tvrzení. Tvrzení 5.3. Nechť p: U —> V je lineární zobrazení mezi Eukleidovskými prostory (konečné dimenze). Potom Mooreova-Penroseova pseudoinverze existuje a je jediná. Značíme ji p+. □ 42 5. Mooreova-Penroseova pseudoinverze Tradičně se Mooreova-Penroseova pseudoinverze definuje pomocí singulárního rozkladu (singulár value decomposition). Tento přístup je výhodný i z dalších důvodů. Uvažujme proto adjungované zobrazení tp* : V —> U. Lemma 5.4. Zobrazení p*p je samoadjungované a platí (p*p(u),u) > 0 (říkáme, že ip*ip je pozitivně semidefinitní). Navíc kei(p*p) = ker p. Důkaz. Z definice adjungovaného zobrazení platí (p*p{u),v) = (p(u),p(v)) = (u,p*p(v)) a navíc prostřední člen je pro u = v nezáporný. Inkluze ker( 0 Zkonstruujme nyní vhodnou ortonormální bázi V, vzhledem k níž bude mít p co nejjednodušší tvar. Prvně se zabývejme obrazem p, který je generován p{u\),..., p{ur): (p(ui),p(uj)) = (p*p(ui),Uj) = \i(ui,Uj) = XiSij. Jsou tedy vektory p{ui) navzájem kolmé o velikostech W{uí)\ = \Z% = Si. Tato čísla nazýváme singulární hodnoty zobrazení p. Položíme Vi = j-(p(ui) pro i = 1,..., r a doplníme v±,..., vr do ortonormální báze (3 = (v±,..., vn) prostoru V. Vzhledem k těmto bázím má p> matici ís1 0 ...... 0\ 0 '•• '•• : (^)/3a = : sr ' ■ ■ : '•• 0 '• v° ...... '•• 'V 43 5. Mooreova-Penroseova pseudoinverze (tato matice má rozměry m x n). Poznamenejme, že matice adjungovaného zobrazení p* je „stejná", akorát má rozměry n x m. V těchto bázích je také extrémně jednoduché napsat Mooreovu-Penroseovu pseudoinverzi /(si)-1 0 la/3 0 o \ v o Tímto souřadnicovým zápisem se často Mooreova-Penroseova pseudoinverze definuje. Elegantně to lze provést následující úvahou. Pracujme pro jednoduchost ve standardních Eukleidovských prostorech a místo p pracujme s maticí M. Ve výše popsaných bázích a, /3 má M diagonální matici, označme ji S. To znamená, že lze psát M = PEQ*, kde P, Q jsou ortogonální matice. Tomuto rozkladu matice M se říká singulární rozklad. Mooreovu-Penroseovu pseudoinverzi potom můžeme spočítat jako M+ = QT,+P*, kde S+ vznikne (tak jako výše) z diagonální matice £ inverzí všech nenulových prvků. Poznamenejme ještě, že z matice {p)pa lze také odvodit geometrický význam singulárních hodnot. Uvážíme-li v U jednotkovou sféru, pak její obraz při zobrazení p je (v některých směrech možná zdegenerovaný) elipsoid, jehož délky poloos jsou právě singulární hodnoty. Tvrzení 5.5. Platí následující vztahy • Je-li p injektivní, potom p+ = {p*p>)~1p*■ • Je-li p surjektivní, potom p+ = p*{pp* Důkaz. V bázích a, /3 jsou všechny uvažované matice diagonální. V případě injektivního p má ip*ip na diagonále pouze čísla s2. Proto (p*^)^1 existuje a má na diagonále čísla s^2 a tím pádem pravá strana má na diagonále prvky s^1. Týž diagonální tvar levé strany jsme odvodili před tvrzením. Podobná analýza funguje v případě surjektivního p. □ cv Poznámka. Je-li U = V © W, má každý vektor u G U jednoznačné vyjádření u = v + w, kde v G V a w G W. Označme v = p{u) a dostáváme tak lineární zobrazení p: U —> U (s hodnotami ve V), kterému říkáme projekce na V ve směru W. Uveďme nyní ještě dvě alternativní charakterizace. Lineární zobrazení p: U —> U je projekce na V ve směru W, právě když p\y = id a p\\y = 0. Lineární zobrazení p: U —> U je projekce, právě když pop = p; v takovém případě se jedná o projekci na imp ve směru kerp. Ukažte, že projekce je samoadjungovaná, právě když je kolmá4. Věta 5.6. Platí 1. pp+p = p 2. p+pp+ = p+ 4Podle definice je projekce p samoadjungovaná, právě když (u,p{v)) = (p(u),v). Tato podmínka je triviálně splněná pro u, v G ker p a m, u G im p. Pro u G ker p, v G imp tato podmínka je (u,v) = 0, tedy právě ker p _L imp. Zbylý případ u G im p, v G ker p je symetrický. 44 5. Mooreova-Penroseova pseudoinverze 3. p p je samoadjungované 4- pp+ je samoadjungované Naopak každé zobrazení ip splňující tyto čtyři vztahy s p+ nahrazeným ip je Mooreovou-Penroseovou pseudoinverzí k p, tj. ip = p+. Důkaz. Je jednoduché ověřit vztahy z tvrzení pro Mooreovu-Penroseovu pseudoinverzi; vlastnosti (3) a (4) platí proto, že příslušné kompozice jsou kolmé projekce na podprostory im p a (ker p)^. V tomto i opačném směru je podstatné si uvědomit, že projekce je samoadjungovaná, právě když je kolmá. Podle (1) a (3) je p+p samoadjungovaná projekce (neboť (p+p)2 = p+p) ve směru kei(p+p) = ker p (neboť ~keip C kei(p+p) C ~kei(pp+p) = ~keip), nutně tedy kolmá. Proto je jejím obrazem (ker p)^ a p+ tedy splňuje první definiční vztah. Druhý se dokáže symetricky. Téměř v jakékoliv knize pojednávající o Mooreově-Penroseově pseudoinverzi lze najít alternativní důkaz hrubou silou. □ 5.2. Aproximace řešení soustavy lineárních rovnic Zabývejme se soustavou lineárních rovnic Ax = v. Pokud je matice A čtvercová a invertibilní, lze formálně tuto soustavu vyřešit vynásobením inverzí A^1, x = A~1Ax = A~1v. V případě, že A nemá inverzi nebo dokonce není ani čtvercová, lze stále něco říct o řešeních pomocí Mooreovy-Penroseovy pseudoinverze. Tvrzení 5.7. Soustava Ax = v má řešení, právě když AA+v=v Důkaz. Pokud platí AA+v = v, pak zřejmě A+v je řešením. Naopak, pokud Ax = v pro nějaké x, potom AA+v = AA+ Ax = Ax = v. Jiný důkaz spočívá v tom, že AA+ je projekce na imi, a proto rovnost AA+v = v je ekvivalentní tomu, že v G im A, což je zřejmě to samé, že soustava má řešení. □ Vidíme tedy, že i v případě, že A nemá inverzi, nebo dokonce není ani čtvercová, můžeme nějaké její řešení (v případě, že existuje) najít jako A+v. V následujícím ukážeme, jaký geometrický význam toto řešení má. Obecněji se budeme zabývat otázkou geometrického významu A+v i v případě, kdy soustava Ax = v nemá řešení. Řekneme, že x je nejlepší aproximace řešení, jestliže minimalizuje výraz |Ac — v\, tj. pokud pro libovolné y platí \Ax — v\ < \Ay — v\ Zřejmě je tedy Ax bod imi, který je nejblíž v, je to tedy kolmá projekce vektoru v do podprostoru imA Tu umíme podle předchozího napsat pomocí pseudoinverze jako AA+v. Platí tedy Lemma 5.8. Vektor x je nejlepší aproximací řešení soustavy Ax = v, právě když platí Ax = AA+v. 45 5. Mooreova-Penroseova pseudoinverze Zejména tedy A+v je nejlepší aproximace řešení. Obecně je takových nejlepších aproximací víc. Mezi nimi lze A+v charakterizovat pomocí následující věty Věta 5.9. Vektor A+v je nejlepší aproximace řešení soustavy Ax = v s nejmenší normou, „zkráceně" nejmenší nejlepší aproximace řešení. Důkaz. Množina nejlepších aproximací je právě množinou řešení soustavy Ax = AA+v a jedná se tedy o afinní podprostor se zaměřením ker A. Vektor z tohoto afinního podprostoru s nejmenší normou je tedy jediný a to právě ten, který je kolmý na zaměření ker A. Přitom ale A+v G im A+ = (ker A)L. □ Příklad (Aproximace přímkou). Nechť jsou v rovině dány body (xi,yi),..., (xn, yn). Úkolem je vést těmito body přímku. Pokud by to bylo možné přesně, existovaly by a, b (koeficienty v rovnici přímky a + bx = y) takové, že a ■ 1 + b ■ x\ = y± a ■ 1 + b ■ xn = yn Naším úkolem je tedy vyřešit soustavu (vzhledem k neznámým a, b) s rozšířenou maticí /l xx yi Vn) \1 Xn Její nejmenší nejlepší aproximace řešení je /i fyi\ (a,b) t \1 xn) \yn) Přímka s rovnicí y = a + bx se nazývá aproximací přímkou zadané n-tice bodů. Je potřeba však vysvětlit, v jakém smyslu je to nejoptimálnější odpověď na naší otázku proložení přímky zadanými body. Tato přímka minimalizuje ^ ((a + bxi yi) , i=l tedy součet čtverců odchylek funkčních hodnot a + bxi od zadaných yi. Tato aproximace se používá, pokud víme, že zadané hodnoty í/j můžou být zatíženy chybou, ale X{ jsou naměřeny přesně. 46 5. Mooreova-Penroseova pseudoinverze 5.3. Kolmá projekce do podprostoru Nechť V = [vi,... ,Vk] C U je podprostor. Kolmá projekce vektoru u do F je takový vektor P{u) = x\V\ + • • • + XkVk, který je nejblíž k u. Jedná se tedy o nejlepší aproximaci řešení soustavy x±vi + • • • + xkvk = u. Označíme-li A = (v± • • • v^) matici na levé straně, dostáváme z předchozího formulku (x\ • • • Xk)T = A+u a tedy P(u) = («!••• vk)(x! • • • xk)T = AA+v. Předpokládáme-li nyní, že vektory v±,..., vk jsou lineárně nezávislé, je A maticí injektivního zobrazení a dostáváme tak formulku P = A(A*A)-1A*. V případě, že byl systém vektorů dokonce ortonormální, je matice uprostřed jednotková a tedy P = AA*. 47 6. Multilineární algebra V celé této kapitole budeme pracovat s vektorovými prostory nad pevným tělesem K. 6.1. Báze a souřadnice Prvně připomeňme důležité vlastnosti bází a souřadnic. Lineární zobrazení a: Kn —> U je jednoznačně určené obrazy U{ = a(ej) a lze jej tedy chápat jako n-tici vektorů (u±,... ,un). Přitom se jedná o bázi, tj. a posílá bázi na bázi, právě když je a izomorfismus. Inverzní zobrazení p = aT1: U —> Kn pak posílá každý vektor u na jeho souřadnice (u)a a budeme mu tedy říkat souřadnicové zobrazení (nebo prostě souřadnice na U). Lemma 6.1. Vektory ui,...,un tvoří bázi U, právě když se každé zobrazení {u{\ —> V jednoznačně rozšiřuje na lineární zobrazení U —> V. Poznámka. V řeči univerzální algebry to znamená, že báze vektorového prostoru je koncept totožný s volnou algebrou. Následující důkaz je vhodné v tomto směru chápat. Důkaz. To, že báze má vlastnost z tvrzení, známe z dřívějška. Nechť tedy naopak u±,... ,un mají vlastnost z trvzení. Zejména tedy existuje zobrazení p: U —> Kn, posílající uí i—> ej. Ze stejné vlastnosti standardní báze dostáváme zobrazení a: Kn —> U posílající i—> U{. Protože složené zobrazení atp posílá uí i—> uí, stejně jako identické zobrazení, plyne z jednoznačnosti rozšíření atp = id a symetricky také pa = id; tím pádem je a skutečně báze. □ 6.2. Faktorový prostor Nechť U je vektorový prostor, V jeho podprostor. Tento podprostor definuje na U ekvivalenci u\ ~ U2 právě tehdy, když u\ — U2 G V. Třídu ekvivalence obsahující vektor u budeme značit [u]. Je to množina [u] = u + V = {u + v | v G V}. Množinu všech tříd ekvivalence označujeme U /V. Jakožto kvocient komutativní grupy podle její podgrupy je to opět komutativní grupa, navíc můžeme na této množině definovat násobení skalárem z K takto: [u] + [v] = [u + v] k[u] = [ku] Tyto operace jsou nezávislé na výběru reprezentantů a není obtížné se přesvědčit, že z UjV vytvářejí vektorový prostor nad K. Je-li W komplementární podprostor k V, tj. U = W © V, pak projekce U —> U/V se zužuje na izomorfismus W —?► U /V: ke každému u + V G U /V hledejme vzor w G W tak, že u + V = w + V, tj. u = w + v pro nějaký vektor v G V; podle definice přímého součtu lze toto jediným způsobem. Je-li U konečněrozměrný prostor, pak dim U /V = dim U — dim V. Důkaz je jednoduchý: Zvolme bázi v±, ..., Vk prostoru V a doplňme ji na bázi v±, ..., Vk, Vk+i, ..., vn prostoru U. Stačí ukázat, že [vfc+i], ..., [vn] je báze prostoru U /V. 48 6. Multilineární algebra Cvičení. Dokažte předchozí tvrzení. Označme p: U —> UjV surjektivní lineární zobrazení definované předpisem p(u) = [u]. Toto zobrazení se nazývá projekce. Nechť p: U —> W je lineární zobrazení a nechť V C ~keip. Potom existuje právě jedno lineární zobrazení p: U jV —> W takové, že p = pop, tedy že následující diagram komutuje U— A U/V p musí být definováno předpisem p([u}) = p(u). Díky tomu, že pro v G V je p{v) = 0, je pro u± ~ 112 (p{ui) = W je lineární zobrazení. Pak známá věta z algebry říká U/ ker p = im p, což pro dimenze znamená dim U — dim ker p = dim im p (známe z dřívějška). 6.3. Prostory lineárních a multilineárních zobrazení Lineární zobrazení z vektorového prostoru U do vektorového prostoru V vytvářejí vektorový prostor, který budeme označovat Bom(U,V). Důvodem pro toto označení je skutečnost, že lineární zobrazení se často nazývají homomor-fismy vektorových prostorů. Nechť Ui, ..., Uq, V jsou vektorové prostory. Zobrazení p: Ui x • • • x Uq —> V se nazývá multilineární (nebo g-lineární), jestliže je lineární v každé své složce, tj. p(u1} ...,CLUi+ bVi, ...,Un)= CLp){ui, ...,uq)= a M zadaná předpisem f(x1,x2,x3)=x3, 5(2/1,2/2,2/3) = 2/1- Ukážeme, že zobrazení fK3xl3^t, M). Tedy řxls ueR3, u=[x2\, í?g(m3)*, « = (2/1,2/2,2/3) ,i3 Vyčíslení formy rj na vektoru u je potom maticové násobení a x 3 v(u) = (2/1,2/2,2/3) [ x2 \ = yix1 +y2x2 +y3x3 yX3 Nechť a = (u±,... ,un) je báze W1. Matice přechodu od a ke standardní bázi e = (ei,... ,en) je (id)£)Q, = A {ui, ■ ■ ■, un) = (ei,..., en)(id)£)a. Duální báze k (ei,..., en) je f1 = (1, 0,..., 0), ..., fn = (0,..., 0,1) a duální báze (rj1,..., r]n) k (ui,..., un) je určena řádky matice A^1, neboť musí platit : ■{u1,...,un) = (rii{uj))={fy=E. \vnJ Důsledek 6.3 (o druhém duálu). Nechť U je vektorový prostor konečné dimenze. Pro vektor u £ U efinujme lineární formu evu g (U*)* na duálním prostoru U* pomocí předpisu evu{vf) = i](u). Potom vzniklé zobrazeníev: U —> (U*)* je lineární izomorfismus. Důkaz. Podle předchozí věty k bázi (ei, ..., en) prostoru U lze najít duální bázi (f1, ..., fn) prostoru U*. Ukážeme, že (evei, ..., even ) tvoří duální bázi k (f1, ..., fn). Platí totiž ev„(/<) = /'(,,) = (! proi:i' I (J pro 1 7^ j Protože je zjevně ev lineární a převádí bázi na bázi, jedná se o izomorfismus. □ 51 6. Multilineární algebra * Poznámka. Zabývejme se nyní krátce tím, co se stane pro U nekonečné dimenze. Jak jsme viděli, formy f1 jsou bází jistého podprostoru U* a eveí jsou k nim opět duální, takže jsou lineárně nezávislé. Zobrazení ev je tedy injektivní a U je izomorfní podprostoru U daného právě prvky tvaru evu. Od tohoto okamžiku budeme považovat prostory U a ([/*)* za totožné. Zobrazení ( —, —): U* x U —> K definované (r],u) = r)(u) je bilineární a někdy se nazývá dualita nebo párování. Pomocí duality se dají vyjádřit podmínky pro duální bázi jako (/■J,ej) = 5\ a pro souřadnice platí symetrické vztahy (/■',«) = v?, (r],e,i) = r]i. 6.5. Duální lineární zobrazení Nechť tp: U —> V je lineární zobrazení. Zobrazení tp*: V* —> U* definované pro 9 £ V* předpisem K a (—, —)y: V* x V —>■ K lze definici psát (^(ř?),n)l/=(ř?,^))y, což formálně připomíná definici adjungovaného zobrazení, kde skalární součiny jsou nahrazeny dualitami. Výhodou tohoto zápisu je jeho symetrie a lepší přehlednost. Podobnost s definicí adjungovaného zobrazení není náhodná. Je-li totiž U reálný Eukleidovský vektorový prostor, je zobrazení R:U^U*, u^(u,-} izomorfismus - prostory mají stejnou dimenzi a injektivita plyne z toho, že (u, —} = 0 znamená zejména \u\2 = (u,u) = 0, tj. u = 0. Při této identifikaci R pak dualita vypadá (Ru,v) = ((u, -},v) = (u,v), tj. dualita je přesně skalární součin. Pro komplexní skalární součin je R izomorfismus U = U* a situace je o něco komplikovanější. Příklad. Nechť tp: U —> U je zobrazení (p(u) = 3u. Vypočtěte tp*: U* —> U* z definice. Platí (V(#))(u) = 0{ip{u)) = 9{3u) = 39{u). Tedy *(0) = 39. Zabývejme se nyní souřadnicovým zápisem duálního zobrazení. Připomeňme, že vektory zapisujeme do sloupce, zatímco lineární formy do řádku a dualita je násobení matic. Definice duálního zobrazení íp*{rj) = r]p> pak v souřadnicích dává (ip*(r]))a = (i])p((p)pa a je tedy dáno násobením maticí {ip)pa zprava. 52 6. Multilineární algebra 6.6. Dualita a podprostory Nechť U C V je vektorový podprostor a uvažujme vložení a k němu duální surjektivní zobrazení t*: V* -» U*, které je zřejmě dáno předpisem rj i—> r}\jj. Definujme U± = ker L* = {r] G V* | Vu G C/: (í?, n) = 0}, kde podmínku u) = 0 si lze představovat jako vr] _L U neboli r] G Č7^"; proto také tento podprostor duálního prostoru značíme tímto symbolem. Přiřazení U i—> zadává zobrazení Dy. {podprostory V} —> {podprostory V*}, které zjevně obrací uspořádání, tj. pokud Uq C U±, pak ř/g1 5 U^. Navíc, pokud U má dimenzi d, pak ř7^ má dimenzi n — d (také říkáme, že má kodimenzi d); to je proto, že je jádrem surjektivního zobrazení V* -» U* z n-rozměrného do d-rozměrného prostoru. Naším dalším krokem bude ukázat, že zobrazení Dy je bijekce (a tedy antiizomorfismus uspořádaných množin - ve skutečnosti svazů). Zabývejme se proto tím, co se stane při druhé aplikaci „kolmého doplňku". Geometrická intuice z Eukleidovských prostorů říká, že druhý kolmý doplněk musí nutně obsahovat původní prostor a ve skutečnosti se musí rovnat, protože mají stejné dimenze. Stejný argument funguje i obecně, (U^ = {v G V | Ví? G UL : (v, v) = 0}, Protože se však všechny formy z podle definice nulují na U, platí U C (ř7"L)"L. Zároveň mají oba prostory stejnou dimenzi, musí být tedy totožné, (ř7"L)"L = U. Věta 6.4. Přiřazení U \—> určuje bijektivní zobrazení Dy. {podprostory V} —> {podprostory V*}, U i—> s následujícími vlastnostmi • Dy převrací uspořádání, • je-li U dimenze d, pak je dimenze n — d, • ([/oílf/i)1 = U^ + Ut, □ Poznámka. Vše je důsledkem prvního bodu, dokonce i vztah mezi dimenzemi. Můžeme totiž vyčíst dimenzi U jako délku d nejdelšího striktně rostoucího řetězce podprostorů 0 = Uo C u1c...cud = u. 53 6. Multilineární algebra Pěknou aplikací je popsání svazku všech rovin v prostoru procházejících danou přímkou p. Přechodem ke kolmým doplňkům to znamená popsat všechny přímky obsažené v rovině p^. To je ale jednoduché - jejich směrové vektory jsou právě všechny nenulové prvky p^. Pokud je p zadaná implicitně jako řešení soustavy a (v) = (3(v) = 0 dvou rovnic, je p^ = [a, (3] a přímka ležící v p^ je proto generovaná libovolnou jejich nenulovou lineární kombinací aa + 6/3. Přechodem zpátky vidíme, že rovnice odpovídající roviny obsahující p je {aa + b/3)(v) = 0, ve výsledku tedy libovolná nenulová lineární kombinace definujících rovin přímky p. Zabývejme se dále vztahem mezi podprostory zadanými implicitním a parametrickým popisem. Nechť je podprostor W C V* zadán parametricky jako W = [rf,... ,rf\. Potom W± = {v G V | V?? G W: (r),v) = 0} = {v G V | (q1, v) = ■■■ = (r]k,v) = 0}. To je ale popis W1- jako prostoru řešení soustavy lineárních rovnic rf{v) = 0,... ,i]k(v) = 0, tedy implicitní popis. Stejný princip funguje naopak. Je-li U = [v±,..., Vd], pak U± = {V€V*\ (v,v1)=--- = (r,,vd)=0.} Formálně tak převod parametrického popisu na implicitní je elementární. Parametrický popis U je ekvivalentní implicitnímu popisu U^, ten lze pomocí vyřešení soustavy s parametry převést na parametrický popis, který je zpětně ekvivalentní implicitnímu popisu U. Tvrzení 6.5. Nechť jsou na V zadány formy r]°,r)1,..., r)k. Jestliže libovolné v G V splňující rfiv) = • • • = nk{v) = 0 splňuje zároveň rf(v) = 0, pak rf G [i]1,..., r]k]. Poznámka. Opačná implikace je triviální: je-li rf G [i]1,... ,i]k], pak z ^(v) = ■ ■ - rik(v) = 0 plyne jednoduše rf(v) = 0. V případě implikace {^{v) = • • • = r]k(v) = 0) (i]°(v) = 0) můžeme mluvit o tom, že rovnice rf(v) = 0 je logickým důsledkem zmíněné soustavy. Věta tedy říká, že pokud je rf{v) = 0 logickým důsledkem, je ve skutečnosti „algebraickým" důsledkem; lze odvodit ze soustavy tím nej triviálnějším možným způsobem - je kombinací rovnic soustavy. V jistém smyslu se jedná o úplnost jistého logického systému: implikace, které platí, jsou právě ty, které lze dokázat (pomocí zmíněného jednoduchého pravidla). Důkaz. Implikaci lze vyjádřit jako [r]°,r]1,...,r]k]± = [r]\...,r]k]±. Druhou aplikací Dy dostáváme [rf, r]1,..., r]k] = [rf,..., r]k] a zejména r]° G [r]1,..., r]k]. □ Následující tvrzení je dobře známe z teorie řešení soustavy lineárních rovnic a lze jej vyvodit z Gaussovy eliminační metody. Uvádíme zde alternativní důkaz pomocí duality. Tvrzení 6.6. Soustava rovnic Ax + b = 0 nemá řešení, právě když existuje lineární kombinace jejích řádků (tedy rovnic) tvaru 1 = 0. Důkaz. Trik spočívá v „projektivizaci" soustavy. Původní soustava nemá řešení, právě když každé řešení soustavy Ax + bt = 0 splňuje také t = 0. Podle předchozího tvrzení to nastane právě tehdy, když forma zadaná řádkem (0,..., 0,1), tj. (0 | 1) je lineární kombinací řádků rozšířené matice (A \ b). □ 54 6. Multilineární algebra 6.7. Prostory multilineárních forem Zabývejme se nyní multilineárními formami. Pro jednoduchost zápisu se omezíme pouze na případ Lin2(č7, V;K). Nechť rj G U*, 9 G V* jsou lineární formy. Definujme bilineární formu 0Qr]:UxV^K, (9 0 rj){u, v) = n(u) ■ 6 (v) (součin funkčních hodnot - prvků tělesa K); všimněte si, že argumenty se dosazují do lineárních forem v opačném pořadí než je pořadí jejich zápisu - toto bude naše konvence, která není úplně běžná. Poznámka. Při práci s bilineárními formami a později s tenzorovým součinem je výhodnější se vzdát uspořádání prvků báze a pracovat s neuspořádanými bázemi. V dalším budeme zkracovat na „{e^} je báze Č7". Lemma 6.7. Nechť {e{\ je báze U, {ej} báze V* s příslušnými duálními bázemi {f1} a {f1}. Potom množina {f1 0 f1 \ i = 1,..., n; j = 1,..., m} tvoří bázi Lin2(č7, V; K). Důkaz. Pointou důkazu je, že dvě bilineární formy se rovnají, právě když dávají stejné hodnoty na všech dvojicích (ei,ej) bázových vektorů (to by mělo být čtenáři známo, případně by to měl zvládnout dokázat sám). Pokusme se napsat bilineární formu <í> jako kombinaci r,s Tato rovnost bude podle předchozího splněna, právě když pro každé i, j bude platit r,s r,s §r §a 1 J Je tedy vidět, že koeficienty existují a to jediné: <&íj = <ř(ej,ej). To ale přesně znamená, že daná množina je báze. □ Poznámka. Předchozí důkaz je analogií vztahu rji = i](ei) pro souřadnice formy - souřadnice bilineární formy jsou také dány hodnotami na prvcích báze, <&íj = <ř(ej, ej). 55 7. Tenzorový součin 7.1. Tenzorový součin vektorových prostorů Pointa tenzorového součinu je, že chceme převést bilineární zobrazení na lineární. Konkrétně bilineární zobrazení U x V —» W bude ekvivalentní lineárnímu zobrazení U (8> V —> W. Symbolicky Lm2(U, V; W) ^ Hom([/ © V, W), kde však říkáme víc než v předchozím - vyžadujeme, aby se jednalo o izomorfismus vektorových prostorů (a ne jen o bijekci). Tímto vztahem je tenzorový součin určen jednoznačně až na izomorfismus a ve většině aplikací není potřeba znát přesnou definici a vystačíme si s touto vlastností. Pokusme se s její pomocí „odvodit" definici tenzorového součinu. Dosaďme do uvedeného vztahu W = K. Dostáváme Lm2(U,V;K) = {U®V)*. Budeme-li nyní předpokládat, že má U (8> V konečnou dimenzi, lze psát U ®V ^Lin2([/,F;K)* Chceme-li tedy dostát tomu, že tenzorový součin převádí bilineární zobrazení na lineární, jsme vedeni k následujícímu: Definice 7.1. Nechť U & V jsou vektorové prostory konečné dimenze. Definujeme jejich tenzorový součin U (g> V á= Lhi2(č7, V; K)*. Prvek tenzorového součinu t G U (8> V nazýváme tenzor. (V analogii k předchozímu výkladu pro lineární formy jde o verzi „druhého duálu" pro více činitelů.) Definujme nyní bilineární zobrazení t: U x V —> U ®V předpisem t(u,v): 3> 1-4- $(u,v), jedná se tedy o „evaluaci" (viz srovnání druhého duálu s původním vektorovým prostorem). V následujícím budeme značit u (g> v = t(u, v) a je to tedy zobrazení, které každou bilineární formu posílá na její hodnotu na dvojici (u,v). Lemma 7.2. Zobrazení t je bilineární, tj. (aiui + 02^2) <8> v = ai ■ ui (g> v + a2 ■ u2 (g> v a analogicky pro druhou složku. Důkaz. Levá strana je dána evaluací <í> 1-4- $(ai«i + a2u2,v), zatímco pravá je dána jako lineární kombinace evaluací, tedy <í> 1-4- ai$>(ui,v) + a2Q(u2, v). Tyto dva výrazy se rovnají díky bilinearitě <í>. □ 56 7. Tenzorový součin Tenzory tvaru u U ®V dané (u, v) i—> u 0 v. Věta 7.4 (Univerzální vlastnost tenzorového součinu). Nechi; F: U x V —?► W je bilineární zobrazení. Potom existuje pravé jedno lineární zobrazení tp: U 0 V —> W takové, že p{u ®w) = F(u, v), tj. takové, že následující diagram komutuje U x V—^W t / Důkaz. Jsme nuceni položit p{ei 0 ej) = F(ei,ej). Jelikož takové tenzorové součiny tvoří bázi, je tímto p díky linearitě jednoznačně určeno. Zbývá ukázat, že podmínka opravdu platí. Přitom jsou ale obě F,pot bilineární zobrazení U x V —> W. Podle předchozího se shodují na dvojicích bázových vektorů a musí tedy být stejné. □ * Důsledek 7.5. Existuje přirozený izomorfismus Hom([/ 0 V, W) -=+ Lin2([/, V; W), daný p i—> p o t. Následující tvrzení říká, že tenzorový součin je svou univerzální vlastností určen až na izomorfismus jednoznačně. 57 7. Tenzorový součin * Věta 7.6 (o jednoznačnosti tenzorového součinu). Nechť S je vektorový prostor a nechť s: V~i x • • • x Un —> S je n-lineární zobrazení, které má stejnou vlastnost jako zobrazení t: V~i x • • • x Un —» ř7i (8> • • • ®Un z předchozí věty. Potom existuje právě jeden izomorfismus o: U\ ® ■ ■ ■ ® Un —> S ak němu inverzní r: S —> U\ ® ■ ■ ■ ® Un tak, že komutuje diagram Ui x • • • x U, Důkaz. Provedeme pouze náznak. Existence lineárního zobrazení o plyne z univerzální vlastnosti t, existence lineárního zobrazení r plyne z univerzální vlastnosti zobrazení s. Identity r o a = id, o o r = id se dokáží dalším použitím předchozí věty (především jejího tvrzením o jednoznačnosti). □ Poznámka. Existují i jiné definice tenzorového součinu vektorových prostorů než je ta, kterou jsme použili. Podle předchozího tvrzení lze však vždy ukázat, že jsou na prostorech konečné dimenze ekvivalentní s naší definicí. Jedna z možností, která funguje i pro U, V nekonečné dimenze, je U®V = T/T0, kde T je vektorový prostor všech formálních lineárních kombinací dvojic (u,v) £ U x V (pro K nekonečné a U, V netriviální nemá T konečnou dimenzi!), tj. T je volný vektorový prostor na množině U x V, a Tq je jeho podprostor generovaný prvky [au\ + bu2, v) — a(ui,v) — b(u2,v) (u, av± + bv2) — a(u, v±) — b(u, v2) Zobrazení t: U x V —> T/Tq je t(u,v) = [(u,v)]. 7.3. Asociativita a komutativita tenzorového součinu Uvažujme zobrazení U± x U2 x U3 —> (U± (g> U2) ® U3, (ui,u2,us) i-> {u\ (g> u2) (g> U3. To je zřejmě lineární v každé složce (protože tenzorový součin vektorů je lineární v každé složce) a díky univerzální vlastnosti tenzorového součinu tak existuje jediné lineární zobrazení a: U! (C/i 0 U2) ® U3, ui (ui (g) u2) (g) u3. Jedná se o izomorfismus, protože posílá bázi na bázi. Obdobně pro každou permutaci o množiny {1,..., n} existuje právě jeden lineární izomorfismus Pa ■ Ui ® ■ ■ ■ ® Un -> ř7CT(i) ® ■ ■ ■ ® č7CT(n), Ui <%>■■■<%> Un I-> ^(1) (g> • • • (g> UCT(n). Jednotkou pro tenzorový součin je těleso K, tj. platí K® U = U. Tento izomorfismus je předepsán k (g u 1—> ku (skalární násobení v U). 58 7. Tenzorový součin 7.4. Tenzorový součin lineárních zobrazení Nechť ifi'. U i —> Ví jsou lineární zobrazení. Potom zobrazení Ui x • • • x Un —> V\ (g> • • • (g> Vn, definované předpisem (u±,... ,un) i—> • • • (g> • • • (g> ř7n Vi (g> • • • (g> Fn takové, že Zobrazení • • • <8> n nazýváme tenzorovým součinem lineárních zobrazení tpi,..., ipn. 7.5. Tenzorový součin a dualita Tvrzení 7.7. Nechť U a V mají konečnou dimenzi. Pak zobrazení V* ® U* Lin2([/, V; K) = (U ® V)* dané předpisem 6<®r]*-^>r]Q6je izomorfismus. Důkaz. Zobrazení převádí bázi f3 (g> fl na bázi f3 0 fl (ve druhém vyjádření jsou pak obrazy f3 ®f duální k é® e3). □ Jakožto zobrazení U ® V —» K je obraz tenzoru 9 (g> rj dán předpisem u (g> v i—?► • #(w) a lze jej tedy popsat jako kompozici kde přirozený izomorfismus K (g> K = K je dán předpisem a (g> 6 i—> a&. 7.6. Izomorfismus mezi Hom(ř7, V) a Uvažujme bilineární zobrazení F x U* -+ Hom([7, F) definované předpisem (v, rj) i—> v ■ f] kde v ■ f] je lineární zobrazení u i—?► v ■ r](u) (skalární násobek vektoru v). V souřadnicích je toto zobrazení opět dáno násobením matic, tentokrát v opačném pořadí než u evaluace. Podle univerzální vlastnosti tenzorového součinu toto zobrazení indukuje lineární zobrazení V®U* -^Hom(U,V). Věta 7.8. Je-li U konečné dimenze, pak je výše uvedené zobrazení izomorfismus. 59 7. Tenzorový součin Důkaz. Nechť a = (ej) je báze U s duální bází (/■?) a nechť (3 = (ej) je báze prostoru V. Ukážeme, že ke každému tp: U —> V existuje jediný vzor, ten si označme 'i,3 Jeho obraz je Y2i j{eí ' f1)01) a stačí porovnat hodnoty na bázových vektorech es 'i,3 't Dostáváme tak jediné řešení: a'ls musí být i-tá souřadnice tp(es). Zejména je tedy a* rovno prvku matice zobrazení tp, a\ = {{ f3 na matici , která má jediný nenulový prvek na místě (i,j) roven 1. Zjevně matice Ej tvoří bázi prostoru všech matic, což dává alternativní důkaz předchozí věty. Z předchozí věty je dobře vidět, že většina tenzorů není „jednoduchých", tj. tvaru v (g> rj. Takovým nenulovým tenzorům totiž odpovídají přesně zobrazení U —> V hodnosti 1, neboť jejich obraz je právě podprostor generovaný v. Ve skutečnosti má ale většina zobrazení maximální hodnost min{dimč7, dimF}. cv Cvičení. Jaký je vzor id £ Hom(č7, U)l 7.7. Tenzorová algebra vektorového prostoru Definice 7.9. Algebrou rozumíme vektorový prostor A, který je současně okruhem a to takovým způsobem, že násobení A x A —» A je bilineární. Alternativně tedy můžeme psát násobení jako lineární zobrazení A (g> A —> A. Známe již poměrně dost příkladů algeber - algebru čtvercových matic, algebru komplexních čísel (obecněji libovolné rozšíření těles), za chvíli poznáme algebru kvaternionů. Tenzorový součin p kopií duálního prostoru U* a q kopií prostoru U se označuje T«U = U ®---®U(g)U* ® • • • ® CT . Jeho prvky se nazývají tenzory typu (p, q). Díky Větě 7.8 je TpU = Hom(č7®p, U®q). Naším dalším cílem bude z těchto prostorů vyrobit tzv. tenzorovou algebru vektorového prostoru U. Prvně definujeme násobení V-v-' V-v-' V-v-' tj. součinem tenzoru typu (pi,qi) a tenzoru typu (p2,Q2) Je tenzor typu (pi + P2,Qi + Q2), konkrétně ((ui ®-"®u?1)®(i)1®'"®if1))® {{vi 0 ■ ■ ■ 0 vq2) W je jednoznačně určeno svými zúženími Ví —> W, kterážto mohou být libovolná lineární zobrazení. * Položme Tq U = K. Potom tenzorová algebra vektorového prostoru U je direktní součet vektorových prostorů oo p,q=0 To je opět vektorový prostor, i když nekonečné dimenze. Násobení na T*U je jednoznačně určeno tím, že má být bilineární a svým chováním na jednotlivých TpU. Příklad. Součinem tenzorů 2 f ®U!®U2- 3f2 ®u3® u3, 4/3 ® u3 - f2 0 «i je tenzor (2/1 ® ui ® u2 - 3f2 ®u3® u3) 0 (4/3 ®u3- f2 ® ui) = = 8/1 <8> f ® ui ® u2 ® u3 - 2 f ® f2 ®u1(S)U2®u1 -I2f2 ® f3 ®u3®u3®u3 + 3f2 0 f2 (8> u3 (8> u3 (8> «i. 7.8. Souřadnice tenzorů Nechť a = {e{\ je báze prostoru U a a* = {f1} duální báze prostoru U*. Potom všechny tenzory tvaru eh ® ■ ■ ■ ® eiq ® fjl ® ■ ■ ■ ® fp tvoří bázi prostoru Tp(U) a každý tenzor t G Tp(U) lze psát právě jedním způsobem ve tvaru £ • eil ® • • • ® ei? ® ® • • • ® íl,...,jq Ji.....Íp Čísla ilj/"%jv £ K nazýváme souřadnicemi tenzoru i G Tp{U) v bázi a. Všimněte si, že dolní index p značí počet dolních indexů, zatímco horní index q značí počet horních indexů u souřadnic. Každý vektor u G U je tenzorem typu (0,1), neboť To(U) = U. 61 7. Tenzorový součin Jeho souřadnice v bázi a budeme zapisovat pomocí horních indexů n u = a*ej. i=i Každá lineární forma r] £ U* je tenzorem typu (1,0), neboť 7?(í/) = U*. Její souřadnice v bázi a budeme zapisovat pomocí dolních indexů n Každá bilineární forma g na U je tenzorem typu (2, 0), neboť T2°([7) = U* 0 U* ~ Lin2([/ x U,K). Její souřadnice v bázi a budeme zapisovat pomocí dolních indexů i, j Každé lineární zobrazení p: U —> U je tenzorem typu (1,1), neboť Tl{U) = U®U* ~ Hom([/, [/). Jeho souřadnice v bázi a budeme zapisovat takto: p = ^2a)ei®fj. i, j Ukážeme, že matice lineárního zobrazení p: U —> U v bázi a je kde i označuje řádek a j sloupec. Platí totiž, že v i-tém řádku a j-tém sloupci matice ((p)a,a je i-tá souřadnice vektoru p(ej), tj. f\p{e3)) = ľ(^ďser® A{e3) ^ r,s ' = fi('£arserr ^ r,s Od této chvíle budeme tedy v kapitole o multilineární algebře značit matice zobrazení jako (ap, kde i značí řádek a j sloupec. 62 (erJ = a j 7. Tenzorový součin Násobení tenzorů lze v souřadnicích popsat takto: (t (g> sÝ1'lqi+q2 = £n"'íql SÍ K na dvojici vektorů u a v je postupně součin tenzorů g ®u®v a následná kontrakce prvních a druhých složek (tj. složení s evaluací U (g> U* —> K). V souřadnicích i,j,t,s i,j Vyčíslení lineárního zobrazení p: U —> U na vektoru u £ U je postupně součin tenzorů p®uíiU®U*®U a kontrakce mezi druhou a první složkou. V souřadnicích = a)xsfj(es)ei = ^ ( aJxJ Ie* M> i 3 Souřadnice výsledného vektoru jsou tedy • a*x-'. Kroneckerův tenzor S je prvkem U®U*, který odpovídá identickému zobrazení z Hom(č7, U). Jeho souřadnice v libovolné bázi jsou 7.9. Grafický kalkulus Ve cvičení jsme reprezentovali tenzory pomocí obrázků, dále pak jejich tenzorový součin, identitu, evaluaci, skládání, atd. Základní identity jsou u u®u*®u u u* u*®u®u* -^->-u* Díky nim lze přecházet mezi zobrazeními U®p —> U®q a tenzory z TpU. Dále jsme definovali stopu zobrazení, tj. prvku T\\J jako napojení výstupu do vstupu (kontrakce). 7.10. Souřadnice tenzorů při změně báze Nechť a = jej} je báze prostoru U s duální bází a* = {f1} prostoru U* a nechť /3 = {ej} je jiná báze prostoru U s duální bází /3* = {f1}. Nechť A = (ďj), i značí řádky, j značí sloupce, je matice přechodu od báze a k bázi /3, tj. A = (id)^a, (ei,... ,en) = (ěi,.. .,ěn)A. 63 7. Tenzorový součin Dále nechť B V/v Dualita potom říká E V/v lei )•••)°n) B V/v (el)• • • ) en)A, díky čemuž B = A 1. Označíme-li Z? = (&*•), pak dostáváme vztahy jejichž dosazením do vztahu definicujícího souřadnice tenzoru dostaneme následující větu. Věta 7.10. Nechť t £ Tp(U) je tenzor o souřadnicích t1^"1? ^ bázi a. Jeho souřadnice v bázi /3 jsou při použití sumační konvence Vi-X ~~ akial2 ■ ač t^";^bl}_b[?. .. .bl? kq hh...lp ji j2 (Sčítáme tedy přes všechny indexy k\, ..., kq, l\, ..., lp.) □ Příklad. Nechť u je vektor se souřadnicemi x% v bázi a a xl v bázi /3. Podle předchozí věty (2 uX Tedy (u)p = A(u)a = (id)íga(u)c což je nám známo již z dřívějška. Příklad. Nechť / je lineární forma se souřadnicemi yj v bázi a* a souřadnicemi yj v bázi /3*. Podle předchozí věty ví = ^yib) i Tedy (/)/?* = (f)a'B = (/)a.(Íd)a/3, kde jsou ale souřadnice forem brány jako řádky jako obvykle. Příklad. Lineární zobrazení p: U —> U je tenzor typu (1,1). Jeho matice (p)aa = {ť1-) je zadána souřadnicemi tohoto tenzoru. Podle předchozí věty jsou jeho souřadnice v bázi /3 *5 = £aÍtŕ&i = Eai(E*ŕ« 'i,3 maticově (W = A(p)aaB = A(p)aaA 1 = (id^^^id)^, což je nám již známý vztah pro transformaci matice zobrazení. 64 7. Tenzorový součin Příklad. Bilineární forma na U je tenzor typu (2,0). Matice této formy je dána souřadnicemi tenzoru (tij) (i značí řádek, j sloupec). Podle předchozí věty % = £*^&H£&H£ífci&5)' maticově Ť = BTTB = (id)^T(idW, což je nám již z dřívějška známý vztah pro transformaci matice bilineární formy. Poznámka. Pořadí má být opačné. Příklad. Nechť V je vektorový prostor s bází (ei, e2) a duální bází (f1, f2). Vyjádřete tenzor f1 0 (ei + e2) G Tl(V) v bázi (éí, e2) a duální bázi (f1, f2), jestliže (ěí,ě2) = (e1,e2)^ * Řešení. Platí (ei,ě2) = (e1,e2)A. Chceme vyjádřit ei, e2 pomocí éí, e2 a Z1, /2 pomocí f1, f2. Z předchozí rovnice okamžitě dostáváme ,_i ----f-2 1 {ei,e2) = {e1,e2)A =(ei,e2)l g _1 Dále hledáme vyjádření ve tvaru Platí E = (f(ej)) = (^2) (^2) = 5 (j^ (éí,é^)A_1 = B ■ EA-1 = B ■ A'1. Tedy musí být B = A^1, proto (J2) = (3 2) (já) • Odtud dosadíme do našeho tenzoru f1 ® (ei + e2) = (fí + J2)® (-2éí + 3é2 + éí - e2) = {71+72)®{-e1+2e2) = -f1 (g> éí - f2 ® éí + 2/1 ®e2+ 2f2 ® e2. 65 7. Tenzorový součin 7.11. Tenzory ve fyzice, jiná definice tenzoru Předchozí věta o transformaci souřadnic tenzoru při změně báze nám umožňuje porozumět tomu, jak jsou tenzory chápány ve fyzice. Tenzor typu (p, q) nad vektorovým prostorem U každé bázi a v U přiřazuje np+9-tici čísel ^h"%Jv ^ P^čemž Při změně báze probíhá transformace těchto čísel podle věty z předchozího paragrafu. 66 p 8. Symetrické a antisymetrické tenzory 8.1. Symetrická mocnina Od této chvíle nechť K je těleso charakteristiky 0. Grupu permutací množiny {l,...,q} označme T,q. Dennice 8.1. Definujme symetrickou mocninu SqU jako kvocient (^)q U podle vektorového podprostoru generovaného tenzory tvaru ua(l) <8> • • • <8> ^cr(g) - Ui (g) ■ ■ ■ (g) Uq. Třídu prvku u\ V multilineární zobrazení, pak existuje jediné lineární zobrazení G: &)q U —> V díky univerzální vlastnosti tenzorového součinu. Je-li navíc <ř symetrické, pak G{Ua(l) ® ■■■ ®Ua(q)) = $(nCT(l), • • • = $(«1, ...,Uq) = G{uX Ua^ - Ul ■ ■ ■ Uq) (Uq+l Sq+rU má tvar {u\ ■ ■ ■ uq) ■ {uq+\ ■ ■ ■ uq+r) = Ui ■ --UqUq+1 ■ ■■Uq+r. 67 8. Symetrické a antisymetrické tenzory ** 8.2. Symetrické tenzory Uvedeme nyní alternativní definici SqU, konkrétně jako podprostoru (g)9 U. K tomu budeme potřebovat několik definic. Pro permutaci o G T,q máme lineární zobrazení Pa ■■ ®q U ->• (g)9 U, Ul g> • • • g> Ug !->• Ua(q) g> • • • g> Ua(q). cv Platí pT o pCT = paOT; to je proto, že pTpa(ui <8> • • • <8> m9) vznikne z výše uvedeného vztahu pro Pa(ui g> • • • g>ug) tím, že na i-té místo napíšeme člen na r(i)-tém místě, tj. ua(T^y Výsledkem tak bude uo-(t(1)) ® ■ ■ ■ ® Ua(r(q)) = Par («1 <8> • • • <8> Uq). Konkrétně si lze předchozí důkaz demonstrovat na příkladu P(23)P(12)(U1 ®u2 ®U3) = P(23)(^2 <8> «1 ®«3) = ^2 <8> ii3 ® «1 = P(123)(ul ® ^2 <8> ^3)5 přičemž (12)(23) = (123) / (23)(12). Definice 8.3. Řekneme, že tenzor t G (g)9 ř7 je symetrický, jestliže pCTí = í pro každou permutaci u\ g> u2 dostaneme tenzor (sčítance odpovídají postupně permutacím id, (12), (23), (13), (231) a (321)) -{Ul g> Ul g> U2 + Ul g> Ul g> U2 + Ul g> U2 g> U\ + U2 g> U\ g> U\ + U\ g> U2 g> U\ + 6 .1 1 1 +U2 g> Ul (g) Ul) = -Ul g> UX g> U2 + -Ml g> U2 g) Ul + -U2 g> Ul g) Ul O O O Symetrizace zjevně zadává lineární zobrazení Sym: (g)9 ř7 —>■ (g)9 ř7. Lemma 8.5. Platí pa o Sym = Sym = Symop^. Důkaz. Dokážeme první rovnost, druhá se dostane podobně. Platí pCT(Sym(í)) = ^ PÁPÁt)) = J H P™* = é H Pr* = Sym(í) (pro r G T • • • (g> uq) = Sym(ucr(1-) (g> • • • (g> Mff(9)), tj. Sym faktorizuje přes S*9?/, takže dostáváme indukované zobrazení s: SqU —> U. Platí s(ui • • • u9) = Sym(ui (g> • • • (g> uq) = ^ ^ uct(1) (g> • • • (g> uCT(9), z čehož dostáváme p(s(u! • • • Ug)) = ^^2 uCT(1) • • • uct(9) = ^2 U± • • • U1 = U± • • • U1 reSq reSq a tím pádem p o s = id. Názorně to znamená, že s vybírá z každé třídy rozkladu SqU = (^)9č7/kerp nějakého reprezenta této třídy; proto p indukuje izomorfismus ims ^> SqU. Přitom zjevně im s = im Sym a podle důsledku se jedná o prostor symetrických tenzorů. 8.3. Báze prostoru symetrických tenzorů Budeme používat zkrácené značení u"1 ... , pokud se vektor u j vyskytuje v součinu a j-krát. Věta 8.7. Nechť (ei,..., en) je báze prostoru U. Potom {e"1 ... | a± + • • • + an = q} je báze Sq{U). Důkaz. Tvrzení dokážeme s pomocí Lemmatu 6.1, budou nás tedy zajímat lineární zobrazení Sq(U) —> V nebo ekvivalentně symetrická g-lineární zobrazení <í>: t[q U —> V. To je jednoznačně určeno svými hodnotami na g-ticích bázových vektorů s tím, že tyto hodnoty mohou být libovolné, ale symetrické, tj. jsou jednoznačně určeny (libovolnými) hodnotami na (e^,..., ej ), kde i\ < ■ ■ ■ < iq. Při izomorfismu Linq(U, ...,[/; V)sym ^ Rom(SqU, V) odpovídá <í> lineárnímu zobrazení F: SqU —> V a platí tedy, že toto je jednoznačně určené svými (libovolnými) hodnotami F(eh ■■■eíq) = *(eil,...,ei?), kde i\ < ■ ■ ■ < iq, jak jsme chtěli dokázat. □ Důsledek 8.8. Dimenze prostoru Sq(U) je (n+^ 1)- Důkaz. Spočítejte, kolik existuje n-tic (a±,..., an) nezáporných celých čísel takových, že a± + ■ ■ ■ + an = q. (Je jich stejně, jako je různých posloupností q znaků • a n — 1 znaků |, například (1,0,2,1) odpovídá • | | •• | •.) □ Speciálně pro U = (Kn)* můžeme chápat formy f1 z duální standardní báze jako proměnné xl (jsou to zobrazení Kn —> K jejichž hodnota na (x1,..., xn) je právě xl). Potom lze symetrickou algebru S^K™)* ztotožnit s algebrou K[a;1,..., xn] polynomů nad tělesem K v proměnných prvky této algebry pak interpretovat jako polynomiální funkce na Kn. 69 8. Symetrické a antisymetrické tenzory 8.4. Antisymetrická mocnina Označme signcr znaménko permutace o. Zopakujeme předchozí výklad pro antisymetrická (nebo též alternující) g-lineární zobrazení, tj. zobrazení <í>: Y\q U —> V splňující $(uCT(i), • • -,u^g)) = signcr • ...,uq) pro libovolnou permutaci (zjevně stačí zkontrolovat pro transpozice, které generují Tiq). Vektorový prostor antisymetrických g-lineárních zobrazení budeme značit Ling(č7,..., U; V)ait- Definice 8.9. Definujme antisymetrickou mocninu AqU jako kvocient (^)q U podle vektorového podprostoru generovaného tenzory tvaru ua(l) ® ■ ■ ■ ® ua(q) ~ sign O ■ Ui ® ■ ■ ■ ® Uq. Třídu prvku u\ uq budeme značit u\ A • • • A uq; platí tedy uCT(i) A • • • A u^fa) = sign o • ui A • • • A uq. Zejména platí u\ A • • • A uq = 0, kdykoliv U{ = u j (prohozením Ui, u j se výraz jednak nezmění a podle definice změní znaménko; v nulové charakteristice to znamená, že je tento výraz nulový). Antisymetrická mocnina AqU má opět jistou univerzální vlastnost: nqu—*—t v Li S / t ^ , / AqU Je-li <ř multilineární zobrazení, pak existuje jediné lineární zobrazení G: U —> V díky univerzální vlastnosti tenzorového součinu. Je-li navíc <ř antisymetrické, pak G{ua(i) ®---®ua(qy) = $(^(1),...,^)) = sign o-•$(«!,..., u9) = sign a ■ G{ux ® ■ ■ ■ ® uq). Proto G indukuje jediné lineární zobrazení F, pro které zjevně platí F(Ul A • • • A Uq) = $(Ul,...,uq). Naopak, pokud je F lineární zobrazení, pak kompozice F o po t je antisymetrické g-lineární zobrazení. Věta 8.10. Platí Hom(A9ř7, V) = Lin9(ř7, ...,[/; F)ait. □ Ukážeme nyní, že AqU je ve skutečnosti kvocientem podle ideálu, takže se jedná opět o algebru. Protože je (^)q U generovaný jednoduchými tenzory, stačí ukázat, že iua(i) ® • • • <8> ua^ - sign a ■ ui • • • (g> uq+r) opět leží v jádře projekce a podobnou symetrickou vlastnost. To je ale jasné, neboť se jedná o generující tenzor pro permutaci cr + id, která je a na prvních q prvcích a identita na posledních r prvcích. Násobení AqU (g> ArU —> Aq+rU má tvar (u\ A • • • A uq) • {uq+\ A • • • A uq+r) = Ui A • • • A Uq A Uq+i A • • • A Uq+r. 70 8. Symetrické a antisymetrické tenzory ** 8.5. Antisymetrické tenzory Uvedeme nyní alternativní definici AqU, konkrétně jako podprostoru (^)q U. K tomu budeme potřebovat několik definic. Definice 8.11. Řekneme, že tenzor t £ &)q U je antisymetrický, jestliže pat = signcr • t pro každou permutaci o. Definice 8.12. Antisymetrizace tenzoru t je tenzor Alt (i) = ^ STe£q signcr • Prt- V předchozí definici používáme nulovou charakteristiku K k tomu, abychom mohli dělit nenulovým číslem q\ 7^ 0. Příklad. Antisymetrizací tenzoru u\ g> u\ g> u2 dostaneme tenzor (sčítance odpovídají postupně permutacím id, (12), (23), (13), (231) a (321)) 1, -{Úl g> Ui g> U2 - Ui g> Ui g> - ^1 © U2 g> til - ii2 © ^1 © ^1 + Ui g> © «1 + U2 g> «1 © Ml) = 0 O Antisymetrizace zjevně zadává lineární zobrazení Alt: ř7 —>■ &)q U. Lemma 8.13. Platí pa o Alt = sign a ■ Alt = Alt opa. Důkaz. Dokážeme první rovnost, druhá se dostane podobně. Platí pCT(Alt(í)) = ji SÍgI1T ' PÁPÁť)) = g\ SÍgnřJ ' SÍSn(T ° a) • Proat reSq reSq = sign o • sign r • pTt = signcr • Alt (i) (pro těS, zjevně probíhají permutace t o a přes každý prvek T,q právě jednou). □ Důsledek 8.14. Obraz Alt((^)9č7) sestává právě ze symetrických tenzorů. Důkaz. Podle lemmatu je pcr(Alt(í)) = sign a ■ Alt (i), takže Alt(í) je vždy antisymetrický. Na druhou stranu každý antisymetrický tenzor t leží v obraze Alt, neboť Alt(*) = Í signr-prí = ^ Y, t = t- D reSq reSq Ve skutečnosti z důkazu jednoduše plyne Alt o Alt = Alt, takže Alt je projekce na prostor antisymetrických tenzorů. Druhá rovnost z lemmatu říká Alt(ucr(1-) g> • • • g> Mff^) = sign a ■ Alt(«i g> • • • g> uq), tj. Alt faktorizuje přes AqU, takže dostáváme indukované zobrazení s: AqU —> &)q U. Platí s(ui A • • • A uq) = Alt(«i g> • • • g> uq) = |f ^ sign a • ^(1) <8> • • • <8> ua^, r£Sq z čehož dostáváme p(s(ui A • • • A Uq)) = |f ^2 sign a • ^(í) A • • • A = ^ ^ ni A • • • A uq = u\ A • • • A uq reSq reSq a tím pádem p o s = id. Názorně to znamená, že s vybírá z každé třídy rozkladu AqU = (^)9č7/kerp nějakého reprezenta této třídy; proto p indukuje izomorfismus ims ^> AqU. Přitom zjevně im s = im Alt a podle důsledku se jedná o prostor antisymetrických tenzorů. 71 8. Symetrické a antisymetrické tenzory 8.6. Báze prostom antisymetrických tenzorů Věta 8.15. Nechť (ei,..., en) je báze prostom U. Potom {e^ A • • • A ejg | i\ < ■ ■ ■ < iq} je báze Ag(U). Důkaz. Důkaz je analogický symetrickému případu s tím, že antisymetrická g-lineární forma í>: Y\q U —> K je jednoznačně určena svými hodnotami na g-ticích bázových vektorů s tím, že tyto hodnoty mohou být libovolné, ale antisymetrické, tj. jsou jednoznačně určeny (libovolnými) hodnotami na (e^,..., ej ), kde i\ < ■ ■ ■ < iq. Při izomorfismu Linq(U, ...,[/; V)alt = Hom(A9í/, V) odpovídá <í> lineárnímu zobrazení F: AqU —> K a platí tedy, že toto je jednoznačně určená svými (libovolnými) hodnotami F(eh f\--- f\eiq) = $(eil,...,ei?), kde i\ < ■ ■ ■ < iq. □ Důsledek 8.16. Platí l 71 dimA^t/) = kde n = dim U. Věta 8.17 (Lineární nezávislost a vnější součin). Vektory u±,..., uq G U jsou lineárně závislé právě tehdy, když u\ A • • • A uq = 0. Důkaz. Jsou-li u±,..., uq lineárně nezávislé, lze je doplnit na bázi (u±,..., uq, uq+i,..., un) prostoru U. Potom u\ A • • • A uq je jeden z prvků báze Xq(U), tudíž je různý od nuly. Jsou-li ui,..., uq lineárně závislé, pak jeden z nich je lineární kombinací ostatních, nechť je to 9-1 Uq = ^""^ alUi. 1=1 Potom u\ A • • • A uq = ui A • • • A Ug-i A ( alu,i J ^ i=i ' 9-1 = ^2 a^l A • • • A Uq-i A Ui = 0. □ i=l 8.7. Vnější mocnina lineárního zobrazení Nechť p: U —> V je lineární zobrazení. Již dříve jsme ukázali, že existuje lineární zobrazení p®1 = p®-..®p; 0qU^0qV takové, že pm{uX (g> • • • (g> Uq) = p{ux) (8> • • • p(uq). 72 8. Symetrické a antisymetrické tenzory Nyní ukážeme, že existuje zobrazení na kvocientech (g)9 U ► (g)9 v p p MU---^ MV Aq K tomu zjevně stačí p o pm(ua^ (g) • • • (g) = sign o- • p o íp®q{ui ® ■■■®uq) neboli ^Kx(i)) a • • • a = signcr • MV. 8.8. Vnější mocniny a determinanty Věta 8.18. Nechť p: U —» U je lineárni zobrazení, které má v bázi a = (ei,..., en) prostom U matici A = (cŕj). Potom platí U posílající standardní bázi (ei,..., en) na danou n-tici vektorů, pro tato zobrazení pak platí B = a o P a dostáváme komutativní diagram ei A • • • A e. det P ■ e\ A • • • A er Tvrzení jednoduše plyne z komutativity. □ 73 8. Symetrické a antisymetrické tenzory Příklad. Nechť matice A AA2? Řešení. AA2: A2R = R ->• Příklad. Nechť 1 2 3 4 reprezentuje lineární zobrazení'. '. Čemu se rovná A2 Podle předchozí věty je matice tohoto zobrazení rovna detA = -l. c A (\ 0 0 0\ 4 0 0 0 3 8 2 0 \2 1 4 3/ Najděte kanonický tvar matice AA3. Matice A má vlastní čísla 1, 0, 2, 3 a příslušné vlastní vektory u±, u2, 113, 114 tvoří bázi R4. Potom Ui A u j A Uk tvoří bázi A3M4. Protože Aa3(uí A u j A Uk) = Auí A Au j A Au^ = XiXjXkUi A u j A u^, má matice AA3 vlastní vektory, které tvoří bázi A3M4 s vlastními čísly 0, 0, 0, 6. Tedy Jordánův kanonický tvar matice AA3 bude /0 0 0 0\ 0 0 0 0 0 0 0 0 \0 0 0 6/ Kontrolní otázky 1. Nechť lineární transformace p: U —> U má vlastní čísla X±, A2, A3, ..., Afc. Jaká vlastní čísla má duální zobrazení p*: U* —» U*l 2. Nechť R3[x\ je vektorový prostor polynomů stupně nejvýše 3. Udejte příklad nenulové lineární formy M.s[x] —> R, nenulové bilineární formy M.s[x] xl[i] —> R, nenulové 3-lineární formy R3[x] x R3[x] x M3[x] ->• M. 3. Vyslovte definici tenzorového součinu U ®V & vysvětlete, co je tenzor u 0 v, kde u g ř7 a u g F. 4. Ukažte, jak se použije univerzální vlastnost tenzorového součinu pro definici zobrazení pi (g> P2, kde : U\ —> Ví, P2 '■ U2 —> V2 jsou lineární zobrazení. Nechť p\ je dáno maticí '1 2\ . . , /3 4\ ,r Í3\ (1N 4 I, p2 je dano matici I I. Vypočtete p\ (g> p2 na I ^ I (g> I 5. Udejte příklad nenulového symetrického tenzoru S'3(M2). 6. Vysvětlete, co znamená symbol ivu, kde v g ř7, íj g Afc(č7*). Vyjádřete pro ř7 y) = xiy2 - x2yi + x2y3 - ^3ž/2 a v = (1, 2, 3). Příklady k procvičení 1. Vyčíslete tenzory: 74 8. Symetrické a antisymetrické tenzory (a) t = f1 ® e2 + f ® (ei + 3e3) G T^M3) na vektoru v = e± + 5e2 + 4e3 a formě / = /1 + /2+/3- (b) t G Tg (M4) se všemi souřadnicemi rovnými 3 na pětici (v, v, v, f, /), kde f = f1 — f4 a v = e\ + 2e2 + 3e3 + 4e4. (c) r = 2 • i (g> s + s (2> i, kde i = 2 • f1 (g> ei, s = f2 ® (2ei — e2), na čtveřici (ei, 3ei — 62,2/! +Z2,/1). [Řešení: (a) /) = 21; (b) t(v, v, v, f, f) = 0; (c) r(eu 3ei - e2, 2/1 + /2, /x) = -16.] 2. Spočtěte souřadnice (a) t\2 tenzoru t G T2(M2), jehož souřadnice jsou v bázi (ei, e2) všechny rovny 1, v nové bázi (ěi,ěi) = (ei, e2) (b) í}2 tenzoru i = /x (g> f2 (g> (ei + e2) G T£(R2) v nové bázi (ěi,ěi) = (ei, e2) (c) í31 tenzoru /2 (g> /x (g> e3 (g> ei + f3 (g> /3 (g> ei (g> e2 G T22(M3) v nové bázi /l 0 0 (ěi,ě2",ě^) = (ei,e2,e3) 2 1 0 \3 2 1 (d) í123 tenzoru í G T2(M3) se všemi souřadnicemi rovnými dvěma v bázi (ei,e2,e3) v nové bázi /l 2 3^ (ěT,^,^) = (ei,e2,e3) 0 1 2 \0 0 1, [Řešení: (a) t{2 = -9; (b) í}2 = 4; (c) = 3; (d) = 0.] 3. Spočtěte kontrakci tenzoru (a) 3 • f1 g> ei g> e2 — 2 • f2 (g> e2 (g> e2 podle 1. a 2. složky. (b) (Z1 - 2/3 + 3/4) 0 (ei + 3e2 - e3) (c) (f1 + f2+ř + ŕ) ®el + (f1 + 2/2 + 2/3 + 4/4) ®e2+ 2{f - f2 - /4) 0 e3 (d) /2 (g> Z1 (g> e3 (g> ei + /3 (g> /3 (g> ei (g> e2 podle druhých složek. [Řešení: (a) -2e2; (b) 3; (c) 3; (d) f2 ® e3.] 75 8. Symetrické a antisymetrické tenzory 4. Pomocí matice /2 1 0 0\ 110 0 "0011 \0 0 1 2/ proveďte snížení a povýšení tenzoru (f1 + f2) (g> (e3 + e^) — (f1 + /3) (g> e3 [Řešení: Snížení (3ei + 2e2) 0 (e3 + e4) - (2e± + e2 + e3 + e4) (g> e2, povýšení (f1 + /2) (g> /3 + (/l+/3)0(/4_2/3).] 5. Nechť t G Tq(U) je symetrický a s G T^iJJ) antisymetrický tenzor. Dokažte, že tenzor vzniklý násobením a následnou kontrakcí v obou složkách tijS13 je roven nule. 6. Dokažte, že pro operátory symetrizace S: Tq{U) —> Sq{U) a antisymetrizace A: Tq{U) —> Aq{U) platí SoA = AoS = 0. 7. Dokažte, že pro dimč7 > 2 nejsou prostory A2(A2(Č7)) a A4(Č7) izomorfní. 8. Dokažte, že tenzor t^/u G Tq(U) symetrický vzhledem k i, j a antisymetrický vzhledem k j, k je roven nule. 76 9. Determinanty, objemy a orientace 9.1. Objemová forma a determinant Objemová forma na U je libovolná nenulová antisymetrická n-lineárni forma Vol: Yľa U —> K, kde n = dim U, tj. Vol g Linn([/,..., U; K)alt 2a Hom(An[/, K) 3 vol; odpovídající lineární formu budeme značit vol: AnU —> K. Nechť (ei,...,en) je libovolná báze U. Nenulovost Vol je ekvivalentní tomu, že vol(ei A • • • Aen) = Vol(ei,..., en) 7^ 0, neboť Anč7 je generovaný e\ A • • • A en. Hodnotu Vol(«i,..., un) nazýváme orientovaným objemem rovnoběžnostěnu určeného těmito vektory. Díky objemové formě můžeme interpretovat determinant operátoru p: U —> U. Platí totiž Vol((/5(ui),..., p{un)) = vol((/j(ui) A • • • A p{un)) = det p ■ vol(«i A • • • A un) = det 0. Vraťme se nyní k obecné situaci reálného vektorového prostoru U. Věta 9.1. Dvě báze a, (3 jsou shodně orientované, právě když je lze spojit cestou, tj. právě když existuje spojité zobrazení 7: [0,1] U x • • • x U = Un splňující následující • 7(0) = a, 7(1) = (3 a • pro každé t g [0,1] je n-tice *y(t) bází U. Poznámka. Spojitost jistě dává smysl pro U = Mn. Avšak libovolný (konečně rozměrný) reálný vektorový prostor je izomorfní W1 a spojitost lze definovat ve smyslu tohoto izomorfismu -hlavně na volbě takového izomorfismu nezávisí. 78 9. Determinanty, objemy a orientace Důkaz. Není těžké se přesvědčit, že každou čtvercovou matici s kladným determinantem lze napsat jako součin elementárních s kladným determinantem. Prohození dvou sloupců lze nahradit kompozicí operací / —> I + II, II —> II — I, I —> I + II, která samozřejmě zároveň s prohozením sloupců také jeden z nich vynásobí číslem —1, ale Gaussova eliminace lze provádět i s touto operací. Vynásobení dvou sloupců číslem — 1 lze nahradit provedením dvou předchozích složených operací za sebou. Dále není těžké se přesvědčit, že každá z elementárních matic Tj s kladným determinantem lze spojit s jednotkovou maticí E cestou Ti procházející pouze maticemi s kladným determinantem. Jejich součin T = T\- ■ -Tk pak lze spojit s jednotkovou maticí jednoduše pomocí cesty íh+ri(í)---rfc(í). Jelikož však platí a = (3 ■ T, hledaná cesta mezi bázemi a, (3 lze volit například jako t ^ p ■T1(t)---Tk(t). V opačném směru veličina (det id7(í-)a) £ Mx závisí spojitě na t a její hodnota pro t = 0 je 1. Proto i její hodnota pro t = 1 musí být kladná, tj. (detid^) > 0 a báze a, (3 jsou shodně orientované. □ Důležitým příkladem objemové formy je objemová forma vzniklá ze skalárního součinu na orientovaném Eukleidovském prostoru £. To by nemělo být překvapující - skalární součin na £ udává smysl velikosti vektorů a úhlů mezi nimi; z těchto údajů lze objem spočítat. Objemová forma však udává orientovaný objem, proto je navíc potřeba ještě volba orientace. Z jiného úhlu pohledu na Eukleidovském prostoru jsou dvě objemové formy a není žádný důvod preferovat jednu z nich; ten nastává až při zafixování orientace. Pro neorientovaný Eukleidovský prostor bychom mohli nadefinovat pouze neorientovanou objemovou „formu" | Vol |; k ní se vrátíme za chvíli. Nechť a = (e±,... ,en) je libovolná kladně orientovaná ortonormální báze. Kanonickou objemovou formu zafixujeme požadavkem Vol(ei,... ,en) = 1. Je-li (é"i,..., é~n) jiná kladně orientovaná ortonormální báze, pak matice přechodu má kladný determinant a je ortogonální, takže tento determinant musí být roven 1, a proto Vol(ěi,..., én) = 1 • Vol(ei,..., en) = 1 a požadavek na Vol tedy nezávisí na volbě báze a. Nechť nyní (3 = (u±,... ,un) je libovolná n-tice vektorů a pišme (3 = a ■ P, kde „transformační matice" P má prvky souřadnice vektorů Uj v bázi a, tj. pl- = fl(uj). Potom Vol(«i,..., un) = det P ■ Vol(ei,..., en) = det P. Jelikož je báze a kladná, má (3 stejné znaménko jako det P, tedy jako Vol(«i,..., un). 79 9. Determinanty, objemy a orientace Tvrzení 9.2. Orientovaný objem Vol(ui,... ,un) lze spočítat jako determinant matice, jejíž j-tý sloupec je tvořen souřadnicemi vektoru u j v libovolné kladné ortonormální bázi (ta však musí být stejná pro všechny sloupce). Zejména signVol(ui, ...,un)= sign(ui,.. .,un). Jeho druhou mocninu lze spočítat jako Gramův determinant (Vol(ui,... ,un))2 = det((ui,Uj)) z matice, jejíž prvek na pozici je skalární součin (uí,Uj). Důkaz. Druhé tvrzení plyne z prvního uvážením det(PTP). Na pozici dostaneme součin i-tého a j-tého sloupce P, tedy Y^fk{^)fk{u]) = {u^u]) k (jedná se o vzorec pro skalární součin v ortonormálních souřadnicích). □ Jako důsledek dostáváme vzorec pro neorientovaný objem na Eukleidovském prostoru jako odmocninu z Gramová determinantu - ten závisí pouze na skalárním součinu a nikoliv na orientaci. Z tohoto pohledu lze interpretovat Gramův-Schmidtův ortogonalizační proces jako vzorec pro objem. Během něj totiž měníme každý vektor pouze přičítáním násobků předchozích vektorů a nemění se tedy orientovaný objem. Přitom po provedení celého procesu a pro vzniklý ortogonální systém (v±,... ,vn) je Gramová matice diagonální a neorientovaný objem je tak roven | Vol(ui,.. .,un)\ = |«i| • • • \vn\, tedy součinu velikostí vektorů v±,... ,vn. Znaménko je též jako u původního orientovaného objemu a je tedy určeno tím, zda je (ui,... ,un) báze kladná či záporná (v případě, že se nejedná vůbec o bázi, je objem beztak nulový). Přitom velikost vektoru v{ je rovna výšce rovnoběžnostěnu určeného u±,..., uí s podstavou danou prvními i—l vektory. Jedná se tedy o vzorec objem rovnoběžnostěnu = objem podstavy x výška Hlavní význam této formulky je pro nás v tom, že po několika stránkách je snad konečně zřejmé, proč tomuto objektu říkáme orientovaný objem. 9.3. Geometrie v rovině a prostoru Prvně se zabývejme rovinou £2, kterou budeme chápat jako M 2 se standardním skalárním součinem a standardní orientací. Ta je mimochodem totožná s tou vzniklou z komplexní struktury na C = ffi2. Pro vektory u, v G £2 počítejme neorientovaný objem z Gramová determinantu (Vol(u,v)ý (u,u) (u,v) (v,u) (v,v) \u\ \v\ (u,v)2 i 121 12 ■ 2 \u\ \v\ sm a, kde a je úhel mezi vektory u, v a rovnost plyne z (u,v) = \u\\v\ cos a. Odmocněním dostáváme vztah | Yo\{u,v)\ = \u\\v\\sina|. 80 9. Determinanty, objemy a orientace Standardně bereme a G [0,7r], díky orientaci můžeme nyní rozšířit definiční obor na a G (—7T, 7r] a zvolit znaménko podle orientace (u, v). Mluvíme pak o orientovaném úhlu od vektoru u k vektoru v a můžeme psát = Vol(u, = \u\\v\ sin a. Budeme psát a = <(u, v). (Lépe je samozřejmě brát a G M/27rZ.) Orientovaný úhel se hodí v úlohách, ve kterých je potřeba (zejména algoritmicky) rozhodnout o viditelnosti objektů v rovině. Dalším případem je úloha rozhodnout, zda mnohoúhelník A\ ■ ■ ■ An zadaný posloupností vrcholů je kladně či záporně orientovaný (v případě, že nevíme, zda je konvexní). Velice jednoduchým způsobem (alespoň z teoretického pohledu) je spočítat všechny orientované úhly <{AnAi, AľA2), <(A±A2, A2A3),<(An^An, AnA{) podél mnohoúhelníka a sečíst je. Pokud je součet roven 2tv, je mnohoúhelník kladně orientovaný, pokud — 2tv, je záporně orientovaný. Ostatní případy nemohou pro mnohoúhelník nastat a lze takto i detekovat některé případy, kdy se nejedná o mnohoúhelník (zdaleka ne však všechny). V případě, kdy je mnohoúhelník konvexní, budou mít všechny úhly stejné znaménko a to lze spočítat pomocí orientovaného objemu (u čtyřúhelníku stačí spočítat znaménka i v nekonvexním případě). Jiným řešením je sečíst orientované objemy \ Vol(AiA2, A1A3) + + Í VoKAiAn-i, A1An). Pokud je výsledek kladný, je mnohoúhelník kladně orientovaný a naopak. Příklad. Ukažme nyní, že výše uvedený součet vyjadřuje obsah mnohoúhelníku A\ ■ ■ ■ An. V prvním kroku dokážeme o něco obecněji, že součet Vol(XAu XA2) + ■■■+ Vol(VAn_i, XAn) + Vol(XAn, XA{) nezávisí na volbě bodu X. To je tím, že Vol(YAi, YAi+1) = Vol(YX + XA,t, YX + XAi+1) = Vol(XAi,XAi+1)+Vol(YX,XAi+1)+Vol(XAi,YX), kde členy Vol(YX, XAi+1) se při sečtení vyruší se členy Vol(XAi, YX) = - Vol(YX, XAj). V dalším kroku ukážeme, že existuje vnitřní diagonála AiAj, která protíná mnohoúhelník pouze v koncových bodech. Pak lze induktivně předpokládat, že vzorec pro obsah funguje pro oba mnohoúhelníky vzniklé rozdělením podél AiAj a jejich sečtením dokázat, že tento vzorec funguje také pro původní mnohoúhelník (členy obsahující diagonálu se vyruší). Nechť Ai je bod s nejmenší x-ovou souřadnicí. Pokud leží uvnitř trojúhelníku Aí-\AíAí+\ nějaký další vrchol mnohoúhelníku, zvolíme za Aj ten s nejmenší x-ovou souřadnicí. Pokud ne, zvolíme za dělící diagonálu Aí-iAí+i. Poznámka. Orientovaná Eukleidovská rovina5 je kanonicky (jednorozměrným) komplexním vektorovým prostorem: násobení i je rotace o 90° v kladném směru. Tím lze také definovat 5Ve skutečnosti stačí mít skalární součin zadán až na násobek - takové struktuře se říká konformní; lze v ní měřit úhly a porovnávat velikosti. Typickým příkladem konformního zobrazení, které není ortogonální, je stejnolehlost. 81 9. Determinanty, objemy a orientace orientovaný úhel mezi nenulovými vektory u, v jako <(u, v) = &ľg(v/u) - je totiž v = z-u pro jediné komplexní číslo z, jehož argument je přesně onen orientovaný úhel. Neorientovaná rovina má dvě komplexní struktury, které se navzájem liší o komplexní konjugaci. Ve výsledku je tak úhel jednoznačný až na znaménko. Přejděme nyní ke standardnímu orientovanému Eukleidovskému třírozměrnému prostoru £3. Krom skalárního součinu lze na £3 definovat vektorový součin pomocí objemové formy. Po dosazení dvou vektorů u, v £ £3 se z objemové formy stane lineární forma Vo\(u,v, -): £3 ->• R. Každá lineární forma je rovna skalárnímu součinu s jednoznačně určeným vektorem, který v tomto případě značíme u x v. Je tedy definován vztahem Vól(u,v,w) = (u x v,w). V kladné ortonormální bázi lze vektorový součin spočítat jako u x v = (u x v, e±) ■ e\ + (u x v, e2) ■ e2 + (u x v, e3) • e3 u1 v1 1 u1 v1 0 u1 v1 0 u1 v1 ei u2 v2 0 ei + u2 v2 1 e2 + u2 v2 0 es = u2 v2 e2 u3 v3 0 u3 v3 0 u3 v3 1 u3 v3 es kde výsledný determinant dává smysl pouze, pokud jej rozvineme podle třetího sloupce; dostaneme pak korektní vzorec u x v u2 v2 u3 v3 ei + u3 v3 u1 v1 e2 + u1 v1 u2 v2 es- Zabývejme se nyní abstraktními vlastnostmi vektorového součinu. Z antisymetrie platí (u x v, u) = Vol(u, v, u) = 0, a proto je u x v kolmý na u a analogicky také na v. Tím je určen jeho směr, nyní určíme orientaci a na závěr jeho velikost. Orientace je dána tím, že Vol(u, v, u x v) = (u x v, u x v) > 0 a je tedy (u,v,u x v) kladně orientovaná (za předpokladu, že se jedná o bázi; v opačném případě však u x v = 0 a jeho orientaci není potřeba určovat). Zbývá spočítat velikost u x v. Pomocí Gramová determinantu \u x v\2 = (u x v, u x v) = Vól(u, v,u x v) (u,u) (u,v) (v,u) (v,v) o o o 0 (u x v, u x v) 1/2 \u\2\v\2 1 \2\l/2 1 1 (u, v) ) -\ux v\ Pomocí úhlu a mezi vektory u, v dostáváme finální vztah \u x v\ = \u\\v\ sin a. Tentokrát není možné přiřadit úhlu a orientaci jako v rovinném případě. 82 9. Determinanty, objemy a orientace Věta 9.3. Vektorový součin má následující vlastnosti (které ho jednoznačně určují) • Vektorový součin — x — je antisymetrické bilineární zobrazení. • Vektor u x v je kolmý na u a v. • Vektor u x v je nenulový, právě když jsou u, v lineárně nezávislé a pak • báze (u, v, u x v) je kladně orientovaná. • Platí\u x v\ = \u\\v\sin<(u,v). 9.4. Vztah kvaternionů a orientovaného objemu Obecně můžeme říct, že objemová forma je kompatibilní se skalárním součinem, jestliže I Vol(ui,..., un)\ = \u\ \ ■ ■ ■ \un\ kdykoliv u\,... ,un tvoří ortonormální systém vektorů. Nad M je pak objemová forma Vol určena jednoznačně až na znaménko (orientaci), nad C jednoznačně až na násobek komplexní jednotkou. Jednoduchou modifikací ortonormální báze lze najít takovou ortonormální bázi, jejíž objem je roven 1. Standardní báze W1 a Cn jsou příklady takových bází. Zabývejme se prvně krátce situací v reálné Eukleidovské rovině £2. Objemová forma je Vol: £2 x £2 R, kterou můžeme díky skalárnímu součinu přepsat jako Vol(u, v) = (Iu, v). Protože je objemová forma kompatibilní se skalárním součinem, máme Vol(ei, ei) = 0, Vol(ei, e2) = 1, Vol(e2, ei) = -1, Vol(e2, e2) = 0 a tedy Ie\ = e2, /e2 = —e\. Díky tomu I2 = — id a zobrazení / zadává na V strukturu komplexního vektorového prostoru: v (a + bi) = va + I(vb) (samozřejmě, / je rotace o 90° v kladném směru). Nyní se zabývejme stejnou situací v „komplexní Eukleidovské rovině" £^- Předpokládejme, že skalární součin je lineární v druhé složce a tzv. „konjugovaně lineární" v první složce, tj. platí (au, v) = a~(u, v). Objemová forma je Vol: £2 x £2 —> C, kterou můžeme díky skalárnímu součinu přepsat jako Vol(u, v) = (Ju, v). Tentokrát je J: ££ —> £2 konjugovaně lineární, (J(ua),v) =Yo\(ua,v) = a\o\(u, v) = a(Ju,v) = ((Ju)a,v), tj. J(ua) = (Ju)ä. Z kompatibility se skalárním součinem Je± = e2, Je2 = — e\ a proto J2 = — id (druhá iterace už je lineární) a zobrazení J zadává na £2 strukturu kvaternio-nického vektorového prostoru: definujme kvaternionickou algebru H jako podalgebru generovanou /, J £ Hom^V, V), kde I = iE je násobení imaginární jednotkou i. Ukážeme, že jako vektorový prostor je generovaná E, I, J, K = IJ: už víme, že platí I2 = J2 = —E, IJ = —JI = K, počítejme nyní K2 = —JIIJ = J2 = —E a obdobně JK = —KJ = /, KI = -IK = J. Platí Ee\ = e\, le\ = e\i, Je\ = e2, Ke\ = e2i 83 9. Determinanty, objemy a orientace a tedy zobrazení H —> £^ , Q 1—> Qe± je izomorfismus. Obrazy E, I, J, K značíme postupně 1, i, j, k a v dalším budeme o H uvažovat jako o prostoru M4 = k] společně s násobením daným výše uvedenými vztahy. 1 i j k 1 1 i j k i i -1 k -j j j -k -1 i k k j —i -1 9.5. Dodatek ke geometrii v prostoru V této části dáme do souvislosti geometrii v prostoru s kvaterniony. Připomeňme, že kva-terniony vzniknou z komplexních čísel přidáním jednotky j, která antikomutuje s komplexní jednotkou i, tj. platí ij = —ji, a splňuje i2 = j2 = —1. Označme k = ij. Potom máme následující q = (a + xi) + (y + zi)j = a + (xi + y j + zk). Číslo a nazveme reálnou částí kvaternionu q a v = xi + y j + zk jeho vektorovou částí; lze totiž tuto část ztotožnit s vektorem (x, y, z) G M3. Chápeme proto komplexní jednotky i, j, k jako vektory standardní báze. Pro jejich součin platí výše uvedená tabulka, díky níž se snadno ověří, že v ■ w = —(v,w) + v x w. Jelikož je skalární součin komutativní a vektorový součin antikomutativní, dostáváme snadno vztahy (v, w) = —^{vw + wv) = — Re(uv), v x w = ^(vw — wv) = Im(uv). Orientovaný objem Vól(u,v,w) získáme jako reálnou část Vol(u, v, w) = —j(uvw — vuw + wuv — wvu) = — Ke(uvw). Zabývejme se nyní inverzí kvaternionu q = a+v. K tomu nám poslouží konjugovaný kvaternion q* = a — v. Platí q*q = (a — v)(a + v) = aa — vv = aa + (v, v) = \a\2 + \v\2 = \q\2 a tedy q^1 = \q\~2q*. Zejména, pokud je q jednotkový kvaternion, tj. \q\ = 1, dostáváme q^1 = q*. Kvaterniony mají také goniometrický tvar; my si vystačíme s jednotkovými kvaterniony, pro něž platí q = cos tp + v sin tp, kde p G [0,7r] a v G M3 je jednoznačně určený jednotkový vektor s výjimkou q = ±1, tj. p G {0,7r}, kdy není určený vůbec. Občas je také výhodné zapisovat ef° = cos p + v sin tp. Tento vztah dává smysl zejména, když výraz vlevo rozvineme do Taylorovy řady a využijeme vztahu v2 = — \v\2 = —1. Pro inverzní kvaternion platí (e^)-1 = e-^. 84 9. Determinanty, objemy a orientace Poznámka. Obecně pak platí vztah log(evew) = v + w+ vxw + -- - a známé pravidlo pro násobení mocnin v kvaternionech neplatí - důvodem je, že nejsou komutativní. Dva ryze imaginární kvaterniony komutují, vw = wv, právě když v \\ w a antikomutují, vw = —wv, právě když v _L w. Lze proto spočítat pro v \\ w což znamená, že vektor w se touto konjugací zachovává. Naopak pro v _L w platí we-Pv = ^(cos tp — v sin tp) = (cos tp + v sin ip)w = e^w a proto é^we-^ = é^é^w = e2^vw = (cos2p>)w + (sm2p>)v x w. Vektor v x w je kolmý jak na v, tak na w a má stejnou velikost jako w. Leží tedy épvwe~Lpv na kružnici procházející w a v x w a nachází se od w vzdálen o úhel 2tp. Ve výsledku tak konjugace épv geometricky odpovídá rotaci o úhel 2tp okolo osy dané vektorem v. Z těchto úvah plyne poměrně praktický popis toho, jak spočítat složení dvou rotací. Příklad. Nechť například R je rotace okolo osy x o úhel 60° a S je rotace okolo osy z o úhel 90°. Potom R odpovídá konjugaci kvaternionem e71"/6'* a S konjugaci e7T^4'k. Jejich složení SR je potom dané kvaternionem e*/4-ke*/6-i = ^/2j2 + . fc)(>/3/2 + 1/2 • i) = 76/4 + 72/4 • i + V2/4 • j + 76/4 • fe. Ve výsledku se tak jedná o rotaci okolo osy dané vektorem (1,1, y/Š) o úhel 2 arccos(\/6/4). Poznamenejme, že tento příklad lze počítat také pomocí matic. Složení dvou zadaných rotací má matici u 2 2 10 0. Vlastní vektor příslušný vlastnímu číslu 1 je (l,l,\/3), jak se snadno spočítá, a stopa této matice je | = 1 + (cos ip + i sin ip) + (cos ip — i sin p>) = 1 + 2 cos vwv je na vektorech v \\ w rovno vwv = vvw = —w a na vektorech v _L w rovno vwv = —vvw = w. /I o 0 \ \o 4 o \ 2 \) 85 9. Determinanty, objemy a orientace Jedná se tedy o reflexi vzhledem k rovině kolmé na vektor v (opět předpokládáme, že \v\ = 1). Zabývejme se nyní tím, co se stane při složení dvou reflexí, prvně podle roviny kolmé na v a poté podle roviny kolmé na v'. Dostaneme w i-> v'vwvv' = (—v'v)w(—vv') = ({v', v) — v' x v)w((v, v') — v x v'), tj. rotaci okolo vektoru v x v' = —v' x v o úhel 2 arccos(u, v'). 86 10. Smithův normální tvar celočíselných matic 10.1. Celočíselné matice Celočíselná matice tvaru n x m je kolekce celých čísel A = {á1-) indexovaná dvojicemi i = 1,... ,n a j = 1,... ,m. Píšeme A G Matnxm^- Celočíselné matice odpovídají homo-mornsmům grup: Lemma 10.1. Homomorfismy grup 7Lm —> 7Ln odpovídají přesně celočíselným maticím typu m x n. Homomorfismus příslušný matici A G MatnxmZ je x i—> Ax. Důkaz. Každý homomorfismus grup p: 7Lm —> Tli1 je jednoznačně určen obrazy p(e±),..., p{em) které ale můžou být libovolné: p(xľ, ...,xm)= p{e1x1 + ■■■+ emxm) = pie^x1 + ■■■ + p(em)xm { 0 a tyto jsou potom určené zcela jednoznačně. V dalším budeme vždy tuto volbu preferovat. Důkaz. Hlavním krokem je pomocí řádkových a sloupcových operací vyrobit v levém horním rohu největší společný dělitel všech prvků matice, dále pomocí něj vyeliminovat všechny prvky pod ním a vpravo od něj a následně použít indukci. Základním krokem je vytvoření největšího společného dělitele prvků ležících v témž řádku nebo sloupci. K tomu budeme využívat Eukleidův algoritmus, který spočítá největšího společného dělitele následujícím způsobem: jsou-li a, b nenulová celá čísla taková, že \a\ > vydělíme číslo a číslem b se zbytkem, a = qb + r. Potom gcd(a, b) = gcd(6, r). Nahrazením dvojice (a, b) dvojicí (6, r) se tedy největší společný dělitel nezmění. Navíc po konečném (ve skutečnosti velmi malém) počtu kroků vyjde r = 0; potom příslušné b v tomto kroku je hledaný největší společný dělitel. Pokud se vyskytují a, b v jednom sloupci, můžeme výše popsaný algoritmus realizovat pomocí řádkových operací a nahradit tak tyto dva prvky dvojicí (d, 0), kde d je největší společný dělitel a, b. To samé lze aplikovat na výskyt a, b v temže řádku pomocí sloupcových operací. 1. Vraťme se nyní k naší matici A. Prvně přesuňme na pozici (1,1) pomoci operací libovolný nenulový prvek matice A (rozmyslete si zvlášť případ A = 0). V dalších krocích se bude vždy prvek na této pozici zmenšovat, díky čemuž bude náš algoritmus konečný. 2. Pomocí Eukleidova algoritmu a jeho implementace pomocí řádkových a sloupcových operací můžeme dosáhnout toho, že prvek v levém horním rohu je jediný nenulový prvek v prvním řádku a prvním sloupci, tj. dostaneme matici tvaru 0 A 88 10. Smithův normální tvar celočíselných matic 3. Pokud by nyní prvek a\ nedělil nějaký prvek a*- matice A, můžeme jej pomocí přičtení řádku dostat do prvního řádku a pomocí kroku 2. opět na pozici (1,1) vyrobit menší prvek. Po konečném počtu kroku tak vznikne matice blokového tvaru qi o\ o A'J' v níž bude prvek q± v levém horním rohu dělit všechny prvky matice A'. 4. Na submatici A' můžeme použít indukční předpoklad a převést ji na Smithův normální tvar s invariantními faktory q2,...,qr. Protože q± dělil všechny prvky A', dělí i g2 (podle indukčního předpokladu je to největší společný dělitel všech prvků A') a tím pádem q± | g2 | • • • | qr tak, jak požadujeme. Zbývá dokázat jednoznačnost; ta bude plynout z invariantnosti dj vůči řádkovým/sloupcovým operacím a z jednoduchého výpočtu největších společných dělitelů dj pro matici ve Smithově normálním tvaru, kterým začneme. Zřejmě, pokud submatice obsahuje k-tý řádek, nikoliv však k-tý sloupec matice ve Smithově normálním tvaru, pak její determinant je nulový (jelikož obsahuje nulový řádek). Proto stačí uvažovat submatice složené z nějakých řádků a týchž sloupců. Ty jsou diagonální a jejich determinant je roven součinu prvků na diagonále - libovolných i prvků diagonály. Tedy největší společný dělitel je di = gcd{gfcl ■■■qki | 1 < fa < ■ ■ ■ < fa < r} = qi ■ ■ ■ qi a vskutku platí qi = di/di-i pro matici ve Smithově normálním tvaru. Zbývá dokázat invarianci největšího společného dělitele dj vzhledem ke sloupcovým operacím. Uvažujme tedy „starou" a „novou" matici, kde nová vznikne ze staré pomocí sloupcových operací (zatím ne nutně invertibilních). Zřejmě každý sloupec každé nové submatice je celočíselnou kombinací starých sloupců a její determinant je tedy celočíselnou kombinací starých subdeterminantů; zejména je každý nový subdeterminant dělitelný největším společným dělitelem dj starých subdeterminantů a zejména je nové dj dělitelné starým dj. Pokud byly operace invertibilní, lze také starou matici vyrobit z nové a proto je i staré dj dělitelné novým dj a tudíž se rovnají. □ Poznámka. Není špatné si povšimnout, že z existenční části plyne, že každá invertibilní matice je součinem elementárních matic, neboť jediná invertibilní matice ve Smithově normálním tvaru je jednotková matice, tedy P~ľAQ = E a A = PQ^1, a v převodu na Smithův normální tvar jsme používali pouze elementární matice. Smithův normální tvar je vhodný k algoritmickým výpočtům s komutativními grupami. Platí totiž následující vztahy im A = [qi ■ Pe\,..., qr ■ Per] ker A = [Qer+1,.. .,Qem], tedy obraz i jádro homomorfismu A lze jednoduchým způsobem získat ze sloupců matic P a Q a z invariantních faktorů Oj. 89 10. Smithův normální tvar celočíselných matic 10.2. Prezentace konečně generovaných komutativních grup Nechť M je komutativní grupa. V následujícím budeme komutativní grupy uvažovat vždy aditivně, tj. grupovou operaci budeme značit +, jednotku 0 a inverzi prvku a značíme —a. Nechť k G Z a a G M. Definujme a ■ k jako 0, pokud k = 0, jako a + • • • + a pokud k > 0 a jako ( — k) ■ (—a), pokud k < 0. Toto označení by čtenáři mělo být známe z multiplikativního zápisu ak, kde značí přesně to stejné. Výhodou tohoto zápisu je, že v každé (komutativní) grupě umíme automaticky násobit celými čísly, můžeme se tedy bavit o celočíselných kombinacích a používat okamžitě některé další pojmy z vektorových prostorů. Nechť cii,..., an £ M jsou libovolné prvky komutativní grupy M. Uvažujme následující homomorfismus grup p:Zn^M, (x1,... ,xn) ^ aix1 H----anxn. Lemma 10.4. Zobrazení p je skutečně homomorfismus grup. Navíc platí 1. p je surjektivní, právě když prvky a±,... ,an generují M. 2. p je injektivní, právě když jsou prvky a±,... ,an „lineárně nezávislé nad Z". □ Omezme se nyní na situaci, kdy prvky a±,... ,an generují M. Potom je p podle předchozího surjektivní a z algebry známe následující fakt, M ^ Zn/kerp, nazývaný první věta o izomorfismu. K pochopení konečně generovaných komutativních grup bude tedy dobré zkoumat grupu Zn a její podgrupy. Věta 10.5. Každá podgrupa Zn je opět konečně generovaná a ve skutečnosti izomorfní Zm pro nějaké m 2/i> • • • > Vm jsou lineárně nezávislé nad Z, pokud jsou lineárně nezávislé y±,..., ym a í / 0 (případ t = 0 je triviální a vyřeší se zvlášť). □ Poznámka. Podobné tvrzení pro nekomutativní grupy neplatí. Existuje grupa, která je generována dvěma prvky (jedná se o volnou grupu na dvou generátorech), která obsahuje pod-grupu, která je generovaná třemi, čtyřmi, ... prvky a dokonce i podgrupu, která není konečně generovaná. Přejděme nyní k hlavnímu konceptu této části - prezentacím. Nechť M je komutativní grupa generovaná prvky a±,..., an a uvažme surjektivní homomorfismus ip:Za^»M, ip(x1,... ,xn) = aix1 H-----^ anxn jako předtím. Podle předchozí věty je ker tp opět konečně generovaná komutativní grupa a můžeme tedy najít další surjektivní homomorfismus V>: Zm^kerp. Zavedeme-li pro složení Zm —> ker p TU1 označení R, budeme vzniklou situaci zapisovat Zm Zn M. V každé takové posloupnosti budeme vyžadovat, aby p> byl surjektivní homomorfismus grup a ker p> = im R. Potom dostáváme izomorfismus M ^ Zn/ker(^ = Zn/imR. Všimněme si, že pravá strana Zn/imi? závisí pouze na homomorfismu (matici) R. Říkáme proto, že R prezentuje komutativní grupu M. Poznámka. Prezentace grupy M lze definovat konkrétněji pomocí generátorů M a relací mezi nimi. Generátory e±,..., en grupy Zn odpovídají (zvoleným) generátorům a±,..., an grupy M a generátory grupy Zm budou odpovídat relacím mezi a±,..., an. Obrazy generátorů e j G 7Lm jsou nějaké celočíselné kombinace R(ej) =eir) + --- + enr™. Z podmínky ker p> = im R plyne, že analogické kombinace aiVj H-----h anrr- = 0 jsou nulové. To jsou přesně ony zmiňované relace mezi generátory M a M je v jistém smyslu „nejobecnější" komutativní grupa s generátory ai,...,an splňujícími tento systém relací. Přesněji, je-li ./V jiná komutativní grupa s prvky b±,..., bn splňujícími tytéž relace hr] + • • • + 6nr™ = 0, existuje jediný homomorfismus grup M —?► N posílající aj na 6j. Tento fakt nebudeme dokazovat, poznamenejme ale, že plyne (celkem snadno) z univerzální vlastnosti kvocientu 7Ln j im i?. 91 10. Smithův normální tvar celočíselných matic Konečně generované komutativní grupy jsou ve výsledku prezentovány celočíselnými maticemi. Nyní ukážeme, že ze znalosti Smithova normálního tvaru lze prezentovanou grupu zcela zrekonstruovat, samozřejmě až na izomorfismus. Obecněji se zabývejme případem ekvivalentních matic a jimi prezentovaných komutativních grup Z n -> M 1 Q s P 1 z m—>z n —v N Tvrdíme, že naznačený homomorŕismus M —» N existuje a je to navíc izomorfismus. Prezentované grupy můžeme ztotožnit s kvocienty podle obrazů a hledáme tedy homomorŕismus Zn/imR^Zn/imS. Ten lze jednoduše definovat předpisem i + imfí^ Px + imS. Jelikož se každý jiný reprezentant třídy x+imfí liší od x o prvek tvaru Ry, příslušná pravá strana se změní o třídu prvku PRy = SQy £ im S* a zůstane proto stejná - zobrazení je dobře definované. Inverzní zobrazení je určené týmž předpisem s P nahrazeným P-1. Tento výsledek lze vyjádřit heslem: izomorfní prezentace určují izomorfní grupy. Zabývejme se nyní tím, jakou grupu prezentuje matice ve Smithově normálním tvaru. Lemma 10.6. Je-li S ve Smithově normálním tvaru s nenulovými prvky q±\ ■ ■ ■ \qr na diagonále, pak Zn/ im S -=-► Z/qi x • • • Z/qr x Zn-'r Důkaz. Potřebné zobrazení se definuje snadno (x1,...,xn)+imS^([x1},...,[xr},xr+1,...,xn) a je jednoduché ověřit, že se jedná o dobře definovaný homomorŕismus grup. Stejně snadno se definuje i inverzní zobrazení. □ V kombinaci s předchozími úvahami dostáváme první část následující věty. Věta 10.7. Každá konečně generovaná komutativní grupa je izomorfní součinu cyklických grup (1) Z/qi x • • • x Z/qr x Zk, kde 1 7^ q\ \ ■ ■ ■ \ qr. Dvě takové grupy jsou izomorfní, právě když se rovnají odpovídající řády qi,... ,qr konečných cyklických faktorů a exponenty k beztorzních částí. Důkaz. Existenční část plyne z toho, že každá konečně generovaná komutativní grupa má prezentaci a taje ekvivalentní prezentaci ve Smithově normálním tvaru. Činitele tvaru Z/l = 0 můžeme vynechat. nd Jednoznačnost se dokáže následovně. Jsou-li dvě grupy tvaru (1) izomorfní, musí být izomorfní i jejich torzní části Zjq\ x • • • x Z/qr. Přitom qr je řád největší konečné cyklické 92 10. Smithův normální tvar celočíselných matic podgrupy a musí být tedy stejný pro obě grupy. Součin zbylých konečných cyklických grup je kvocient torzní části podle její největší cyklické podgrupy a musí být tedy opět izomorfní pro obě grupy. Podle indukčního předpokladu se musí rovnat všechna odpovídající q±,... ,qr-i-Kvocient podle torzní části je roven Zk a opět musí být tato grupa izomorfní odpovídající grupě 7jk . Tento izomorfismus je zprostředkován invertibilní maticí. Jelikož každá taková musí být nutně čtvercová, dostáváme k = k'. □ Poznámka. V tom důkazu jednoznačnosti je díra (největší cyklická podgrupa není jednoznačná a není jasné, proč by měl existovat izomorfismus velkých grup převádějící jednu na druhou), asi to chce fakt dělat přes vnější mocniny, viz níže. Alternativní věta dává rozklad každé konečně generované komutativní groupy na součin cyklických grup, jejichž řád je mocninou prvočísla. To snadno plyne opět ze Smithova normálního tvaru: jelikož je grupa Z/pkl x • • • x Z/p^r prezentována diagonální maticí s čísly pkl,... ,p^r na diagonále a tato má invariantní faktory 1,..., l,^1 • • -pkrr (jelikož dr-i = 1), platí Z/p'l1 x • • • x Z/pf *á Z/p'l1 ---pf (tomuto tvrzení se také říká Čínská zbytková věta). V opačném směru pak lze každou cyklickou grupu rozložit na součin cyklických grup, jejichž řád je mocninou prvočísla. Tento rozklad je také jednoznačný. ** 10.3. Poznámky Je-li M konečná, lze dát invariantnímu faktoru qn následující význam. Jedná se o nejmenší číslo t, pro které M ■ t = 0, tedy nejmenší číslo dělitelné řádem každého prvku. Poněkud abstraktněji definujme Ann(M) = {i £ Z | M • í = 0}, anihilátor komutativní grupy M. Jedná se vždy o podgrupu a platí Ann(M) = qn ■ 7L. Podobnou iterpretaci lze dát s trochou práce i zbývajícím invariantním faktorům, konkrétně Ann^+^M) = q,t ■ Z, k tomu je však potřeba definovat vnější mocniny komutativních grup, což značně přesahuje obsah kurzu. Vzhledem k jednoznačnosti z předchozí věty můžeme zformulovat jednoznačnost prezentace konečně generované komutativní grupy. Pro každé dvě prezentace musí jejich Smithovy normální tvary být shodné až na jedničky na diagonále (ty zhruba řečeno odpovídají přidání nového generátoru x společně s relací x = 0) a nadbytečné nulové sloupce (ty zase odpovídají relacím, které lze odvodit z ostatních relací). Mají-li matice R, S stejné rozměry, pak prezentují stejnou grupu, právě když jsou ekvivalentní (ve smyslu, že je lze na sebe převést řádkovými a sloupcovými úpravami). 93 11. Smithův normální tvar polynomiálních matic 11.1. Polynomiální matice Polynomiální matice tvaru n x m je kolekce polynomů A indexovaná dvojicemi i 1,... ,n, j = 1,... ,m. Tedy ď- je polynom, přesněji polynom s koeficienty v tělese K a v proměnné A. Píšeme A £ MatnxmK[A]. Lemma 11.1. Polynomiální matice A je invertibilní, právě když je čtvercová a její determinant je nenulový konstantní. Důkaz. Důkaz se provede stejně jako pro celočíselné matice. □ Věta 11.2 (o Smithově normálním tvaru). Pro libovolnou polynomiální matici A existují invertibilní polynomiální matice P a Q takové, že 0 P-XAQ 0 Q2 0\ \o ............ 0 OJ kde Qi\q2\~ "\Qr se postupné dělí. Polynomy qi se nazývají invariantní faktory, pravá strana se nazývá Smithův normální tvar polynomiální matice A. Každý jiný takový se liší pouze vynásobením qi nenulovou konstantou. Konkrétněji platí qi = di/di-i, kde di = gcdjdet S \ S je submatice A tvaru i x i} Důkaz. Důkaz se provede stejně jako pro celočíselné matice; jeho základem byl Eukleidův algoritmus, který funguje i pro K [A]. □ Opět můžeme vyžadovat polynomy qi normované, dostaneme pak Smithův normální tvar zcela jednoznačně. Poznámka. Je zajímavé se zamyslet nad tím, které (komutativní) okruhy umožňují Smithův normální tvar. Potřebujeme nějakou formu Eukleidova algoritmu a pro tzv. Eukleidovské obory (obory integrity s Eukleidovým algoritmem) není naprosto žádný problém. Ve skutečnosti lze tuto větu zobecnit na obory hlavních ideálů (obory integrity, kde každý ideál je hlavní), nevystačíme si však již s elementárními operacemi: k vyrobení největšího společného dělitele nestačí odčítat násobky, ale jsou potřeba obecnější (invertibilní) lineární kombinace. Ve výsledku se dá ukázat, že nad obory hlavních ideálů již není každá invertibilní matice součinem elementárních. Rozdíl mezi invertibilními maticemi a součiny elementárních matic je jedním z důležitých aspektů studovaných algebraickou K-teorií okruhu R. Ta je velmi důležitá v rozličných odvětvích matematiky - od geometrie, přes algebru až k teorii čísel. 94 11. Smithův normální tvar polynomiálních matic Stejně jako celočíselné matice měly vztah ke konečně generovaným komutativním grupám a jejich prezentacím, mají také polynomiální matice vztah k nějakým matematickým objektům a jejich prezentacím. Pokusme se jejich definici motivovat následujícím porovnáním číselné matice A G MatnxmK lineární zobrazení Km —> Kn celočíselné matice A G MatnxmZ homomorfismy grup Zm —> TU1 polynomiální matice A G MatnXm K[X] homomorfismy ??? K[X]m -+ K[X] n Definice 11.3. Nechť M je komutativní grupa. Řekneme, že M je K.[X]-modul, jestliže je zadáno zobrazení K[X] x M —^ M, (p,x)h+p-x, nazývané „násobení skaláry", splňující obvyklé axiomy vektorového prostoru p ■ (q ■ x) = (p ■ q) ■ x 1 • x = x p ■ (x + y) = p ■ x + p ■ y {p + q) ■ x = p ■ x + q ■ x Příklad. Důležitým K[A]-modulem je K[A]n, tj. množina všech n-tic polynomů společně se sčítáním po složkách a násobením po složkách P • (qi, ...,qn) = (pqi, ■ ■ -,pqn) Každý K[A]-modul M je automaticky vektorovým prostorem nad K: když umíme prvky M násobit polynomy, umíme je zejména násobit konstantními polynomy, které lze jednoduše ztotožnit s prvky tělesa K, lze psát K^K[X\. Zároveň násobení lineárním polynomem A je zobrazení m\ : M —> M, x \—> X ■ x, o kterém ověříme, že se jedná o lineární zobrazení: m\(ax + by) = A • ax + A • by = (aX) • x + (bX) • y = a{m\x) + b{m\y) Věta 11.4. Předchozí konstrukce zadává bijektivní korespondenci {K[X]-moduly M} í*"0*** ^T*'1^* je vektorový\ [prostor a 1 : V —^ V je operátor J M i-> (M, m x) V <-1 (V, T) V dalším budeme pro operátor T na vektorovém prostoru V používat pro odpovídající K[A]-modul označení (V,T). 95 11. Smithův normální tvar polynomiálních matic Důkaz. Zbývá ukázat, jak se pro operátor T: V —> V na vektorovém prostoru V definuje násobení skaláry z K[A]. Má-li se jednat o inverzi ke konstrukci (M, m\), jsme nuceni položit px = (po + piA H-----h PkXk)x = pox + piTx -\-----h pkTkx, kde T'lx značí i-násobnou iteraci operátoru T, tj. = (T o • • • o T)x = T(- • • T{Tx) ■■■)■ je totiž Vx = A(- • • X{Xx) • • •) = T(- • • T(Tx) • • • )• □ Z předchozího důkazu si zapamatujme vztah pro násobení polynomem p na K[A]-modulu (V,T). Budeme ho zapisovat ve tvaru p ■ x = p(T)x, kde p(T) značí, tak jako v důkazu, výsledek formálního dosazení operátoru T do polynomu p, tj. p(T) = po Id +PlT + ■■■+ pkTk. Poznámka. Výhodou uvažování K[A]-modulů namísto operátorů je to, že základním stavebním kamenem (konečně generovaných) K[A]-modulů je K[A]n (jak za chvíli uvidíme), který je jako vektorový prostor s operátorem nekonečně rozměrný a tedy z pohledu lineární algebry dost netypický. Konkrétně K [A] jako vektorový prostor je {(a0,ai,...) |3fcGN0:V/>fe:a( = 0}, množina posloupností čísel (odpovídajících posloupnostem koeficientů polynomů), která jsou od jistého indexu počínaje všechna nulová. Operátor je pak dán (a0,ai,...) i-)- (0,a0,ai,...) Dalším přirozeným pojmem je homomorfismus K[A]-modulů, který je přímou analogií lineárního zobrazení. Definice 11.5. Nechť M, N jsou dva K[A]-moduly. Zobrazení N se nazývá homo-morfismem 'K[X]-modulů, jestliže platí ip(x + y) = ip(x) + U je homomorfismus 'K[X]-modulů, právě když komutuje následující diagram. 96 11. Smithův normální tvar polynomiálních matic Důkaz. Jelikož je p> lineární, zachovává násobení všemi konstantními polynomy. Zbývá tedy zkontrolovat zachovávání násobení polynomem A, ale to jsou přesně operátory v diagramu. □ V případě, že je

: K[A]n —> M splňující K[A]n jsou v bijekci s polynomiálními maticemi A G MatnxmK[A], jejímž i-tým sloupcem je právě obraz e^. Příslušný homomorfismus je dán x \—> Ax. Důkaz. Vše je jasné z rovnosti (pip1, ...,pn) = p>{e1p1 + • • ■enpn) = p>{e1)p1 + ■■■ + p>{en)pn = aip1 H-----h anpn. Naopak výsledný vzorec je homomorfismus K[A]-modulů pro libovolné 04,..., &n G M. □ V dalším se nám ještě budou hodit kvocienty K[A]-modulů. Nechť M je K[A]-modul. Podmodul N C M je podmnožina uzavřená na nulu, sčítání a násobení skaláry. Zejména je ./V podgrupa vzhledem ke sčítání. Na kvocientu grup M/N definujeme strukturu K[A]-modulu následovně: {x + N) ■ p = xp + N Je jednoduché ověřit, že se jedná o dobře definované zobrazení, které splňuje všechny axiomy K[A]-modulu. * 11.2. Kanonická prezentace operátoru na Kn Nechť T: Kn —> Kn je operátor na Kn a uvažujme příslušný K[A]-modul (Kn, T). Narozdíl od situace pro konečně generované komutativní grupy existuje kanonická prezentace (tj. taková, která nezávisí na žádných volbách). Uvažujme homomorfismus K[A]-modulů • e^, kde na levé straně je interpretováno jako n-tice polynomů, zatímco na pravé straně jako n-tice čísel6. V obou případech se jedná o n-tici složenou z 1 na i-tém místě a z 0 na zbylých místech. Zřejmě je p> surjektivní zobrazení, popíšeme nyní jeho jádro a dostaneme tím prezentaci pro (Kn,T). Tvrzení 11.8. Nechť T je operátor na Kn. Potom K[X]n T~XE > K[A]n (Kn, T) je prezentace příslušného K.[\]-modulu. 6Alternativní pohled na prvky K[A]n je jako polynomy s koeficienty v K". Zobrazení je pak dáno předpisem u0 + A«i H-----h \kvk i-> «o + Tví H-----h Tkvk. 97 11. Smithův normální tvar polynomiálních matic Důkaz. Zbývá ukázat, že im(T — XE) = ker tp. Zaprvé platí tp o (T — XE) = O, neboť pro generátory G K[A]n platí ^ o (T - AE)(ei) = ^(Tei - Aeť) = Te^ - Ta = 0. Proto im(T — A-E) C ker KÍMn-> K[A]n/ im S(X) S(X) Opět se jednoduše přesvědčíme, že K[A]7imiS(A) ^ k[X]/(qi) x • • • x k[X]/(qn), kde q± \ ■ ■ ■ \qn jsou polynomy vyskytující se na diagonále Smithova normálního tvaru S(X). Věta 11.9. Dva operátory T, T' jsou podobné, právě když polynomiální matice T — XE, T' — XE mají týž Smithův normální tvar. Zejména lze problém podobnosti řešit algoritmicky. Poznámka. Nad algebraicky uzavřeným tělesem lze problém podobnosti „řešit" s pomocí Jordánova kanonického tvaru. Algoritmicky je však tento přístup nevhodný, protože obecně nelze spočítat vlastní čísla a tím pádem ani Jordánův kanonický tvar. Na druhou stranu Smithův normální tvar je zcela algoritmický. Důkaz. Jsou-li operátory T a T' podobné, T' = PTP^1, budou podobné i T' - XE = P(T - XE)P-1. Tím spíš budou ekvivalentní a proto budou mít týž Smithův normální tvar. Nechť naopak T — XE, T' — XE mají týž Smithův normální tvar. Potom jsou ekvivalentní a podle předchozího diagramu jsou izomorfní prezentované moduly (kn,T) = (kn, T'). To ale přesně znamená, že operátory jsou podobné podle Tvrzení 11.6. □ 98 11. Smithův normální tvar polynomiálních matic Poznámka. Výhodou oproti případu komutativních grup je existence kanonické prezentace. O něco obtížněji lze také dokázat, že dva K[A]-moduly prezentované libovolnými (v kontrastu s kanonickými) polynomiálními maticemi týchž rozměrů jsou izomorfní, právě když mají tyto matice týž Smithův normální tvar; viz případ komutativních grup. Místo Jordánova kanonického tvaru je možné popsat jiný kanonický tvar, který nevyžaduje nalezení kořenů charakteristického polynomu a lze jej spočítat algoritmicky. Jelikož je (Kn,T)^K[X]/(qi) x...xK[%), stačí popsat K[A]-modul K[A]/(g) jako vektorový prostor společně s operátorem. Nalezneme vhodnou (kanonickou) bázi a v ní matici příslušného operátoru m\. Nechť q = ao + a±X + • • • + ak-iXk 1 + Xk. Potom takovou bází je a = ([1], [A], • • • , [Afc_1]) a jednoduše ( 0 1 0 o o 0 1 -a0 \ -a-k-i) Tedy (Kn,T) má ve vhodné bázi blokově diagonální tvar s bloky výše uvedeného tvaru na diagonále. Tento tvar se nazývá racionální kanonický tvar operátoru - pro jeho kanoničnost je však nutno vyžadovat, aby se polynomy příslušné jednotlivým blokům postupně dělily tak jako ve Smithově normálním tvaru. Invariantní faktor qn má poměrně jednoduchou interpretaci v řeči K[A]-modulů, z níž lze jednoduše dokázat následující větu. Tvrzení 11.10 (Cayleyho-Hamiltonova věta). Nechť x(A) tický polynom T. Potom platí x(T) = 0. det(T — XE) značí charakteris- Důkaz. Z věty o Smithově normálním tvaru platí x = Qi • • • Qn- Přitom pro libovolné x€K[X]/(gi) X---xK[X]/(qn) zjevně platí qnx = 0. Protože je však tento K[A]-modul izomorfní (Kn, T), platí to samé i pro K[A]-modul (Kn,T). Pro libovolné v G Kn tak máme qn(T)v = 0. Protože ale toto platí pro libovolné v, musí být qn{T) = 0 jakožto operátory na Kn. Tím spíš tedy x(^) = 0- d Definice 11.11. Z důkazu předchozí věty plyne, že ve skutečnosti platí již qn{T) = 0 a není těžké se přesvědčit, že qn je nejmenší polynom (vzhledem k dělitelnosti), pro který tento vztah platí. Nazývá se minimální polynom operátoru T. Poznámka. Opět poněkud abstraktněji lze minimální polynom popsat následovně. Definujme anihilátor K[A]-modulu M jako Ann(M) = {p G K[X] \ p • M = 0}. Není těžké se přesvědčit, že se vždy jedná o ideál a v našem případě je Ann(M) s trochou práce lze dát význam i zbylým invariantním faktorům, ). Opět AnntA-^M) 99 11. Smithův normální tvar polynomiálních matic kde například A^j^M je kvocient A2 M podle podprostoru generovaného rozdíly TxAy—xATy. Operátor na tomto kvocientu je zadán předpisem T[x A y] d= [Tx A y] = [x A Ty}. 11.3. Jordánův kanonický tvar Jelikož Smithův normální tvar T — XE zcela určuje operátor T až na podobnost, nemělo by být překvapením, že z něj lze spočítat Jordánův kanonický tvar T. Nechť proto nyní K je algebraicky uzavřené těleso. Potom každý cyklický modul K[A]/(g) lze psát s využitím rozkladu q = (A — Ai)ri • • • (A — Xk)Vk ve tvaru7 k[X]/(q) 2é k[X]/((X - AxD x • • • x K[A]/((A - Afc)rfe) (formální podobnost s rozkladem na prvočinitele není vůbec náhodná). Zbývá tedy popsat K[A]-modul tvaru K[A]/((A-Ao)r). Tvrzení 11.12. Cyklický ¥L[X]-modul K[A]/((A — Ao)r) je izomorfní operátoru na W s maticí Ao o 0 Ao/ Důkaz. Jakožto vektorový prostor má K[A]/((A — Ao)r) bázi ([(A-A0)r-1])...)[A-Ao],[l]) Počítejme matici operátoru m\ (násobení polynomem A) vzhledem k této bázi. Zjevně platí A[(A - Ao)4"1] = ((A - Ao) + Ao)[(A - Ao)*"1] = [(A - A0)J] + A0[(A - Aoř1]. V případě i = r pak [(A — Ao)r] = 0 a dostáváme přesně matici z tvrzení. □ Věta 11.13. Je-li těleso K algebraicky uzavřené, je každý operátor podobný operátoru v Jordánově kanonickém tvaru. Obecněji tvrzení platí pro operátor T nad libovolným tělesem, nad kterým se charakteristický polynom T zcela rozkládá. □ Je-li T — XE ekvivalentní J — XE, řekněme J-XE = P(X)(T - XE)Q(X) 7Jednoduchý důkaz tohoto faktu využívá Smithův normální tvar - K[A]-modul napravo je prezentován diagonální maticí s mocninami (A — \i)ri na diagonále; její Smithův normální tvar má na diagonále 1,... , 1, q. 100 11. Smithův normální tvar polynomiálních matic (nyní u -P(A) nebudeme psát inverzi, protože v tomto tvaru dostaneme výsledek z algoritmu počítajícího Smithův normální tvar), lze spočítat matice přechodu mezi oběma operátory. Začněme s maticí přechodu od T k J. Tu dostaneme z následujícího diagramu k[\]'> T-XE >K[A] QW V]n<- - -*(Kn,T) I P(A) 1 Sž 1 R ^ eVj ■» (Kn, J) naznačené zobrazení Kn —> K[A]n zobrazí n-tici čísel na n-tici příslušných konstantních polynomů (a nejedná se o homomorfismus K[A]-modulů). Složením dostaneme pro P = p0 + APi + • • • + XkPk následující vyjádření pro matici přechodu Fl: v ^ evj(P(X)v) = PQv + JPlV + ■■■ + JkPkv = PMt(J)v, kde poslední zápis značí dosazení matice J do polynomiální matice P(X) zleva. Matice přechodu v opačném směru lze získat buď jako inverzní matici k Pleft(J) nebo pomocí transponování všech matic (formálně přechodu k duálním prostorům). Konkrétně dostáváme diagram in i r K[A]n^—^> K[A] P*(A) k[X]r >(Kn,T*) i Q*(A) s 15* J*-\E ■+(kn,J*) nebo jednodušeji rovnici J* -XE = Q*(A)(T* - XE)P*(X) Podle předchozího dostáváme S* = (Q*)leít(J*) a zpětným transponováním S = ((Q*)left(J*))* = (Qo + J*Ql + ■■■ + {J*)kQÍT = Qo + Qi J + • • • + QkJk = QTÍght(J). Jelikož je S matice přechodu od J k T, skládají se její sloupce z vektorů báze, v níž T nabývá Jordánova kanonického tvaru J. Matici Q(X) lze získat tak, že veškeré sloupcové operace provádíme zároveň na matici T — XE a na jednotkové matici (řádkové operace však pouze na T — XE). Pokud takto převedeme T — XE na J — XE, vytvoří sloupcové operace přesně matici Q(X). Dosadíme-li pak do ní matici J zprava, získáme hledanou matici přechodu S. Vhodnou adaptací lze výpočet zjednodušit. Není potřeba pomocí dalších operací převádět Smithův normální tvar na J — XE, neboť lze využít bázi K[A]n/imfíz důkazu Tvrzení 11.12, kde B je Smithův normální tvar T — XE. Uveďme si to na zásadním příkladu B /l 0 0 o \ 1 o (A - A0)7 101 11. Smithův normální tvar polynomiálních matic Potom forma fl na prostoru Kn vpravo nahoře se zobrazí na formu na K[A]n s týmž názvem, dále pak pomocí Q*(X) na flQ(X), tj. na i-tý řádek matice Q(X). Na závěr je potřeba spočítat, jakou formu na Kn v pravém dolním rohu tato reprezentuje. Vyjádříme ji proto ve tvaru8 modulo imB = (f1,..., /r_1, fr(X — Ao)r). Matice a* je hledanou maticí přechodu (v případě B = J — XE se výpočet zjednodušil tím, že počítání modulo im£? je dosazování J). O něco složitější, ale stále zvládnutelný, je případ, kdy q = (A — Ai)ri • • • (A — Xk)Tk- Pak za bázi kvocientu K[A]/(g) lze vzít polynomy psát ar,_i^+- • -+Qo (A—Ai)ri = K,-i(A-A£)^ 1+- ■ -+a0) {x_qXe)re = Pe{X-\eye,lze lineární kombinaci přepsat do tvaru p\ (A-Ai)ri + ''' + Vk (A-Afc)rfc a JeJ^ nmovost dává (A — Xg)'1 \ pe, protože ostatní členy jsou (A — \e)re dělitelné a naopak (A-A£)ri Je s nim nesou