Tietotekninen algebra [lecture notes] [PDF]

Zitiervorschau

Tietotekninen algebra Vesa Halava

Luentomoniste

Turun yliopisto Matematiikan ja tilastotieteen laitos 20014 Turku

2012

Sisältö 1 Kertausta: matriisit ja lineaariset yhtälöryhmät 1.1 1.2 1.3 1.4 1.5 1.6

Matriisit ja niiden operaatiot . . . Elementaariset vaakarivioperaatiot Lineaariset yhtälöryhmät . . . . . Käänteismatriisi . . . . . . . . . . Determinantit . . . . . . . . . . . . Matriisit -ohjelmalla . . .

Matlab

2 Vektoriavaruudet 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9

Vektoriavaruus . . . . . . . . n-ulotteinen reaaliavaruus . . Aliavaruus . . . . . . . . . . . Lineaarikombinaatio . . . . . Lineaarinen riippumattomuus Vektoriavaruuden kanta . . . Matriisin aste . . . . . . . . . Kannanvaihto . . . . . . . . . Vektorijoukon ortogonalisointi

. . . . . . . . .

. . . . . . . . .

3 Ominaisarvot ja lineaarikuvaukset 3.1 3.2 3.3 3.4 3.5

Ominaisarvot . . . . . . . . Lineaarikuvaukset . . . . . Lineaarikuvauksen matriisi . Similaariset matriisit . . . . Matriisien diagonalisointi .

4 Ryhmäteoriaa 4.1 4.2 4.3 4.4 4.5 4.6

. . . . .

. . . . .

. . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . . . . . . . . lause . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

Ryhmän määritelmä ja esimerkkejä Kokonaisluvut ja jäännösluokat . . Aliryhmä . . . . . . . . . . . . . . Ryhmän generointi . . . . . . . . . Aliryhmän sivuluokat ja Lagrangen Normaali aliryhmä ja tekijäryhmä

1

1 3 4 7 8 11

17

17 18 19 21 25 28 33 37 39

43

43 48 52 56 57

62

62 65 72 73 74 78

Alkusanat Tällä kurssilla käsitellään abstraktin algebran perusasioita. Tarkastelussa pääpaino on lineaarialgebran eli vektoriavaruuksien teorialla sekä matriisien teorialla. Lisäksi käsitellään ryhmäteorian alkeita ja tässä yhteydessä myös lukuteorian perusasioita. Abstraktin algebran rakenteilla on monia sovelluksia nykyaikaisessa tietotekniikassa. Jo pelkästään matriisit ja vektorit ovat osa algoritmien, niiden suunnittelun ja implementoinnin peruskäsitteistöä. Esimerkiksi graasissa sovelluksissa ns. vektoriavaruuksien ominaisuudet kuten kanta ja niihin liittyvät kannanvaihtomatriisit ovat käytössä. Ryhmäteorialla taas on sovelluksia esimerkiksi kryptograassa. Tähän vuoden 2012 versioon lisätty osioita, joissa käsitellään laskemista -ohjelman avulla. Kirjallisuutta (kurssin tueksi [t] tai jatkoksi [j]):

Matlab

F. R. Gantmacher, The Theory of Matrices, Chelsea Publishing, 1959. [t/j] J. von zur Gathen, J. Gerhard, Modern Computer Algebra, Cambridge, 2003. [j] W. H. Greub, Linear Algebra, Springer-Verlag, 1974. [t/j] E. Jurvanen, Tietotekninen algebra, Turun yliopisto, 2006. [t] M. Koppinen, Lineaarialgebra, osat 1 ja 2, Turun yliopisto, 2006. [t] S. Lang, Linear Algebra, Springer-Verlag, 1971. [t/j] T. Mäkelä, Matlab, https://sites.google.com/site/laskenta/matlab. E. Neuman, Using Matlab in Linear Algebra, http://www.math.siu.edu /matlab/tutorial3.pdf

1

1

Kertausta: matriisit ja lineaariset yhtälöryhmät

1.1

Matriisit ja niiden operaatiot

Kerrataan aluksi matriisin määritelmä.

Määritelmä 1.1. Kaaviota    A= 

a11 a21 .. .

a12 . . . a22 . . . .. .

a1n a2n .. .

am1 am2 . . .

amn

   , 

jossa on m vaakariviä ja n pystyriviä, kutsutaan m × n -matriisiksi tai tyyppiä m × n olevaksi matriisiksi. Jos matriisin alkiot aij ∈ R kaikilla 1 ≤ i ≤ m ja 1 ≤ j ≤ n, niin matriisia A kutsutaan myös reaalimatriisiksi. Tällä kurssilla tarkastellaan reaalimatriisien lisäksi myös (ominaisarvojen yhteydessä) kompleksilukumatriiseja , joiden alkiot ovat luonnollisesti kompleksilukuja. Matriisin i:nnen vaakarivin j :s alkio aij on matriisin A kohdassa (i, j) oleva alkio. Matriisi A kirjoittetaan joskus myös muodossa

A = (aij ) = Am×n = (aij )m×n .

Määritelmä 1.2. Matriisia, jossa m = n, siis vaakarivejä ja pystyrivejä on yhtä monta, kutsutaan neliömatriisiksi. Olkoon A = (aij )n×n . 1. Neliömatriisin alkiot a11 , . . . , ann , ovat ns. diagonaalialkiot. 2. Neliömatriisi on yläkolmiomatriisi, jos aij = 0 kun i > j (diagonaalin alapuolella pelkkiä nollia). 3. Neliömatriisia I = (aij ), missä ( 1, aij = 0,

jos i = j, muulloin,

kutsutaan identiteettimatriisiksi.

Määritelmä 1.3. Nollamatriisi 0 on matriisi, jonka kaikki alkiot ovat nollia, ts. 0 = (0)m×n

Palautetaan seuraavaksi mieleen matriisien keskeiset operaatiot.

Määritelmä 1.4. Matriisin A = (aij )m×n transpoosi on matriisi AT =

(aji )n×m . Ts. matriisin transpoosi saadaan matriisista vaihtamalla vaakarivit pystyriveiksi, järjestys säilyttäen. Tyyppiä m × n olevan matriisin transpoosi on siis tyyppiä n × m.

1.1 Matriisit ja niiden operaatiot

2

Seuraavaksi määritellään matriisien summa, erotus ja reaaliluvulla kertominen. Huomaa, että matriisien summassa ja erotuksessa matriisien pitää olla samaa tyyppiä.

Määritelmä 1.5. Olkoon A = (aij )m×n ja B = (bij )m×n , ja r ∈ R. 1. A + B = (aij + bij )m×n , 2. A − B = (aij − bij )m×n , ja 3. rA = Ar = (raij )m×n . Matriisien tulossa taas ensimmäisen matriisin pystyrivin lukumäärän pitää olla sama kuin toisen matriisin vaakarivien lukumäärän.

Määritelmä 1.6. Olkoon A = (aij )m×n ja B = (bij )n×p . Matriisien A ja B tulo A · B = AB = (cij )m×p , missä cij

n X

=

aik bkj

k=1

= ai1 b1j + ai2 b2j + . . . + ain bnj . Tulomatriisin AB kohdan (i, j) alkio saadaan siis kertomalla matriisin A i:nnen vaakarivin alkiot matriisin B j :nnen pystyrivin vastaavilla alkioilla ja laskemalla saadut tulot yhteen. Huomaataan myös, että tyyppiä m × n ja n × p olevien matriien tulomatriisi on tyyppiä m × p.

Esimerkki 1.7. Merkitään  A=

3 −1 1 1 0 2



 ,

B=

0 1 −1 2 0 1



 ,

C=

1 −1 2 0

 .

Nyt summa A + C ei ole määritelty, kuten ei myöskään tulo AC. Seuraavat matriisit taas ovat määriteltyjä:     3 0 0 3 −3 , , 3C = A+B= 3 0 3 6 0     2 −1 −1 1 2 T CA = , C = . 6 −2 2 −1 0 Seuraavassa lauseessa kerrataan matriisien peruslaskutoimitusten keskeiset laskulait.

Lause 1.8.

Matriisilaskutoimituksille ovat voimassa mm. seuraavat lasku-

säännöt: 1.

A + B = B + A,

2.

(A + B) + C = A + (B + C),

1.2 Elementaariset vaakarivioperaatiot 3.

A(BC) = (AB)C,

4.

A(B + C) = AB + AC,

5.

(A + B)C = AC + BC,

6.

(rs)A = r(sA),

7.

r(AB) = (rA)B = A(rB),

8.

(r + s)A = rA + sA,

9.

r(A + B) = rA + rB,

missä

3

A, B, C ovat kussakin kohdassa sellaisia matriiseja, että laskutoimir , s ∈ R.

tukset ovat määriteltyjä, ja Todistus.

Sivuutetaan.

Huomautus 1.9. Yleensä AB 6= BA; ts. matriisitulo ei kommutoi. Määritelmä 1.10. Neliömatriisille A määritellään positiiviset potenssit An (n ≥ 0) luonnollisella tavalla:

A0 = I, 1.2

A1 = A,

Ak+1 = Ak A (k ≥ 1).

Elementaariset vaakarivioperaatiot

Määritelmä 1.11. Tyyppiä m × n olevaa matriisia P sanotaan redusoiduksi porrasmatriisiksi (lyh. RPM), jos jollakin luvulla r (0 ≤ r ≤ m) seuraavat ehdot ovat voimassa.

1. Jokaisella r ensimmäistä vaakarivistä on ainakin yksi nollasta poikkeava alkio, ja viimeiset m − r vaakariviä koostuvat pelkästään nollista. 2. Jokaisella r ensimmäistä vaakarivistä vasemmalta ensimmäinen nollasta poikkeava alkio on 1. Tätä ykköstä sanotaan rivin johtavaksi ykköseksi. 3. Jos vaakarivin i johtava ykkönen on kohdassa (i, ji ), niin j1 < j2 < ... < jr . 4. Johtavien ykkösten ylä- ja alapuolella on pelkästään nollia.

Esimerkki 1.12. Matriisi          

0 0 0 0 0 0 0

1 0 0 0 0 0 0

0 1 0 0 0 0 0

0 0 1 0 0 0 0

∗ ∗ ∗ 0 0 0 0

0 0 0 1 0 0 0

0 0 0 0 1 0 0

∗ ∗ ∗ ∗ ∗ 0 0

∗ ∗ ∗ ∗ ∗ 0 0

0 0 0 0 0 1 0

∗ ∗ ∗ ∗ ∗ ∗ 0

∗ ∗ ∗ ∗ ∗ ∗ 0

         

1.3 Lineaariset yhtälöryhmät

4

on tyyppiä 7 × 12 oleva redusoitu porrasmatriisi, missä r = 6. (Symboli ∗ voidaan korvata millä tahansa luvulla.)

Määritelmä 1.13. Matriisin elementaariset vaakarivioperaatiot ovat seuraavat.

1. Vaihdetaan kahden vaakarivin paikkaa. 2. Kerrotaan jonkin vaakarivin kaikki alkiot nollasta poikkeavalla vakiolla. 3. Lisätään jokin vaakarivi vakiolla kerrottuna johonkin toiseen vaakariviin. Elementaariset vaakarivioperaatioden -menetelmä on erittäin käyttökelpoinen matriisien muunnosmenetelmä kuten kurssin kuluessa tullaan huomaamaan. Jos matriisista A voidaan elementaaristen vaakarivioperaatioiden avulla muuntaan matriisiksi B (ja toisin päin) sanotaan, että matriisit A ja B ovat vaakariviekvivalentit, ja merkitään A ∼ B.

Lause 1.14.

Jokainen matriisi voidaan elementaarisilla vaakarivioperaa-

tioilla muuntaa redusoiduksi porrasmatriisiksi. Todistus.

Sivuutetaan.

Seuraus 1.15.

Jokainen neliömatriisi voidaan elementaarisilla vaakarivi-

operaatioilla muuntaa 1) identiteettimatriisiksi tai 2) matriisiksi, jonka alin vaakarivi on nollarivi.

Väite seuraa edellisestä lauseesta. Jos r = n, niin jokaisella vaakarivillä on johtava ykkönen, joten RPM on identiteettimatriisi. Muulloin RPM:ssä on selvästi nollarivi. Todistus.



 3 1 1 0 Esimerkki 1.16. Muunnetaan matriisi  2 2 2 2 elementaarisilla −2 4 3 1 vaakarivioperaatioilla RPM:ksi. 1.3

Lineaariset yhtälöryhmät

Määritelmä 1.17. Lineaarisessa yhtälöryhmä on joukko yhtälöitä  a11 x1     a21 x1    

+ a12 x2 + a22 x2

+ . . . + a1n xn + . . . + a2n xn .. .

= b1 = b2

am1 x1 + am2 x2 + . . . + amn xn = bm

1.3 Lineaariset yhtälöryhmät

5

missä aij ∈ R ja bi ∈ R ovat vakioita (siis lukuja) ja termit xj ovat muuttujia, kun 1 ≤ i ≤ m ja 1 ≤ j ≤ n. Merkitään       a11 . . . a1n x1 b1    .   .  .. A = (aij )m×n =  ...  , X =  ..  , B =  ..  . .

am1 . . . amn

xn

bm

Edellinen yhtälöryhmä voidaan nyt esittää matriisitulon avulla muodossa

AX = B. Luvut c1 , c2 , . . . , cn ovat lineaarisen yhtälöryhmän ratkaisu, jos sijoitus x1 = c1 , x2 = c2 , . . . , xn = cn toteuttaa yhtälöryhmän, ts.   c1   A  ...  = B.

cn Lineaarista yhtälöryhmää ratkaistaessa riittää käyttää seuraavia kolmea operaatiota, jotka eivät muuta ratkaisua. 1. Vaihdetaan kahden yhtälön paikkaa. 2. Kerrotaan jokin yhtälö nollasta eroavalla vakiolla. 3. Lisätään jokin yhtälö vakiolla kerrottuna johonkin toiseen yhtälöön. Huomaa, että vastaavat operaatiot matriiseilla ovat juuri elementaariset vaakarivioperaatiot. Yhtälöryhmä AX = B voidaankin ratkaistaan siten, että se esitetään matriisimuodossa (A B), joka muunnetaan redusoiduksi porrasmatriisiksi. Redusoidusta porrasmatriisi muodosta yhtälöryhmänratkaisu on helppo lukea. Näin kuvattua ratkaisualgoritmia kutsutaan Gaussin eliminointimenetelmäksi.

Esimerkki 1.18. Ratkaistaan yhtälöryhmä    

− x2 x1 + x2 3x1 + x2    2x1 + 4x2

− x3 + x3 − 2x3 + x3

+ x4 + x4 + 2x4 − 2x4

= 0 = 6 . = 3 = −1

Esitetään yhtälöryhmä matriisimuodossa AX = B ja muodostetaan matriisi   0 −1 −1 1 0  1 1 1 1 6  . (A B) =   3 1 −2 2 3  2 4 1 −2 −1

1.3 Lineaariset yhtälöryhmät

6

Vaihdetaan ensin kahden ensimmäisen vaakarivin paikkaa, jolloin saadaan matriisi 

−1 1 1 4

0  1   3 2

−1 1 −2 1

 0 6   3  −1

1 1 2 −2



1  0 ∼  3 2

1 −1 1 4

1 −1 −2 1

 6 0  , 3  −1

1 1 2 −2

jossa on kohdassa (1, 1) nollasta poikkeava alkio. Kertomalla tarvittaessa sopivalla vakiolla saadaan tähän kohtaan aina ykkönen. Lisäämällä ensimmäinen vaakarivi sopivilla vakioilla kerrottuna muihin vaakariveihin, saadaan ensimmäisen pystyrivin muiksi alkioiksi nollat: 

1  0   3 2

1 −1 1 4

1 −1 −2 1

 6 0   3  −1

1 1 2 −2



1  0  ∼ 0 0

1 −1 −2 2

1 −1 −5 −1

 6 0  . −15  −13

1 1 −1 −4

Kerrotaan toinen vaakarivi luvulla −1 ja lisätään se sopivilla vakioilla kerrottuna muihin vaakariveihin, niin että saadaan toisen pystyrivin muiksi alkioiksi nollat: 

 1 1 1 1 6  0 −1 −1 1 0     0 −2 −5 −1 −15  0 2 −1 −4 −13



 1 1 1 1 6  0 1 1 −1 0   ∼  0 −2 −5 −1 −15  0 2 −1 −4 −13



1  0 ∼  0 0

 0 0 2 6 1 1 −1 0  . 0 −3 −3 −15  0 −3 −2 −13

Jakamalla kolmas vaakarivilla luvulla −3 ja lisäämällä saatu vaakarivi jälleen muihin vaakariveihin sopivilla vakioilla kerrottuna saadaan  1 0 0 2 6  0 1 1 −1 0     0 0 −3 −3 −15  0 0 −3 −2 −13 

 1 0 0 2 6  0 1 1 −1 0   ∼  0 0 1 1 5  0 0 −3 −2 −13





1 0  0 1  ∼ 0 0 0 0

 0 2 6 0 −2 −5  . 1 1 5  0 1 2

Lisäämällä lopuksi viimeinen vaakarivi sopivilla vakioilla kerrottuna muihin saadaan matriisi 

1  0   0 0

0 1 0 0

0 0 1 0

2 −2 1 1

 6 −5   5  2



1  0  ∼ 0 0

0 1 0 0

0 0 1 0

0 0 0 1

 2 −1  , 3  2

mistä ratkaisu x1 = 2, x2 = −1, x3 = 3, x4 = 2 on helppo lukea.

Lause 1.19.

Jos

homogeenisessa

 a11 x1     a21 x1    

+ a12 x2 + a22 x2

lineaarisessa yhtälöryhmässä

+ . . . + a1n xn + . . . + a2n xn

= 0 = 0

.. .

am1 x1 + am2 x2 + . . . + amn xn = 0

on vähemmän yhtälöitä kuin tuntemattomia, ts. aina myös epätriviaali ratkaisu

m < n, niin yhtälöllä on (x1 , . . . , xn ) 6= (0, 0, . . . , 0).

1.4 Käänteismatriisi

7

Muunnetaan yhtälöryhmän kertoimien matriisi RPM:ksi. Koska m < n, on tässä RPM:ssä johtavia ykkösiä vähemmän kuin tuntemattomia. Siis jotakin muuttujaa vastaavalla pystyrivillä ei ole johtavaa ykköstä. Tällaista pystyriviä vastaavan muuttujan arvo voidaan valita vapaasti. Todistus.

Esimerkki 1.20. Ratkaistaan yhtälöryhmä 

1.4

x1 − x2 + 2x3 = 0 . 3x1 + x2 + 4x3 = 0

Käänteismatriisi

Määritelmä 1.21. Neliömatriisin A käänteismatriisilla tarkoitetaan sellaista matriisia B, että

AB = I = BA. Jos käänteismatriisi on olemassa, siitä käytetään merkintää A−1 (= B). Jos matriisilla A on käänteismatriisi, niin sanotaan, että A on säännöllinen tai kääntyvä. On selvää, että jos A on tyyppiä n × n oleva säännöllinen matriisi, niin sen käänteismatriisi A−1 on tyyppiä n × n.     3 −5 2 5 , silkäänteismatriisi on Esimerkki 1.22. Matriisin −1 2 1 3 lä         2 5 3 −5 1 0 3 −5 2 5 . = = 1 3 −1 2 0 1 −1 2 1 3

Esimerkki 1.23. Olkoon A neliömatriisi, jonka yksi pystyrivi on nollar-

ivi. Tällöin matriisilla A ei ole käänteismatriisia. Nimittäin, olipa B mikä tahansa matriisi, matriisitulossa BA yksi pystyrivi on nollarivi, joten tämä tulomatriisi ei voi olla identiteettimatriisi millään matriisilla B. Vastaava päättely voidaan tehdä myös matriiseille, joissa yksi vaakarivi on nollarivi.

Esimerkki 1.24. Tarkastellaan määritelmän 1.17 lineaarista yhtälöryhmää AX = B, kun m = n. Jos matriisilla A on käänteismatriisi ja matriisi A−1 tunnetaan, voidaan yhtälöryhmä ratkaista matriisikertolaskulla: X = IX = (A−1 A)X = A−1 (AX) = A−1 B.

Lause 1.25.

A ja B ovat matriiseja, joilla on käänteismatriisit A−1 ja B−1 , niin myös matriisilla AB on käänteismatriisi, nimittäin B−1 A−1 . Yleisemmin, jos Ai (i = 1, . . . , k ) ovat matriiseja, joilla on käänteisma−1 triisit Ai , niin myös matriisilla A1 . . . Ak on käänteismatriisi, nimittäin −1 −1 matriisi Ak . . . A1 . Jos

1.5 Determinantit Todistus.

8

Ensimmäinen väite seuraa matriisituloista

(AB)(B−1 A−1 ) = AIA−1 = AA−1 = I = B−1 B = B−1 IB = B−1 A−1 AB. Toinen väite seuraa induktiolla.

Lause 1.26.

Matriisilla

A on käänteismatriisi, jos ja vain jos A voidaan

elementaarisilla vaakarivioperaatioilla muuntaa identiteettimatriisiksi. Todistus.

Sivuutetaan.

Edellisestä lauseesta saadaan algoritmi käänteismatriisin laskemiseksi: neliömatriisi A muunnetaan elementaarisilla vaakarivioperaatioilla redusoiduksi porrasmatriisiksi P. Jos matriisissa P on alimpana nollarivi, tiedetään, että käänteismatriisia ei ole olemassa, muuten P = I. Jos A on kääntyvä, niin samat vaakarivioperaatiot, jotka muuttivat sen identiteettimatriisiksi, muuttavat identiteettimatriisin matriisiksi A−1 . Siis

( A | I ) ∼ ( I | A−1 ).

Esimerkki 1.27. Etsitään matriisien matriisit. 1.5



2 3 1 2





 1 1 1 ja  0 2 3  käänteis5 5 1

Determinantit

Determinantin määritelmään varten määritellään permutaatioiden käsite, joka kyllä itsessäänkin on tärkeä matemaattinen käsitte.

Määritelmä 1.28. Joukon {1, 2, . . . , n} permutaatio on jono (j1 , j2 , . . . , jn ), missä luvut kaikki luvut 1, 2, . . . , n esiintyvät jossakin järjestyksessä.

Määritelmä 1.29. Joukon {1, 2, . . . , n} permutaatiossa (j1 , j2 , . . . , jn ) paria (j` , jk ) sanotaan inversioksi, jos ` < k ja j` > jk . Permutaatio on parillinen, jos sen inversioiden määrä on parillinen, ja muuten pariton. Permutaation merkki on ( +1, sign(j1 , j2 , . . . , jn ) = −1,

jos (j1 , j2 , . . . , jn ) on parillinen, jos (j1 , j2 , . . . , jn ) on pariton.

Esimerkki 1.30. Joukon {1, 2, 3} permutaatiot (ilman pilkkuja ja sulkeita) ovat: 123, 132, 213, 231, 312, 321. Permutaation 231 inversiot ovat (2, 1) ja (3, 1), joten sign(231) = 1. Permutaatio 132 taas on pariton, eli sign(132) = −1. Huomaa, että joukolla {1, 2, . . . , n} on n! permutaatiota.

1.5 Determinantit

9

Määritelmä 1.31. Neliömatriisin A = (aij )n×n determinantti det(A) on reaaliluku

det(A) =

a11 a21 .. .

a12 a22 .. .

... ...

a1n a2n .. .

an1 an2 . . .

ann

X sign(j1 , j2 , . . . , jn )a1j1 a2j2 · · · anjn , =

missä summaan otetaan kaikkien joukon {1, 2, . . . , n} permutaatiot (j1 , j2 , . . . , jn ). Kaksirivisen matriisin determinantti on   a11 a12 a11 a12 = sign(12)a11 a22 + sign(21)a12 a21 det = a21 a22 a21 a22

= a11 a22 − a12 a21 , ja kolmirivisen   a11 a12 a13 a11 a12 a13   det a21 a22 a23 = a21 a22 a23 a31 a32 a33 a31 a32 a33



= a11 a22 a33 + a12 a23 a31 + a13 a21 a32 −a11 a23 a32 − a13 a22 a31 − a12 a21 a33 . Toisaalta, n-rivisen yläkolmiomatriisin determinantti on aina diagonaalialkioiden tulo: a11 a12 a13 . . . a1n 0 a22 a23 . . . a2n 0 0 a33 . . . a3n = a11 a22 a33 . . . ann . .. .. .. .. . . . . 0 0 0 . . . ann Determinantin määritelmän summan laskeminen on käytännössä hankalaa suurille matriiseille. Seuraavia laskusääntöjen avulla determinantti voidaan laskea tehokkaasti.

Lause 1.32.

1. Jos determinantin kaksi vaakariviä vaihdetaan keskenään,

niin determinantin merkki vaihtuu. 2. Jos determinantissa on kaksi identtistä vaakariviä, niin determinantti on nolla. 3. Determinantin jonkin rivin kaikista alkioista voidaan ottaa tekijä eteen:

a11 . . . a1n a11 . . . a1n .. .. .. .. . . . . cai1 . . . cain = c ai1 . . . ain . .. .. .. .. . . . . an1 . . . ann an1 . . . ann

c∈R

1.5 Determinantit 4. Jos

10

A = (aij )n×n ja c ∈ R, niin det(cA) = cn det(A).

5. Determinantin arvo ei muutu, jos johonkin vaakariviin lisätään toinen vaakarivi vakiolla kerrottuna. 6. Determinantin arvo ei muutu, jos vaakarivit muutetaan pystyriveiksi järjestys säilyttäen, siis

det(A) = det(AT ). Laskusäännöt ovat voimassa, kun niissä vaakarivit korvataan pystyriveillä.

Edellä oleva lause tarjoaa erittäin tehokkaan algoritmin determinantin arvon laskemiseksi: determinanttia vastaava matriisi muunnetaan laskusääntöjä käyttäen yläkolmiomatriisiksi, jonka arvo on helppo laskea.

Esimerkki 1.33. 4 3 2 3 −2 5 2 4 6

4 0 −5 −10 3 2 = 2 3 −2 5 = 2 0 −8 −4 1 1 2 3 2 3 1 1 2 3 2 3 = −2 0 −8 −4 = (−2)(−5)(−4) 0 2 1 0 −5 −10 0 1 2 1 2 3 1 2 3 2 = 40 0 1 2 = 40 0 1 0 2 1 0 0 −3 = −120.



Determinantin tärkein ominaisuus on seuraava.

Lause 1.34.

Neliömatriisilla

A on käänteismatriisi, jos ja vain jos det(A) 6=

0. Todistus.

Sivuutetaan.

Seuraava lause antaa laskusäänöt tiettyjen determinanttien laskemiseen.

Lause 1.35. 1.

Olkoot

A ja B ovat n × n -matriiseja.

det(AB) = det(A) det(B).

2. Jos Todistus.

A on kääntyvä, niin det(A−1 ) = Sivuutetaan.

1 . det(A)

1.6 Matriisit

Matlab-ohjelmalla

11

Käänteismatriisin määritelmässä B on matriisin A käänteismatriisi, jos AB = I ja BA = I. Seuraavan lauseen mukaan käänteismatriisiksi todistamisessa riittää, jos lasketaan vain toinen näistä tuloista.

Lause 1.36. olemassa ja

Jos

A

−1

A ja B ovat n × n -matriiseja ja AB = I, niin A−1 on = B.

Todistus. Koska 1 = det(I) = det(AB) = det(A) det(B), niin det(A) 6= 0. Siis A−1 on olemassa ja tietysti AA−1 = I. Näin ollen

A−1 = A−1 I = A−1 (AB) = (A−1 A)B = IB = B.

1.6

Matriisit

Matlab

-ohjelmalla

Matlab-ohjelmalla matriisit luodaan listaamalla matriisin alkiot vaakariveittäin, käyttäen puolipistettä rivierottimena. Esimerkiksi matriisit     1 −2 3 0 1 −1 A= ja B = −2 7 4 2 0 1 luodaan seuraavasti:

>> A=[1 -2 3;-2 7 4] A = 1 -2

-2 7

3 4

>> B=[0 1 -1;2 0 1] B = 0 2

1 0

-1 1

Matriisien summa lasketaan + komennolla ja vakiolla r kertominen r ∗ A komennolla. Matriisikertolaskua varten määritellään matriisi   2 −4 C= . 3 7 Matriisitulo lasketaan myös ∗ komennolla

1.6 Matriisit

Matlab-ohjelmalla

12

>> A+B ans = 1 0

-1 7

2 5

4 -14

-6 -8

>> -2*A ans = -2 4

>> C=[2 -4;3 7] C = 2 3

-4 7

>> A*C ??? Error using ==> mtimes Inner matrix dimensions must agree. >> C*A ans = 10 -11

-32 43

-10 37

Huomaa, että jos matriisien tyypit eivät ole kertolaskuun sopivat, tulee virheilmoitus. Matriisin A transpoosi saadaan komennolla A', esimerkiksi

>> B' ans =

1.6 Matriisit 0 1 -1

Matlab-ohjelmalla

13

2 0 1

Määritellään uusi matriisi A ja lasketaan sen determinantti komennolla det(A) ja käänteismatriisi komennolla inv(A). Jotta tulokset olisivat paremmin luettavissa, kannattaa valita lukujen esitysmuodoksi rationaaliluvut format rat-komennolla.

>> format rat >> A=[1 -2 3 -2;-2 7 4 -4; 2 0 3 -1; 7 -1 2 -5] A = 1 -2 2 7

-2 7 0 -1

3 4 3 2

-2 -4 -1 -5

>> det(A) ans = 416 >> inv(A) ans = -99/416 -53/208 31/416 -105/416

-23/416 15/208 3/416 -37/416

105/416 31/208 131/416 187/416

37/416 3/208 -41/416 -49/416

Neliömatriisin A potenssit voidaan laskea komennolla Ak, esimerkiksi

>> A^3 ans = 116 -105 -154 479 19 -21

-39 182 26

-3 -142 7

1.6 Matriisit 127

-81

-65

Matlab-ohjelmalla

14

30

>> A^47 ans = 1.0e+042 * 0.5390 -2.2190 0.1177 0.4743

-1.2578 5.1781 -0.2747 -1.1069

-0.5325 2.1921 -0.1163 -0.4686

0.3417 -1.4066 0.0746 0.3007

Huomaa, että tästä matriisin A47 esityksenä on reaaliluvut, rationaaliluku esityksessä antaa matriisin kaikki alkiot muodossa ∗, joka tarkoittaa, että luvut rationaalinen esitys vie liikaa tilaa. Matriisin muuntaminen redusoiduksi porrasmatriisiksi tapahtuu komennolla rref. Esimerkiksi

Matlab

>> rref(B) ans = 1 0

0 1

1/2 -1

Matlab

Tarkastellaan lopuksi lineaaristen yhtälöryhmien ratkaisua -ohjelmistolla. Ratkaistaan ensin Esimerkin 1.18 yhtälöryhmä. Määritellään kerroin matriisi A ja yhtälöiden oikeanpuolen pystyvektori B , ja ratkaistaan yhtölöryhmä AX = B linsolve-komennolla.

>> A=[0 -1 -1 1;1 1 1 1; 3 1 -2 2; 2 4 1 -2] >> B=[0;6;3;-1] A = 0 1 3 2 B = 0

-1 1 1 4

-1 1 -2 1

1 1 2 -2

1.6 Matriisit

Matlab-ohjelmalla

15

6 3 -1 >> linsolve(A,B) ans = 2 -1 3 2 Yhtälöryhmä olisi voitu ratkaista myös komennolla A\B, joka vastaa oikeastaan vektorin B kertomista oikealta matriisin A käänteismatriisilla. Lineaarinen homogeeninen yhtälöryhmän ratkaisuun linsolve ei sovellu, sillä se antaa ainoastaan triviaalin ratkaisun. Esimerkiksi jos

>> A=[0 -1 -1 1;1 1 1 1; 3 1 -2 2] A = 0 1 3

-1 1 1

>> B=zeros(3,1) B = 0 0 0 >> linsolve(A,B) ans = 0 0 0 0

-1 1 -2

1 1 2

1.6 Matriisit

Matlab-ohjelmalla

16

Komento null(A,'r')) ratkaisee lineaarisen homogeenisen yhtälöryhmän AX = 0 antamalla ratkaisuavaruuden generaattori vektorit. Optio r pakottaa vastauksen rationaaliseen muotoon, ilman sitä vastaukset vektorit muodostavat ratkaisuavaruuden ortonormaalikannan (ks. Esimerkki 2.10, Kappaleet 2.6 ja 2.9). Toisaalta, redusoitu porrasmatriisi antaa myös aika hyvän tavan ratkaisuun.

>> null(A,'r') ans = -2 2 -1 1 >> rref(A) ans = 1 0 0

0 1 0

0 0 1

2 -2 1

Tästä nähdään, että ratkaisut ovat muotoa XT = (x, y, z, t) = t(−2, 2, −1, 1).

17

2 2.1

Vektoriavaruudet Vektoriavaruus

Abstraktin algebran perusidea on tutkia samanaikaisesti kaikkia algebrallisia rakenteita, joilla on samat ominaisuudet. Tällaisessa rakenteessa on aina mukana epätyhjä joukko objekteja tai alkioita, joille on määritelty joitakin operaatioita (esim. +, ·, −), funktioita, vakioita (esim. 0, 1), yms. Tämän kurssin keskeinen algebrallinen rakenne on vektoriavaruus. Siinä joukkoa alkioita käsitellään kahden laskutoimituksen avulla, joita kutsutaan yhteenlaskuksi ja skalaarilla kertomiseksi. Ensin annetaan laskutoimituksille joukko sääntöjä, tässä seitsemän kappaletta, V1V7, ja sen jälkeen ruvetaan etsimään muita ominaisuuksia, jotka seuraavat ainoastaan näistä seitsemästä säännöstä. Kun huomataan, että jokin joukko laskutoimituksineen, esimerkiksi polynomien tai matriisien joukko, noudattaa laskusääntöjä V1 V7, tiedämme heti, että joukolla on muutkin säännöistä V1V7 seuraavat ominaisuudet. Täten meidän ei tarvitse enää todistaa aivan kaikkia samoja asioita erikseen polynomeille ja matriiseille.

Määritelmä 2.1. Epätyhjä joukko V on vektoriavaruus laskutoimitusten + ja · suhteen, jos V on suljettu näiden laskutoimitusten suhteen, ts. u+v ∈V

kaikilla u, v ∈ V ja

a·u∈V

kaikilla a ∈ R, u ∈ V

ja seuraavat laskusäännöt ovat voimassa: V1. u + (v + w) = (u + v) + w kaikilla u, v, w ∈ V (assosiatiivisuus), V2. on olemassa sellainen alkio 0 ∈ V , ns. nollavektori, että u + 0 = u = 0 + u kaikilla u ∈ V , V3. jokaista u ∈ V kohti on olemassa −u ∈ V , ns. vektorin u vastavektori, joka toteuttaa ehdon u + (−u) = 0 = (−u) + u, V4. u + v = v + u kaikilla u, v ∈ V (kommutatiivisuus), V5. a · (u + v) = a · u + a · v ja (a + b) · u = a · u + b · u kaikilla a, b ∈ R, u, v ∈ V (distributiivilait), V6. a · (b · u) = (ab) · u kaikilla a, b ∈ R, u ∈ V (skalaarin siirtäminen), V7. 1 · u = u kaikilla u ∈ V . Sanotaan, että kolmikko (V, +, ·) on vektoriavaruus. Joukon V alkioita kutsutaan vektoreiksi ja merkitään u, v, w, x, y, . . . Kertoimina olevia reaalilukuja, a, b, c . . . , sanotaan skalaareiksi. Vektori u + v on vektorien u ja v summa ja a · u on vektorin u skalaarimonikerta.

2.2 n-ulotteinen reaaliavaruus

18

Käytännössä kertomerkki · jätetään usein merkitsemättä ja kirjoitetaan merkinnän a · u sijasta lyhyemmin au. Huomaa, että vektoreiden vähennyslasku voidaan määritellä yhteenlaskulla vastavektorin avulla

u − v = u + (−v) ∈ V.

Esimerkki 2.2. Kaikkien tyyppiä m × n olevien matriisin joukko Mm×n (R)

on vektoriavaruus matriisien yhteenlaskun ja skalaarilla kertomisen suhteen.

Esimerkki 2.3. Olkoon Pn = { p(x) = a0 + a1 x + a2 x2 + · · · + an−1 xn−1 | a0 , . . . , an−1 ∈ R } kaikkien enintään astetta n − 1 olevien polynomien joukko. Kahta polynomia pidetään samoina, jos ja vain jos niiden kaikki kertoimet ovat samoja. Silloin Pn on vektoriavaruus, kun yhteenlasku ja reaaliluvulla kertominen määritellään kuten polynomeille yleensäkin.

Esimerkki 2.4. Olkoon X epätyhjä joukko ja F (X, R) = {f : X → R | f on funktio}. reaaliarvoisten joukon X funktioiden joukko. Silloin F (X, R) on vektoriavaruus, kun funktioiden yhtäsuuruus, summa ja skalaarilla kertominen määritellään tavalliseen tapaan:

f = g : f (x) = g(x) kaikilla x ∈ X , f + g : (f + g)(x) = f (x) + g(x) kaikilla x ∈ X , a · f : (a · f )(x) = a · f (x) kaikilla a ∈ R, x ∈ X . 2.2

n-ulotteinen

reaaliavaruus

Olkoon n jokin positiivinen kokonaisluku. Tyypillisin esimerkki vektoriavaruudesta on järjestettyjen reaalilukujonojen joukko

Rn = {(u1 , u2 , . . . , un ) | u1 , u2 , . . . , un ∈ R} varustettuna seuráavilla laskutoimituksilla: vektoreiden u = (u1 , u2 , . . . , un ) ja v = (v1 , v2 , . . . , vn )summa

u + v = (u1 , u2 , . . . , un ) + (v1 , v2 , . . . , vn ) = (u1 + v1 , u2 + v2 , . . . , un + vn ) ja skalaarilla r ∈ R kertominen yhtälöllä

ru = (ru1 , ru2 , . . . , run ). Lukuja ui kutsutaan vektorin u = (u1 , u2 , . . . , un ) komponenteiksi.

2.3 Aliavaruus Lause 2.5.

Joukko

19

Rn edellisillä laskutoimituksilla on vektoriavaruus.

Joukko Rn todellakin toteuttaa laskusäännöt V1V7, sillä kaikki ominaisuudet palautuvat reaalilukujen ominaisuuksiin. Nollavektori on 0 = (0, 0, . . . , 0). Vektorin u = (u1 , . . . , un ) vastavektori on vektori −u = (−u1 , . . . , −un ). Todistus.

Avaruuden Rn vektoreiden u = (u1 , . . . , un ) ja v = (v1 , . . . , vn ) erotukselle saadaan luonnollinen kaava

u − v = u + (−v) = (u1 − v1 , . . . , un − vn ). sia.

Tästä eteenpäin tarkastellaan reaaliavaruuksia Rn ja niiden ominaisuuk-

2.3

Aliavaruus

Määritelmä 2.6. Jos joukon Rn epätyhjä osajoukko U muodostaa vektoriavaruuden Rn :n operaatioiden + ja · suhteen, niin U on avaruuden Rn aliavaruus.

Aliavaruus on itseasiassa hyvin yksinkertainen käsite, kuten seuraavassa nähdään.

Lause 2.7 (Aliavaruuskriteeri).

U joukon Rn epätyhjä osajoukko. Tällöin U on vektoriavaruuden R aliavaruus jos ja vain jos U on suljettu operaatioiden + ja · suhteen, ts. seuraavat kaksi ehtoa ovat voimassa: Olkoon n

(i) jos

u, v ∈ U , niin u + v ∈ U , ja

(ii) jos

u ∈ U , a ∈ R, niin a · u ∈ U .

Siis U on vektoriavaruus jos ja vain jos se toteuttaa vektoriavaruuden määritelmän alussa olevat ehdot, jotka ovat tarkalleen ehdot (i) ja (ii), sekä ehdot V1V7. Ehdosta (ii) seuraa, että 0 ∈ U , sillä 0 · u = 0 kaikille u ∈ U , joten V2 on voimassa. Ehto V3 seuraa myös kohdasta (ii), sillä (−1)u = −u avaruudessa Rn . Ehdot V1 ja V4V7 voimassa avaruudessa Rn , joten ne ovat voimassa myös joukon U alkioille avaruudessa Rn . Todistus.

Huomautus 2.8. Edellisen lauseen todistuksessa todettiin, että (−1)u =

−u. Tämä yhtälö on itse asiassa yleisesti voimassa on voimassa kaikille vektoriavaruuksille, joissa skalaarit ovat reaalilukuja. Aliavaruuskriteerin avulla on siis yleensä hyvin helppo testata, onko annettu joukko U aliavaruus vai ei.

2.3 Aliavaruus

20

Esimerkki 2.9. Olkoon U = {(a − b, a + 3b) | a, b ∈ R}. Tämä on epätyhjä, sillä esimerkiksi (0, 0) kuuluu siihen. Joukko U on vektoriavaruuden R2 aliavaruus, sillä jos u = (a − b, a + 3b), v = (a0 − b0 , a0 + 3b0 ) ja r ∈ R, niin

u + v = ((a + a0 ) − (b + b0 ), (a + a0 ) + 3(b + b0 )) ∈ U ja

ru = (ra − rb, ra + 3 · rb) ∈ U.

Esimerkki 2.10. Olkoon A m × n-matriisi. Tarkastellaan homogeenisen lineaarisen yhtälöryhmän AX = 0 ratkaisuja. Olkoon HA kaikkien tämän yhtälöryhmän ratkaisujen joukko, ts. HA = {u | AuT = 0} ⊆ Rn . Osoitetaan, että HA on avaruuden Rn aliavaruus. Selvästi HA ei ole tyhjä joukko, sillä yhtälöryhmällä on triviaaliratkaisu 0n ∈ HA . Nyt jos X1 , X2 ∈ HA ja r ∈ R, niin

A(XT1 + XT2 ) = AXT1 + AXT2 = 0 + 0 = 0 ja

A(rXT1 ) = rAXT1 = r0 = 0,

joten X1 + X2 ∈ HA ja rX1 ∈ HA . Huomaa, että vaakavektorin transpoosin avulla vektorit voidaan esittää pystyvektoreina. Avaruutta HA kutsutaan matriisin A nolla-avaruudeksi.

Esimerkki 2.11. Joukot {0} ja Rn ovat avaruuden Rn aliavaruuksia. Niitä kutsutaan Rn :n triviaaleiksi aliavaruuksiksi. Esimerkki 2.12. Olkoon U = {(a, b, c) | a, b, c ∈ R, a + b + c < 0}. Osoitetaan aliavaruuskriteerin avulla, että U ei ole avaruuden R3 aliavaruus.

Esimerkki 2.13. Olkoon A m × n-matriisi ja Y ∈ Rm , Y 6= 0. Muodosta-

vatko (epähomogeenisen) lineaarisen yhtälöryhmän

AX = YT ratkaisut avaruuden Rn aliavaruuden?

2.4 Lineaarikombinaatio 2.4

21

Lineaarikombinaatio

Vektoriavaruuden määritelmä takaa sen, että jos u1 , . . . , uk ∈ Rn ja a1 , . . . , ak ∈ R, niin myös a1 u1 + . . . + ak uk ∈ Rn .

Määritelmä 2.14. Vektori v ∈ Rn on vektoreiden u1 , . . . , uk lineaarikombinaatio, jos on olemassa sellaiset reaaliluvut a1 , . . . , ak , että v = a1 u1 + · · · + ak uk . Kaikkien vektoreiden u1 , . . . , uk lineaarikombinaatioiden joukko on

L(u1 , . . . , uk ) = { a1 u1 + · · · + ak uk | a1 , . . . , ak ∈ R}.

Esimerkki 2.15. Vektori (2, 1, 5) on vektoreiden (1, 2, 1), (1, 0, 2) ja (1, 1, 0) lineaarikombinaatio, sillä

(2, 1, 5) = x1 (1, 2, 1) + x2 (1, 0, 2) + x3 (1, 1, 0) toteutuu, jos ja vain jos yhtälöllä

(2, 1, 5) = (x1 + x2 + x3 , 2x1 + x3 , x1 + 2x2 ), toisin sanoen yhtälöryhmällä   x1 + x2 + x3 = 2 2x1 + x3 = 1  x1 + 2x2 = 5 on ratkaisu. Laskemalla löydetään ratkaisu x1 = 1, x2 = 2, x3 = −1. Siis (2, 1, 5) ∈ L((1, 2, 1), (1, 0, 2), (1, 1, 0)).

Lause 2.16.

u1 , . . . , uk ovat avaruuden Rn vektoreita, niin niiden n lineaarikombinaatioiden joukko L(u1 , . . . , uk ) on avaruuden R aliavaruus. Kun

Lause todistetaan aliavaruuskriteerin avulla. Joukko L(u1 , . . . , uk ) ei ole tyhjä, sillä nollavektori 0 = 0u1 + · · · + 0uk ∈ L(u1 , . . . , uk ). Olkoon r ∈ R ja u, v ∈ L(u1 , . . . , uk ), sanotaan u = a1 u1 + · · · + ak uk ja v = b1 u1 + · · · + bk uk . Nyt

Todistus.

u + v = (a1 + b1 )u1 + · · · + (ak + bk )uk , ja

ru = ra1 u1 + · · · + rak uk , joten u + v ja ru kuuluvat myös joukkoon L(u1 , . . . , uk ).

2.4 Lineaarikombinaatio

22

Annettu vektorijoukko generoi siis aina jonkin Rn :n aliavaruuden, joka voi mahdollisesti olla myös koko avaruus Rn . Jos tosiaan L(u1 , . . . , uk ) = Rn , sanotaan, että vektorit u1 , . . . , uk generoivat vektoriavaruuden Rn .

Esimerkki 2.17. Tutkitaan, generoivatko edellisen esimerkin vektorit (1, 2, 1),

(1, 0, 2) ja (1, 1, 0) koko vektoriavaruuden R3 . Olkoon (a, b, c) ∈ R3 mielivaltainen. On siis tutkittava, löytyykö sellaiset luvut x1 , x2 ja x3 , että (a, b, c) = x1 (1, 2, 1) + x2 (1, 0, 2) + x3 (1, 1, 0). Tämä on yhtäpitävä yhtälöryhmän   x1 + x2 + x3 = a 2x1 + x3 = b  x1 + 2x2 = c kanssa. Kertomalla ensimmäinen yhtälö luvulla -2, toinen luvulla 2, kolmas luvulla 1 ja laskemalla saadut yhtälöt yhteen saadaan

x1 =

−2a + 2b + c . 3

Vastaavasti saadaan

x2 =

a−b+c , 3

x3 =

4a − b − 2c . 3

Näin vektorit siis generoivat koko vektoriavaruuden R3 . Olkoon v avaruuden Rk vektori. Vektori v = (v1 , . . . , vk ) voidaan ajatella 1 × k matriisina
v1 v2 · · · vk . Luonnollisesti vektorin transpoosilla vT tarkoitetaan k × 1 matriisia   v1  v2    vT =  .  .  .. 

vk Matriisia vT kutsutaan myös pystyvektoriksi. Merkitään (u1 | u2 | · · · | uk ):lla n × k matriisia, jonka pystyriveinä ovat vektorit u1 , . . . , uk . Pystyviivoja | ei siis esiinny auki kirjoitetussa matriisissa. Olkoon A = (u1 | u2 | · · · | uk ). Edellisten esimerkkien mukaisesti siis v ∈ Rn on vektoreiden u1 , . . . , uk lineaarikombibaatio jos ja vain jos yhtälöllä

AX = (u1 | u2 | · · · | uk )X = v

2.4 Lineaarikombinaatio

23

on ratkaisu. Selvästi, jos vektori XT = (x1 , . . . , xk ) on tämän yhtälöryhmän ratkaisu, niin v = x1 u1 + · · · + xk uk . Toisaalta, lineaarikombinaatioiden joukko L(u1 , . . . , uk ) voidaan esittää matriisitulojen joukkona

L(u1 , . . . , uk ) = { x1 u1 + · · · + xk uk | x1 , . . . , xk ∈ R} = {AxT | x ∈ Rk }. Tässä siis vektori x käy läpi kaikki avaruuden Rk vektorit, ts. vektori x = (x1 , x2 , . . . , xk ) ∈ Rk kun x1 , . . . , xk ∈ R.

Esimerkki 2.18. Edellisen perusteella

Matlabilla kysymykseen onko vek-

tori joidenkin vektoreiden lineaarikombinaatio voidaan ratkaista ratkaisemalla edellä mainittu yhtälöryhmä. Onko v = (2, 3, 1, 1, 4) vektoreiden u1 = (2, 5, −3, −9, −8), u2 = (5, −7, −2, −4, 9) ja u3 = (1, 6, −5, −3, 0) lineaarikombinaatio?

>> U1=[2 5 -3 -9 -8] U2=[5 -7 -2 -4 9] U3=[1 6 -5 -3 0] U1 = 2

5

-3

-9

-8

5

-7

-2

-4

9

6

-5

-3

0

1

1

4

U2 =

U3 = 1

>> V=[2 3 1 1 4] V = 2

3

>> linsolve([U1' U2' U3'],V') ans =

2.4 Lineaarikombinaatio

24

-715/2126 195/4039 1247/2354 Kaikki linsolve komennolla ratkaistut yhtälöryhmät tulee tarkistaa, koska komennon yksi ominaisuus on, että se etsii ratkaisua likiarvotekniikoilla. Esimerkiksi tässä tapauksessa saatu ratkaisu on väärä, nimittäin redusoitu porramuoto yhtälöryhmän matriiisista (u1 | u2 | u3 | v) antaa

>> rref([U1' U2' U3' V']) ans = 1 0 0 0 0

0 1 0 0 0

0 0 1 0 0

0 0 0 1 0

mistä nähdään, ettei yhtälöryhmällä ole ratkaisua.

Määritelmä 2.19. Vektoreita e1 = (1, 0, 0, . . . , 0), e2 = (0, 1, 0, . . . , 0), .. . en = (0, 0, 0, . . . , 1) kutsutaan vektoriavaruuden Rn perusvektoreiksi. On selvää, että

L(e1 , . . . , en ) = Rn , Vektoriavaruuden R3 tapauksessa merkitään usein  vaikkakaan ei tällä kurssilla  i = (1, 0, 0), j = (0, 1, 0), k = (0, 0, 1).

Lause 2.20. niin

Jos vektorit

u1 , . . . ,uk ∈ Rn generoivat vektoriavaruuden Rn ,

k ≥ n.

Tehdään vastaoletus, että vektorit u1 , . . . ,uk generoivat avaruuden R ja k < n. Määritellään n × n matriisi U = (u1 | u2 | · · · | uk | 0 | · · · | 0), missä nollapystyrivejä on luonnollisesti n − k kappaletta. Koska L(u1 , . . . , uk ,0,. . . ,0) = Rn , niin kullekin vektorille ei on olemassa pystyvektori vi ∈ Rn , jolle Uvi = eTi . Todistus. n

2.5 Lineaarinen riippumattomuus

25

Olkoon matriisi B = (v1 | v2 | · · · | vn ), niin saadaan, että

UB = (e1 | e2 | · · · | en ) = I. Lauseen 1.36 nojalla matriisilla U on kääntyvä. Tämä on kuitenkin mahdotonta, koska matriisissa U on ainakin yksi nollista koostuva pystyrivi, kun k < n (ks. esimerkki 1.23.) Vastaoletus johti siis ristiriitaan, ja väite seuraa tästä. 2.5

Lineaarinen riippumattomuus

Määritelmä 2.21. Vektorit u1 , . . . , uk ∈ Rn ovat lineaarisesti riippumattomia, jos yhtälöllä x1 u1 + · · · + xk uk = 0

(1)

on vain triviaali ratkaisu x1 = · · · = xk = 0. Tällöin sanotaan myös, että joukko {u1 , . . . , uk } on lineaarisesti riippumaton. Jos yhtälöllä taas (1) on jokin epätriviaali ratkaisu (jokin xi 6= 0), niin vektorit ovat lineaarisesti riippuvia ja sanotaan, että joukko {u1 , . . . , uk } on lineaarisesti riippuva.

Esimerkki 2.22. Vektorit (2, 0, 1, 4), (3, −1, 0, 0), (−5, 3, 2, 8) ∈ R4 ovat

lineaarisesti riippuvia, sillä

2(2, 0, 1, 4) − 3(3, −1, 0, 0) − (−5, 3, 2, 8) = (0, 0, 0, 0).

Lause 2.23.

Vektorit

u1 , . . . , uk ovat lineaarisesti riippuvia, jos ja vain jos

niistä jokin voidaan esittää muiden lineaarikombinaationa. Todistus. Oletetaan ensin, että vektorit ovat lineaarisesti riippuvia. Yhtälöllä (1) on siis jokin epätriviaalu ratkaisu

t1 u1 + . . . + tk uk = 0, missä jokin kerroin, esim. ti 6= 0. Silloin ui voidaan esittää muiden lineaarikombinaationa:

ui = −

t1 ti−1 ti+1 tk u1 − . . . − ui−1 − ui+1 . . . − uk . ti ti ti ti

Oletetaan nyt, että jokin vektoreista, esim. ui on muiden lineaarikombinaatio, siis on olemassa luvut a1 , a2 , . . . , ai−1 , ai+1 , . . . , ak , joille

ui = a1 u1 + . . . + ai−1 ui−1 + ai+1 ui+1 + . . . + ak uk . Tällöin

a1 u1 + . . . + ai−1 ui−1 + (−1)ui + ai+1 ui+1 + . . . + ak uk = 0, joten vektorit ovat lineaarisesti riippuvia.

2.5 Lineaarinen riippumattomuus

26

Esimerkki 2.24. Vektorit (1, 0, 0), (0, 1, 0), (0, 0, 0) ovat lineaarisesti riippuvia. Kuitenkaan vektoria (1, 0, 0) ei voida esittää kahden muun vektorin (0, 1, 0) ja (0, 0, 0) lineaarikombinaationa. Edellinen lause on kuitenkin (tietysti) voimassa, mutta tässä tapauksessa vain yksi vektoreista, nimittäin (0, 0, 0) voidaan esittää kahden muun lineaarikombinaationa. Merkitään yhtälössä (1) vektoria ui = (u1i , . . . , uni ) kaikilla i = 1, . . . , k . Kun tarkastellaan yhtälöä koordinaateittain saadaan lineaarinen homogeeninen yhtälöryhmä    u11 x1 + u12 x2 + . . . + u1k xk = 0   u21 x1 + u22 x2 + . . . + u2k xk = 0 (2) ..  .    un1 x1 + un2 x2 + . . . + unk xk = 0 Tämä yhtälöryhmä voidaan kirjoittaa matriisimuotoon   x1  x2    (u1 | u2 | · · · | uk )  .  = 0. .  . 

xk

Lause 2.25.

Oletetaan, että

1. Jos vektorit

u1 , . . . , uk ∈ R n .

u1 , . . . ,uk ovat lineaarisesti riippumattomia, niin k ≤ n.

2. Vektorit

u1 , . . . ,uk ovat lineaarisesti riippumattomia jos ja vain jos (u1 | u2 | · · · | uk ) voidaan elementaarisilla vaakarivioperaatioilla muuntaa RPM:ksi, jossa on k porrasta.

matriisi

Todistus. Ensimmäinen väite seuraa lauseesta 1.19, sillä tapauksessa k > n yhtälöryhmällä (2) olisi epätriviaali ratkaisu. Toinen väite seuraa siitä, että jos vektorit ovat lineaarisesti riippumattomia, on yhtälöryhmällä (2) vain triviaali ratkaisu. Yhtälöryhmällä (2) on vain triviaali ratkaisu jos ja vain jos se voidaan Gaussin menetelmällä muuntaa yhtälöryhmäksi  x1 = 0     x2 = 0     ..   . 

          

xk = 0 0 = 0 .. . 0 = 0

2.5 Lineaarinen riippumattomuus

27

Tämä taas on tosi jos ja vain jos elementaarisilla vaakarivioperaatioilla saadaan   1 0 ··· 0  0 1 ··· 0      ..   .    0 1  (u1 | u2 | · · · | uk ) ∼  0 0 .  0 0 0 0      ..   .

0 0

Seuraus 2.26.

0 0

u1 , . . . , un ∈ Rn . Joukko {u1 , . . . , un } on lineaarisesti riippumaton, jos ja vain jos matriisi (u1 | · · · | un ) on kääntyvä eli det(u1 | · · · | un ) 6= 0. Olkoon

Edellisen lauseen mukaan joukko {u1 , . . . , un } on lineaarisesti riippumaton, jos ja vain jos matriisi A = (u1 | · · · | un ) voidaan muuttaa elementaarisilla vaakarivioperaatioilla identiteettimatriisiksi (k = n). Lauseen 1.26 mukaan tämä pitää paikkaansa jos ja vain jos matriisi A on kääntyvä. Lauseen 1.34 mukaan A on kääntyvä jos ja vain jos det(A) 6= 0.

Todistus.

Joukon {u1 , . . . , uk } lineaarisen riippumattomuuden tarkistaminen onnistuu siis muuntamalla matriisi (u1 | · · · | uk ) RPM:ksi ja katsomalla onko näin saadussa matriisissa portaita k kappaletta. Jos k = n, niin riittää laskea det(u1 | · · · | un ).

Esimerkki 2.27. Ovatko vektorit (2, 5, −3, −9, −8), (5, −7, −2, −4, 9),

(1, 6, −5, −3, 0) ja (1, 0, 0, −1, 1) lineaarisesti riippumattomia? Edellisen perusteella ratkaisu löytyy illa kahdella eritavalla, joko käyttämällä null-komentoa yhtälöryhmän (2) ratkaisujen etsimiseksi tai rref-komennolla lauseen 2.25 kohdan 2 mukaisesti.

Matlab

>> U1=[2 5 -3 -9 -8] U2=[5 -7 -2 -4 9] U3=[1 6 -5 -3 0] U4=[1 0 0 -1 1] null([U1' U2' U3' U4'],'r') . . . ans = Empty matrix: 4-by-0

2.6 Vektoriavaruuden kanta

28

>> rref([U1' U2' U3' U4']) ans = 1 0 0 0 0

0 1 0 0 0

0 0 1 0 0

0 0 0 1 0

Molemmilla tavoilla huomataan, että vektorit ovat lineaarisesti riippumattomia. 2.6

Vektoriavaruuden kanta

Määritelmä 2.28. Olkoon V jokin avaruuden Rn aliavaruus. Joukko B = {u1 , . . . , uk } ⊆ V muodostaa vektoriavaruuden V kannan, jos jokainen vektori v ∈ V voidaan esittää tarkalleen yhdellä tavalla vektoreiden u1 , . . . , uk lineaarikombinaationa

v = a1 u1 + . . . + ak uk . Kertoimia ai sanotaan vektorin v koordinaateiksi kannan B suhteen. Vektorin v koordinaattiesitys kannan B suhteen on vB = (a1 , . . . , ak ).

Esimerkki 2.29. Vektoriavaruuden Rn perusvektorien joukko E = {e1 , . . . , en } muodostaa vektoriavaruuden Rn luonnollisen kannan. Esimerkki 2.30. Vektorijoukko {(1, 2, 1), (1, 0, 2), (1, 1, 0)} muodostaa vek-

toriavaruuden R3 kannan esimerkin 2.17 laskun mukaan.

Lause 2.31.

V jokin avaruuden Rn aliavaruus. Joukko {u1 , . . . , uk } ⊆ V muodostaa vektoriavaruuden V kannan, jos ja vain jos Olkoon

1.

{u1 , . . . , uk } on lineaarisesti riippumaton, ja

2.

L(u1 , . . . , uk ) = V .

Oletetaan, ensin, että vektorit u1 , . . . , uk ∈ Rn muodostavat vektoriavaruuden V kannan. Määritelmän mukaan jokaisella vektorilla v ∈ V on tarkalleen yksi esitysmuoto

Todistus.

v = a1 u1 + · · · + ak uk , missä a1 , . . . , ak ∈ R. Siis kaikilla v ∈ V , v ∈ L(u1 , . . . , uk ) eli V ⊆ L(u1 , . . . , uk ). Toisaalta, L(u1 , . . . , uk ) ⊆ V , koska vektorit ui ∈ V ja V

2.6 Vektoriavaruuden kanta

29

on avaruuden Rn aliavaruus, joten aliavaruuskriteerin mukaan kaikki vektoreiden u1 , . . . , uk lineaarikombinaatiot kuuluvat avaruuteen V . Siis V = L(u1 , . . . , uk ), joten ehto 2 on voimassa. Osoitetaan vielä, että ehto 1 on voimassa. Kannan määritelmän mukaan myös nollavektorilla on vain yksi esitys

0 = 0u1 + · · · + 0uk . Yhtälö x1 u1 + · · · + xk uk = 0 on siis tarkalleen yksi ratkaisu, joten sen täytyy olla x1 = 0, . . . , xk = 0. Täten vektorit u1 , . . . , uk ovat lineaarisesti riippumattomia. Oletetaan nyt, että vektorit u1 , . . . , uk ovat lineaarisesti riippumattomia ja generoivat vektoriavaruuden V , eli että ehdot 1 ja 2 ovat voimassa. Osoitetaan, että {u1 , . . . , uk } on avaruuden V kanta. Ehdosta 2 seuraa, että jokaisella vektorilla v ∈ V on ainakin jokin esitys muodossa v = a1 u1 + · · · + ak uk . (3) Jotta vektorit u1 , . . . , uk muodostaisivat kannan, tämän esityksen on oltava ainoa. Oletetaan, että jollakin v on olemassa myös toinen esitys, sanotaan

v = a01 u1 + · · · + a0k uk .

(4)

Kun vähennetään yhtälö (4) puolittain yhtälöstä (4), saadaan

0 = (a1 − a01 )u1 + · · · + (ak − a0k )uk . Koska vektorit u1 , . . . , uk ovat lineaarisesti riippumattomia, on a1 − a01 = 0, . . . , ak −a0k = 0. Siis a1 = a01 , . . . , ak = a0k , ja v on vain yksi esitys ja vektorit u1 , . . . , uk muodostavat avaruuden V kannan. Seuraavan lauseen mukaan avaruuden V kannassa on suurin mahdollinen määrä lineaarisesti riippumattomia avaruuden V vektoreita.

Lause 2.32.

Rn aliavaruudella V on kanta {u1 , . . . , um }, niin mitkä tahansa k > m vektoria avaruudesta V ovat lineaarisesti riippuJos avaruuden

via.

Olkoot v1 , . . . , vk ∈ V mitkä tahansa k > m vektoria. Jokainen niistä (j = 1, . . . , k ) voidaan kirjoittaa muodossa Todistus.

vj = a1j u1 + a2j u2 + · · · + amj um . Yhtälö

x1 v1 + x2 v2 + . . . + xk vk = 0

2.6 Vektoriavaruuden kanta

30

on yhtäpitävä yhtälöryhmän    a11 x1 + a12 x2 + . . . + a1k xk = 0   a21 x1 + a22 x2 + . . . + a2k xk = 0 ..  .    am1 x1 + am2 x2 + . . . + amk xk = 0 kanssa. Tämä on homogeeninen lineaarinen yhtälöryhmä, jossa on vähemmän yhtälöitä kuin tuntemattomia (k > m, joten sillä on lauseen 1.19 nojalla myös ei-triviaali ratkaisu (x1 , . . . , xk ). Näin vektorit v1 , . . . , vk ovat lineaarisesti riippuvia. Avaruuden Rn luonnollisessa kannassa on n vektoria. Näin ollen mitkä tahansa k > n avaruuden Rn vektoria ovat lineaarisesti riippuvia.

Lause 2.33. udella

Jos

V on avaruuden Rn aliavaruus (jollakin n), niin avaru-

V on kanta.

Olkoon V avaruuden Rn aliavaruus. Jos V = {0}, sovitaan, että sillä on kantana tyhjä joukko. Oletetaan, että V 6= {0}. Koska V on avaruuden Rn aliavaruus, niin edellisen lauseen mukaan se voi sisältää korkeintaan n lineaarisesti riippumatonta vektoria. Olkoon B = {u1 , . . . , um } suurin mahdollinen (maksimaalinen) joukko lineaarisesti riippumattomia avaruuden V vektoreita. Osoitetaan, että V = L(B), jolloin lauseen 2.31 mukaan B on avaruuden V kanta. Jos V 6= L(B), niin on olemassa v ∈ V , v ∈ / L(B). Osoitetaan, että joukko {u1 , . . . , um , v} on tällöin lineaarisesti riippumaton, mikä on ristiriidassa joukon B maksimaalisuuden kanssa. Jos {u1 , . . . , um , v} on lineaarisesti riippuva, niin yhtälöllä Todistus.

x1 u1 + · · · + xm um + yv = 0 on epätriviaali ratkaisu. Jos y = 0, niin joukko {u1 , . . . , um } on lineaarisesti riippuva, mikä on vastoin oletusta. Siis y 6= 0, joten

v=−

x1 xm u1 + · · · − um y y

ja siis v ∈ L(u1 , . . . , um ), mikä on vastoin oletusta. Siis välttämättä joukko {u1 , . . . , um , v} on lineaarisesti riippumaton, mutta tällöin joukko {u1 , . . . , um } ei ole suurin lineaarisesti riippumaton joukko. Näin ollen ei voi olla olemassa vektoria v ∈ V , v ∈ / L(u1 , . . . , um ). Siis V = L(u1 , . . . , um ). ta.

Itseasiassa edellisen lauseen todistus antaa tavan etsiä avaruudelle V kan-

2.6 Vektoriavaruuden kanta Seuraus 2.34.

31

V avaruuden Rn aliavaruus. Suurin mahdollinen lineaarisesti riippumaton joukko avaruuden V vektoreita on sen kanta. Olkoon

Kuten edellä huomattiin, vektoriavaruuden kanta ei ole yksikäsitteinen. Esim. avaruudella R3 on luonnollinen kanta {e1 , e2 , e3 } ja esimerkin 2.30 kanta {(1, 2, 1), (1, 0, 2), (1, 1, 0)}. Kuitenkin kaikissa vektoriavaruuden kannoissa on sama määrä vektoreita.

Lause 2.35.

Olkoon

V avaruuden Rn aliavaruus. Jokaisessa aliavaruuden

V kannassa on yhtä monta vektoria. Jos vektoriavaruudella olisi kaksi kantaa, joista toisessa olisi m vektoria ja toisessa n vektoria, ja jos m > n, niin edelliset m vektoria olisivat lineaarisesti riippuvia lauseen 2.32 nojalla, eivätkä siis muodostaisi kantaa. Todistus.

Määritelmä 2.36. Avaruuden Rn aliavaruuden V kannan alkioiden lukumäärää

- joka on siis kannan valinnasta riippumaton - sanotaan vektoriavaruuden V dimensioksi. Jos vektoriavaruuden V kannassa on n vektoria, merkitään dim(V ) = n. Erityisesti dim(Rn ) = n. Seuraava lause voidaan todistaa seurausten 2.34 ja 2.26 avulla.

Lause 2.37.

u1 , . . . , un muodostavat vektoriavaruuden Rn kannan, jos ja vain jos matriisi (u1 | · · · | un ) on kääntyvä. Vektorit

Esimerkki 2.38. Esitetään vektorin (3, −1, 2) koordinaatit kannan B = {(1, 0, 1), (2, 1, 0), (−1, 0, 2)} suhteen. Yhtälöstä (3, −1, 2) = a1 (1, 0, 1) + a2 (2, 1, 0) + a3 (−1, 0, 2) saadaan lineaarinen yhtälöryhmä  3  a1 + 2a2 −a3 = a2 = −1 .  a1 +2a3 = 2 Ratkaistaan yhtälöryhmä Gaussin eliminointimenetelmällä, jolloin     1 2 −1 3 1 0 0 4  0 1 0 −1  ∼  0 1 0 −1  . 1 0 2 2 0 0 1 −1 Siispä a1 = 4, a2 = a3 = −1 ja (3, −1, 2)B = (4, −1, −1). illa sama onnistuu taas linsolve tai rref-komennoilla:

Matlab

2.6 Vektoriavaruuden kanta

32

>> B=[1 2 -1;0 1 0;1 0 2] V=[3;-1 ;2] linsolve(B,V) . . . ans = 4 -1 -1 >> rref([B V]) ans = 1 0 0

0 1 0

0 0 1

4 -1 -1

Yleisesti siis vektorin v ∈ Rn esitys kannan B = {u1 , . . . , un } suhteen etsitään seuraavasti. Matriisi

(u1 | u2 | · · · | un | v). muunnetaan matriisi elementaarisilla vaakarivioperaatioilla matriisiksi

( I | vB ). Silloin viimeinen pystyrivi on vektorin v esitys kannan B suhteen. Alkuun tulee aina identiteettimatriisi I, sillä matriisi (u1 | u2 | · · · | un ) on säännöllinen lauseen 2.37 mukaan.

Esimerkki 2.39. Jos V on vektoriavaruuden Rn aliavaruus, niin dim(V ) ≤

dim(Rn ) = n. Minkälaisia ovat vektoriavaruuden R3 aliavaruudet joiden dimensio on 1? Entä aliavaruudet joiden dimensio on 2?

Esimerkki 2.40. Etsi matriisin 

 3 −2 1 1 2 −1 0 A = 0 1 −1 4 2 2 −1 0 0 −2 1

2.7 Matriisin aste

33

nolla-avaruuden HA kanta. Nolla-avaruus on siis homogeenisen lineaarisen yhtälöryhmän   3x1 −2x2 +x3 +x4 +2x5 −x6 = 0 x2 −x3 +4x4 +2x5 = 0  2x1 −x2 −2x5 +x6 = 0 ratkaisujen muodostama avaruus. Kuten ensimmäisessä luvussa mainittiin, matriisin A nolla-avaruuden kanta saadaan issa suoraan komennolla null(A,'r'). Siis

Matlab

>> A=[3 -2 1 1 2 -1;0 1 -1 4 2 0;2 -1 0 0 -2 1 ] null(A,'r') . . . ans = -5 -10 -6 1 0 0

-6 -14 -12 0 1 0

2 5 5 0 0 1

joten

HA = L((−5. − 10, −6, 1, 0, 0), (−6, −14, −12, 0, 1, 0), (2, 5, 5, 0, 0, 1)) missä generoivat vektorit muodostavat avaruuden kannan. 2.7

Matriisin aste

Edellä osoitetiin, että kaikilla vektoriavaruuden Rn aliavaruuksilla on kanta. Mutta miten aliavaruuden V kanta löydetään? Oletetaan, että V = L(u1 , . . . , um ) ja halutaan etsiä sille kanta. Seurauksen 2.34 mukaan riittää etsiä suurin mahdollinen lineaarisesti riippumaton joukko avaruuden V vektoreita Tämä voi käytännössä olla hankalaa. Tarkastellaan siis generoivaa joukkoa {u1 , . . . , um }. Jos se on lineaarisesti riippumaton, niin se on selvästi avaruuden V kanta. Jos generoiva joukko taas ei ole lineaarisesti riippumaton, niin lauseen 2.23 mukaan jokin sen vektoreista, sanotaan uj , on muiden lineaarikombinaatio, joten uj voidaan pudottaa pois, ja jäljelle jääneet vektorit generoivat edelleen avaruuden V . Kun jatketaan samalla tavalla, kunnes jäljellä on lineaarisesti riippumaton

2.7 Matriisin aste

34

joukko, löydetään selvästi avaruuden V kanta. Käytännössä sen vektorin, joka on muiden lineaarikombinaatio, löytäminen voi olla työlästä. On olemassa myös elementaarisia vaakarivioperaatioita käyttävä tapa etsiä avaruuden V kanta. Määritellään aluksi muutama matriiseihin liittyvä käsite.

Määritelmä 2.41. Olkooon A m × n-matriisi, jonka vaakariveinä ovat vektorit u1 , . . . , um ∈ Rn . Merkitään

 u1   A =  ...  . um 

Matriisin A vaakariviavaruus on Rn aliavaruus VA = L(u1 , . . . , um ). Matriisin A aste rA = dim(VA ), ts. matriisin aste on sen vaakariviavaruuden dimensio.

Esimerkki 2.42. Lemma 2.43.

1

Matlabilla matriisin A aste löytyy komennolla rank(A).

Jos

A ∼ B (siis matriisi B saadaan matriisista A elementaarisilla vaakarivioperaatioilla), niin VA = VB ja siis tietysti rA = rB . Todistetaan väite, kun B saadaan matriisista yhden elementaarisen vaakarioperaation avulla, väite seuraa tästä. Olkoon A m × n-matriisi, jonka vaakariveinä ovat vektorit u1 , . . . , um ∈ n R . On selvää, että jos B saadaan matriisista A vaihtamalla kahden vaakarivin paikka, se ei muuta matriisin vaakariviavaruutta mitenkään. Jos taas jokin vaakarivi, sanotaan uj on kerrottu luvulla c 6= 0, niin Todistus.

VA = {a1 u1 + · · · + aj uj + · · · + am um | ai ∈ R} = {a1 u1 + · · · + aj cuj + · · · + am um | ai ∈ R} = VB . Oletetaan nyt, että matriisin B jokin vaakarivi on saatu kun matriisin A samaan vaakariviin on lisätty sen toinen vaakarivi kerrottuna vakiolla c. Kuten edellä mainittiin, matriisin vaakarivien järjestys ei vaikuta vaakariviavaruuteen, joten voidaan olettaa, että matriisin A ensimmäiseen vaakariviin on lisätty cui . Nyt

VB = {a1 (u1 + cui ) + · · · + ai (ui ) + · · · + am um | ai ∈ R} = {a1 u1 + · · · + (ai + a1 c)ui + · · · + am um | ai ∈ R} = VA , koska (ai + a1 c) käy läpi kaikki reaaliluvut jokaiselle luvulle a1 . Siis vaakariviavaruus säilyy kun matriisia muunnetaan elementaarisilla vaakarivioperaatioilla. Väite seuraa tästä. 1

Lemma eli apulause.

2.7 Matriisin aste

35

Seuraus 2.44.

Jos A m × n-matriisi ja C redusoitu porrasmatisiisi, jolle A ∼ C, niin VA = VC .

Lemma 2.45.

Olkoon

eroavat vaakarivit ovat

C m × n redusoitu porrasmatriisi, jonka nollasta u1 , . . . , uk . Silloin rC = k ja u1 , . . . , uk on avaruuden

VC kanta. Todistus. Jos u1 , . . . , uk on lineaarisesti riippumaton joukko, niin molemmat väitteet tulee todistettu. Nimittäin, u1 , . . . , uk triviaalisti generoi VC , joten se on avaruuden VC kanta jos ja vain jos se on lineaarisesti riippumaton. Tällöin rC = dim(VC ) = k . Tarkastellaan yhtälön

0 = x1 u1 + · · · + xk uk

(5)

ratkaisuja. Jokainen vektoreista u1 , . . . , uk sisältää kompponentin, jossa on ns. johtava ykkönen. Muissa vektoreissa vastaava komponentti on 0. Siis jos xi 6= 0, niin vektorin ui johtavan ykkösen mukainen komponentti summassa x1 u1 +· · ·+xk uk on xi . Näin ollen yhtälöllä (5) ei ole epätriviaalia ratkaisua, joten vektorit ovat lineaarisesti riippumattomia. Edellisen lauseen mukaan siis avaruuden V = L(u1 , . . . , um ) dimensio ja kanta voi etsiä seuraavalla tavalla: Kirjoitetaan vektorit u1 , . . . , uk matriisiksi   u1  ..   . ,

um joka muunnetaan redusoiduksi porrasmatriisiksi   v1  ..   .     vk     0 ,    ..   . 

0 missä nollasta erovata vektorit vi (0 ≤ k ≤ m) muodostavat avaruuden V kannan. Huomaa, että jos vektorit u1 , . . . , um ovat lineaarisesti riippumattomia, niin k = m. Näin ollen yllä oleva menetelmä sopii myös lineaarisen riippumattomuuden tarkasteluun. Lauseen 2.25 mukaan lineaarinen riippumattomuus voitiin todeta kirjoittamalla vektorit matriisiin pystyriveiksi ja suorittamalla vastaava prosessi. Miksi pysty- ja vaakarivi menetelmät molemmat toimivat lineaarisen riippumattomuuden määräämiseen? Syy näkyy seuraavasta lauseesta.

2.7 Matriisin aste Lause 2.46. Todistus.

Olkoon

36

A m × n-matriisi. Silloin rA = rAT .

Sivuutetaan.

Huomaa kuitenkin, että pystyrivi menetelmä

Esimerkki 2.47 (Kanta

Matlab

ei sovellu kannan etsimiseen!

illa). Etsitään aluksi vektoreiden avaruuden U = L((1, 0, 0, 0, 1), (1, 0, 1, 0, 1), (1, 0, 0, 0, 1), (1, 0, 1, 0, 0), (0, 1, 1, 1, 1), (1, 1, 0, 1, 1), (1, 1, 1, 1, 1) jokin kanta. Kirjoitetaan vektorit matriisn A vaakariveiksi ja muunnetaan redusoiduksi porrasmatriisiksi.

>> A=[1 0 0 0 1;1 0 1 0 1; 1 0 0 0 1; 1 0 1 0 0; 0 1 1 1 1; 1 1 0 1 1;1 1 1 1 1] rref(A) . . . ans = 1 0 0 0 0 0 0

0 1 0 0 0 0 0

0 0 1 0 0 0 0

0 1 0 0 0 0 0

0 0 0 1 0 0 0

Avaruuden U kannaksi saadaan siis

B = {(1, 0, 0, 0, 0), (0, 1, 0, 1, 0), (0, 0, 1, 0, 0), (0, 0, 0, 0, 1)} Entä mitkä alkuperäisen joukon vektoreista muodostavat avaruuden U kannan? Tämä saadaan selville etsimällä johtaviern ykkösten paikat matriisin AT kanssa ekvivalentista RPM:sta, koska matriisin vaaka- ja pystyriviavaruuksien dimensio on sama jaelementaarisissa vaakarivi muunnoksissa pystyrivit eivät vaihdapaikkaa. Siis muunnetaan AT RPM:ksi ja katsotaan millä pystyriveille tulee johtava ykkönen. Näitä pystyrivejä vastaavat vektorit muodostavat avaruuden U kannan. in rref palauttaa vektorin, jossa on listattuna johtavien ykkösten pystyrivit RPM:ssä. Seuraavassa se luetaan muuttujaan pivot.

Matlab

>>D=A' [B,pivot]=rref(D) B =

2.8 Kannanvaihto 1 0 0 0 0

0 1 0 0 0

1 0 0 0 0

0 0 1 0 0

0 0 0 1 0

2 -2 1 1 0

37 1 -1 1 1 0

pivot = 1

2

4

5

Nyt johtavien ykkösten vektorit saadaan tulostettua komennolla

>> >> D(:,pivot)' ans = 1 1 1 0

0 0 0 1

0 1 1 1

0 0 0 1

1 1 0 1

Nämä ovat siis alkuperäisen generaattori joukon vektorit

C = {(1, 0, 0, 0, 1), (1, 0, 1, 0, 1), (1, 0, 1, 0, 0), (0, 1, 1, 1, 1)}. 2.8

Kannanvaihto

Olkoon V jokin avaruuden Rm aliavaruus. Tiedetään vektoriavaruuden V kaksi kantaa: B = {v1 , . . . , vn } ja C = {w1 , . . . , wn }. Jos tiedetään vektorin x koordinaatit kannan B suhteen, miten voidaan laskea sen koordinaatit kannan C suhteen?

Esimerkki 2.48. Tarkastellaan avaruutta R3 ja kahta sen kantaa B = {v1 , v2 , v3 } ja C = {w1 , w2 , w3 }. Vektori x ∈ R3 voidaan esittää yksikäsitteisessä muodossa x = c1 v1 + c2 v2 + c3 v3 .

Koska myös C = {w1 , w2 , w3 } on kanta, jokainen vektori vi voidaan esittää yksikäsitteisesti sen avulla ja siten on olemassa sellaiset skalaarit aij , 1 ≤ i, j ≤ 3, että

v1 = a11 w1 + a21 w2 + a31 w3 , v2 = a12 w1 + a22 w2 + a32 w3 , v3 = a13 w1 + a23 w2 + a33 w3 .

2.8 Kannanvaihto

38

Sijoitetaan nämä edelliseen yhtälöön ja saadaan

x = (a11 c1 + a12 c2 + a13 c3 )w1 + (a21 c1 + a22 c2 + a23 c3 )w2 + (a31 c1 + a32 c2 + a33 c3 )w3 . Kun vektorin x koordinaatit uuden kannan suhteen ovat    0   a11 a12 c1 a11 c1 + a12 c2 + a13 c3  c02  =  a21 c1 + a22 c2 + a23 c3  =  a21 a22 a31 a32 c03 a31 c1 + a32 c2 + a33 c3

c01 , c02 , c03 , niin   c1 a13 a23   c2  . c3 a33

Edellä oleva matriisi (aij )3×3 on kannanvaihdon C → B matriisi, merkitään PC→B . Silloin xC = PC→B xB .

Määritelmä 2.49. Olkoot B = {v1 , . . . , vn } ja C = {w1 , . . . , wn } vektoriavaruuden V kaksi kantaa. Tyyppiä n × n oleva matriisi PC→B on kannanvaihdon C → B matriisi, kun sen i:ntenä pystyrivinä on vektorin vi koordinaatit kannassa C .

Samanlailla kuin esimerkissä 2.48 todistetaan seuraava lause.

Lause 2.50.

Olkoot

B = {v1 , . . . , vn } ja C = {w1 , . . . , wn } vektoriavaruuden V kaksi kantaa ja x ∈ V . Silloin xC = PC→B xB . Huomaa, että kannanvaihdon B → B matriisi on identiteettimatriisi I.

Lause 2.51. vaihdon

Olkoot B , C ja D vektoriavaruuden V kantoja. Silloin kannanC → B matriisi PC→B on aina säännöllinen. Lisäksi

PD→B = PD→C PC→B

ja

PB→C = (PC→B )−1 .

Kun x ∈ V , niin PC→B xB = xC ja PD→C xC = xD . Yhdistämällä nämä nähdään PD→C PC→B xB = xD = PD→B xB . Koska tämä yhtälö PD→C PC→B xB = PD→B xB pätee kaikille vektoreille x ∈ V , niin voidaan päätellä (harjoitustehtävä), että PD→C PC→B = PD→B . Kun valitaan D = B , niin PB→C PC→B = PB→B = I. Siis matriisilla PC→B on olemassa käänteismatriisi ja se on PB→C . Todistus.

Olkoot B = {v1 , . . . , vn } ja C = {w1 , . . . , wn } vektoriavaruuden Rn kantoja. Sivulla 32 todettiin, että vektorin vi esitys (vi )C voidaan laskea muuntamalla matriisi

(w1 | w2 | · · · | wn | vi ). elementaarisilla vaakarivioperaatioilla matriisiksi

( I | (vi )C ).

2.9 Vektorijoukon ortogonalisointi

39

Kannan C esitys voidaan laskea kaikille vektorille vi samalla kertaa, kun muunnetaan matriisi

( w1 | · · · | wn | v1 | · · · | vn ) matriisiksi ( I | P ). Tämä voidaan tehdä, sillä matriisi (w1 | · · · | wn ) on säännöllinen (lause 2.37). Silloin matriisin P j :nnes pystyrivi on (vj )C eli vanha kantavektori lausuttuna uuden kannan C avulla, joten P on juuri kannanvaihdon C → B matriisi.

Esimerkki 2.52. Tiedetään, että A = {(1, 0, −1, 0), (0, 1, 0, −1), (1, 1, 0, 0), (0, 0, 1, −1)} ja B = {(1, 0, 1, 0), (1, 0, 0, 0), (1, 1, 0, 0), (1, 0, 0, −1)} ovat avaruuden R4 kantoja. Etsitään kannanvaihdon A → B matriisi.

>>A=[1 0 1 0;0 1 1 0; -1 0 0 1; 0 -1 0 -1] B=[1 1 1 1;0 0 1 0; 1 0 0 0; 0 0 0 -1] C=rref([A B]) P=C(:,5:end) . . . P = 0 -1 1 1

2.9

1/2 -1/2 1/2 1/2

0 0 1 0

1 0 0 1

Vektorijoukon ortogonalisointi

Vektoriavaruus Rn on varustettu sisätulolla (pistetulolla) (, ), joka määritellään

(x, y) = x·y = x1 y1 +· · ·+xn yn ,

kun x = (x1 , . . . , xn ) ja y = (y1 , . . . , yn ).

Sisätulon avulla avaruuden Rn vektoreille määritellään normi eli vektorin

pituus

|x| =

Lemma 2.53. Todistus.

Kaikille

p (x, x).

x, y ∈ Rn ja kaikille c ∈ R, (cx, y) = c(x, y).

Demonstraatiot.

2.9 Vektorijoukon ortogonalisointi

40

Vektoreita x ja y sanotaan kohtisuoriksi eli ortogonaalisiksi, jos (x, y) = 0; tällöin merkitään x⊥y. Nollavektori 0 on kohtisuorassa kaikkia vektoreita vastaan. Vektorijoukkoa S sanotaan ortogonaaliseksi, jos

x⊥y

∀x, y ∈ S, x 6= y.

Vektorijoukkoa S sanotaan ortonormaaliseksi (tai ortonormaaliksi), jos se on ortogonaalinen ja lisäksi jokaisen sen vektorin pituus on 1. Aliavaruuden U ortonormaalikanta on avaruuden U kanta, joka on ortonormaalinen vektorijoukko.

Lause 2.54.

Jos vektorit

x1 , . . . , xm ovat keskenään ortogonaalisia ja xi 6= 0

kaikilla i, niin ne ovat lineaarisesti riippumattomia. Todistus. Olkoon c1 x1 + · · · + cm xm = 0, missä ci ∈ R. Otetaan puolittain sisätulo vektorin xj kanssa (1 ≤ j ≤ m) ja käytetään lemmaa 2.53:

c1 (x1 , xj ) + · · · + cj j(xj , xj ) + · · · + cm (xm , xj ) = 0. Ortogonaalisuuden nojalla (xi , xj ) = 0, kun i 6= j ,joten summaan jää vain termi cj (xj , xj ). Koska xj 6= 0, niin (xj , xj ) = |xj |2 6= 0, joten cj = 0. Ottamalla sisätulo vuorotellen kaikkien vektoreiden xi kanssa saadaan siis c1 = · · · = cm = 0. Edellisestä lauseesta seuraa luonnollisesti, että myös ortonormaalinen vektorijoukko on lineaarisesti riippumaton. Jos u1 , . . . , um ∈ Rn ovat keskenään ortonormaaliset, niin ne muodostavat aliavaruuden L(u1 , . . . , um ) ortonormaalikannan. Kannan ortonormaalisuus helpottaa usein laskelmia, niin kuin seuraavissa lauseissa näemme. Ensinnäkin vektorin koordinaatit ortonormaalikannassa saadaan sisätuloina.

Lause 2.55.

B = {u1 , . . . , um } aliavaruuden U ⊆ Rn ortonormaalikanta. Silloin vektorin x ∈ U kantaesitys on Olkoon

xB = ((x, u1 ), (x, u2 ), . . . , (x, um )) Todistus.

Demonstraatiot.

Esimerkki 2.56. Avaruuden R3 aliavaruudella T = {(x, y, z) | x+y+z = 0}

on kanta {(1, −1, 0), (1, 1, −2)}, joka on lisäksi ortogonaalinen. Se ei ole ortonormaalinen, mutta normalisoimalla sen alkiot, eli jakamalla kumpikin pituudellaan, saadaan aliavaruuden T ortonormaalikanta B = {u1 , u2 }, missä 1 1 u1 = √ (1, −1, 0), u2 = √ (1, 1, −2). 2 6

2.9 Vektorijoukon ortogonalisointi

41

Vektori x = (1, −2, 1) on aliavaruuden T vektori. Lasketaan sisätulot

1 3 (x, u1 ) = √ ((1, −2, 1), (1, −1, 0)) = √ 2 2 1 3 (x, u2 ) = √ ((1, −2, 1), (1, 1, −2)) = − √ . 6 6  3 3  3 3 Siis xB = √ , − √ eli xB = √ u1 − √ u2 . 2 6 2 6 Seuraava lause osoittaa, että sisätulon laskukaava pätee edelleen, vaikka siinä käytettäisiin vektorien koordinaatteja jonkin muun ortonormaalikannan suhteen kuin luonnollisen kannan.

Lause 2.57.

{u1 , . . . , um } avaruuden Rn aliavaruuden U ortonormaalikanta. Jos kahden vektorin x, y ∈ U kantaesitykset ovat xB = (r1 , . . . , rm ) ja yB = (s1 , . . . sm ), niin Olkoon

(x, y) = r1 s1 + · · · + rm sm . Todistus.

Demonstraatiot.

Avaruuden Rn aliavaruudelle U löydetään ortonormaalikanta valitsemalla sille ensin jokin kanta, sitten ortogonalisoimalla tämä seuraavan lauseen todistuksessa esitettävällä GraminSchmidtin menetelmällä ja lopuksi normalisoimalla.

Lause 2.58.

Olkoot vektorit

x1 , . . . , xm lineaarisesti riippumattomia. Määritetään

vektorit seuraavasti:

   y1 = x1 ,   yj = xj − Tällöin vektorit

j−1 X (xj , yi ) i=1

(yi , yi )

yi ,

(j = 2, . . . , m).

(6)

y1 , . . . , ym ovat ortogonaalisia ja L(y1 , . . . , ym ) = L(x1 , . . . , xm ).

Sivuutetaan. Konstruktion idea on, että vektoreita xj , j = 2, . . . , m "käännetään"jo määriteltyjen vektoreiden y1 , . . . , yj−1 avulla kohtisuoraksi näitä aiemmin määriteltyjä vastaan. Käyttämällä aiemmin määriteltyjä vekroreita taataan, ettei generoitu aliavaruus muutu. Itse "käännön pituus"taas on vektorin xj projektion pituus vektorilla yt , t = 1, . . . , j − 1. Todistus.

Seuraava lausee seuraa edellisestä, kun muistetaan, että ortogonaalisen joukon muuntaminen ortonormaaliksi onnistuu vektorin normin avulla.

2.9 Vektorijoukon ortogonalisointi Lause 2.59.

Jokaisella avaruuden

42

Rn aliavaruudella U on ortonormaalikan-

ta.

Esimerkki 2.60. Joukko B = {−1, 1, 0), (−1, 1, 1), (2, 0, −3)} on avaruuden

R3 kanta. Ortogonalisoidaan se GraminSchmidtin menetelmällä. Määritetään vektorin (2, 1, −1) esitys syntyvässä avaruuden R3 ortonormaalikannassa.

Esimerkki 2.61.

Matlab

-ohjelmassa ei suoraan ole saatavilla Gramin Schmidtin ortogonalisaatiota. Toisaalta ortogonaalinen (itse asiassa ortonormaali) kanta löydetään komennolla qr, joka palauttaa matriisin QR-hajotelman. Ensimmäisnen komennon palauttama matriisi, Q alla, generoi saman pystyriviavaruuden kuin matriisi A ja sen pystyrivin ovat ortogonaalisia. Seuraavassa matriisi A on esimerkin 2.52 kannan A muodostoma matriisi.

>> A [Q,R]=qr(A) A = 1 0 -1 0

0 1 0 -1

1 1 0 0

0 0 1 -1

Q = 985/1393 0 -985/1393 0

0 985/1393 0 -985/1393

1/2 1/2 1/2 1/2

1/2 -1/2 1/2 -1/2

1393/985 0 0 0

0 1393/985 0 0

985/1393 985/1393 1 0

-985/1393 985/1393 0 1

R =

√ Huomaa, että 985/1393 on luvun 1/ 2 likiarvo, jota

Matlab käyttää.

43

3 3.1

Ominaisarvot ja lineaarikuvaukset Ominaisarvot

Määritelmä 3.1. Olkoon A n × n -matriisi. Skalaari λ on matriisin A ominaisarvo, jos on olemassa sellainen pystyvektori v ∈ Rn , v 6= 0, että Av = λv. Vektori v on tällöin ominaisarvoon λ kuuluva matriisin A ominaisvektori. Kirjoitetaan matriisiyhtälö Av = λv muodossa Av − λv = 0 eli Av − λIv = 0, missä I on n × n -identiteettimatriisi. Viimeinen yhtälö voidaan kirjoittaa muodossa (A − λI)v = 0, joten v on homogeenisen lineaarisen yhtälöryhmän (A − λI)x = 0 (7) ratkaisu. Matriisin A ominaisarvo on siis sellainen λ, että yhtälöllä 7 on epätriviaali ratkaisu v. Määritelmän mukaanhan ominaisvektori on aina nollasta eroava. Voidaan osoittaa, että lineaarisella homogeenisella yhtälöryhmällä on epätriviaali ratkaisu täsmälleen silloin, kun kerroinmatriisin determinantti on nolla (ks. demonstraatiot). Saadaan siis yhtälö

det(A − λI) = 0. Jos merkitään A = (aij ), niin edellinen yhtälö voidaan kirjoittaa muodossa a11 − λ a . . . a 12 1n a21 a22 − λ . . . a2n = 0. .. .. .. . . . an1 an2 . . . ann − λ Kun lasketaan determinantin arvo, saadaan n:nnen asteen polynomi p(λ) muuttujan λ suhteen kertoimina matriisin alkioiden aij tulojen summia. Polynomia pA (λ) = det(A − λI) sanotaan matriisin A ominaisarvopolynomiksi tai karakteristiseksi polynomiksi. Matriisin A ominaisarvot ovat tarkalleen ominaisarvoyhtälön eli karakteristisen yhtälön pA (λ) = 0 ratkaisut. Huomaa, että tällä yhtälöllä on n kompleksiluku ratkaisua, joista osa voi olla samoja. Olkoot λ1 , . . . , λk matriisin A erisuuret ominaisarvot. Silloin on olemassa kokonaisluvut t1 , . . . , tk , joille ti ≥ 1 ja

pA (λ) = (−1)n (λ − λ1 )t1 (λ − λ2 )t2 · · · (λ − λk )tk ,

3.1 Ominaisarvot

44

ja t1 +· · ·+tk = n. Lukua ti sanotaan ominaisarvon λi kertaluvuksi tai että λi on kertalua ti . Onkin luontevaa ajatella, että ominaisarvoja tarkasteltaessa skalaarit ovat kompleksilukuja ja matriisit kompleksilukumatriiseja. Huomaa, että Cn on vektoriavaruus aivan kuten Rn .

Esimerkki 3.2. Etsitään matriisin  A=

1 2 −4 −5

ominaisarvot. Matriisin ominaisarvopolynomi 1−λ 2 det(A − λI) = −4 −5 − λ

 on = λ2 + 4λ + 3

ja ominaisarvoyhtälö on λ2 + 4λ + 3 = 0. Koska λ2 + 4λ + 3 = (λ + 3)(λ + 1), niin ominaisarvot ovat λ1 = −3 ja λ2 = −1.

Esimerkki 3.3. Matriisin  2 0 0 A= 1 1 2  −1 0 1 

karakteristinen polynomi on 2−λ 0 0 1−λ 2 p(λ) = 1 −1 0 1−λ

= (2 − λ)(1 − λ)(1 − λ),

joten ominaisarvot ovat λ1 = 1, λ2 = 1 ja λ3 = 2. Ominaisarvoon λ kuuluvat ominaisvektorit voidaan etsiä seuraavalla tavalla: Sijoitetaan ominaisarvo yhtälöön (7) ja etsitään saadun yhtälön epätriviaalit ratkaisut. Ratkaisuja on ääretön määrä, joista jokainen on ominaisarvoon λ kuuluva ominaisvektori.

Esimerkki 3.4. Matriisin 

 2 0 0 A= 1 1 2  −1 0 1 ominaisarvot ovat λ1 = λ2 = 1 ja λ3 = 2. Ratkaistaan yhtälöstä (A − λi I)vi = 0 vektori vi jokaisella ominaisarvolla λi . Etsitään ensin v1 = (x, y, z):

( A − λ1 I | 0 ) = ( A − I | 0 )       1 0 0 0 1 0 0 0 1 0 0 0 =  1 0 2 0  ∼  0 0 2 0  ∼  0 0 1 0 . −1 0 0 0 0 0 0 0 0 0 0 0

3.1 Ominaisarvot Tästä saadaan yhtälöryhmä      1 0 0 x 0  0 0 1  y  =  0  0 0 0 z 0

45

 eli

   x 0  z = 0  0 0

eli

  x = 0 z = 0 ,  0 = 0

jonka ratkaisu on



   0 0    y 1 , v1 = =y 0 0 missä y on mikä tahansa nollasta eroava luku. Nämä ovat ominaisarvoon 1 kuuluvat ominaisvektorit. Ominaisarvoon λ3 = 2 kuuluvat vektorit v3 = (x, y, z) lasketaan samoin:

( A − λ3 I | 0 ) = ( A − 2I | 0 )       0 0 0 0 0 0 0 0 0 0 0 0 2 0  ∼  1 −1 2 0  ∼  1 0 1 0 , =  1 −1 −1 0 −1 0 0 −1 1 0 0 −1 1 0 josta saadaan yhtälöryhmä  0 = 0  x+z = 0  −y + z = 0

eli



x = −z . y = z

Ominaisvektoreita ovat siis kaikki vektorit     −1 −z v3 =  z  = z  1  z 1 kaikilla z 6= 0. Tarkistetaan vielä lasku:        2 0 0 −z −2z −z Av3 =  1 1 2   z  =  2z  = 2  z  = λ3 v3 . −1 0 1 z 2z z Matriiseilla ja sen ominaisarvoilla ja ominaisvektoreilla on seuravat ominaisuudet.

Lause 3.5.

Olkoon

A n × n -matriisi ja v sen ominaisarvoon λ kuuluva

ominaisvektori. 1. Silloin

λk on matriisin Ak ominaisarvo ja v siihen kuuluva omi-

naisvektori. 2. Jos ja

A on kääntyvä matriisi, niin 1/λ on matriisin A−1 ominaisarvo

v siihen kuuluva ominaisvektori.

3.1 Ominaisarvot Todistus.

46

Demonstraatiot.

Lause 3.6. Olkoon A n × n -matriisi. Jos v1 , . . . , vm ovat vastaavasti sen eri ominaisarvoihin λ1 , . . . , λm kuuluvat ominaisvektorit, niin vektorit v1 , ...,

vm ovat lineaarisesti riippumattomia.

Oletetaan, että vektorit v1 , . . . , vm ovat lineaarisesti riippuvia. Olkoon k ensimmäinen indeksi, jolla v1 , . . . , vk ovat lineaarisesti riippuvia. Silloin yhtälössä a1 v1 + · · · + ak vk = 0 Todistus.

kerroin ak ei voi olla nolla, muuten jo k − 1 aikaisempaa vektoria olisi lineaarisesti riippuvia. Kun merkitään di = −ai /ak , voidaan kirjoittaa

vk = d1 v1 + d2 v2 + · · · + dk−1 vk−1 .

(8)

Kerrotaan yhtälö (8) arvolla λk ja saadaan

λk vk = d1 λk v1 + d2 λk v2 + · · · + dk−1 λk vk−1 .

(9)

Kun taas yhtälö (8) kerrotaan matriisilla A, saadaan

λk vk = d1 λ1 v1 + d2 λ2 v2 + · · · + dk−1 λk−1 vk−1 ,

(10)

sillä Avi = λi vi . Kun (10) vähennetään yhtälöstä (9), niin

0 = d1 (λk − λ1 )v1 + d2 (λk − λ2 )v2 + · · · + dk−1 (λk − λk−1 )vk−1 . Koska ainakin jokin luvuista di on nollasta eroava ja luvut λi ovat eri lukuja, nähdään, että vektorit v1 , . . . , vk−1 ovat lineaarisesti riippuvia vastoin luvun k valintaa. Siispä v1 , . . . , vm ovat lineaarisesti riippumattomia. Matriisin lineaarisesti riippumattomien ominaisvektoreiden lukumäärällä on merkitystä tämän luvun lopussa ns. diagonalisoituvuuteen liittyen. Edellisen lauseen mukaan n × n -matriisilla on n lineaarisesti riippumatonta ominaisvektoria ainakin, jos kaikki ominaisarvot ovat erisuuria. Huomaa kuitenkin, että matriisilla voi olla n lineaarisesti riippumatonta ominaisvektoria vaikka sillä olisi useampi kertaisia ominaisarvoja. Merkitään Vλ :lla joukkoa, johon kuuluvat kaikki ominaisarvoon λ kuuluvat matriisin A ominaisvektorit ja nollavektori. Koska A0 = 0 = λ0, huomataan, että

Vλ = {v | Av = λv}.

Lause 3.7.

Olkoon

A n×n -matriisi ja λ sen kertalukua t oleva ominaisarvo.

Silloin 1.

Vλ on avaruuden Cn aliavaruus, ja

2.

1 ≤ dim(Vλ ) ≤ t.

3.1 Ominaisarvot Todistus.

47

Sivuutetaan.

Huomaa, että jos λ ∈ R, niin Vλ on avaruuden Rn aliavaruus. Seuraava lause voidaan todistaa kahden edellisen lauseen avulla.

Lause 3.8.

A n × n -matriisi ja λ1 , . . . , λm sen eri ominaisarvot. Oletetaan, että λi on kertalukua ti , kaikilla 1 ≤ i ≤ m. Matriisilla A on n lineaarisesti riippumatonta ominaisvektoria jos ja vain jos kaikilla 1 ≤ i ≤ m, dim(Vλi ) = ti . Todistus.

Olkoon

Sivuutetaan.

Esimerkki 3.9.

Matlab

-ohjelmalla matriisin karakteristinen saadaan komennolla poly ja sen juuret komennolla roots. Toisaalta matriisin ominaisarvot ja niihin liittyvät ominaisvektorit saadaan eig komenolla. Etsitään matriisin   2 0 2 A= 3 1 1  −1 0 −1 ominaisarvot ja niihin kuuluvat ominaisvektorit.

>> A=[2 0 2;3 1 1; -1 0 -1] A = 2 3 -1

0 1 0

2 1 -1

-2

1

>> poly(A) P = 1 >> roots(P) ans = 0 1 1 >> [V,D]=eig(A)

0

3.2 Lineaarikuvaukset

48

V = 0 1 0

* -1 *

1 0 0

0 1 0

-881/2158 881/1079 881/2158

D = 0 0 0

Karakteristinen polynomi P (λ) = 1λ3 − 2λ2 + 1λ + 0 ja sen juuret ovat siis λ1,2 = 1 ja λ3 = 0. Komennon eig palauttama matriisi D sisältää ominaisarvot diagonaalillaan ja näitä vastaavat ominaisvektorit löytyvät matriisin V pystyriveinä. Tiedetään, että AV = V D. 3.2

Lineaarikuvaukset

Määritelmä 3.10. Funktio T : Rn → Rm on lineaarikuvaus, jos se toteuttaa ehdot

1. T (v1 + v2 ) = T (v1 ) + T (v2 ) ja 2. T (rv1 ) = rT (v1 ) kaikille skalaareille r ∈ R ja vektoreille v1 , v2 ∈ Rn . Lineaarikuvaus siis säilyttää yhteenlaskun ja skalaarilla kertomisen. Edellä olevat ehdot voidaan myöskin yhdistää ekvivalentiksi ehdoksi

T (r1 v1 + r2 v2 ) = r1 T (v1 ) + r2 T (v2 ) kaikille skalaareille r1 , r2 ∈ R ja vektoreille v1 , v2 ∈ Rn .

Esimerkki 3.11. Osoitetaan, että f : R2 → R3 , f (x, y) = (x + y, −3y, 2x −

y), on lineaarikuvaus. Olkoot u = (a1 , a2 ) ja v = (b1 , b2 ). Silloin u + v = (a1 + b1 , a2 + b2 ) ja ru = (ra1 , ra2 ) ja nyt f (u + v) = ((a1 + b1 ) + (a2 + b2 ), −3(a2 + b2 ), 2(a1 + b1 ) − (a2 + b2 )), = ((a1 + a2 ) + (b1 + b2 ), −3a2 − 3b2 , (2a1 − a2 ) + (2b1 − b2 )), = (a1 + a2 , −3a2 , 2a1 − a2 ) + (b1 + b2 , −3b2 , 2b1 − b2 ) = f (u) + f (v),

3.2 Lineaarikuvaukset

49

joten ehto 1 on voimassa, ja

f (ru) = (ra1 + ra2 , −3ra2 , 2ra1 − ra2 ) = r(a1 + a2 , −3a2 , 2a1 − a2 ) = rf (u), joten myös ehto 2 on voimassa. Siis f on lineaarikuvaus.

Esimerkki 3.12. Identiteettikuvaus I : Rn → Rn , I(v) = v, on aina lineaarikuvaus. Samoin on myös nollakuvaus O : Rn → Rn , O(v) = 0.

Esimerkki 3.13. Osoitetaan, että jos T : R → R on lineaarikuvaus, niin on olemassa sellainen a ∈ R, että T (x) = ax kaikilla x ∈ R. Merkitään T (1) = a. Koska T säilyttää skalaarilla kertomisen, niin kun x ∈ R, T (x) = T (x · 1) = xT (1) = xa = ax. Toisaalta jos T : R → R on määritelty niin, että T (x) = ax jollekin skalaarille a ∈ R, niin T on lineaarikuvaus. Nimittäin jos x, y ∈ R ja r ∈ R on jokin skalaari, niin

T (x + y) = a(x + y) = ax + ay = T (x) + T (y), T (rx) = a(rx) = r(ax) = rT (x).

Esimerkki 3.14. Yleistetään edellinen esimerkki lineaarikuvauksille Rm → R. Jos a1 , . . . , am ∈ R, niin kuvaus T : Rm → R,

T (x1 , . . . , xm ) = a1 x1 + · · · + am xm ,

on lineaarikuvaus. Jos taas T : Rm → R on lineaarikuvaus, niin T on tätä muotoa, merkitään vain T (ei ) = ai , jolloin

T (x1 e1 + · · · + xm em ) = x1 T (e1 ) + · · · + x1 T (e1 ) = a1 x1 + · · · + am xm .

Esimerkki 3.15. Olkoon A m × n -matriisi. Ajatellaan vektoriavaruudet

Rn ja Rm pystyvektoriavaruuksina. Osoitetaan, että matriisilla kertominen TA : Rn → Rm , TA (u) = Au, on lineaarikuvaus. Olkoot u, v ∈ Rn ja r ∈ R. Silloin matriisien distributiivilain mukaan TA (u + v) = A(u + v) = Au + Av = TA (u) + TA (v). Käyttämällä taas lauseen 1.8 kohtaa 7, saadaan

TA (rv) = A(rv) = r(Av) = rTA (v).

Lause 3.16.

Jos

T : Rn → Rm on lineaarikuvaus, niin T (0) = 0 ja T (u −

v) = T (u) − T (v).

3.2 Lineaarikuvaukset Todistus.

50

Demonstraatiot.

Kahden kuvauksen f : X → Y ja g : Y → Z yhdistetty kuvaus g ◦ f : X → Z määritellään kaavan (g ◦ f )(u) = g(f (u)) avulla. On helppo nähdä, että kahden lineaarikuvauksen yhdistetty kuvaus on lineaarinen. Olkoon f : X → Y funktio. Silloin joukon A ⊆ X kuva on

f (A) = {f (x) | x ∈ A}, ja joukon B ⊆ Y alkukuva on

f −1 (B) = {x ∈ X | f (x) ∈ B}.

Lause 3.17.

T : Rn → Rm lineaarikuvaus ja U jokin avaruuden Rn m aliavaruus ja S jokin avaruuden R aliavaruus. Silloin Olkoon

1.

T (U ) on avaruuden Rm aliavaruus, ja

2.

T −1 (S) on avaruuden Rn aliavaruus.

1. Harjoitustehtävä. 2. Koska S on aliavaruus, niin 0 ∈ S ja T (0) = 0, joten 0 ∈ T −1 (S). Siis −1 T (S) ei ole tyhjä. Todistetaan väite käyttäen aliavaruuskriteeriä: (i) Olkoot x ja y joukon T −1 (S) vektoreita, joten T (x) ja T (y) kuuluvat avaruuteen S . Koska T on lineaarikuvaus ja S suljettu yhteenlaskun suhteen, niin T (x + y) = T (x) + T (y) ∈ S . Siis x + y ∈ T −1 (S), joten kriteeri (i) on voimassa. (ii) Jos r ∈ R, niin T (rx) = rT (x), joten myös T (rx) ∈ S , ja rx ∈ T −1 (S). Täten T −1 (S) täyttää molemmat aliavaruudelta vaadittavat ehdot. Todistus.

Määritellään kaksi erikoistapausta aliavaruuksista liittyen lineaarikuvaukseen.

Määritelmä 3.18. Olkoon T : Rn → Rm lineaarikuvaus. Avaruuden Rn aliavaruus

ker(T ) = T −1 (0) = { x ∈ Rn | T (x) = 0 }

on kuvauksen T ydin, ja avaruuden Rm aliavaruus

im(T ) = T (Rn ) = { T (x) | x ∈ Rn } on kuvauksen T kuva-avaruus. Funktio f : X → Y on injektio, jos ehdosta f (x) = f (y) seuraa x = y . Injektiivisellä funktiolla kuvan f (X) jokaisella alkiolla y on täsmälleen yksi alkio x ∈ X , jolle f (x) = y . Silloin voidaan siis määritellä käänteiskuvaus f −1 : f (X) → X , missä f −1 (y) = x. Lineaarikuvauksella T on tällainen käänteiskuvaus, kun ydin on mahdollisimman pieni.

3.2 Lineaarikuvaukset Lause 3.19. 1.

Olkoon

51

T : Rn → Rm lineaarikuvaus. Silloin

T on injektio, jos ja vain jos ker(T ) = {0}, ja

2. jos

T on injektio, niin käänteiskuvaus T −1 : T (Rn ) → Rn on lin-

eaarikuvaus.

1. Olkoon T on injektio ja v ∈ ker(T ), ts. T (v) = 0. Tiedetään, että myös T (0) = 0. Koska T on injektio ja T (v) = T (0), niin v = 0. Oletetaan nyt, että ker(T ) = {0} ja T (v1 ) = T (v2 ) joillekin v1 , v2 ∈ Rn . Tällöin T (v1 − v2 ) = T (v1 ) − T (v2 ) = 0,

Todistus.

joten (v1 − v2 ) ∈ ker(T ). Koska ker(T ) = {0}, v1 − v2 = 0, mistä saadaan, että v1 = v2 . T on siis injektio. 2. Oletetaan, että T injektio, ja osoitetaan, että käänteiskuvaus T −1 : T (Rn ) → Rn on lineaarikuvaus. Valitaan kaksi vektoria w1 ja w2 kuvasta T (Rn ), jolloin siis olemassa vektorit v1 , v2 ∈ Rn ,joille T (v1 ) = w1 ja T (v2 ) = w2 . Käänteiskuvauksen määritelmän mukaan T −1 (wi ) = vi , kun i = 1, 2. Koska T on lineaarikuvaus,

T (v1 + v2 ) = T (v1 ) + T (v2 ) = w1 + w2 , joten v1 + v2 = T −1 (w1 + w2 ). Siis T −1 (w1 + w2 ) = T −1 (w1 ) + T −1 (w2 ). Samalla tavalla yhtälöstä T (rv1 ) = rT (v1 ) = rw1 seuraa, että T −1 (rw1 ) = rv1 = rT −1 (w1 ). Näin ollen T −1 täyttää molemmat lineaarikuvauksen ehdot.

Esimerkki 3.20. Lasketaan lineaarikuvauksen T : R3 → R3 , T (x, y, z) = (x − y, y + z, 2x + 2z), ydin ja kuva. Ytimen laskemiseksi ratkaistaan yhtälö T (x, y, z) = 0 eli (x − y, y + z, 2x + 2z) = (0, 0, 0). Tämä yhtälö voidaan kirjoittaa yhtälöryhmäksi    x−y =0 y+z =0,

 

2x + 2z = 0

jonka ratkaisu on (r, r, −r) kaikilla r ∈ R. Siis

ker(T ) = {r(1, 1, −1) | r ∈ R} = L(1, 1, −1). Ytimen kannaksi voidaan siis valita {(1, 1, −1)}, joten dim(ker(T )) = 1. Vektorilla x = (c1 , c2 , c3 ) ∈ R3 on esitys x = c1 e1 + c2 e2 + c3 e3 . Tällöin

T (x) = c1 T (e1 ) + c2 T (e2 ) + c3 T (e3 ), joten vektorit T (e1 ), T (e2 ), T (e3 ) virittävät avaruuden im(T ). Siis

im(T ) = L(T (e1 ), T (e2 ), T (e3 )) = L((1, 0, 2), (−1, 1, 0), (0, 1, 2)).

3.3 Lineaarikuvauksen matriisi

52

Huomataan, että (1, 0, 2) on vektorien (0, 1, 2) ja (−1, 1, 0) erotus, joten

im(T ) = L((−1, −1, 0), (0, 1, 2)). Nämä vektorit ovat lineaarisesti riippumattomat, joten ne muodostavat kuvan kannan ja dim(im(T )) = 2. 3.3

Lineaarikuvauksen matriisi

Seuraavaksi osoitetaan, että lineaarikuvaus voidaan aina määritellä matriisin avulla. Lineaarikuvauksen matriisin ominaisuuksia voidaan käyttää kuvauksen ominaisuuksia tarkasteltaessa. Matriisi ilmoitetaan aina vektoriavaruuksien kannan suhteen. Huomaa, että vektoriavaruuden kannat ovat aina järjestettyjä.

Lemma 3.21.

{b1 , . . . , bn } jokin avaruuden Rn kanta. Jokainen linm eaarikuvaus T : R → R määräytyy täysin kantavektoreiden bi kuvista. Ts. jos tiedetään vektorit T (b1 ), . . . , T (bn ), voidaan kuva T (x) laskea jokaiselle n vektorille x ∈ R . Olkoon n

Olkoon x mielivaltainen Rn :n vektori. Koska {b1 , . . . , bn } on avaruuden R kanta, x voidaan esittää yksikäsitteisesti muodossa

Todistus. n

x = x1 b1 + · · · + xn bn , missä luvut x1 , . . . , xn ∈ R. Koska lineaarikuvaus T säilyttää yhteenlaskun ja skalaarilla kertomisen, niin

T (x) = x1 T (b1 ) + · · · + xn T (bn ). Siis T (x) määräytyy täysin kantavektoreiden kuvista T (b1 ), . . . , T (bn ). la.

Edellisen lemman avulla saadaan lineaarikuvaus esitettyä matriisin avul-

Lause 3.22.

T : Rn → Rm lineaarikuvaus ja olkoot B = {b1 , . . . , bn } n m ja C = {c1 , . . . , cm } avaruuksien R ja R järjestetyt kannat vastaavasti. Silloin on olemassa sellainen kantojen B ja C suhteen yksikäsitteinen m × n n -matriisi M, että kaikilla x ∈ R Olkoon

T (x)C = MxB . Olkoon x ∈ Rn . Koska B on kanta, on olemassa sellaiset yksikäsitteiset luvut x1 , . . . , xn ∈ R, että Todistus.

x = x 1 b1 + · · · + x n bn .

3.3 Lineaarikuvauksen matriisi

53

Siis xB = (x1 , . . . , xn ). Silloin edellisen lemman mukaan

T (x) = x1 T (b1 ) + · · · + xn T (bn ). Jokainen T (bi ) on Rm vektori ja koska C on avaruuden Rm kanta, on vektoreilla T (bi ) yksikäsitteinen esitys

T (bi ) = a1i c1 + · · · + ami cm , joten T (bi )C = (a1i , . . . , ami ). Kun sijoitetaan vektorin T (x) kaavaan nämä vektorien T (bi ) esitykset ja kerätään termit yhteen, saadaan yhtälö

T (x) = (a11 x1 + · · · + a1n xn )c1 + · · · + (am1 x1 + · · · + amn xn )cm , Nyt

T (bx)C = (a11 x1 + · · · + a1n xn ), . . . , (am1 x1 + · · · + amn xn ))    a11 a12 . . . a1n x1  a21 a22 . . . a2n   x2     = .. .. ..   ..     . . . .  am1 am2 . . .

amn

xn

= (T (b1 )C | · · · | T (bn )C )xB . Matriisi M = (T (b1 )C | · · · | T (bn )C ) on siis haluttu matriisi. Se on lisäksi yksikäsitteinen valittujen järjestettyjen kantojen suhteen, sillä koordinaattivektorit ovat yksikäsitteisiä annetussa kannassa.

Määritelmä 3.23. Olkoon B = {b1 , . . . , bn } on vektoriavaruuden Rn kanta

ja C vektoriavaruuden Rm kanta. Lineaarikuvauksen T : Rn → Rm matriisi kantojen B ja C suhteen on m × n -matriisi MB,C (T ) = (T (b1 )C | · · · | T (bn )C ).

Kun sekaannuksen vaaraa ei ole, voidaan merkitä lyhyemmin MB,C (T ) = M(T ). Lauseen 3.22 mukaan T (x)C = MB,C (T )xB . Kun vektorien koordinaatit on ilmoitettu oikeiden kantojen B ja C suhteen, yhtälö on muotoa T (x) = M(T )x. Lineaarikuvaus muuttuu siis matriisikertolaskuksi.

Esimerkki 3.24. Lineaarikuvaus T : R3 → R3 , T (x1 , x2 , x3 ) = (x1 +x2 , x2 − x3 , 2x1 + x2 − 5x3 ) kuvaa luonnollisen kannan vektorit E = {e1 , e2 , e3 } seuraavasti: T (1, 0, 0) = (1, 0, 2), T (0, 1, 0) = (1, 1, 1), T (0, 0, 1) = (0, −1, −5). Täten sen matriisi on   1 1 0 ME,E (T ) =  0 1 −1  . 2 1 −5

3.3 Lineaarikuvauksen matriisi

54

Lineaarikuvauksen matriisin selvittämiseksi on siis etsittävä vektoreiden T (b1 ), . . . , T (bn ) esitys kannassa C = {c1 , . . . , cm }. Tämä onnistuu helpommin muodostamalla matriisi

( c1 | · · · | cm || T (b1 ) | · · · | T (bn ) ) ja muunnetaan se elementaarisilla vaakarivioperaatioilla matriisiksi ( I | M ). Vasemmalle saadaan identiteettimatriisi, koska ensimmäiset m pystyvektoria muodostavat avaruuden Rm kannan. Oikealle tulee matriisi M = MB,C (T ). Huomaa, että T (bi ) ∈ Rm kaikilla i, ja matriisi M on siis m × n matriisi.

Esimerkki 3.25. Etsitään lineaarikuvauksen T : R3 → R3 , T (x1 , x2 , x3 ) = (x1 + x2 , x2 − x3 , 2x1 + x2 − 5x3 ) matriisi kantojen B = {(1, 1, 1), (1, 1, 0), (1, 0, 0)}

ja

C = {(2, 1, 1), (1, 2, 1), (1, 2, 2)} suhteen. Nyt T (1, 1, 1) = (2, 0, −2), T (1, 1, 0) = (2, 1, 3) ja T (1, 0, 0) = (1, 0, 2), joten redusoidaan matriisi seuraavasti:

4 2  1 2 1 1 2 2 1 3 3    1 2 2 0 1 0 ∼ 2 −2 −2   0 1 0 . 8 5 1 1 2 −2 3 2 0 0 1 − 2 3 3 





1 0 0

Silloin haluttu matriisi on

2  4 1 3   3  MB,C (T ) =   2 −2 −2  . 8 5 − 2 3 3 

Testataan saatua matriisia laskemalla vektorin x = (1, 4, 3) kuva kuvauksessa T . Koska (1, 4, 3) = 3(1, 1, 1) + (1, 1, 0) − 3(1, 0, 0), niin xB = (3, 1, −3). Nyt  4 2     1 3 3 3   3   1  =  10  . MB,C (T )xB =   2 −2 −2  5 8 −3 −11 − 2 3 3 Vektori (3, 10, −11) on ilmoitettu kannassa C , jolloin se on luonnollisessa kannassa 3(2, 1, 1) + 10(1, 2, 1) − 11(1, 2, 2) = (5, 1, −9). Tulos on tosiaan oikein, sillä T (x) = T (1, 4, 3) = (5, 1, −9). Lineaarikuvaus voidaan siis aina esittää matriisikertolaskun avulla. Käytännössä olisi kätevää, jos lineaarikuvauksen matriisia olisi helppo käsitellä.

3.3 Lineaarikuvauksen matriisi

55

Tässä kannan valinta on ratkaisevassa asiassa. Tutkitaan nyt, miten lineaarikuvauksen matriisi muuttuu, kun kanta vaihdetaan. Tarkastelaan tässä vain lineaarikuvauksia T : Rn → Rm , joissa n = m. Jos kannat B ja C ovat samat, merkitään lineaarikuvauksen T matriisia lyhyesti näin: MB (T ) = MB,C (T ).

Lause 3.26.

T : Rn → Rn lineaarikuvaus, ja olkoot B ja C vektoriavaruuden R kaksi kantaa. Jos P on kannanvaihdon C → B matriisi, niin

n

MB (T ) = P−1 MC (T )P.

Todistus.

niin

Olkoon

Olkoon x ∈ Rn . Koska P −1 on kannanvaihdon B → C matriisi,

MB (T )xB = T (x)B = P−1 T (x)C = P−1 MC (T )xC = P−1 MC (T )PxB . Nyt MB (T )xB = (P−1 MC (T )P)xB . Koska yhtälö pätee kaikille vektoreille x ∈ Rn , niin MB (T ) = P−1 MC (T )P. Edellisen lauseen yhtälön B = P−1 AP mukaista yhteyttä matriisien A ja B välillä tarkastellaan seuraavassa pykälässä.

Esimerkki 3.27. Lineaarikuvauksen matriisi löytyy tietysti myös käyttäen

Matlab-ohjelmaa. Tarkastellaan tässä kuitenkin lineaarikuvauksen ytimen

ja kluvan etsimistä. Ydin, tai oikeastaan ytimen kanta, löydetään tietysti tutulla (null)-komennolla ja kuva-avaruuden kanta taas orth-komennolla. Etsitään lineaarikuvauksen T : R6 → R3 , T (x1 , x2 , x3 , x4 , x5 , x6 ) = (x1 − 2x2 + 2x4 + 3x5 − 2x6 , 0x2 + x3 − 2x4 + 3x5 + 2x6 , −1x1 − 2x2 − x3 + 4x6 ) ydin ja kuva-avaruus.

>>A=[ 1 -2 0 2 3 -2; 0 1 1 -2 3 2; -1 -2 -1 0 0 4] null(A,'r') . . . ans = -2 0 2 1 0 0

1 2 -5 0 1 0

14/3 4/3 -10/3 0 0 1

3.4 Similaariset matriisit

56

>> orth(A) ans = -453/794 3049/7363 261/368

-1510/2039 -2686/4245 -575/2541

463/1304 -973/1487 1117/1673

>> format short >> orth(A) ans = -0.5705 0.4141 0.7092 3.4

-0.7406 -0.6327 -0.2263

0.3551 -0.6543 0.6677

Similaariset matriisit

Määritelmä 3.28. Olkoot A ja B n × n -matriiseja. A on similaarinen matriisin B kanssa, jos on olemassa sellainen säännöllinen matriisi P, että B = P−1 AP.

Lauseen 3.26 mukaan siis lineaarikuvauksen matriisit eri kantojen suhteen ovat similaariset.

Lause 3.29. 1. Matriisi

Olkoot

A, B ja C n × n -matriiseja.

A on similaarinen itsensä kanssa.

2. Jos

A on similaarinen matriisin B kanssa, niin B on similaarinen matriisin A kanssa. Voidaankin sanoa, että A ja B ovat similaariset.

3. Jos

A on similaarinen matriisin B kanssa ja B similaarinen matriisin C kanssa, niin A on similaarinen matriisin C kanssa.

4. Jos

A on similaarinen matriisin B kanssa, niin det(A) = det(B).

5. Jos

A on similaarinen matriisin B kanssa, niin niiden ominaisarvot

ja karakteristiset polynomit ovat samat.

A on similaarinen matriisin B kanssa, niin Am on similaarinen m matriisin B kanssa, kun m ∈ N.

6. Jos

7. Jos

A on similaarinen matriisin B kanssa, niin A on säännöllinen täsB on säännöllinen, ja silloin A−1 on similaarinen −1 matriisin B kanssa.

mälleen silloin, kun

3.5 Matriisien diagonalisointi

57

Näytetään vain kohdat 4 ja 5 ja jätetään muut harjoitustehtäviksi. 4. Koska B = P−1 AP, niin

Todistus.

det(B) = det(P−1 AP) = det(P−1 ) det(A) det(P) 1 = det(A) det(P) = det(A). det(P) 5. Tarkastellaan matriiseja A − λI ja B − λI. Jos B = P−1 AP, niin

B − λI = P−1 AP − λP−1 IP = P−1 (A − λI)P, joten matriisit ovat similaariset. Silloin myös det(A − λI) = det(B − λI) kohdan 4 mukaan, joten matriisien A ja B karakteristiset polynomit ja yhtälöt ovat samat. Tällöin myös ominaisarvoyhtälöiden ratkaisut eli ominaisarvot ovat samat. Kahden annetut matriisit toteaminen similaarisiksi tai epäsimilaarisiksi on käytännössä yleisesti vaikeaa. Edellisen lauseen kohtaa 4 voidaan käyttää osoittamaan, etteivät annetut matriisit ole similaariset.     2 1 1 2 eivät ole ja B = Esimerkki 3.30. Matriisit A = 1 2 2 1 similaariset, sillä det(A) = −3 6= 3 = det(B).     2 0 1 0 eivät ole ja B = Esimerkki 3.31. Matriisit A = 0 2 0 4 similaariset, vaikka det(A) = 4 = det(B), sillä matriisin A ominaisarvot ovat 1 ja 4, kun taas matriisin B ominaisarvot ovat 2 ja 2. 3.5

Matriisien diagonalisointi

Similaarisuuden erikoistapauksena käsitellään matriisien ns. diagonalisoituvuutta.

Määritelmä 3.32. Matriisi A on diagonalisoituva, jos se on similaarinen

diagonaalimatriisin kanssa. Silloin on olemassa sellainen säännöllinen matriisi P ja diagonaalimatriisi D, että A = PDP−1 . Kun P ja D on löydetty, sanotaan, että A on diagonalisoitu ja silloin D = P−1 AP. Koska diagonaalimatrisin monet ominaisuudet on helppo tarkistaa tai laskea, on diagonalisoinnissa hyötyä erilaisten matriisilaskujen nopeutuksessa. Matriisin diagonalisointi voidaan ajatella vastaavan lineaarisen yhtälöryhmän yhtälöiden muuntamista ekvivalentiksi yhtälöryhmäksi, jossa yhtälöt ovat jokin joukko koordinaattiakselien monikertoja. Entä mitkä matriisit sitten ovat diagonalisoituvia? Tarkastellaan seuraavaksi tätä ongelmaa.

3.5 Matriisien diagonalisointi

58

Oletetaan, että A on diagonalisoituva ja A = PDP−1 . PD. Kirjoitetaan  c1 0 . . .  0 c2 . . .  P = (P1 | · · · | Pn ) ja D= . ..  .. . 0 0 ...

Nyt siis AP =

0 0 .. .

   , 

cn

jolloin nähdään, kun tarkastellan yhtälöä AP = PD pystyriveittäin, että

AP1 = c1 P1 ,

AP2 = c2 P2 ,

...,

APn = cn Pn .

Tässä siis vektori Pj on matriisin P j :s pystyvektori. Siispä diagonaalimatriisin D diagonaalialkiot ci ovat matriisin A ominaisarvot ja matriisin P pystyvektorit ovat vastaaviin ominaisarvoihin kuuluvat ominaisvektorit. Koska P on kääntyvä matriisi, nämä ominaisvektorit ovat siis lineaarisesti riippumattomat. Tästä saammekin seuraavan lauseen todistuksen toisen puolen.

Lause 3.33. n×n -matriisi A on diagonalisoituva, jos ja vain jos matriisilla A on n lineaarisesti riippumatonta ominaisvektoria x1 , . . . , xn . Silloin jos Ax1 = λ1 x1 , . . . , Axn = λn xn , niin A = PDP−1 , missä   λ1 0 . . . 0  0 λ2 . . . 0    P = (x1 | · · · | xn ) ja D= . .. ..  .  .. . .  0 0 . . . λn On vielä osoitettava, että jos matriisilla A on n lineaarisesti riippumatonta ominaisvektoria x1 , . . . , xn , niin A on diagonalisoituva. Olkoot Ax1 = λ1 x1 , . . . , Axn = λn xn . Koska vektorit x1 , . . . , xn ovat lineaarisesti riippumattomia, seurauksen 2.26 mukaan matriisi P = (x1 | · · · | xn ) on säännöllinen. Kun matriisien pystyrivit kirjoitetaan esille, niin

Todistus.

AP = A(x1 | x2 | · · · | xn ) = (Ax1 | Ax2 | · · · | Axn ) = (λ1 x1 | λ2 x2 | · · · | λn xn )  λ1 0 . . .  0 λ2 . . .  = (x1 | x2 | · · · | xn )  . ..  .. . 0

0 ...

0 0 .. .

    = PD. 

λn

Nyt A = PDP−1 ja A on diagonalisoitu. Oletetaan, että luvut λ1 , . . . , λk matriisin A eri suuret ominaisarvot ja merkitään ominaisarvon λi kertalukua ti :llä. Lauseen 3.8 mukaan, että matriisilla on n lineaarisesti riippumatonta ominaisvektoria jos ja vain jos sen dim(Vλi ∪ {0}) = ti kaikilla i.

3.5 Matriisien diagonalisointi

59

Seuraus 3.34. vain jos

Olkoon A kuten edellä. Tällöin A on diagonalisoituva jos ja dim(Vλi ∪ {0}) = ti kaikilla matriisin A eri ominaisarvoilla λi .

Esimerkki 3.35. Diagonalisoidaan matriisi  3 −2 0  0 0  A= 1 . 3 −3 2 2 

Sen ominaisarvopolynomi on

det(A − λI) = −λ3 + 5λ2 − 8λ + 4 = −(λ − 1)(λ − 2)2 , joten ominaisarvot ovat λ1 = 1 ja λ2 = λ3 = ominaisvektorit saadaan laskemalla    2 −2 0 0    ( A − λ1 I | 0 ) =  1 −1 0 0  ∼   3 −3 1 0 2

2. Ominaisarvon λ1 = 1  2 0 3   2 0 1 − 0 . 3 0 0 0 0

1 0 −

2 2 Ominaisvektorit ovat siis muotoa ( r, r, r), missä r ∈ R, r = 6 0. Valitaan 3 3 näistä x1 = (2, 2, 3). Ominaisarvon λ2 = λ3 = 2, joka on kertalukua 2, ominaisvektorit taas saadaan laskemalla     1 −2 0 0 1 −2 0 0   0 0 0 , ( A − λ2 I | 0 ) = ( A − 2I | 0 ) =  1 −2 0 0  ∼  0 3 0 0 0 0 −3 0 0 2 joten ominaisvektoreita ovat kaikki vektorit (2r, r, s), missä r, s ∈ R \ {0}. Näistä voidaan valita kaksi lineaarisesti riippumatonta vektoria x2 = (0, 0, 1) ja x3 = (2, 1, 0). Nyt matriisit P, D, P−1 ovat  1      − 1 0 2 0 2 1 0 0  2   3    2 0 1 , D= 0 2 0  , P−1 =  P=  −3 1  . 2 3 1 0 0 0 2 1 −1 0 Tarkistuslaskulla nähdään, että A = PDP−1 . Esimerkissä 3.4 esiintynyt 3 × 3 -matriisi A ei ole diagonalisoituva, koska sillä on vain kaksi lineaarisesti riippumatonta ominaisvektoria. Tarkastellan lopuksi kahta diagonalisoituvuuden sovellutusta. Aloitetaan lineaarikuvauksen matriisin diagonalisointiin liittyvällä esimerkillä. Kun avaruuden Rn lineaarikuvauksen matriisi diagonalisoidaan, saadaan tietoa lineaarikuvauksen geometrisesta käyttäytymisestä.

3.5 Matriisien diagonalisointi

60

Esimerkki 3.36. Olkoon T : R2 → R2 lineaarikuvaus T (x, y) = (−9x − 24y, 4x + 11y).   −9 −24 Kuvauksen matriisin ME (T ) = ominaisarvot ovat λ1 = −1 ja 4 11 λ2 = 3 ja niihin kuuluvat ominaisvektorit x1 = (−3, 1) ja x2 = (2, −1). Silloin ME (T ) on diagonalisoituva. Tarkastellaan ominaisvektoreiden  x1 ja x2 −3 2 kuvia lineaarikuvauksessa diagonalisoinnin avulla. Matriisi P = 1 −1   −1 −2 ja P−1 = , joten −1 −3 

−9 −24 4 11



 =

−3 2 1 −1



−1 0 0 3



−1 −2 −1 −3

 .

Kerrotaan yhtälö puolittain matriisilla P, jolloin voidaan tarkastellaan matriisin P pystyrivien kuvautumista kuvauksessa T ,      −3 −3 −9 −24 , = −1 1 1 4 11      2 2 −9 −24 . =3 −1 −1 4 11 Kuvaus T siis vaihtaa vektorin x1 suunnan vastakkaiseksi ja venyttää vektoria x2 kolminkertaiseksi sen entiseen suuntaan. Koska joukko C = {x1 , x2 } on vektoriavaruuden R2 kannan, jokaisella v ∈ R2 vektorilla on yksikäsitteinen esitys vC = (a, b). eellisen perusteella siis, jos vC = (a, b) vektoriksi T (v)C = (−a, 3b).

Esimerkki 3.37. Diagonalisointuvuus nopeuttaa matriisin potenssien laskemista. Olkoon A diagonalisoituva matriisi n × n -matriisi, A = PDP−1 , missä   α1 0 ... 0  0 α2 . . . 0    D= . . ..  . . .  . . .  0 0 . . . αn Nyt −1 −1 −1 Ak = PDP · PDP | {z · · · PDP } kkpl

= PDIDI · · · IDP−1 = PDk P−1 .

3.5 Matriisien diagonalisointi

61

Diagonaalimatriisin potenssit on helppo laskea, nimittäin  k  α1 0 ... 0  0 αk . . . 0  2   k D = . .. ..  .  .. . .  k 0 0 . . . αn Nähdään, että diagonalisoituvan matriisin k :nnen potenssin laskemiseen riittää aina kaksi matriisikertolaskua ja n:n luvun αi potenssiin k korotusta. Olkoon A kuten esimerkissä 3.35. Lasketaan A23 .

Esimerkki 3.38.

Matlab

-ohjelmalla matriisin diagonalisoituvuuden voi tarkistaa eig-komennon avulla, ks. esimerkki 3.9.

62

4

Ryhmäteoriaa

Tässä luvussa käytetään seuraavia merkintöjä: Luonnollisten lukujen joukko on N = {0, 1, 2, . . . }, positiivisten kokonaislukujen joukko N+ = {1, 2, 3, . . . } ja kokonaislukujen joukko Z = {. . . , −2, −1, 0, 1, 2, . . . }. 4.1

Ryhmän määritelmä ja esimerkkejä

Ryhmä on algebrallinen systeemi, joka toteuttaa seuraavan määritelmän ehdot.

Määritelmä 4.1. Olkoon G joukko, jossa on määritelty sellainen binäärioperaatio ∗, että

R0. a ∗ b ∈ G kaikilla a, b ∈ G (G suljettu operaation ∗ suhteen), R1. a ∗ (b ∗ c) = (a ∗ b) ∗ c kaikilla a, b, c ∈ G (assosiatiivisuus), R2. on olemassa sellainen alkio e ∈ G, ns. neutraalialkio, että a ∗ e = a = e ∗ a kaikilla a ∈ G, R3. jokaista a ∈ G kohti on olemassa sellainen alkio a−1 ∈ G, ns. käänteisalkio, että a−1 ∗ a = e = a ∗ a−1 . Tällöin sanotaan, että pari (G, ∗) (tai jos sekaanuksen vaaraa ei ole, lyhyemmin G) on ryhmä. Jos lisäksi on voimassa ehto R4. a ∗ b = b ∗ a kaikilla a, b ∈ G, sanotaan, että G on kommutatiivinen ryhmä eli ns. Abelin ryhmä. Laskutoimitusta * nimitetään ryhmätoimitukseksi. Merkin * tilalla käytetään myös pistettä ·, mutta yleensä kirjoitetaan vain lyhyesti

ab = a ∗ b. Usein neutraalialkiota merkitään 1:llä tai 1G :llä ja sitä kutsutaan ryhmän ykkösalkioksi. Jos ryhmätoimitus on yhteenlasku, on neutraalialkiota tapana nimittää nolla-alkioksi 0 ja käänteisalkiota a−1 vasta-alkioksi −a. Jos n ∈ N+ , niin merkintä an tarkoittaa alkiota a ∗ a ∗ . . . ∗ a (missä a esiintyy n kertaa). Assosiatiivisuuden (ehto R1) nojalla sulkumerkkejä ei tarvitse kirjoittaa näkyviin. Sovitaan, että a0 = e ja a−n = (a−1 )n . Näin potenssi ak on määritelty kaikille kokonaisluvuille k . Potensseilla on helppo todistaa seuraavat laskusäännöt:

am an = am+n ,

(am )n = amn ,

(ab)−1 = b−1 a−1 ,

4.1 Ryhmän määritelmä ja esimerkkejä

63

kun a, b ∈ G ja n, m ∈ Z. Huomaa kuitenkin, että sääntö (ab)n = an bn on voimassa vain, jos ryhmä on Abelin ryhmä. Missä tahansa ryhmässä on voimassa seuraavat ns. supistussäännöt: Jos a, b, c ∈ G, niin

ab = ac =⇒ b = c

ja

ba = ca =⇒ b = c.

Ryhmätaulussa vaakarivit ja pystyrivit indek-

soidaan ryhmän alkioilla ja vaakarivin a ja pystyrivin b leikkauskohtaan merkitään alkio a ∗ b. Supistussääntöjen seurauksena taulukon jokaisella vaakarivillä jokainen ryhmän alkio esiintyy täsmälleen kerran, samoin käy pystyriveille. Vieressä on ainoan kolmen alkion ryhmän ryhmätaulu.

∗ 1 a b

1 1 a b

a a b 1

b b 1 a

Esimerkki 4.2. 1) Q∗ = Q \ {0}, R∗ = R \ {0}, C∗ = C \ {0} ovat kaikki

Abelin ryhmiä tavallisen kertolaskun suhteen. Ykkösalkiona on luku 1 ja luvun a käänteisalkiona on käänteisluku a−1 = 1/a. 2) Z∗ = Z \ {0} ei ole ryhmä kertolaskun suhteen. 3) Kääntyvien n × n -reaalilukumatriisien joukko

GL(n, R) = {A = (aij )n×n | det(A) 6= 0} on ryhmä matriisien kertolaskun suhteen. Siitä käytetään nimitystä yleinen lineaarinen ryhmä. Ykkösalkiona on identiteettimatriisi I ja matriisin A käänteisalkiona on käänteismatriisi A−1 . 4) Olkoon GL(n, Z) niiden ryhmään GL(n, R) kuuluvien matriisien joukko, joiden kaikki alkiot ovat kokonaislukuja. Tämä joukko GL(n, Z) ei ole ryhmä matriisien kertolaskun suhteen. 5) Z, Q, R, C ovat kaikki Abelin ryhmiä tavallisen yhteenlaskun + suhteen. 6) Ei-negatiivisten kokonaislukujen joukko ei ole ryhmä yhteenlaskun suhteen. 7) Mn (R) = { kaikki n × n -matriisit} on Abelin ryhmä matriisien yhteenlaskun suhteen. Nolla-alkiona on nollamatriisi   0 ... 0  .. ..   . . 

0 ... 0 ja matriisin A = (aij )n×n vasta-alkiona on vastamatriisi −A = (−aij )n×n . 8) Rn on Abelin ryhmä vektoreiden tavallisen yhteenlaskun suhteen. 9) Joukko C[a, b] = {f : [a, b] → R | f jatkuva } on Abelin ryhmä, kun määritellään f + g ehdolla

(f + g)(x) = f (x) + g(x) kaikilla x ∈ [a, b].

4.1 Ryhmän määritelmä ja esimerkkejä

64

Nolla-alkiona on nollafunktio

x → 0 kaikilla x ∈ [a, b] ja −f määräytyy ehdosta

(−f )(x) = −f (x) kaikilla x ∈ [a, b]. Tämä esimerkki antaa viitteitä siitä, että ryhmän käsitteellä on merkitystä myös algebran ulkopuolella, esim. analyysissa.

Esimerkki 4.3. Tarkastellaan seuraavaksi permutaatioita, ks. määritelmä ??.

Permutaatio määriteltiin joukon {1, 2, . . . , n} alkioiden muodostamana jonona (j1 , j2 , . . . , jn ) = α, missä kaikki luvut 1, 2, . . . , n esiintyvät jossakin järjestyksessä. Merkitään joukkoa {1, 2, . . . , n} = [n]. Permutaatio voidaan ajatella kuvauksena α : [n] → [n], missä α(i) = ji . Huomataan, että permutaatiota vastaava kuvaus on aina bijektio, koska kaikki joukon [n] alkiot esiintyvät tarkalleen yhden alkion kuvana. Toisaalta jokainen bijektio β joukolta [n] itselleen määrittelee permutaation (β(1), β(2), . . . , β(n)). Joukon [n] permutaatiot muodostavat ryhmän, kun operaationa on kuvausten yhdistys. Ykkösalkiona on permutaatio (1, 2, . . . , n), jota vastaava kuvaus on ns. identiteettikuvaus. Tästä ryhmästä käytetään merkitään Sn ja sitä kutsutaan n alkion symmetriseksi ryhmäksi. Huomaa, että ryhmässä Sn on n! alkiota. Permutaatio (α(1), α(2, . . . , α(n)) on kuvausten yhdistämisen yhteydessä yleensä selkeämpi kirjoittaa muodossa   1 2 ··· n . α(1) α(2) · · · α(n) Esimerkiksi ryhmässä S3 on seuraavat kuusi alkiota:       1 2 3 1 2 3 1 2 3 , α2 = , α3 = , α1 = 3 1 2 1 2 3 2 3 1

 α4 =

1 2 3 1 3 2



 , α5 =

1 2 3 2 1 3



 , α6 =

1 2 3 3 2 1

 .

missä esim. α2 tarkoittaa kuvausta, joka kuvaa ykkösen kakkoseksi, kakkosen kolmoseksi ja kolmosen ykköseksi. Permutaatiot aikaisemman määritelmämme mielessä ovat siis näiden alemmat rivit; ylärivihän näissä kaikissa on sama. Kuvausten yhdistäminen on helppoa, joten tässä ryhmässä laskutoimitus on hyvin konkreettinen: esimerkiksi      1 2 3 1 2 3 1 2 3 α4 ◦ α6 = = = α2 . 1 3 2 3 2 1 2 3 1

4.2 Kokonaisluvut ja jäännösluokat

65

Kuvausten yhdistämisessä on huomattava, että ensin operoidaan oikeanpuoleisella (α6 ) ja vasta sitten vasemmanpuoleisella kuvauksella (α4 ). Alkio α1  jota yleensä merkitään vain lyhyesti 1:llä  on ryhmän ykkösalkio. Ryhmä S3 ei ole kommutatiivinen, sillä esimerkiksi

α4 α6 = α2 ,

α6 α4 = α3 .

Yleisesti, jos M on jokin epätyhjä joukko, niin merkitään

S(M ) = {f : M → M | f on bijektio }. Bijektioita f ∈ S(M ) kutsutaan joukon M permutaatioiksi. Joukko S(M ) on selvästi ryhmä kuvausten yhdistämisen suhteen, ykkösalkiona identiteettikuvaus. Ryhmää S(M ) kutsutaan joukon M symmetriseksi ryhmäksi.

Lause 4.4.

Olkoot

G1 , . . . , Gn ryhmiä. Silloin karteesinen tulo

G1 × . . . × Gn = {(x1 , . . . , xn ) | xi ∈ Gi } on ryhmä operaation

(x1 , . . . , xn ) · (y1 , . . . , yn ) = (x1 y1 , . . . , xn yn ) suhteen. Tätä ryhmää kutsutaan ryhmien Todistus.

4.2

G1 , . . . , Gn suoraksi tuloksi.

Sivuutetaan.

Kokonaisluvut ja jäännösluokat

Tässä pykälässä käsitellään ns. jäännösluokkia ja niiden muodostamia ryhmiä. Aluksi käydään läpi tarvittavia lukuteoreettisia peruskäsitteitä.

Jaollisuudesta Määritelmä 4.5. Olkoot a ja b kokonaislukuja ja a 6= 0. Sanotaan, että a jakaa luvun b (tai b on jaollinen luvulla a tai a on luvun b tekijä), jos on

olemassa sellainen kokonaisluku k , että

b = ka. Tällöin merkitään a | b. Jos a ei jaa lukua b, merkitään a 6 | b.

Lause 4.6.

a | b ja a | c, niin a | (b + c). 2. Jos a | b, niin myös a | bc kaikille c ∈ Z. 3. Jos a | b ja b | c, niin a | c.

Todistus.

1. Jos

Sivuutetaan.

4.2 Kokonaisluvut ja jäännösluokat

66

Määritelmä 4.7. Kokonaislukua p ≥ 2 sanotaan alkuluvuksi, jos sen ainoat positiiviset tekijät ovat 1 ja p. Jos n ≥ 2 ei ole alkuluku, se on yhdistetty luku. Esimerkki 4.8. Luku 1 ei ole alkuluku. Pienimmät alkuluvut ovat 2, 3, 5,

7, 11, 13, 17, 19, 23, . . .

Lause 4.9 (Aritmetiikan peruslause).

Jokainen positiivinen kokonaisluku

n ≥ 2 voidaan kirjoittaa alkulukujen tulona. Tällainen esitys on tekijöiden järjestystä lukuunottamatta yksikäsitteinen. Todistus.

Sivuutetaan.

Alkulukua, joka esiintyy luvun a tekijänä kutsutaan luvun a alkuteki-

jäksi.

Lause 4.10.

Alkulukuja on äärettömän paljon.

Oletetaan, että p1 , . . . , pk ovat ainoat alkuluvut ja tarkastellaan lukua n = 1+p1 . . . pk . Luku n voidaan kirjoittaa alkulukujen tulona. Olkoon p jokin luvun n alkutekijöistä. Jos muita alkulukuja kuin p1 , . . . , pk ei ole olemassa, niin p on niistä jokin, sanotaan p = pi . Tällöin p jakaa luvun n − p1 . . . pk = 1, mikä on ristiriita.

Todistus.

Lause 4.11.

n on yhdistetty luku, niin luvulla n on alkulukutekijä, joka √ on suuruudeltaan enintään n. Todistus.

Jos

Sivuutetaan.

Jos x ∈ R, merkitään

bxc = { suurin kokonaisluku ≤ x}. Selvästi

x − 1 < bxc ≤ x.

Lause 4.12.

(11)

Olkoon

a kokonaisluku ja d positiivinen kokonaisluku. Silloin on olemassa yksikäsitteiset sellaiset kokonaisluvut q ja r , että a = dq + r,

0 ≤ r < d.

Valitaan q = ba/dc, r = a − dq . Väite on voimassa, koska kaavan (11) nojalla Todistus.

0=a−d

a a ≤ r = a − dq < a − d( − 1) = d, d d

ts. 0 ≤ r < d. Jos myös q 0 ja r0 toteuttaisivat ehdot a = dq 0 + r0 ja 0 ≤ r < d, niin 0 dq + r0 = dq + r ja siis d(q − q 0 ) = r0 − r. Näin luku r0 − r on jaollinen luvulla d ja toisaalta −d < r0 − r < d, joten r0 − r = 0, ts. r0 = r. Tällöin välttämättä myös q 0 = q .

4.2 Kokonaisluvut ja jäännösluokat

67

Määritelmä 4.13. Olkoot a ja b kokonaislukuja, jotka eivät molemmat ole nollia. Jos d on sellainen positiivinen kokonaisluku, että d|a ja

ja

d|b

aina, jos c | a ja c | b, niin myös c | d,

niin lukua d kutsutaan lukujen a ja b suurimmaksi yhteiseksi tekijäksi. Jos tällainen luku on olemassa, niin se on selvästi yksikäsitteinen ja sille käytetään merkintää syt(a, b). Seuraava lause osoittaa, että syt(a, b) on aina olemassa ja antaa nopean algoritmin sen löytämiseksi.

Lause 4.14 (Eukleideen algoritmi).

Kokonaislukujen

a ja b 6= 0 suurin

yhteinen tekijä voidaan aina laskea soveltamalla lausetta 4.12 toistuvasti:

a = q1 |b| + r1 ,

0 < r1 < |b|,

|b| = q2 r1 + r2 ,

0 < r2 < r1 ,

r1 = q3 r2 + r3 ,

0 < r3 < r2 ,

.. .

.. .

rn−2 = qn rn−1 + rn ,

0 < rn < rn−1 ,

rn−1 = qn+1 rn . Prosessi päättyy, koska

r1 > r2 > r3 > . . . ja luvut ri ovat ei-negatiivisia

kokonaislukuja. Tällöin

syt(a, b) = rn = viimeisen jakolaskun jakaja. Lisäksi tällä menetelmällä löydetään aina sellaiset kokonaisluvut

u ja v , että

ua + vb = syt(a, b). Todistus.

Kulkemalla yhtälöketjussa alhaalta ylöspäin todetaan, että

rn | rn−1 , rn | qn rn−1 + rn = rn−2 , . . . , rn | b, rn | a. Kulkemalla ylhäältä alaspäin todetaan, että

c | a, c | b, c | r1 , . . . , c | rn . Siis rn = syt(a, b). Lisäksi kulkemalla taas alhaalta ylöspäin saadaan

rn = rn−2 − qn rn−1 = rn−2 − qn (rn−3 − qn−1 rn−2 ) = −qn rn−3 + (1 + qn−1 qn )rn−2 ... = ua + vb, joka on vaadittu kokonaislukuesitys suurimmalle yhteiselle tekijälle.

4.2 Kokonaisluvut ja jäännösluokat Lause 4.15.

Jos

68

p on alkuluku ja p | ab, niin p | a tai p | b.

Jos p6 | a, niin syt(a, p) = 1 koska p on alkuluku. Edellisen lauseen nojalla on siis olemassa sellaiset kokonaisluvut s ja t, että 1 = sa + tp. Kertomalla tämä puolittain luvulla b saadaan b = sab + tpb, mistä nähdään, että p | b. Todistus.

Kongruenssi ja jäännösluokat modulo n. Jos a on kokonaisluku ja n positiivinen kokonaisluku, niin lauseen 4.12 nojalla on olemassa yksikäsitteiset kokonaisluvut q ja r, joille a = qn + r, 0 ≤ r < n. Lukua r sanotaan luvun a jäännökseksi modulo n. Selvästi kahdella luvulla on sama jäännös modulo n tarkalleen silloin, kun niiden erotus on jaollinen luvulla n. Seuraavan määritelmän avulla useat jaollisuustarkastelut voidaan muuttaa muotoon, joka on monessa suhteessa analoginen yhtälöiden ja yhtälöryhmien teorian kanssa. Määritelmä 4.16. Oletetaan, että n on positiivinen kokonaisluku ja a, b ∈

Z. Jos

n | a − b, sanotaan että a on kongruentti luvun b kanssa modulo n ja merkitään

a ≡ b (mod n).

Esimerkki 4.17. 12 ≡ 3 (mod 9), 5 ≡ −1 (mod 3), a ≡ b (mod 2) jos ja vain jos a ja b ovat molemmat parillisia tai molemmat parittomia. Lause 4.18. vuista 2. 3. 4. 5.

1. Jokainen kokonaisluku on kongruentti tarkalleen yhden lu-

0, 1, . . ., n − 1 kanssa modulo n. Aina a ≡ a (mod n). Jos a ≡ b (mod n), niin b ≡ a (mod n). Jos a ≡ b (mod n) ja b ≡ c (mod n), niin myös a ≡ c (mod n). Jos a ≡ b (mod n) ja c ≡ d (mod n), niin a + c ≡ b + d (mod n)

ja

ac ≡ bd (mod n). 6. Jos

ca ≡ cb (mod n) ja lisäksi syt(c, n) = 1, niin a ≡ b (mod n).

Kohdat 1, 2 ja 3 ovat selviä lauseen 4.12 nojalla, kohta 4 ja kohdan 5 ensimmäinen väite helppoja. Kohdan 5 jälkimmäinen väite nähdään seuraavasti. Koska a ≡ b (mod n), niin n | a − b ja tietysti myös n | c(a − b), joten ac ≡ bc (mod n)  siis kongruessin molemmat puolet saa kertoa samalla kokonaisluvulla. Näin ollen myös bc ≡ bd (mod n) ja siis ac ≡ bc ≡ bd (mod n) kohdan 4) nojalla. Todistus.

4.2 Kokonaisluvut ja jäännösluokat

69

Todistetaan vielä kohta 6. Lauseen 4.14 nojalla  koska syt(c, n) = 1  on olemassa sellaiset kokonaisluvut u ja v , että uc + vn = 1. Näin ollen

n | uc(a − b) + vn(a − b) = a − b.

Soveltamalla edellisen lauseen kohdan 5 jälkimmäistä väitettä useita kertoja peräkkäin todetaan, että ehdosta a ≡ b (mod n) seuraa, että ak ≡ bk (mod n) kaikilla positiivisilla kokonaisluvuilla k .

Esimerkki 4.19. Selvitetään, mikä on jakojäännös, kun luku 12120 + 1 jae-

taan luvulla 7. On siis selvitettävä, minkä luvuista 0, 1, . . . , 6 kanssa luku 12120 + 1 on kongruentti modulo 7. Koska 12 ≡ 5 (mod 7), on 12120 ≡ 5120 (mod 7). Edelleen 5120 = (52 )60 = 2560 ja 25 ≡ 4 (mod 7), joten

12120 ≡ 5120 ≡ 2560 ≡ 460 . Samalla tavalla jatkamalla todetaan, että

460 = 6420 ≡ 120 = 1 ja siis

(mod 7)

12120 + 1 ≡ 460 + 1 ≡ 1 + 1 = 2

(mod 7).

Kysytty jakojäännös on siis 2.

Määritelmä 4.20. Olkoon a jokin kokonaisluku. Luvun a määräämällä jäännösluokalla modulo n tarkoitetaan joukkoa {x ∈ Z | x ≡ a (mod n)}. Tätä merkitään myös symbolilla a (jolloin luku n ajatellaan tunnetuksi). Aina a ∈ a.

Esimerkki 4.21. Jos n = 5, niin 2 = {x ∈ Z | x ≡ 2

(mod 5)}

= {. . . , −8, −3, 2, 7, 12, 17, . . .} = {2 + 5k | k ∈ Z}.

Lause 4.22.

Oletetaan, että n on kiinnitetty. a = b ⇔ a ≡ b (mod n) ⇔ n | a − b. 2. Jos a = a0 ja b = b0 , niin 1.

a + b = a0 + b0 3. Kaikki jäännösluokat modulo

ja

ab = a0 b0 .

n ovat 0, . . . , n − 1.

4.2 Kokonaisluvut ja jäännösluokat

70

1. Jos a = b, niin a ∈ a = b, joten a ≡ b (mod n). Kääntäen, jos a ≡ b (mod n), nin

Todistus.

x ∈ a ⇔ x ≡ a (mod n) ⇔ x ≡ b (mod n) ⇔ x ∈ b. 2. Koska a = a0 ja b = b0 , niin kohdan 1) nojalla a ≡ a0 (mod n) ja b ≡ b0 (mod n). Lauseen 4.18 kohdan 5) nojalla a + b ≡ a0 + b0 (mod n) ja ab ≡ a0 b0 (mod n) ja jälleen kohdan 1) nojalla a + b = a0 + b0 ja ab = a0 b0 . 3. Jäännösluokat 0, 1, . . . , n − 1 ovat kaikki eri joukkoja kohdan 1) nojalla; muita ei ole lauseen 4.18 kohdan 1) nojalla. Vaikka 0, . . . , n − 1 ovat kaikki jäännösluokat modulo n, niin samasta jäännösluokasta voidaan tietysti käyttää useita eri nimiä. Esim. jos n = 5, niin 2 = 7 = −3.

Määritelmä 4.23. Joukolle, jonka alkioina ovat kaikki jäännösluokat modulo n, käytetään merkintää Zn : Zn = {0, 1, . . . , n − 1}. Joukossa Zn voidaan edellisen lauseen kohdan 2) perusteella määritellä yhteenja kertolasku asettamalla a+b=a+b ja

a · b = ab. Näin Zn on oikeastaan joukoista koostuva joukko. Ääretön joukko Z on jaettu äärellisen moneen palaan 0, . . . , n − 1.

Esimerkki 4.24. Z2 = {0, 1}, missä ja

0 = {. . . , −2, 0, 2, 4, . . .} = {parilliset luvut} 1 = {. . . , −3, −1, 1, 3, . . .} = {parittomat luvut}.

Esimerkiksi 0 + 0 = 0 + 0 = 0, 1 + 1 = 1 + 1 = 0, 1 · 1 = 1 · 1 = 1.

Esimerkki 4.25. Z3 = {0, 1, 2}, missä

0 = {. . . , −3, 0, 3, 6, . . .} 1 = {. . . , −2, 1, 4, 7, . . .} 2 = {. . . , −1, 2, 5, 8, . . .}. Esimerkiksi 2 + 1 = 3 = 0 ja 2 · 2 = 2 · 2 = 4 = 1.

4.2 Kokonaisluvut ja jäännösluokat

71

Joukko Zn on ryhmä operaation a + b = a + b suhteen. Aikaisemmin osoitettiin, että tämä on hyvin määritelty operaatio, siis jäännösluokkien edustajien valinnasta riippumaton. Ryhmäaksioomat on helppo todeta oikeiksi, 0 on nolla-alkio ja −a on alkion a vasta-alkio. Koska joukossa Zn on n alkiota, on kyseessä ns. äärellinen ryhmä. Edellä määriteltiin jäännösluokille myös kertolasku a · b = ab ja todettiin, että tämä on hyvin määritelty. Kuitenkaan Zn  tai aina edes Zn \ {0}  ei ole ryhmä tämän operaation suhteen, sillä kaikilla a ∈ Zn ei ole käänteisalkiota joukossa Zn . Kuitenkin seuraava tulos on voimassa.

Lause 4.26.

Olkoon

n > 1 ja Z∗n = {a ∈ Zn | syt(a, n) = 1}.

Z∗n on Abelin ryhmä jäännösluokkien kertolaskun suhteen. Ryhmän ∗ Zn alkioita kutsutaan alkuluokiksi mod n. Silloin

Ensinnäkin, jos syt(a, n) = 1 ja a ≡ b (mod n), niin myös syt(b, n) = 1. Jos nimittäin c | b ja c | n, niin c | (a − b) + b = a ja näin c | syt(a, n) = 1. Joukon Z∗n määritelmä on siis mielekäs, ts. jäännösluokan edustajan valinnasta riippumaton. Jos a ∈ Z∗n ja b ∈ Z∗n , niin myös a · b ∈ Z∗n . Täten Z∗n on suljettu kyseisen operaation suhteen. Assosiatiivisuus ja ykkösalkion olemassaolo (= 1) ovat ilmeisiä. Olkoon a ∈ Z∗n . Koska syt(a, n) = 1, on olemassa sellaiset kokonaisluvut u ja v , että au + vn = 1. (12) Todistus.

Täten

1 = au + vn = a · u + vn = a · u. Yhtälöstä (12) nähdään, että syt(u, n) = 1, joten u ∈ Z∗n . Siis u on alkion a käänteisalkio. Näin on osoitettu, että jokaisella alkiolla on käänteisalkio.

Määritelmä 4.27. Ryhmän Z∗n kertaluvulle (= alkioiden lukumäärälle) käytetään merkintää ϕ(n). Funktiota ϕ nimitetään Eulerin ϕ-funktioksi. Jos p on alkuluku, niin Z∗p = Zp \ {0} ja siten ϕ(p) = p − 1.

Esimerkki 4.28. Z∗9 = {1, 2, 4, 5, 7, 8}, ϕ(9) = 6 ja esimerkiksi 4−1 = 7, 8

−1

= 8.

Sopimus. Kun puhutaan ryhmästä Zn tarkoitetaan, että ryhmätoimitukse-

na on yhteenlasku; samalla tavalla ryhmässä GL(n, R) operaatioksi ajatellaan aina matriisikertolasku, ryhmässä Z∗n kertolasku ja ryhmässä Sn edellä kuvattu kuvausten yhdistäminen.

4.3 Aliryhmä 4.3

72

Aliryhmä

Määritelmä 4.29. Ryhmän (G, ·) osajoukko H muodostaa ryhmän G aliryhmä, jos (H, ·) on ryhmä, ts. H on itse ryhmä ryhmän G laskutoimituksen

suhteen. Tällöin merkitään H ≤ G.

Esimerkki 4.30. (Z, +) ≤ (Q, +) ≤ (R, +) ≤ (C, +).    1 2 3 1 Esimerkki 4.31. Joukko H = { , 1 2 3 1  1 2 aliryhmä, mutta yhden alkion osajoukko { 1 3 aliryhmä.

Lause 4.32 (Aliryhmäkriteeri). män

Ryhmän

 2 3 } on ryhmän S3 3 2  3 } ei ole ryhmän S3 2

G epätyhjä osajoukko H on ryh-

G aliryhmä, jos ja vain jos seuraava ehto on voimassa: jos

h1 , h2 ∈ H, niin myös h−1 1 h2 ∈ H.

(13)

⇒: Jos H on aliryhmä, ja h1 , h2 ∈ H , niin samoin h−1 1 ∈ H ja h1−1 h2 ∈ H , koska aliryhmä sisältää alkioiden käänteisalkiot ja on suljettu ryhmätoimituksen suhteen. ⇐: Oletetaan, että ehto (13) on voimassa ryhmän G osajoukolle H . Koska H on epätyhjä, voidaan valita jokin alkio h ∈ H . Ehdon (13) nojalla

Todistus.

1G = h−1 h ∈ H, joten määritelmän ehto (R2) on voimassa. Nyt jokaiselle h ∈ H on voimassa

h−1 = h−1 1 ∈ H, joten jokaisella alkiolla h ∈ H on käänteisalkio joukossa H , eli (R3) on voimassa. Jos h1 , h2 ∈ H , niin siis h−1 1 ∈ H , ja ehdon (13) nojalla −1 h1 h2 = (h−1 1 ) h2 ∈ H,

ja siis ehto (R0) on voimassa. Assosiatiivisuus (R1) on voimassa koko ryhmässä G ja sitä suuremmalla syyllä sen osajoukossa H .

Esimerkki 4.33. Ryhmän GL(n, R) = {An×n | det(A) 6= 0} osajoukko SL(n, R) = {A ∈ GL(n, R) | det(A) = 1} on sen aliryhmä, sillä SL(n, R) on epätyhjä, ja jos A, B ∈ SL(n, R), niin

det(A−1 B) = det(A−1 ) det(B) =

det(B) = 1, det(A)

ts. A−1 B ∈ SL(n, R). Aliryhmäkriteerin ehdot ovat siis voimassa.

4.4 Ryhmän generointi

73

Määritelmä 4.34. Jos G on ryhmä, niin aina {1G } ja G itse ovat ryhmän G aliryhmiä. Näitä kutsutaan ryhmän G triviaaleiksi aliryhmiksi. Lause 4.35.

Oletetaan, että

myös leikkaus

Hi on ryhmän G aliryhmä kaikilla i ∈ I . Silloin ∩i∈I Hi on ryhmän G aliryhmä.

Sovelletaan aliryhmäkriteeriä. Ensinnäkin kyseinen leikkaus on epätyhjä, koska 1G ∈ Hi jokaisella i ∈ I . Jos h1 , h2 ∈ ∩i∈I Hi , niin silloin kaikilla indeksin arvoilla h1 , h2 ∈ Hi ja (aliryhmäkriteerin nojalla) h−1 1 h2 ∈ Hi , eli h−1 h ∈ ∩ H . 2 i∈I i 1 Todistus.

4.4

Ryhmän generointi

Määritelmä 4.36. Olkoon M jokin ryhmän G osajoukko. Aina on olemassa

sellaisia ryhmän G aliryhmiä, jotka sisältävät joukon M osajoukkonaan  ainakin G itse on tällainen. Muodostetaan kaikkien tällaisten aliryhmien leikkaus ja merkitään sitä symbolilla hM i. Siis \ hM i = H. M ⊆H,H≤G

Edellisen lauseen nojalla hM i on ryhmän G aliryhmä, ja sitä sanotaan joukon M generoimaksi aliryhmäksi. Sanotaan myös, että M generoi ryhmän hM i. Edellisestä määritelmästä nähdään, että jos K on mikä tahansa aliryhmä joka sisältää joukon M osajoukkonaan, niin \ hM i = H ⊆ K, M ⊆H,H≤G

koska K on yksi leikkauksessa mainituista joukoista. Näin hM i on pienin sellainen ryhmän G aliryhmä, joka sisältää joukon M .

Lause 4.37.

Epätyhjän joukon

M ⊆ G generoima aliryhmä koostuu tarkalleen niistä ryhmän G alkioista, jotka ovat muotoa x1 x2 . . . xk , missä k on positi−1 ivinen kokonaisluku ja ja kullakin indeksin i arvolla xi ∈ M tai xi ∈ M . Olkoon H kaikkien tätä muotoa olevien alkioiden joukko. Selvästi kaikki tätä muotoa olevat alkiot sisältyvät jokaiseen ryhmän G aliryhmään, joka sisältää joukon M osajoukkonaan. Näin H ⊆ hM i. Edelleen M ⊆ H , joten riittää osoittaa, että H ≤ G, jolloin hM i ⊆ H . Luonnollisesti H 6= ∅, koska M ⊆ H . Jos x, y ∈ H ja x = x1 . . . xk , missä xi ∈ M tai x−1 i ∈ M (i = 1, . . . , k ), ja y = y1 . . . ys , missä yj ∈ M tai yj−1 ∈ M (j = 1, . . . , s), niin Todistus.

−1 −1 x−1 y = x−1 k xk−1 . . . x1 y1 y2 . . . ys ,

joka on edelleen kyseistä muotoa ja siis kuuluu joukkoon H . Näin aliryhmäkriteerin nojalla H ≤ G.

4.5 Aliryhmän sivuluokat ja Lagrangen lause

74



   1 2 3 1 2 3 Esimerkki 4.38. Permutaatiot a = ja b = gen2 3 1 1 3 2 eroivat koko symmetrisen ryhmän S3 , sillä laskemalla nähdään, että a, a2 , a3 = 1, b, ab ja a2 b ovat kaikki ryhmän S3 alkiot. Lisäksi on voimassa ba = a2 b.

Määritelmä 4.39. Jos G = hM i ja M = {x1 , . . . , xn } on äärellinen joukko, sanotaan, että G on äärellisesti generoitu ja merkitään G = hx1 , . . . , xn i. Erityisen tärkeä erikoistapaus äärellisesti generoidusta ryhmästä on syklinen ryhmä.

Määritelmä 4.40. Ryhmää kutsutaan sykliseksi, jos sen generoi yksi ainoa alkio, ts. ryhmä G on syklinen, jos on olemassa sellainen g ∈ G, että G = hgi. Esimerkki 4.41. Ryhmät (Z, +) = h1i ja (Zn , +) = h1i ovat syklisiä. Koska

myös (Z, +) = h−1i, ei syklisen ryhmän generoija ole yksikäsitteinen.

Lauseen 4.37 nojalla syklisen ryhmän G = hxi kaikki alkiot ovat muotoa xn , missä n ∈ Z. Itse asiassa siis

hxi = {xn | n ∈ Z}. Koska xn xm = xn+m = xm xn (tämä pätee myös negatiivisilla lukujen n ja m arvoilla), niin jokainen syklinen ryhmä on Abelin ryhmä.

Lause 4.42.

Ryhmän

Z jokainen aliryhmä on syklinen.

Oletetaan, että H on ryhmän Z aliryhmä. Jos H = {0}, on H = h0i. Oletetaan siis, että k ∈ H , k 6= 0. Joko k tai −k ∈ H on positiivinen. Olkoon d pienin positiivinen kokonaisluku, joka kuuluu aliryhmään H . Olkoon nyt k ∈ H mielivaltainen. Lauseen 4.12 nojalla voidaan kirjoittaa k = dq + r, missä 0 ≤ r < d. Koska H on aliryhmä, niin r = k − dq ∈ H , joten luvun d määritelmän nojalla r = 0. Tämä osoittaa, että H = hdi = {nd | n ∈ Z}. Todistus.

4.5

Aliryhmän sivuluokat ja Lagrangen lause

Määritelmä 4.43. Olkoon H ≤ G ja a ∈ G. Joukkoa aH = {ah ∈ G | h ∈ H} sanotaan alkion a määräämäksi aliryhmän H vasemmaksi sivuluokaksi ryhmässä G. Vastaavasti

Ha = {ha ∈ G | h ∈ H} on alkion a määräämä aliryhmän H oikea sivuluokka.

4.5 Aliryhmän sivuluokat ja Lagrangen lause

75

Jos ryhmätoimitus on yhteenlasku, vasemmalle sivuluokalle on luonnollista käyttää merkintää a + H . Tällöin siis

a + H = {a + h | h ∈ H}.

Esimerkki 4.44. Tarkastellaan ryhmää (Z4 , +), jossa Z4 = {0, 1, 2, 3}.

Joukko H = {0, 2} on ryhmän Z4 aliryhmä. Esimerkiksi alkion 1 määräämä vasen sivuluokka on joukko 1+H = {1+h | h ∈ H} = {1+0, 1+2} = {1, 3}. Jatkossa tarkastellaan vain vasempia sivuluokkia. Täsmälleen samat tulokset pätevät myös oikeille sivuluokille.

Lause 4.45. aH = bH ⇔ a ∈ bH ⇔ a = bh

jollakin

h ∈ H.

⇒: Koska 1 ∈ H , niin a = a · 1 ∈ aH = bH . ⇐: Oletetaan siis, että a ∈ bH , ts. a = bh jollekin h ∈ H , ja osoitetaan, että aH = bH . Jos x ∈ aH , niin on olemassa h0 ∈ H , jolle x = ah0 ja näin x = ah0 = bhh0 ∈ bH . Siis aH ⊆ bH . Jos x ∈ bH , niin on olemassa h00 ∈ H , jolle x = bh00 ja näin x = bh00 = ah−1 h00 ∈ aH . Siis bH ⊆ aH . Todistus.

Lause 4.46.

Tarkastellaan ryhmän

1. Jokainen ryhmän

G aliryhmän H vasempia sivuluokkia. G alkio kuuluu täsmälleen yhteen sivuluokkaan.

2. Jokaisessa sivuluokassa on sama määrä alkioita. 3. Aliryhmä

H on itse sivuluokka, nimittäin H = 1H . G/H .

Kaikkien sivuluokkien joukolle käytetään merkintää

1. Jos x ∈ G, niin x = x · 1 ∈ xH . Jos myös x ∈ yH , niin lauseen 4.45 nojalla xH = yH . 2. Kuvaus f : aH → bH , f (ah) = bh on selvästi bijektio, joten joukoissa aH ja bH on sama määrä alkioita. Kohta 3. on ilmeinen.

Todistus.

Esimerkki 4.47. Tarkastellaan jälleen ryhmää G = S3 , Esimerkissä 4.38 todettiin, että S3 = {1, a, a2 , b, ab, a2 b} ja että a3 = 1 ja ba = a2 b, kun     1 2 3 1 2 3 a= ja b= . 2 3 1 1 3 2 Olkoon H = {1, b}. Koska b2 = 1, on H ≤ S3 . Nyt

1H = H aH = {a, ab} a2 H = {a2 , a2 b} bH = H (ab)H = aH (a2 b)H = a2 H

H1 = H Ha = {a, a2 b} Ha2 = {a2 , ab} Hb = H H(ab) = Ha2 H(a2 b) = Ha.

4.5 Aliryhmän sivuluokat ja Lagrangen lause

76

On siis kolme eri vasenta (ja oikeata) aliryhmän sivuluokkaa,

G/H = {H, aH, a2 H}, ja

G = H ∪ aH ∪ a2 H = H ∪ Ha ∪ Ha2 .

Kuitenkin aH 6= Ha, joten alkion a määrämät vasen ja oikea sivuluokka voivat olla eri joukkoja. Merkitään seuraavassa ryhmän K kertalukua (= alkioiden lukumäärää) |K|:lla. Seuraavan tärkeän lauseen todistus saadaan nyt helposti.

Lause 4.48 (Lagrange). män

Olkoon G äärellinen ryhmä ja H ≤ G. Jos aliryhH vasempien sivuluokkien lukumäärä ryhmässä G on i, niin

|G| = i|H|. Erityisesti siis ryhmän Todistus.

H kertaluku jakaa ryhmän G kertaluvun.

Väite on voimassa, koska

G = H ∪ a1 H ∪ . . . ∪ ai−1 H ja kaikilla indeksin t arvoilla

|at H| = |H|.

Etsittäessä jonkin äärellisen ryhmän G aliryhmiä Langrangen lause rajoittaa voimakkaasti mahdollisuuksia. Esim. jos |G| = 10, niin ainoastaan sellaiset ryhmän G osajoukot, joissa on 2 tai 5 alkiota, voivat muodostaa G:n epätriviaaleja aliryhmiä.

Määritelmä 4.49. Sanotaan, että alkio a ∈ G on ääretöntä kertalukua, jos ak 6= 1G kaikille k ∈ Z \ {0}. Muussa tapauksessa on olemassa sellainen pienin positiivinen kokonaisluku n, että an = 1G . Tätä lukua n sanotaan alkion a kertaluvuksi ryhmässä G. Lause 4.50. Olkoon G ryhmä ja a ∈ G. Silloin alkion a kertaluku ryhmässä G ja alkion a generoiman syklisen aliryhmän hai = {ak | k ∈ Z} kertaluku ovat yhtäsuuret.

Jos kaikki alkiot ak , k ∈ Z ovat erisuuria, on hai ääretön, ja samoin on tietysti alkion a kertaluku, koska ak = 1G vain arvolla k = 0. Todistus.

4.5 Aliryhmän sivuluokat ja Lagrangen lause

77

Toinen vaihtoehto on, että ak = am joillekin m, k ∈ Z, m > k . Tällöin a = 1G , joten on olemassa pienin sellainen positiivinen kokonaisluku n, jolle an = 1G . Osoitetaan, että m−k

hai = {1, a, a2 , . . . , an−1 }. Luvun n määritelmän nojalla oikealla puolella luetellut alkiot ovat kaikki eri alkioita. Riittää osoittaa, että jokainen alkio ak , missä k ∈ Z, löytyy oikealta puolelta. Näin on, koska lauseen 4.12 nojalla voidaan kirjoittaa k = nq + r, missä 0 ≤ r < n, ja ak = anq+r = (an )q ar = ar .

Lagrangen lause antaa nyt välittömänä seurauksena seuraavan tuloksen.

Lause 4.51.

Olkoon

jakaa ryhmän

G äärellinen ryhmä ja a ∈ G. Silloin alkion a kertaluku G kertaluvun. Näin ollen a|G| = 1G .

Esimerkki 4.52. Tarkastellaan jälleen ryhmää S3 ja käytetään esimerkin

4.38 merkintöjä. Alkion 1 kertaluku on tietysti 1. Alkion a kertaluku on 3, sillä a 6= 1, a2 6= 1, mutta a3 = 1. Alkion a2 kertaluku on niin ikään 3, sillä a2 6= 1, a4 = a3 a = a 6= 1, mutta (a2 )3 = a3 a3 = 1. Kaikkien muiden alkioiden kertaluku on 2, kuten on helppoa todeta suoralla laskulla. Esimerkiksi alkiolle ab 6= 1 riittää todeta, että (ab)2 = abab = aa2 bb = 1 (tässä käytettiin aikaisemmin saatua kaavaa ba = a2 b. Kaikki kertaluvut ovat ryhmän kertaluvun 6 tekijöitä, kuten edellisen lauseen perusteella tiedettiinkin. Sovelletaan edellistä lausetta ryhmiin Z∗n .

Lause 4.53 (Eulerin lause).

Olkoon

G = (Z∗n , ·). Silloin kaikille a ∈ Z∗n

pätee

aϕ(n) = 1, ts.

aϕ(n) ≡ 1

(mod n) , jos a ∈ Z, syt(a, n) = 1.

Jos p on alkuluku, niin triviaalisti ϕ(p) = p − 1.

Lause 4.54 (Fermat'n pieni lause). nen luvulla

Jos

p on alkuluku ja a ∈ Z ei ole jaolli-

p, niin ap−1 ≡ 1

(mod p).

4.6 Normaali aliryhmä ja tekijäryhmä 4.6

78

Normaali aliryhmä ja tekijäryhmä

Määritelmä 4.55. Ryhmän G aliryhmää N sanotaan normaaliksi aliryhmäksi, jos aN = N a kaikille a ∈ G.

Tällöin merkitään N  G. Ehto aN = N a merkitsee, että jokainen tulo an, n ∈ N , voidaan kirjoittaa muodossa an = n1 a jollekin sopivalle n1 ∈ N , jonka ei tarvitse olla sama kuin n.

Lause 4.56.

Jos

G on Abelin ryhmä, niin jokainen ryhmän G aliryhmä on

normaali aliryhmä.

Esimerkki 4.57. Ryhmän S3 aliryhmä H = {1, b} ei ole normaali, sillä

esimerkissä 4.47 todettiin, että

aH = {a, ab} = 6 Ha = {a, a2 b}. Sen sijaan aliryhmä N = hai = {1, a, a2 } on normaali. On näet helppo todeta, että xN = N = N x kaikilla x ∈ N ja

xN = {b, ab, a2 b} kaikilla x ∈ N.

Normaalin aliryhmän merkitys on siinä, että sivuluokkien joukolle G/H voidaan luonnollisella määritellä ryhmän rakenne, jos (ja itse asiassa vain jos) H on normaali aliryhmä.

Lause 4.58.

Olkoon

(G, ·) ryhmä ja N  G. Silloin sivuluokkien joukko G/N = {aN | a ∈ G}

on ryhmä operaation

aN · bN = (ab)N kaikilla a, b ∈ G suhteen. Näin saatua ryhmää

G/N kutsutaan ryhmän G tekijäryhmäksi

N :n suhteen. Todistus. 1) Osoitetaan ensin, että näin määritelty operaatio on hyvinmääritelty, ts. sivuluokkien edustajista riippumaton. Olkoon siis aN = a0 N ja

bN = b0 N . Silloin a = a0 n1 ja b = b0 n2 joillekin n1 , n2 ∈ N . Koska N on normaali, tiedetään, että n1 b0 ∈ N b0 = b0 N , joten n1 b0 = b0 n3 jollekin n3 ∈ N . Nyt saadaan ab = a0 (n1 b0 )n2 = a0 (b0 n3 )n2 = a0 b0 (n3 n2 ) ∈ a0 b0 N,

4.6 Normaali aliryhmä ja tekijäryhmä

79

joten (ab)N = (a0 b0 )N . 2) Assosiatiivisuus:

aN · (bN · cN ) = aN · bcN = a(bc)N = (ab)cN = abN · cN = (aN · bN ) · cN. 3) Ykkösalkiona toimii sivuluokka N = 1N , sillä

1N · aN = aN = aN · 1N. 4) Alkion aN käänteisalkio on a−1 N , sillä

aN · a−1 N = (aa−1 )N = N = (a−1 a)N = a−1 N · aN.

Esimerkki 4.59. Jos G = S3 ja N = {1, a, a2 }, niin esimerkin 4.57 nojalla

N on normaali ja tekijäryhmässä G/N on kaksi alkiota N ja bN ; siis G/N = {N, bN }. Selvästi N · bN = bN · N = bN , N · N = N ja bN · bN = b2 N = 1N = N . Siis G/N on kahden alkion syklinen ryhmä. Jos G on äärellinen ryhmä, niin Lagrangen lauseen nojalla |G/N | = |G|/|N |. Jos ryhmätoimitus ryhmässä G on yhteenlasku ja N on ryhmän G normaali aliryhmä, niin sivuluokkien välinen laskutoimitus tekijäryhmässä saa muodon (a + N ) + (b + N ) = (a + b) + N.

Esimerkki 4.60. Joukko nZ = {. . . , −2n, −n, 0, n, 2n, . . .} on selvästi ryhmän (Z, +) normaali aliryhmä. Tekijäryhmän Z/nZ = {a + nZ | a ∈ Z} alkioina ovat jäännösluokat modulo n

a + nZ = {a + nk | k ∈ Z} = a. Ryhmätoimituksena on

(a + nZ) + (b + nZ) = (a + b) + nZ, ts. a + b = a + b. Näin ollen tekijäryhmä Z/nZ on sama kuin aiemmin määritelty ryhmä Zn .