Soustavy lineárních rovnic Buď (T, +, ) těleso. Pak soustava rovnic a11x1 + a12x2 + + a1nxn = b1, a21x1 + a22x2 + + a2nxn = b2, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . am1x1 + am2x2 + + amnxn = bm, kde m, n jsou přirozená čísla, aij T pro všechna i = 1, 2, . . . , m, j = 1, 2, . . . , n a bi T pro všechna i = 1, 2, . . . , m, se nazývá soustava m lineárních rovnic o n neznámých x1, x2, . . . , xn nad tělesem (T, +, ). Prvky aij se nazývají koeficienty a prvky bi absolutní členy této soustavy. Řešením této soustavy ro- zumíme každou n-tici prvků t1, t2, . . . , tn T takovou, že po dosazení tj za xj pro všechna j = 1, 2, . . . , n přejdou všechny uvedené rovnice v identity, tj. na levé straně každé rovnice vyjde prvek rovný absolutnímu členu na pravé straně rovnice. Matice a11 a12 . . . a1n a21 a22 . . . a2n ... ... ... am1 am2 . . . amn , resp. a11 a12 . . . a1n a21 a22 . . . a2n ... ... ... am1 am2 . . . amn b1 b2 ... bm se nazývají matice soustavy, resp. rozšířená matice sousta- vy. Označíme-li A = (aij) matici soustavy, tj. matici složenou z koeficientů této soustavy, a zavedeme-li vektor absolutních čle- nů b = (b1, b2, . . . , bm) a vektor neznámých x = (x1, x2, . . . , xn), můžeme soustavu napsat v maticovém tvaru A x = b , kde transponované vektory bereme jako matice o jednom sloupci. Řešením soustavy je pak každý vektor t = (t1, t2, . . . , tn) z Tn , 1 pro který platí rovnost At = b . Je tedy množina všech řešení dané soustavy nějakou podmnožinou v Tn . Ukážeme, jak najít a přístupným způsobem popsat všechna řešení zadané soustavy lineárních rovnic. Uvidíme, že taková soustava nemusí mít řešení žádné, může mít řešení jediné anebo může mít řešení mnoho. Soustava lineárních rovnic se nazývá řešitelná, má-li alespoň jedno řešení. Následující Frobeniova věta poskytuje kritérium pro zjištění řešitelnosti dané soustavy. Věta. Buď (T, +, ) těleso, buď A = (aij) matice typu m/n nad (T, +, ) a buď b = (b1, b2, . . . , bm) vektor z Tm . Potom sou- stava lineárních rovnic A x = b je řešitelná právě tehdy, když hodnost matice soustavy, tj. hodnost matice A, je rovna hodnosti rozšířené matice soustavy, tj. hodnosti matice A|b . Důkaz. Je-li soustava A x = b řešitelná, existuje vektor t = (t1, t2, . . . , tn) z Tn takový, že A t = b . Podle definice násobení matic to znamená, že sloupec b je lineární kombi- nací sloupců matice A s koeficienty t1, t2, . . . , tn. Generují tedy sloupce obou matic A i (A|b ) tentýž podprostor ve vektorovém prostoru (Tm , +, ). Mají tudíž obě tyto matice stejnou hodnost. Naopak mají-li obě matice A a (A|b ) stejnou hodnost, ge- nerují sloupce těchto matic podprostory v (Tm , +, ) stejné di- menze, a poněvadž první z nich je obsažen ve druhém, musí tyto podprostory splynout. Poněvadž tyto podprostory vznikají tvorbou lineárních kombinací sloupců matic A a (A|b ), zna- mená to, že sloupec b je nějakou lineární kombinací sloupců matice A, řekněme s koeficienty t1, t2, . . . , tn T. Pak ovšem vektor t = (t1, t2, . . . , tn) je řešením soustavy rovnic Ax = b . Věnujme se nejprve speciálnímu případu, kdy matice dané soustavy lineárních rovnic je čtvercová a regulární. Pak rozší- řená matice této soustavy pochopitelně nemůže mít větší hod- nost, takže podle Frobeniovy věty taková soustava je řešitelná. 2 Uvidíme dále, že tato soustava má jediné řešení a jeho tvar udává následující Cramerovo pravidlo. Věta. Buď (T, +, ) těleso, buď A = (aij) regulární čtvercová matice řádu n nad (T, +, ) a buď b = (b1, b2, . . . , bn) vektor z Tn . Potom soustava lineárních rovnic A x = b má jediné řešení t = (t1, t2, . . . , tn), kde pro každé j = 1, 2, . . . , n je tj = |Aj| |A| , přičemž Aj je matice vzniklá z matice A nahrazením jejího j-tého sloupce sloupcem b . Důkaz. Buď t = (t1, t2, . . . , tn) řešení soustavy A x = b , takže platí At = b . Poněvadž matice A je regulární, existuje k ní inverzní matice A-1 . Vynásobíme-li touto maticí poslední rovnost zleva, obdržíme, že A-1 At = A-1 b , takže vychází, že t = A-1 b . Je tedy takto řešení t dané soustavy určeno jednoznačně. Ukážeme, že má výše uvedený tvar. Podle poslední věty z kapitoly o regulárních maticích máme A-1 = |A|-1 A , kde A je adjungovaná matice k matici A. Je to transponovaná matice k matici složené z algebraických doplňků Aij prvků aij matice A. Z rovnosti t = A-1 b tedy plyne rovnost t = |A|-1 A b , což znamená, že pro každé j = 1, 2, . . . , n je tj = |A|-1 (A1jb1+A2jb2+ +Anjbn). Výraz v závorce je ovšem možno vidět jako Laplaceův rozvoj podle j-tého sloupce determinantu z matice, která se od matice A liší tím, že její j-tý sloupec byl nahrazen sloupcem b . Tedy jde právě o matici Aj, jak byla definována výše. Takže tímto způsobem vychází, že tj = |A|-1 |Aj| pro j = 1, 2, . . . , n. Homogenní soustavy lineárních rovnic Věnujme se dále jinému speciálnímu případu. Mějme obec- nou soustavu lineárních rovnic tak, jak byla zadána na začátku 3 kapitoly. Jsou-li přitom všechny absolutní členy této soustavy rovny nule, tedy má-li daná soustava tvar A x = o , kde A = (aij) je matice typu m/n nad tělesem (T, +, ) a o = (0, 0, . . . , 0) je nulový vektor z Tm , pak mluvíme o tom, že je dána homogenní soustava m lineárních rovnic o n ne- známých nad tělesem (T, +, ). Jedním z řešení takové soustavy je jistě nulový vektor o = (0, 0, . . . , 0) z Tn . Tvrzení. Množina všech řešení homogenní soustavy m line- árních rovnic o n neznámých nad tělesem (T, +, ) tvoří podpro- stor ve vektorovém prostoru (Tn , +, ). Důkaz. Již jsme poznamenali, že nulový vektor o z Tn je ře- šením takové homogenní soustavy lineárních rovnic. Dále jsou-li s = (s1, s2, . . . , sn) a t = (t1, t2, . . . , tn) libovolné dva vektory z Tn , které jsou řešeními dané homogenní soustavy lineárních rovnic, a je-li r T libovolný prvek, pak očividně také vektory s+t a rs jsou rovněž řešeními této soustavy. Tvoří tedy množina všech řešení takové soustavy podprostor v prostoru (Tn , +, ). Poněvadž tedy množina všech řešení homogenní soustavy li- neárních rovnic o n neznámých nad tělesem (T, +, ) tvoří pod- prostor ve vektorovém prostoru (Tn , +, ), což je prostor konečné dimenze n, má rovněž podprostor všech řešení této homogenní soustavy konečnou dimenzi k n. Tvrzení. Množina všech řešení homogenní soustavy m line- árních rovnic o n neznámých s maticí koeficientů A = (aij) nad tělesem (T, +, ) tvoří vektorový prostor dimenze k = n - h(A), kde h(A) je hodnost matice A. Poznámka. V následujícím důkazu popíšeme i metodu, jak najít bázi vektorového prostoru všech řešení dané homogenní soustavy lineárních rovnic. 4 Důkaz. V kapitole o hodnosti matic jsme popsali elemen- tární řádkové úpravy matice A. Snadno lze přímo ověřit, že prováděním elementárních řádkových úprav s maticí A se ne- mění množina všech řešení homogenní soustavy lineárních rovnic A x = o určené touto maticí. Dále jsme v kapitole o hodnosti matic viděli, že matici A lze elementárními řádkovými úpravami převést až na Gauss-Jordanův tvar. Můžeme tedy dále předpo- kládat, že matice A už je v Gauss-Jordanově tvaru. Je-li A nu- lová matice, je množinou všech řešení zmíněné homogenní sou- stavy celý prostor Tn , který má dimenzi n. Předpokládejme tedy dále, že A je nenulová matice. Poněvadž její hodnost je h(A), má tato matice právě tolik nenulových řádků a také tolik hlav- ních prvků. Nechť j1, j2, . . . , jh(A) jsou indexy těch sloupců ma- tice A, v nichž leží hlavní prvky. Je tedy v prvních h(A) řádcích a ve sloupcích s jmenovanými indexy obsažena jednotková ma- tice řádu h(A); zbývající řádky, jsou-li nějaké, jsou nulové. Je-li h(A) = n, pak tato jednotková matice vyplňuje celou horní část matice A pozůstávající z prvních n řádků. Tehdy je ale jediným řešením zmíněné soustavy rovnic nulový vektor o = (0, 0, . . . , 0) z Tn , který tvoří nulový podprostor {o} dimenze 0. Zabývejme se tedy dále situací, kdy 0 < h(A) < n. Zaveďme terminologii, že složkám řešení t = (t1, t2, . . . , tn) homogenní soustavy A x = o , jejichž indexy leží v množině {1, 2, . . . , n}-{j1, j2, . . . , jh(A)}, budeme říkat volné složky. Po- tom je ale evidentní, že vezmeme-li vektor t z Tn takovým způ- sobem, že jeho volné složky zvolíme jako libovolné prvky z T, pak zbývající složky tj1 , tj2 , . . . , tjh(A) můžeme dopočítat tak, aby vektor t byl řešením soustavy rovnic A x = o . Tento do- počet je přitom jednoznačný. Poněvadž počet volných složek vektoru t je roven číslu k = n - h(A), můžeme takto vytvořit k lineárně nezávislých vektorů f1, f2, . . . , fk z Tn , které jsou ře- šeními dané homogenní soustavy lineárních rovnic -- stačí vždy jednu volnou složku zvolit rovnu 1 a ostatní volné složky po- 5 ložit rovny 0. Z jednoznačnosti dopočtu složek vektoru t s in- dexy j1, j2, . . . , jh(A) pak plyne, že zmíněné vektory f1, f2, . . . , fk již generují celý prostor všech řešení t dané soustavy. Skutečně zvolíme-li volné složky vektoru t jakkoliv, bude výsledný vek- tor t lineární kombinací vektorů f1, f2, . . . , fk s koeficienty, jimiž jsou právě zmíněné volné složky tohoto vektoru t. Tvoří tedy vektory f1, f2, . . . , fk bázi vektorového prostoru všech řešení dané soustavy rovnic, takže tento prostor má dimenzi k = n - h(A). Platí ale i tvrzení obrácené vůči tvrzení právě dokázanému: Tvrzení. Buď (T, +, ) těleso a buď W Tn libovolný pod- prostor vektorového prostoru (Tn , +, ) dimenze k n. Pak existuje homogenní soustava lineárních rovnic o n neznámých nad tělesem (T, +, ) s maticí koeficientů A = (aij) hodnosti h(A) = n - k, jejíž všechna řešení tvoří právě podprostor W. Důkaz. Je-li k = n, tedy je-li W = Tn , pak lze vzít za A nulovou matici (s libovolným počtem řádků). Je-li k = 0, tedy je-li W nulový podprostor, pak lze vzít za A jednotkovou ma- tici En řádu n. Zabývejme se tedy dále situací, kdy 0 < k < n. Buď f1, f2, . . . , fk libovolná báze podprostoru W. Vytvořme nej- prve matici B tak, že za její řádky vezmeme právě vektory f1, f2, . . . , fk. Pak hodnost h(B) = k. Uvažujme homogenní sou- stavu lineárních rovnic Bx = o . Podle předchozího tvrzení je množinou všech řešení této soustavy nějaký podprostor U Tn dimenze n - k. Vezměme nyní libovolnou bázi g1, g2, . . . , gn-k podprostoru U a sestavme matici A tak, že za její řádky vez- meme tentokrát vektory g1, g2, . . . , gn-k. Pak ovšem pro hodnost této matice platí h(A) = n - k. Vzniká tak homogenní soustava lineárních rovnic A x = o . Opět podle předchozího tvrzení je množinou všech řešení této poslední soustavy nějaký podpro- stor vektorového prostoru (Tn , +, ) dimenze k. Ukážeme, že je to právě výchozí podprostor W. Poněvadž oba zmíněné pod- 6 prostory mají stejnou dimenzi k, stačí ukázat, že vektory pod- prostoru W jsou řešeními soustavy rovnic A x = o . Znovu poněvadž množina všech řešení této soustavy rovnic tvoří pod- prostor vektorového prostoru (Tn , +, ), postačí jenom ukázat, že vektory f1, f2, . . . , fk, jež tvoří bázi podprostoru W, jsou řešeními soustavy rovnic A x = o . Vzhledem ke konstrukci matic A a B je ale tato poslední podmínka ekvivaventní tomu, že vektory g1, g2, . . . , gn-k jsou řešeními soustavy rovnic B x = o . Tak tomu ale podle výše popsané konstrukce opravdu je. Obecné soustavy lineárních rovnic Věnujme se konečně obecné soustavě lineárních rovnic A x = b , kde A = (aij) je matice typu m/n nad tělesem (T, +, ) a b = (b1, b2, . . . , bm) je vektor z prostoru (Tm , +, ), tak jak byla zadána na počátku této kapitoly. Zaměníme-li v ní vektor b nulovým vektorem o = (0, 0, . . . , 0), získáme soustavu rovnic A x = o , o které mluvíme jako o zhomogenizované soustavě lineárních rovnic. V této situaci platí následující fakt. Tvrzení. Je-li soustava m lineárních rovnic o n neznámých A x = b nad tělesem (T, +, ) řešitelná, pak množina všech řešení této soustavy lineárních rovnic tvoří lineární varietu ve vektorovém prostoru (Tn , +, ). Přitom zaměřením této lineární variety je podprostor vektorového prostoru (Tn , +, ) pozůstáva- jící ze všech řešení zhomogenizované soustavy lineárních rovnic A x = o . Důkaz. Poněvadž soustava lineárních rovnic A x = b je řešitelná, je množina všech jejích řešení neprázdná. Jsou-li dále s = (s1, s2, . . . , sn) a t = (t1, t2, . . . , tn) libovolné vektory z Tn , 7 které jsou řešeními této soustavy, a jsou-li p, q T libovolné prvky splňující p+q = 1, pak A(ps+qt) = pAs +qAt = p b + q b = (p + q) b = b , takže také vektor ps + qt je řešením uvedené soustavy. Tvoří tedy množina všech řešení této soustavy lineární varietu v (Tn , +, ). Podle prvního ze dvou tvrzení v poslední části kapitoly o pod- prostorech vektorových prostorů je zaměřením uvedené lineární variety množina vektorů tvaru {t-s | t Tn , At = b }, kde s Tn je libovolný pevně zvolený vektor splňující A s = b . Ukážeme, že tato množina vektorů je právě množinou všech ře- šení zhomogenizované soustavy A x = o . Nechť tedy nejprve t - s je libovolný vektor z uvedené množiny. Pak A (t - s) = A t - A s = b - b = o , takže vektor t - s je řešením zhomogenizované soustavy A x = o . Nechť naopak vektor z Tn je libovolným řešením této zhomogenizované soustavy. Uvažme vektor t = s + z. Potom pro tento vektor vychází, že A t = A s + A z = b + o = b , takže vektor t je řeše- ním původně zadané soustavy A x = b . Přitom z = t - s, čili vektor z náleží výše uvedené množině vektorů. Je tedy za- měřením lineární variety pozůstávající ze všech řešení soustavy A x = b podprostor všech řešení zhomogenizované soustavy A x = o . Důsledek. Je-li soustava lineárních rovnic o n neznámých A x = b nad tělesem (T, +, ) řešitelná, pak pro libovolný vektor s = (s1, s2, . . . , sn) z Tn , který je řešením této soustavy, platí, že množina všech řešení soustavy A x = b má tvar s + W = {s + z : z W}, kde W Tn je vektorový podprostor všech řešení zhomogeni- zované soustavy lineárních rovnic A x = o . Důkaz plyne bezprostředně z předchozího tvrzení a z textu mezi prvním a druhým tvrzením v poslední části kapitoly o pod- prostorech vektorových prostorů. 8 V kontextu posledního tvrzení a jeho důsledku se používá ná- sledující terminologie. Je-li A x = b libovolná řešitelná sou- stava m lineárních rovnic o n neznámých nad tělesem (T, +, ), pak jeden každý vektor s = (s1, s2, . . . , sn) z prostoru (Tn , +, ), který je řešením této soustavy, se nazývá partikulární řešení soustavy rovnic A x = b . Množinu všech řešení této sou- stavy lze potom získat tak, že k jednomu jejímu partikulárnímu řešení se postupně přičtou všechna řešení příslušné zhomogeni- zované soustavy rovnic. V důkazu tvrzení o dimenzi vektorového prostoru všech řešení dané homogenní soustavy lineárních rov- nic jsme dále viděli, jakým způsobem je možno najít bázi pod- prostoru W vektorového prostoru (Tn , +, ), který je množinou všech řešení zhomogenizované soustavy rovnic Ax = o . Libo- volná báze f1, f2, . . . , fk vektorového podprostoru W všech řešení této zhomogenizované soustavy se pak nazývá fundamentální systém řešení zadané soustavy rovnic Ax = b . Pak platí, že W = f1, f2, . . . , fk , takže množinu všech řešení soustavy rovnic A x = b lze explicitně zapsat ve tvaru s + f1, f2, . . . , fk . Zbývá popsat metodu, jak najít alespoň jedno partikulární řešení s = (s1, s2, . . . , sn) soustavy lineárních rovnic Ax = b . Opět je snadné se přesvědčit, že prováděním elementárních řád- kových úprav, tentokrát ovšem s celou rozšířenou maticí (A|b ) soustavy, se nezmění množina všech řešení soustavy Ax = b . Dále zase můžeme elementárními řádkovými úpravami převést rozšířenou matici (A|b ) až na Gauss-Jordanův tvar. Vyjde-li poslední nenulový řádek v tomto tvaru tak, že má svůj hlavní prvek až v posledním, odděleném sloupci, pak má rozšířená ma- tice (A|b ) větší hodnost než matice A, takže podle Frobeniovy věty nemá soustava A x = b řešení. V opačném případě zvo- líme partikulární řešení s = (s1, s2, . . . , sn) soustavy A x = b například tak, že všechny jeho volné složky položíme rovny 0 9 a zbývající složky vekoru s pak jednoznačně vyjdou. Poté sou- stavu zhomogenizujeme a způsobem popsaným v důkazu již ci- tovaného tvrzení, opět s použitím Gauss-Jordanova tvaru ma- tice A, najdeme fundamentální systém řešení f1, f2, . . . , fk sou- stavy rovnic A x = b . Tím podle předchozího výkladu zís- káme všechna potřebná data ke kompletnímu popisu množiny všech řešení této soustavy rovnic. Tento postup se nazývá Gaus- sova eleminační metoda řešení soustav lineárních rovnic. Tvrzení. Buď (T, +, ) těleso. Pak pro libovolnou lineární varietu Q ve vektorovém prostoru (Tn , +, ) existuje soustava lineárních rovnic Ax = b o n neznámých nad tělesem (T, +, ) taková, že množinou všech řešení této soustavy rovnic je právě lineární varieta Q. Důkaz. Opět podle textu mezi prvním a druhým tvrzením v poslední části kapitoly o podprostorech vektorových prostorů pro libovolný vektor s z Q máme Q = s + W, kde W Tn je zaměření lineární variety Q. Podle předminulého tvrzení v ny- nější kapitole existuje homogenní soustava lineárních rovnic Ax = o , jejíž množinou všech řešení je právě podprostor W. Určeme vektor b z Tm z rovností b = A s . Z důsledku po- sledního tvrzení této kapitoly je pak jasné, že množinou všech řešení soustavy lineárních rovnic A x = b bude právě daná lineární varieta Q. 10