Informace k prednasce "Linearni algebra II" (letni semestr 2000/2001; Jiri Matousek, KAM)

Prednasky  22/II/2001 a 1/III/2001 (prof. Pultr)

Prostory se skalarnim soucinem

• Prostor se skalarnim soucinem (nad realnymi cisly nebo nad komplexnimi cisly!): vektorovy prostor V plus zobrazeni V x V -> R  (nebo -> C) , zvane skalarni soucin (znaceni skalarniho soucinu vektoru u a v bud u.v, nebo jenom uv, nebo <u,v>); axiomy: <v,v> >= 0, rovnost pouze pro v=0, <au,v>=a<u,v> (pro a realne ci komplexni cislo), <u,v+w> = <u,v>+<u,w>, <u,v> = <v,u> (v realnem pripade) ci <v,u> = cislo komplexne sdruzene s <u,v> (v komplexnim pripade). Skalarnim soucinem se k vektorovemu prostoru pridavaji pojmy jako "kolmost", "uhel", "vzdalenost", "delka" (v "cistem" vektorovem prostoru nejsou).
• Priklady: obvykly skalarni soucin v R^n :  <x,y> = x_1 y_1 + x_2 y_2 + ... + x_n y_n. Dalsi priklady pozdeji (pomoci symetrickych pozitivne definitnich matic).
• Pojem normy: norma na vektorovem prostoru V (nad R nebo nad C) je zobrazeni V -> R, znaceni ||v|| a pod.; axiomy: ||v||>=0, rovnost pouze pro v=0, ||av||=|a|.||v|| (a je realne nebo komplexni cislo), trojuhelnikova nerovnost ||u||+||v||>=||u+v||. Norma ||v|| ma vyznam "delky" vektoru v. Skalarni soucin urcuje normu ||v||=odmocnina z <v,v>, ale zdaleka ne kazda norma pochazi ze skalarniho soucinu. Ze standardniho skalarniho soucinu na R^n zmienenho vyse dostaneme Euklidovskou normu (||v|| je prave delka vektoru podle Pythagorovy vety) a Euklidovskou vzdalenost (vzdalenost bodu u a v je ||u-v||).
• Cauchyho-Schwarzova nerovnost <u,v> <= ||u|.||v||, geometricky vyznam, souvislost s kosinovou a Pythagorovou vetou. Definice kolmosti vektoru u a v: <u,v>=0.
• Ortogonalni system (navzajem kolme vektory), ortonormalni system (navic jednotkove), jejich linearni nezavislost.
• Gramova-Schmidtova ortogonalizace (algoritmus, ktery z dane baze udela ortonormalni bazi; linerani obal prvnich k vektoru zustava zachovan pro vsechna k). Veta: Rozsiritelnost libovolneho ortonormalniho systemu na ortonormalni bazi (v konecnedimenzionalnim prostoru!).
• Ortogonalni doplnek mnoziny A (oznaceni: A s kolmitkem nahore) = mnozina vsech vektoru kolmych ke vsem vektorum A. Jeste jeden pohled na homogeni soustavu linearnich rovnic Ax=0 (mnozina reseni = ortogonalni doplnek mnoziny radku matice A).
• Vlastnosti ortogonalniho doplnku (vse v konecne dimenzi): Je to podprostor, je-li U podprostor W pak doplnek U obsahuje doplnek W. Je-li U podprostor pak doplnek doplnku U je U (z rozsiritelnosti ortogonalni baze). Dimenze doplnku U ve V je rovna dim(V)-dim(U). Operace ortog. doplnku je antiisomorfismus mnoziny vsech podprostoru konecnedimensionalniho prostoru V vzhledem k usporadani inkluzi.  "De Morganovy vzorce" (doplnek pruniku je suma doplnku, doplnek sumy je prunik doplnku).
• Pojem ortogonalni a ortonormalni matice (pozor na terminologii v literature - to cemu zde rikame ortonormalni, tj. matice s ortonormalnimi sloupci, se casto nazyva ortogonalni!!!). Pozorovani: ctvrecova matice  ma ortonormalni sloupce prave kdyz A^{-1}=A^T. Tudiz: ma-li ctvercova matice ortonormalni radky, pak ma i ortonormalni sloupce.

Prednaska  8/III/2001

Grupy, zvlaste permutacni:

• Opakovani definice a prikladu grupy. Permutace (vzajemne jednoznacne zobrazeni X na X), symetricka grupa S(X), oznaceni S_n=S({1,2,...,n}). Rubikova kostka jako permutacni grupa. Permutacni grupa = podgrupa nejake S(X). Veta: kazda grupa je isomorfni permutacni grupe. Vseobecne osvetova poznamka o vykonech lidskeho ducha pri klasifikaci jednoduchych konecnych grup.
• Inverze permutace, znamenko permutace sgn(p), sude a liche permutace. Tvrzeni: sgn je homomorfismus S_n do grupy {-1,+1} s nasobenim. Jadro (sude permutace) = alternujici grupa. Transpozice (doporuceny priklad: transpozice je licha, kazda permutace je slozenim transpozic).

Determinant:

• Definice determinantu ctvercove matice (soucet soucinu  se znamenky pres vsechny permutace). Determinant matice 2x2. Doporuceny priklad: napsat determinant obecne matice 3x3 podle definice.
• Pozorovani: determinant trojuhelnikove matice je soucinem diagonalnich prvku.

Prednaska  15/III/2001

• Tvrzeni: transpozici se determinant nemeni (dukaz prerovnanim soucinu a sumy v definici determinantu).
• Tvrzeni: prerovnanim sloupcu podle permutace q se determinant nasobi sgn(q) (dukaz podobny predchozimu). Dusledek: zamena dvou radku meni znamenko determinantu. Dusledek: ma-li matice A dva shodne radky, pak det A = 0.
• Determinant je linearni funkci kazdeho sveho radku. Dusledek: co delaji elementarni radkove operace (nasobeni radku cislem a nasobi determinant cislem a, pricteni nasobku j-teho radku k i-temu radku nemeni determinant). Totez pro sloupce.
• Vypocet det(A) Gaussovou eliminaci. Dusledek: ctvercova matice A je regularni prave kdyz det(A) neni 0. Dusledek: hodnost matice se nezmeni prechodem k vetsimu telesu; napr. jsou-li nejake vektory s racionalnimi slozkami linearne nezavisle nad Q, pak jsou linearne nezavisle i nad R.
• Geometricky vyznam determinantu: linearni zobrazeni odpovidajici matici A prevadi jednotkovou krychli na rovnobeznosten objemu |det(A)| (a plochu ci objem obecne moziny meni v pomeru 1:|det(A)|).

Prednaska  22/III/2001

• Zduvodneni geometrickeho vyznamu determinantu. Poznamka: Znamenko determinantu je dano orientaci obrazu standardni baze. Dve matice A,B\in GL(n,R) maji stejne znamenko det prave kdyz jsou spojeny souvislou cestou v GL(n,R).
• Veta o nasobeni determinantu: det(AB)=det(A)det(B), dukaz pres lemma o determinantu blokove matice a pomoci eliminace aplikovane na vhodnou pomocnou matici.
• Tvrzeni o rozvoji determinantu podle radku (z linearity determinantu jako funkce radku - staci overit pro pripad, kdy rozvinovany radek je nektery z vektoru e_i)
• Vzorec pro inverzni matici k dane regularni matici A: na miste (i,j) je (-1)^{i+j} det(A_{ji})/det(A), kde A_{ij} vznikne vymazanim i-teho radku a j-teho sloupce z A (znovu tez dokazuje existenci inverzni matice).
• Dusledek: Cramerovo pravidlo = vzorecek pro reseni soustavy Ax=b pro ctvercovou A: x_i=det(A[(sloupec i) := b])/det(A). Neprakticky pro vypocet ale uzitecny pro odvozeni vlastnosti reseni.

Prednaska  29/III/2001

• Pouziti Cramerova pravidla: odhad poctu bitu pro presnou reprezentaci pruniku 3 rovin v prostoru, pri danem poctu bitu koeficientu v rovnicich rovin. Hadamardova nerovnost pro odhad determinantu: det(A) <= ||a_1||.||a_2||....||a_n||, kde a_1,...,a_n jsou sloupce A.
• Aplikace determinantu a skalarniho soucinu: nelze najit 4 body v rovine tak, aby vzdalenost kazdych 2 byla liche cele cislo. Postup: necht body jsou 0,a,b,c. Pozorovani: je-li m liche pak m^2 dava zbytek 1 mod 8. Odtud ||a||^2, ||b||^2, ||c||^2 zbytek 1 mod 8, taktez ||a-b||^2, a z kosinove vety 2a.b (skalarni soucin) zbytek 1 mod 8, podobne pro 2a.c a 2b.c. Je-li B matice ((a.a a.b a.c)(b.a b.b b.c) (c.a c.b c.c)) pak 2B je kongruentni matici ((2 1 1)(1 2 1)(1 1 2)) mod 8 a proto det(B) neni 0. Na druhe strane B=AA^T kde A=((a_1 a_2)(b_1 b_2)(c_1 c_2)), proto hodnost(B)<=2 - spor.

Vlastni cisla

• Vlastni cisla souviseji s mnoha otazkami, napr. v geometrii (jak vypadaji isometrie Euklidovskeho prostoru), ve fyzice (jak zni zvon, a dalsi otazky napr. rezonance), v teorii grafu (jak dobry je dany graf jako schema napr. telefonniho propojeni), atd. My se k nim ted dostaneme pres vysetrovani struktury endomorfismu, tj. linearnich zobrazeni vektoroveho prostoru V do sebe. (Pozn.: pro zobrazeni X->X vznika mnoho otazek ktere pro obecne zobrazeni X->Y nemaji smysl - napr. o pevnych bodech a iteracich.)
• Situace: f:V->V linearni zobrazeni, V konecnedimenzionalni, chceme najit bazi (v_1,...,v_n) tak, aby matice f vzhledem k teto bazi byla "jednoducha". (Zde je podstatne ze mame jen 1 bazi ve V! Doporuceny priklad: Je-li f:U->V zobrazeni hodnosti r, pak lze zvolit baze U a V tak, ze matice f je matice E_r doplnena dole a zprava nulami.)
• Opakovani (a ujasneni): matice zobrazeni f:U->V vzhledem k bazim (u_1,...,u_n) a (v_1,...,v_m) [j-ty sloupec jsou souradnice f(u_j) v bazi (v_1,...,v_m)]. Matice prechodu T od baze (v_1,...,v_n) k bazi (w_1,...,w_n) v prostoru V [j-ty sloupec jsou souradnice v_j v bazi (w_1,...,w_n)]. Tvrzeni: matice prechodu od (w_1,...,w_n) k (v_1,...,v_n) je T^{-1} (dukaz: vypoctem, nebo pomoci isomorfismu s K^n).
• Tvrzeni: je-li A matice f:V->V vzhledem k bazi (v_1,...,v_n), pak matice f vzhledem k bazi (w_1,...,w_n) je TAT^{-1}, kde T je matice prechodu od (v_1,...,v_n) k (w_1,...,w_n). Definice: matice A a B jsou podobne kdyz existuje regularni matice T takova, ze B=TAT^{-1} (vschny matie n x n). Nas cil v reci matic: k dane matici A najit podobnou matici B v "jednoduchem" tvaru (napr. casto se postesti B diagonalni).

Prednaska  4/IV/2001

• Pozn.: elementarni radkove (ci sloupcove) upravy obecne NEZACHOVAVAJI podobnost matic, ted musime matice upravovat mnohem opatrneji!!!
• Co dela linearni zobrazeni R^n->R^n, jehoz matice je diagonalni? Natahuje ci zkracuje (a pripadne zrcadli) ve smeru kazde souradnicove osy. Pro obecne linearni zobrazeni, "dobry smer" je takovy, v nemz ono zobrazeni natahuje ci zkracuje ale smer se zachovava. To vede k definici vlastnich cisel a vektoru.
• Je-li f:V->V linearni zobrazeni, kde V je vektorovy prostor nad telesem K (takovemu f se nekdy rika linearni operator), pak cislo lambda\in K se nazyva vlastni cislo zobrazeni f prave kdyz existuje NENULOVY vektor v\in V takovy, ze f(v)=lambda v. Kazdemu takovemu v se rika vlastni vektor prislusny k lambda. Tj. v je ten "dobry smer" v nemz f ucinkuje jako nasobeni cislem lambda.
• Poznamka: je-li v vlastni vektor a t\in K je nenulove pak tez tv je vlastni vektor. Pozor: v nesmi byt 0 ale lambda muze byt 0! Poznamka: vlastni vektor v generuje 1-dimenzionalni invariantni podprostor. Obecne, podprostor W prostoru V se nazyva invariantni podprostor zobrazeni f pokud f(W) je obsazeno ve W.
• Pro ctvercovou matici A jsou vlastni cisla a vlastni vektory jako pro linearni zobrazeni urcene A; explicitne: lambda a nenulovy v musi splnovat rovnici Av=lambda v.
• Priklady, co se muze dit v rovine (kreslete si!):
• Matice ((0 -1)(0 -1)): zrcadleni podle primky y=-x, vl. cisla 1 (vl. vektor v=(-1,1)) a -1 (v=(1,1)). Vl. vektory tvori bazi a zobrazeni ma vzhledem k teto bazi diagonalni matici ((1 0)(0 -1)).
• Matice ((1 1)(0 2)): zkoseni a roztazeni, vl. cisla 1 (v=(1,0)) a 2 (v=(1,1)). Vl. vektory zase tvori bazi a zobrazeni ma vzhledem k teto bazi diagonalni matici ((1 0)(0 2)).
• Rotace v rovine o uhel alfa: pokud alfa neni nasobkem pi, nejsou zadna (realna) vlastni cisla a matice neni podobna zadne diagonalni matici. ALE pokud povolime komplexni cisla, existuje baze z vl. vektoru a diagonalizovat lze.
• Matice ((1 1)(0 1)): jedine vl. cislo 1 a jediny vlastni vektor (1,0) (az na skalarni nasobek), nelze diagonalizovat, ani komplexni cisla nepomuzou.
• Dva exotictejsi priklady:
• V = prostor vsech realnych funkci na [0,1] majicich spojite derivace vsech radu; operator derivace D:V->V, f |-> f', je linearni zobrazeni. Kazde realne lambda je vlastnim cislem, prislusny vlastni vektor je funkce x |-> e^{lambda x}. Dulezite pri reseni linearnich diferencialnich rovnic s konstantnimi koeficienty.
• V = prostor vsech nekonecnych posloupnosti (y_0,y_1,y_2,...) splnujicich y_{n+2}=y_{n+1}+y_n pro vsechna n=0,1,... (jako v minulem semestru pri odvozeni vzorce pro Fibonacciho cisla). P:V->V je operator posunuti doleva, (y_0,y_1,y_2,...) |-> (y_1,y_2,y_3...). Vlastni vektory jsou zjevne nasobky posloupnosti tvaru (t^0,t^1,t^2,...), ptame se pro jaka t je takova posloupnost ve V, z toho vyjdou 2 vlastni cisla a 2 vlastni vektory (jako v prikladu s Fib. cisly).
• Pozorovani: pro f:V->V linearni, baze vzhledem k niz ma f diagonalni matici existuje prave kdyz existuje baze slozena z vlastnich vektoru. Prislusna diagonalni matice ma na diagonale prave vlastni cisla f. Dukaz rozmyslet za domaci ukol!!

Prednaska  12/IV/2001

• Tvrzeni: Jsou-li lambda_1,...,lambda_k NAVZAJEM RUZNA vlastni cisla zobrazeni f (ci matice A), a v_i je nejaky vlastni vektor prislusny lambda_i, potom v_1,...,v_k jsou linearne nezavisle. Dukaz indukci podle k.
• Dusledek: Ma-li n x n matice A n navzajem ruznych vlastnich cisel, pak je diagonalizovatelna. (Obracena implikace obecne neplati!)

Charakteristicky mnohoclen

• Pozorovani: pro pevne lambda je

      Av=lambda.v
homogenni soustavou n rovnic o n neznamych (nezname jsou slozky vektoru v). Jeji matice je A-lambda.E_n. Proto plati: lambda je vlastni cislo prave kdyz ma tato soustava nenulove reseni, coz je prave kdyz det(A-lambda.E_n)=0.
• Nyni se divejme na lambda jako na promennou (abychom to rozlisili, nahradime lambda pismenkem t). Definice: charakteristicky mnohoclen ctvercove matice A je p_A(t)=det(A-t.E_n), kde t je promenna. Podle definice determinantu je to skutecne mnohoclen, a ma stupen presne n. Vlastni cisla A jsou prave jeho koreny.
• Jsou-li A a B podobne matice, plati p_A(t)=p_B(t). Muzeme tedy mluvit o charakteristickem mnohoclenu p_f(t) linearniho zobrazeni f:V->V.
• Jak hledat vlastni cisla dane matice, a jak charakteristicky mnohoclen:
• "rucne" - muzeme pocitat det(A-t.E_n) eliminaci, s t ovsem musime zachazet jako s neznamou, takze pracujeme s maticemi, jejichz prvky jsou obecne mnohocleny v promenne t (a ne jen cisla jako obvykle). V jednoduchych pripadech muzeme tak najit p_A(t).
• p_A(t) lze tez hledat vhodnymi upravami matice A zachovavajicimi podobnost; A se prevede na tvar, v nemz je p_A(t) "videt". Viz napr. vselijake ucebnice numericke matematiky. Koreny p_A(t) se hledaji obecne numerickymi metodami.
• ve "skutecnych" aplikacich, kdy je treba najit vlastni cisla napr. matic 1000x1000, se vlastni cisla zjistuji jinymi (hlavne iterativnimi) metodami, ktere vubec nepocitaji charakteristicky mnohoclen.
• Dulezita poznamka: vypocet vlastnich cisel je vypocetne "dobre zvladnutelna" uloha (existuji polynomialni a prakticky rozume efektivni algoritmy), narozdil od tezkych problemu (jako treba obarveni grafu a jinych NP-uplnych uloh). Vlastnich cisel se nekdy pouziva v algoritmech pro priblizne reseni nekterych takovych tezkych uloh.
• Dulezite koeficienty charakteristickeho mnohoclenu. Pisme p_A(t)=(-1)^n t^n + c_{n-1} t^{n-1} +...+c_0. Potom plati: c_0=det(A) a c_{n-1}=(-1)^{n-1}.stopa(A), kde stopa(A)=a_{11}+a_{22}+...+a_{nn}. (To se da videt z definice determinantu.) Tedy determinant i stopa s zachovavaji podobnostnimi transformacemi, a muzeme mluvit o determinantu ci stope lin. zobrazeni f:V->V.

Prednaska  26/IV/2001

• Pripomenuti o mnohoclenech. Zakladni veta algebry: kazdy nenulovy mnohoclen s realnymi ci komplexnimi koeficienty ma aspon 1 komplexni koren (pomerne tezke, zde bez dukazu). Ma-li p(x) koren alfa, pak p(x)=(x-alfa)q(x) pro nejaky mnohoclen q(x) (tohle je pravda nad kazdym telesem a je to snadne). Dusledek (indukci): mnohoclen p(x) stupne n s realnymi ci komplexnimi koeficienty lze napsat ve tvaru p(x)=a_n(x-alfa_1)(x-alfa_2)...(x-alfa_n), kde alfa_1,...,alfa_n jsou komplexni cisla. Jiny zpusob zapisu:

p(x)=a_n(x-beta_1)^{r_1}(x-beta_2)^{r_2}...(x-beta_k)^{r_k},
kde beta_1,...,beta_k jsou navzajem ruzna komplexni cisla a r_1+r_2+..+r_k=n. Zde r_i se nazyva nasobnost korene beta_i.
• Poznamka: Bud p_A(t) charakteristicky mnohoclen matice A a lambda cislo. Nejvetsi cele cislo r takove, ze p_A(t)=(t-lambda)^r q(x) pro nejaky mnohoclen q(x) se nazyva algebraicka nasobnost vlastniho cisla lambda (specialne, neni-li lambda vubec vlastni cislo, ma algebraickou nasobnost 0). Jestlize A lze diagonalizovat, pak algebraicka nasobnost lambda udava, kolikrat se lambda opakuje na diagonale v diagonalnim tvaru.
• Nad komplexnimi cisly muzeme charakteristicky mnohoclen rozlozit na soucin linearnich cinitelu: p_A(t)=(-1)^n(t-lambda_1)(t-lambda_2)...(t-lambda_n). Potom mame det(A)=lambda_1.lambda_2...lambda_n a stopa(A)=lambda_1+lambda_2+...+lambda_n (kazde vlastni cislo bereme s jeho algebraickou nasobnosti). Pro diagonalni (ci diagonalizovatelne) matice je to videt primo.
• Matice, ktere nelze diagonalizovat: nemaji bazi z vlastnich vektoru, museji mit nutne nejake nasobne vlastni cislo lambda a dimenze reseni soustavy (A-lambda E_n)x=0 je mensi nez algebraicka nasobnost lambda.
• Veta (Jordanuv normalni tvar): Bud A matice n x n, realna ci komplexni. Pak existuje matice J podobna A, tzv. Jordanuv normalni tvar A,  nasledujiciho tvaru: podel hlavni diagonaly J jsou rozestaveny ctvercove bloky J_1,J_2,....,J_k, tzv. Jordanovy bunky, a zbytek J jsou same nuly.  Jordanova bunka J_i je ctvercova  n_i x n_i matice (n_1+n_2+...+n_k=n), na jejiz hlavni diagonale se n_i-krat opakuje nejake cislo lambda_i, a tesne nad diagonalou  (v pozicich (q,q+1) , q=1,2,...,n_i-1) jsou jednicky. Ta lambda_i nemusi byt navzajem ruzna; celkove se na diagonale J objevi kazde vlastni cislo matice A tolikrat, kolik je jeho algebraicka nasobnost. Specialne, pro diagonalizovatelnou matici A jsou vsechna n_i =1. Dale, J je urcena jednoznacne az na prerovnani tech J_i , takze soubor (lambda_1,n_1),...,(lambda_k,n_k) jednoznacne reprezentuje tridu ekvivalence podobnych matic. Vetu nebudeme dokazovat (dukaz pracny).
• Jordanovy bunky velikosti vetsi nez 1x1 jsou to, co "zabranuje diagonalizaci". Z jisteho hlediska jsou "vzacne", napr. pro nahodne generovanou matici A se vyskytnou s malou pravdepodobnosti, ale je rada prirozenych prikladu. Treba: V vektorovy prostor mnohoclenu stupne nejvys 3, D:V->V zobrazeni derivace: jeho matice je podobna Jordanove bunce 4x4 s vlastnim cislem 0 na diagonale.

Specialni matice a zobrazeni

• Opakovani: skalarni soucin realny a komplexni; jsou-li u a v vektory, x a y vektory jejich souradnic vzhledem k nejake ortonormalni bazi, mame <u,v>=x_1y_1+x_2y_2+...+x_n y_n  v realnem pripade, v komplexnim pripade musime jeste vzit ta y_i komplexne sdruzena.
• Definice nekterych dulezitych typu matic (symetricka, hermitovska, ortonormalni, unitarni) a zobrazeni v prostoru se skalarnim soucinem (smoadjungovana, ortogonalni, unitarni):

	Ctvercova matice A se nazyva	zobrazeni f:V->V se nazyva
realny  pripad	SYMETRICKA:    A=A^T	SAMOADJUNGOVANE:  <f(u),v>=<u,f(v)>  pro vsechna u,v
komplexni  pripad	HERMITOVSKA  A=A^T komplex. sdruzene
realny  pripad	ORTONORMALNI (ci ORTOGONALNI):  A^{-1}=A^T	ORTOGONALNI:  <f(u),f(v)>=<u,v>  pro vsechna u,v
komplexni  pripad	UNITARNI:  A^{-1}= A^T komplexne sdruzene	UNITARNI:  <f(u),f(v)>=<u,v>  pro vsechna u,v

• Tyto pojmy jsou velmi dulezite napr. ve fyzice. My se budeme hlavne zabyvat symetrickymi maticemi a ortonormalnimi maticemi (coz jsou matice rotaci kolem pocatku, pripadne se zrcadlenim). Tvrzeni (souvislost zobrazeni a matic - levy a pravy sloupec v horejsi tabulce):
• Zobrazeni f:V->V, kde V je realny vektorovy prostor se skalarnim soucinem, je samoadjungovane prave kdyz jeho matice vzhledem k nejake ortonormalni bazi je symetricka (a pak je symetricka vzhledem ke kazde ortonormalni bazi).
• Zobrazeni f:V->V, kde V je komplexni vektorovy prostor se skalarnim soucinem, je samoadjungovane prave kdyz jeho matice vzhledem k nejake ortonormalni bazi je hermitovska (a pak je hermitovska vzhledem ke kazde ortonormalni bazi).
• Zobrazeni f:V->V, kde V je realny vektorovy prostor se skalarnim soucinem, je ortogonalni prave kdyz jeho matice vzhledem k nejake ortonormalni bazi je ortonormalni (a pak je ortonormalni vzhledem ke kazde ortonormalni bazi).
• Zobrazeni f:V->V, kde V je komplexni vektorovy prostor se skalarnim soucinem, je unitarni prave kdyz jeho matice vzhledem k nejake ortonormalni bazi je unitarni (a pak je unitarni vzhledem ke kazde ortonormalni bazi).
V dukazech se pouzije mimo jine: pro libovolne matice A,B takove, ze soucin AB je definovan, mame (AB)^T= B^T A^T (pozor na prevraceni poradi!!!). Podobne: pro regularni ctvercove matice A, B plati (AB)^{-1}=B^{-1} A^{-1}. To je obecne uzitecne vedet a overit to je doporuceny priklad.
• Tez se pouzije lematko: jsou-li A a B ctvercove matice nad nejakym telesem K a plati-li x^T A y=x^T B y pro kazde dva vektory x,y\in K^n, pak A=B.

Prednaska 3/V/2001

• Tvrzeni: Vsechna vlastni cisla symetricke realne matice jsou realna (dukaz: pocitat

(v komplexne sdruzene)^T A v
dvema zpusoby, kde v je nejaky vlastni vektor).
• Veta: Je-li A ctvercova realna matice, jejiz vsechna vlastni cisla jsou realna, pak existuje ortonormalni matice T takova, ze TAT^{-1} je horni trojuhelnikova matice. Dukaz: indukci dle rozmeru A, v indukcnim kroku vzit jednotkovy vlastni vektor v jako prvni sloupec a doplnit na ortonormalni matici S, uvazit jak vypada S^{-1}AS. Podobne: pro libovolnou (komplexni) ctvercovou matici existuje unitarni T tak, ze TAT^{-1} je horni trojuhelnikova.
• Dulezity dusledek: Symetricka realna matice ma ortonormalni bazi z vlastnich vektoru, tj. existuje T ortonormalni tak, ze TAT^{-1} je diagonalni (staci overit, ze TAT^{-1}=TAT^T je symetricka).

Doporucene priklady

Prednaska 10/V/2001

Aplikace linearni algebry: konstrukce samoopravnych kodu

• Motivace: chceme prenaset (nebo zapisovat a cist) nejaka data, treba retezec 0 a 1. Pri prenosu mohou vznikat chyby, predpokladame ze pravdepodobnost chyby je mala, a pravdepodobnost k chyb pri prenosu daneho poctu bitu je podstatne mensi nez pravdepodobnost k-1 ci mene chyb. Hlavni myslenka: misto retezce w, ktery potrebujeme prenest, prenaset ponekud delsi retezec w', sestrojeny tak, abychom maly pocet chyb vzniklych pri prenosu w' umeli detekovat ci dokonce opravit.
• Priklad: w' dostaneme z w zdvojenim kazdeho bitu, treba w=01 w'=0011; tak muzeme detekovat 1 chybu. Ztrojenim kazdeho bitu, napr, w=01 w'=000111 muzeme uz opravovat 1 chybu. To je dost marnotratny zpusob: ukazeme napr., ze 1 chybu muzeme opravit pomoci kodu, ktery ze 4-bitoveho retezce dela 7-bitovy.
• Definice: S konecna mnozina - abeceda, S^n={w=a_1a_2...a_n: a_1,...,a_n\in S} vsechna slova (libovolne posloupnosti prvku S) delky n. Kod je libovolna podmnozina C mnoziny S^n. Hammingova vzdalenost slov u,v\in S^n je d(u,v)=|{i: u_i ruzne od v_i, i=1,2,...,n}| (z u se da dostat v nejvys d(u,v) "chybami"). Kod C opravuje t chyb pokud pro kazde u\in S^n existuje nejvys jedno v\in C takove, ze d(u,v)<=t.
• Oznacme d(C)=min{d(u,v): u,v\in C, u ruzne od v}. Pozorovani: Pokud d(C)>=2t+1 pak C opravuje t chyb. Cil: najit pro dane n a d co nejvetsi C podmnozina S^n takove, ze d(C)>=d. (Jak merit kvalitu: Shannonova teorie (mira infomace).)
• Linearni kody: S=konecne teleso (hlavni priklad: S={0,1}), S^n je pak vektorovy prostor. Kazdy vektorovy podprostor S^n se nazyva linearni kod. Pozorovani: pro linearni kod je d(C)=min{d(0,w): w\in C, w nenulove}.
• Zadani podprostoru (=lin. kodu):
• bazi: generujici matice G kodu, rozmer n x k, radky = vektory baze, zpravidla se voli tvaru G=(E_k|A). Kodovani: mame-li prenest vektor v\in S^k, posleme v^TG\in C.
• jako jadro linearniho zobrazeni, tj. C je reseni soustavy Px=0, kde P je tzv. matice kontroly parity; to je uzitecne pro dekodovani, viz dale. Je-li G=(E_k|A) pak P=(-A^T|E_{n-k}) (doporuceny priklad: overit ze to funguje!).
• Priklad: Hamminguv kod v Z_2^7 (50.leta): G=(E_4|A), A=((111)(110)(101)(011)). Tj. dostaneme 4 bity a b c d, pripiseme k nim 3 dalsi "kontrolni" bity a+b+c, a+b+d, a+c+d a tech 7 bitu posleme. Tvrzeni: d(C)=3, tedy opravuje 1 chybu (dukaz: vypsat vsech 16 slov). Dalsi priklady: napr. Golayuv kod v Z_3^{11}, d(C)=5.
• Dekodovani: u\in S^n, ktere slovo z C je nejbliz k u? Mohli bychom mit tabulku vsech |S|^n slov; uvidime - staci tabulka velikosti |S|^{n-k}, kde k=dim(C).
• Definujeme ekvivalenci na S^n: u ~ v prave kdyz u-v\in C. To je prave kdyz Pu=Pv (P matice kontroly parity kodu C), a Pw jednoznacne urcuje tridu, do niz patri w. Tabulka: pro kazde s\in S^{n-k} zvol r=r(s)\in S^n tak, ze Pr=s a d(r,0) je minimalni mozne; uloz r(s) do tabulky. Dekodovani slova w\in S^n: spocti s=Pw, najdi r(s) v tabulce, poloz c=w-r. Pozorovani: c\in C a je to nejblizsi slovo k w lezici v C. Pokud generujici matice je tvaru (E_k|A), potom prvnich k bitu c je dekodovanim slova w (po oprave chyb). Doporuceny priklad: sestavit tu tabulku a zkusit si proceduru kodovani a dekodovani pro Hamminguv 7-bitovy kod zmineny vyse.

Prednaska 17/V/2001

Pozitivne definitni a pozitivne semidefinitni matice

• Symetricka ctvercova realna matice A se nazyva pozitivne definitni pokud pro vsechna nenulova x\in R^n plati x^T A x >0, a pozitivne semidefinitni pokud pro vsechna x\in R^n plati x^T A x>=0. Pozitivne definitni matice jsou jista analogie kladnych cisel (asi nejlepsi analogie, jaka se da pro matice definovat).
• Tvrzeni: pro ctvercovou realnou symetrickou matici A je ekvivalentni

(i) A je pozitivne semidefinitni.
(ii) Vsechna vlastni cisla A jsou nezaporna.
(iii) Existuje matice U takova, ze U^T U = A.
Analogie pro pozitivne definitni: vlastni cisla kladna, matice U ma hodnost n.
Poznamka: bez dukazu dalsi ekvivalentni podminka (Jacbiho): Pro k=1,2,...,n plati det(A_k)>=0, kde A_k znaci matici vzniklou z A vymazanim poslednich n-k radku a n-k sloupcu.
• V analyze: Bud D matice druhych parcialnich derivaci funce f:R^n->R, d_{ij} je parcialni derivace f podle x_i a podle x_j v bode a (predp. parcialni derivace spojite v okoli a). Predpokladejme, ze vsechny prvni parcialni derivace v a jsou 0, tj. tecna nadrovina je horizontalni. Je-li D pozitivne definitni ma f v bode a lokalni minimum. Ma-li f v bode a lokalni minimum pak D je pozitivne semidefinitni.
• Dulezita metoda v optimalizaci a jinych algoritmech: semidefinitni programovani = hledani maxima linearni funkce pres mnozinu vsech pozitivne semidefinitnich matic, jejichz prvky splnuji dane linearni rovnice a nerovnosti. Je znam efektivni algoritmus.
• Geometricky priklad: M je dana symetricka (n+1)x(n+1) realna matice. Kdy existuji body x_0,x_1,...,x_n v R^d tak, ze euklidovska vzdalenost x_i a x_j se rovna m_{ij}, pro vsechna i,j? Odpoved: definujme pomocnou n x n matici G,

g_{ij} = (1/2)(m_{0i}^2 + m_{j0}^2 - m_{ij}^2).
Pokud ta x_i existuji a x_0=0, pak g_{ij}=<x_i,x_j>. Existuji prave kdyz G=U^T U pro nejakou d x n matici U. Specialne, pro d=n, ta x_i existuji prave kdyz G je pozitivne semidefinitni.

Strucne o bilinearnich a kvadratickych formach

• K libovolne teleso, V konecnedimenzionalni vektorovy prostor nad nim. Bilinearni forma ve V je zobrazeni b: V x V -> K splnujici: pro kazde u\in V, zobrazeni v|->b(u,v) je linearni, a pro kazde v\in V, zorazeni u|->b(u,v) je linearni.
• Priklad: realny skalarni soucin b(u,v)=<u,v>.
• Priklad: A je n x n matice, V=K^n,

b(x,y)=x^T A y = suma_{i,j} x_i a_{ij} y_j,
x,y\in K^n.
• Vsechny bilinearni formy "vypadaji" takto. Definice: matice bilinearni formy b vzhledem k nejake bazi v_1,...,v_n prostoru V je n x n matice A, kde a_{ij}=b(v_i,v_j). Jsou-li u,v\in V a x,y\in K^n jsou vektory jejich souradnic vzhledem k bazi v_1,...,v_n, pak plati b(u,v)=x^T A y.

Prednaska 18/V/2001

• Co kdyz se zmeni baze? v_1,...,v_n stara baze, v'_1,...,v'_n nova baze, T matice prechodu (v_j = t_{1j}v'_1+t_{2j}v'_2+...+t_{nj}v'_n), S=T^{-1} matice prechodu obracene, A matice formy b vzhledem ke stare bazi, A' vzhledem k nove bazi: vyjde A'=S^T A S.
• Shrnuti o transformacich souradnic v_1,...,v_n stara baze, v'_1,...,v'_n nova baze, T matice prechodu: v_j=suma_i t_{ij}v'_i, S=T^{-1} matice prechodu obracene.

typ objektu	co jsou jeho souradnice	jak se transformuji
VEKTOR  v\in V	x\in K^n, v=suma x_i v_i	x' = T x
ENDOMORFISMUS  f: V->V	matice A typu n x n  a_{ij}=i-ta souradnice f(v_j)  ma-li v souradnice x pak  f(v) ma souradnice Ax	A'=TAT^{-1}
BILINEARNI FORMA  b: V x V -> K	matice A typu n x n  a_{ij} = b(v_i,v_j)  b(u,v) = x^T A y kde  x jsou souradnice u  y jsou souradnice v	A' = S^T A S

• Poznamka: tabulka by mohla pokracovat - existuji jeste dalsi, i slozitejsi typy objektu, jejich souradnice mohou byt i "vicerozmerne matice", s vic nez 2 indexy; poradek do toho vnasi tenzorovy pocet (dulezity hlavne ve fyzice, my zde nebudeme delat).
• Kvadraticka forma je zobrazeni q:V->K tvaru q(v)=b(v,v), kde b je symetricka bilinearni forma (tj. b(u,v)=b(v,u) pro vsechna u,v\in V). V souradnicich:

q(v) = x^T A x= suma_i a_{ii} x_i^2 + 2\suma_{i<j}a_{ij}x_ix_j. Geometricky: pro dimenzi n=2, rovnice q(x)=1 popisuje kuzelosecku (elipsu, hyperbolu, parabolu, dvojici primek,...), ve vyssi dimenzi tzv. kvadriku.
• Poznamka: z kvadraticke formy q muzeme rekonstruovat tu symetrickou bilinearni formu b: b(u,v)=(1/2)(q(u+v)-q(u)-q(v)) (pokud v telese K 1+1 neni 0). Muzeme tedy mluvit o matici kvadraticke formy vzhledem k bazi.
• V dalsim uvazujeme bilinearni a kvadraticke formy nad telesem realnych cisel. Pojem pozitivne definitni a pozitivne semidefinitni kvadraticke (ci symetricke bilinearni) formy jako pro jejich matice (p.d. znamena q(x)>0 pro vsechna nenulova x, a p.s.d q(x)>=0 pro vsechna x), vse nad realnymi cisly. Realny skalarni soucin je presne positivne definitni symetricka bilinearni forma.
• Podobne jako pro endomorfismy, zmenou baze bychom chteli privest matici kvadraticke formy na "pekny" tvar, vyjde to mnohem jednodusseji nez pro endomorfismy. Veta (Sylvesteruv zakon setrvacnosti kvadratickych forem): Pro kazdou kvadratickou formu q (na konecnedimenzionalnim realnem vektorovem prostoru) existuje baze, vzhledem k niz ma q diagonalni matici, ktera ma na diagonale p jednicek, m minus jednicek, a n-p-m nul. To p a m vyjdou stejne pro kazdou bazi (odtud "setrvacnost" v nazvu), rika se jim signatura formy q. Pro matice: pro kazdou symetrickou ctvercovou matici A existuje regularni S s navzajem ortogonalnimi sloupci pro niz S^T A S je diagonalni s 1,-1, a 0 na diagonale.
• Dukaz pouze naznak, nezkousi se. Nejdriv existence te matice S: z casti o vlastnich cislech vime ze existuje ortonormalni T takova, ze D=T^T AT ma na diagonale vlastni cisla A, zbyva rozlozit D=U^T D_0 U, kde U je diagonalni, s odmocninami absolutnich hodnot vlastnich cisel na diagonale, a D_0 je diagonalni jako ve vete. Dale setrvacnost: je-li q kvadraticka forma a v_1,...,v_n baze takova, ze matice q je jako ve vete (+1,-1,0 na diagonale), bud V_+=span(v_1,...,v_p), V_-=span(v_{p+1},...,v_{p+m}) a V_0=span(v_{p+m+1},...,v_n). Pak V je direktnim souctem V_+, V_- a V_0 a plati q(v)=0 pro kazde v\in V_0, q(v)>0 pro kazde nenulove v\in V_+, a q(v)<0 pro kazde nenulove v\in V_-. Mame-li jiny takovy rozklad (V'_+,V'_-,V'_0), ukaze se, ze V_0=V'_0 a dale ze V'_+ protina V_- + V_0 pouze v 0. Odtud dim(V'_+)=dim(V_+) a podobne dim(V'_-)=dim(V_-).
• Pro dimenzi n=2: pro p=2,m=0 je q(x)=1 rovnice elipsy, pro p=m=1 je to rovnice hyperboly. Pozitivne definitni formy maji p=n, pozitivne semidefinitni m=0.

Dualni vektorovy prostor

• V,W vektorove prostory nad telesem K, Hom(V,W) znaci vektorovy prostor vsech linearnich zobrazeni f:V->W. (Je-li dim(V)=n a dim(W)=m pak dim(Hom(U,V))=mn - to se udela pres matice zobrazeni.) Ted se budeme zabyvat pripadem W=K. Definujeme V^*=Hom(V,K), to je dualni vektorovy prostor k prostoru V, jeho prvky, tj.linearni zobrazeni V->K, se jmenuji linearni formy na V.

Prednaska 23/V/2001

• Bud V konecnedimenzionalni, v_1,...,v_n nejaka jeho baze. Definujeme v^*_i\in V^* predpisem v^*_i(v_j)=delta_{ij} (Kroneckerovo delta). Plati: v^*_1,...,v^*_n je baze V^* (tzv. dualni baze k bazi v_1,...,v_n), a tedy V^* je isomorfni V. Isomorfismus neni "kanonicky" (zavisi na volbe baze). Pozor, v^*_i zavisi nejen na v_i, ale taky na vsech ostatnich v_j!
• Poznamka: Pro nekonecnedimenzionalni prostor V neni V^* isomorfni V, je "mnohem vetsi". V prostorech funkci (disciplina: funkcionalni analyza) se zpravidla nepouziva cely V^*, ale jen jeho podprostor tvoreny spojitymi linearnimi formami (pojem spojitosti ovsem v "cistem" vektorovem prostoru nemame, musi se pridat, to vede na Banachovy prostory).
• Poznamka: je-li V konecnedimenzionalni prostor se skalarnim soucinem, mame "kanonicky" isomorfismus V s V^* (posila vektor v na linearni formu x|-><v,x>). V teto situaci se nekdy mezi V a V^* moc nerozlisuje.
• Je-li U podprostor V, definuje se U^o podprostor V^* jako mnozina vsech linearnich forem z V^* jejichz jadro obsahuje U. U^o se jmenuje anihilator podprostoru U. Je to analogie (zobecneni) ortogonalniho doplnku na situaci, kdy nemame zaveden skalarni soucin (ortogonalni doplnek zije ve V, kdezto anihilator ve V^*).
• V reci soustav linearnich rovic: U^o obsahuje vsechny "linearni rovnice", ktere jsou splneny pro vsechny vektory z U.
• Veta: dim(U^o)= dim(V)-dim(U). (Jako pro ortogonalni doplnek.) Je-li u_1,...,u_r baze U a u_{r+1},...,u_n ji doplnuji na bazi V, pak u^*_{r+1},...,u^*_n je baze U^o.
• Dualita "obraci sipky" zobrazeni: pro linearni zobrazeni F:U->V mame linearni zobrazeni F^*:V^*->U^*, dane predpisem F^*(f)(u)=f(F(u)), kde u\in U a f\in V^*. Matice zobrazeni F^* je transponovana vzhledem k matici zobrazeni F (vezmeme-li v U a ve V nejake baze a v U^* a ve V^* baze k nim dualni).
• Plati Im(F^*)=(Ker F)^o a Ker(F^*)=(Im F)^o, a tedy hodnost(F^*)=hodnost(F). Odtud "abstraktni" dukaz toho, ze radkova hodnost matice se rovna sloupcove.
• Druhy dual V^{**} prostoru V: prvky jsou linearni formy na linearnich formach (formalne je to jednoduche ale tezko predstavitelne). Pro konecne dimenzionalni V je V^{**} isomorfni V (uz vime), dokonce kanonicky: v\in V priradime linearni formu v^{**}:V^*->K predpisem v^{**}(f)=f(v), kde f\in V^*. V a V^{**} tedy muzeme povazovat za tyz prostor, a dualita je pak pekne symetricka.
• Pri tomto ztotozneni plati (U^o)^o=U. To je abstraktni verze "dvojiho popisu vektoroveho podprostoru" (bazi nebo jako reseni soustavy linearnich rovnic).