Diszkrét matematika II. példatár

Országok listájaHungaryDebreceni EgyetemInformatikai KarProgramtervező informatikusDiszkrét Matematika 2.JegyzetekDiszkrét matematika II. példatár

Orosz Ágota Kaiser Zoltán

Diszkrét Matematika II. példatár

mobiDIÁK könyvtár

Orosz Ágota Kaiser Zoltán

Diszkrét Matematika II. példatár

mobiDIÁK könyvtár SOROZATSZERKESZT Fazekas István

Orosz Ágota Kaiser Zoltán

Diszkrét Matematika II. példatár
egyetemi jegyzet

mobiDIÁK könyvtár Debreceni Egyetem Informatikai Intézet

Copyright c Orosz Ágota, Kaiser Zoltán, 2004 Copyright c elektronikus közlés mobiDIÁK könyvtár, 2004 mobiDIÁK könyvtár Debreceni Egyetem Informatikai Intézet 4010 Debrecen, Pf. 12 http://mobidiak.unideb.hu

A m egyéni tanulmányozás céljára szabadon letölthet. Minden egyéb felhasználás csak a szerz elzetes írásbeli engedélyével történhet. A m a A mobiDIÁK önszervez mobil portál (IKTA, OMFB-00373/2003) és a GNU Iterátor, a legújabb generációs portál szoftver (ITEM, 50/2003) projektek keretében készült.

Tartalomjegyzék
1. Lineáris leképezések . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1. Vektorterek lineáris leképezései . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2. Bázis- és koordinátatranszformáció . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3. Lineáris transzformációk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2. Euklideszi és unitér terek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1. Lineáris, bilineáris és kvadratikus formák . . . . . . . . . . . . . . . . . . . . . . . 2. Euklideszi terek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3. Euklideszi terek lineáris operátorai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 47 68 83

3. Gráfelmélet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 1. Gráfelméleti alapfogalmak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 2. Euler-kör, Euler-vonal, Hamilton-kör . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 3. Gráfok csúcsmátrixa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Irodalomjegyzék . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

7

1. fejezet

Lineáris leképezések
1. Vektorterek lineáris leképezései
1.1. Feladat. Legyenek V1 és V2 vektorterek a T test felett. Bizonyítsa be, hogy egy : V1 V2 leképezés pontosan akkor lineáris, ha bármely , T és x, y V1 esetén (1) (x + y) = (x) + (y), azaz a lineáris leképezések definíciójában szerepl két tulajdonság (additivitás és homogenitás) az (1) tulajdonsággal egyenérték! Megoldás. 1. Tegyük fel, hogy lineáris. Ekkor az additivitás miatt (x + y) = (x) + (y), és a homogenitás miatt (x) + (y) = (x) + (y), tehát teljesül az (1) tulajdonság. 2. Tegyük fel, hogy teljesül az (1) tulajdonság. Ekkor az = = 1 választással adódik az additivitás illetve a = 1 és y = 0 választással megkapjuk, hogy homogén. 1.2. Feladat. Legyenek V1 és V2 vektorterek a T test felett. Bizonyítsa be, hogy bármely : V1 V2 lineáris leképezés 1. a nullvektort nullvektorba képezi, 2. lineárisan függ vektorokat lineárisan függ vektorokba képez. Megoldás. 1. A lineáris leképezések additivitása miatt (0) = (0 + 0) = (0) + (0) = 2(0), így (0) = 0.
9

10

1. LINEÁRIS LEKÉPEZÉSEK

2. Tegyük fel, hogy az (a) = (a1 , . . . , an ) vektorrendszer lineárisan függ. Ekkor léteznek olyan 1 , . . . , n T nem mind nulla együtthatók, hogy 1 a1 + · · · + n an = 0, így 0 = (0) = (1 a1 + · · · + n an ) = 1 (a1 ) + · · · + n (an ), tehát a (a1 ), . . . , (an ) vektorrendszer szintén lineárisan függ, mert bellük a nullvektor elállítható nem triviális lineáris kombinációként. 1.3. Feladat. Ellenrizze a lineáris leképezések definíciója alapján, hogy az alábbi leképezések lineárisak-e vagy sem. 1. 2. 3. 4. 5. 6. 7. : R2 R, (x1 , x2 ) = x1 : R2 R2 , (x1 , x2 ) = (x1 + 1, x2 ) : R3 R3 , (x1 , x2 , x3 ) = (x1 + 2x2 , x2 - x3 , x2 ) : R2 R3 , (x1 , x2 ) = (x1 , x1 x2 , x2 ) : Rk Rn , (x) = Ax, ahol A Mn×k : P3 P2 , (a3 x3 + a2 x2 + a1 x + a0 ) = 3a3 x2 + a1 : Mn×n Mn×n , (A) = A

Megoldás. 1. Ellenrizzük külön az additivitást és a homogenitást: (x + y) = ((x1 , x2 ) + (y1 , y2 )) = (x1 + y1 , x2 + y2 ) = x1 + y1 , (x) + (y) = (x1 , x2 ) + (y1 , y2 ) = x1 + y1 , tehát az additivitás teljesül. Mivel (x) = ((x1 , x2 )) = (x1 , x2 ) = x1 = (x1 , x2 ) = (x), így a homogenitás is teljesül és a leképezés lineáris. 2. Megvizsgáljuk, hogy additív-e a leképezés: ((x1 , x2 ) + (y1 , y2 )) = = (x1 , x2 ) + (y1 , y2 ) = = (x1 + y1 , x2 + y2 ) (x1 + y1 + 1, x2 + y2 ), (x1 + 1, x2 ) + (y1 + 1, y2 ) (x1 + y1 + 2, x2 + y2 ),

tehát nem az. Ez egyébként abból is látható, hogy (0, 0) = (1, 0) (lásd 1.2 feladat).

1. VEKTORTEREK LINEÁRIS LEKÉPEZÉSEI

11

3. Most a linearitás ellenrzésére az 1.1 feladatban szerepl (1) tulajdonságot használjuk: ((x1 , x2 , x3 ) + (y1 , y2 , y3 )) = (x1 + y1 , x2 + y2 , x3 + y3 ) = ((x1 + y1 ) + 2(x2 + y2 ), (x2 + y2 ) - (x3 + y3 ), x2 + y2 ) = ((x1 + 2x2 ) + (y1 + 2y2 ), (x2 - x3 ) + (y2 - y3 ), x2 + y2 ), (x1 , x2 , x3 ) + (y1 , y2 , y3 ) = (x1 + 2x2 , x2 - x3 , x2 ) + (y1 + 2y2 , y2 - y3 , y2 ) = ((x1 + 2x2 ) + (y1 + 2y2 ), (x2 - x3 ) + (y2 - y3 ), x2 + y2 ),

tehát a leképezés lineáris. 4. Ellenrizzük a homogenitást:

((x1 , x2 )) = (x1 , x2 ) = (x1 , x1 x2 , x2 ), (x1 , x2 ) = (x1 , x1 x2 , x2 ) = (x1 , x1 x2 , x3 ), tehát nem lineáris a leképezés. 5. A mátrixmveletek tulajdonságait felhasználva igazolható, hogy ez a leképezés lineáris: (x + y) = A(x + y) = Ax + Ay = (x) + (y). 6. Ez a leképezés is lineáris, hiszen additív: (p + q) = (a3 x3 + a2 x2 + a1 x + a0 + b3 x3 + b2 x2 + b1 x + b0 ) = ((a3 + b3 )x3 + (a2 + b2 )x2 + (a1 + b1 )x + (a0 + b0 )) = 3(a3 + b3 )x2 + (a1 + b1 ) = 3a3 x2 + a1 + 3b3 x2 + b1 = (a3 x3 + a2 x2 + a1 x + a0 ) + (b3 x3 + b2 x2 + b1 x + b0 ) = (p) + (q) és homogén: (p) = ((a3 x3 + a2 x2 + a1 x + a0 )) = (a3 x3 + a2 x2 + a1 x + a0 ) = 3a3 x2 + a1 = (a3 x2 + a1 ) = (a3 x3 + a2 x2 + a1 x + a0 ) = (p). 7. A transzponálás tulajdonságai miatt lineáris: (A + B) = (A + B) = A + B = (A) + (B).

12

1. LINEÁRIS LEKÉPEZÉSEK

1.4. Feladat. Legyenek V1 és V2 vektorterek a T test felett. Bizonyítsa be, hogy egy : V1 V2 lineáris leképezés esetén Ker altér. Megoldás. A leképezés nulltere (vagy magtere) azon vektorokat tartalmazza, amelyeket a nullvektorba képez: Ker = {x V1 |(x) = 0}, és soha sem üres halmaz, hiszen 0 Ker (lásd 1.2 feladat). Bizonyítanunk kell, hogy zárt a vektortér mveletekre nézve, azaz nulltérbeli vektorok összege és skalárszorosa is nulltérbeli. Legyen x, y Ker , tehát (x) = (y) = 0. Ekkor az additivitás miatt (x + y) = (x) + (y) = 0 + 0 = 0, tehát (x+y) Ker . Ha pedig T tetszleges skalár, akkor a homogenitás miatt (x) = (x) = 0, így (x) Ker .

1.5. Feladat. Legyenek V1 és V2 vektorterek a T test felett. Bizonyítsa be, hogy egy : V1 V2 lineáris leképezés esetén (V1 ) altér.

Megoldás. A leképezés képtere azon V 2 -beli vektorokat tartalmazza, amelyek elállnak valamely V1 -beli vektor általi képeként: (V1 ) = {y V2 |x V1 : (x) = y}, és sohasem üres halmaz mert a nullvektor midig eleme (0) = 0 miatt. Belátjuk, hogy zárt az összeadásra és a skalárszorzásra. Legyen y 1 , y 2 (V1 ). Ekkor léteznek x1 , x2 V1 vektorok, hogy (x1 ) = y 1 és (x2 ) = y 2 , így additivitása miatt (x1 + x2 ) = (x1 ) + (x2 ) = y 1 + y 2 , tehát y1 + y 2 (V1 ). Ha T tetszleges, akkor a homogenitás miatt (x1 ) = (x1 ) = y 1 , azaz y 1 (V1 ).

1.6. Feladat. Legyenek V1 és V2 vektorterek a T test felett. Bizonyítsa be, hogy egy : V1 V2 lineáris leképezés akkor és csak akkor injektív, ha Ker = {0}. Megoldás. 1. Indirekt tegyük fel, hogy a leképezés injektív (azaz különböz vektorok képe különböz), de Ker tartalmaz a nullvektortól különböz x elemet is. Ekkor (x) = 0 és (0) = 0, így az injektivitás miatt x = 0 lenne, ami ellentmond annak, hogy x nem nullvektor.

1. VEKTORTEREK LINEÁRIS LEKÉPEZÉSEI

13

2. Tegyük fel, hogy Ker = {0} de nem injektív, azaz létezik x1 , x2 V1 úgy, hogy x1 = x2 de (x1 ) = (x2 ). Ekkor linearitása miatt tehát (x1 - x2 ) Ker és (x1 - x2 ) = 0, ami ellentmond annak, hogy ker csak a nullvektort tartalmazza. 1.7. Feladat. Legyen : V1 V2 lineáris leképezés. Válaszoljon a következ kérdésekre a nullitás és rangtétel alapján! 1. Ha a V1 vektortér dimenziója 3 és rangja 2, akkor mennyi defektusa? 2. Lehet-e szürjektív leképezés, ha V 1 és V2 dimenziója megegyezik és Ker dimenziója 2? 3. Lehet-e injektív, ha V2 dimenziója kisebb, mint V1 dimenziója? 4. Ha dim V1 = n és izomorfizmus, akkor mennyi V2 ,Ker és (V1 ) dimenziója? Megoldás. 1. A nullitás és rangtétel szerint dim V 1 = def + rg , ahol def = dim Ker a defektusa és rg = dim (V1 ) a rangja, tehát def = 1. 2. Nem, mert szürjektív leképezés esetén rg = dim (V 1 ) = dim V2 , de itt rg = dim V1 - 2 = dim V2 - 2. 3. Nem, mert injektív leképezés esetén az elz feladat alapján def = 0, a nullitás és rangtétel szerint így dim V 1 = rg = dim (V1 ) lenne, ami lehetetlen (V1 ) V2 miatt. 4. Ha izomorfizmus, akkor injektív és szürjektív is, tehát dim Ker = def = 0 és (V1 ) = V2 miatt dim (V1 ) = rg = dim V2 = n. 1.8. Feladat. Határozza meg az alábbi lineáris leképezések nullterét és képterét illetve a leképezések defektusát és rangját. 1. : R3 R2 , (x1 , x2 , x3 ) = (x1 , 0) 2. : R2 R2 , (x1 , x2 ) = (x1 + x2 , x1 - x2 ) 3. : R3 R3 , (x1 , x2 , x3 ) = (x1 + x2 , x2 - x3 , -x1 + x2 - 2x3 ) 4. : R4 R4 , x1 + 2x2 + 3x3 - x4 x1 x 2x + x2 - x3 + 2x4 2 = 1 x3 -x1 + x2 + 4x3 - 3x4 x4 x1 - x2 - 4x3 + 3x4 5. : R3 R4 , (x1 , x2 , x3 ) = (x1 , x1 , x1 , x3 ) 6. : Mn×n Mn×n , (A) = A - A 7. : P2 P3 , (a2 x2 + a1 x + a0 ) = a1 x3 + a1 x2 + (a2 + a0 )x + a1 (x1 - x2 ) = (x1 ) - (x2 ) = 0,

14

1. LINEÁRIS LEKÉPEZÉSEK

Megoldás. 1. A leképezés nullterét azon x R3 vektorok alkotják, amelyekre (x) = 0, tehát keressük azon x = (x1 , x2 , x3 ) vektorokat, amikre (x1 , x2 , x3 ) = (x1 , 0) = (0, 0). Innen x1 = 0 és x2 , x3 tetszleges valós számok, így Ker = L((0, 0, 1), (0, 1, 0)),

defektusa 2, (R3 ) = L(1, 0) a leképezés képtere és rangja 1. 2. Ker meghatározásához keressük azon x = (x 1 , x2 ) vektorokat, amikre (x) = 0, tehát x1 +x2 =0 x1 -x2 =0

homogén lineáris egyenletrendszer megoldásait. Mivel ennek az egyenletrendszernek csak az x = (0, 0) vektor tesz eleget, így Ker = {0}, a defektus nulla, azaz injektív. A nullitás és rangtétel szerint rangja kett, tehát a képtér megegyezik R2 -vel, így ez a leképezés egy izomorfizmus. 3. A leképezés nullterét a (x) = 0 homogén lineáris egyenletrendszer megoldástere adja: x1 +x2 =0 x2 - x3 =0 -x1 +x2 -2x3 =0 x 1 + x2 =0 x2 - x3 =0 2x2 -2x3 =0 x1 +x2 =0 x2 -x3 =0

tehát (x1 , x2 , x3 ) = (-1, 1, 1)t ahol t R tetszleges, így Ker = L(-1, 1, 1) és a leképezés defektusa 1. Tetszleges lineáris leképezés képterének egy generátorrendszerét adják a bázisvektorok képei. Mivel ezek nem szükségképpen lineárisan függetlenek, ki kell bellük választani egy maximálisan lineárisan független vektorrendszert. Határozzuk meg tehát a természetes bázis vektorainak általi képeit: (1, 0, 0) = (1, 0, -1), (0, 1, 0) = (1, 1, 1), (0, 0, 1) = (0, -1, -2). Most válasszunk ki bellük egy maximálisan lineárisan független vektorrendszert (a nullitás és rangtétel szerint ez két vektorból fog állni): (e1 ) 1 0 -1 1 0 -1 1 0 -1 (e2 ) 1 1 1 0 1 2 0 1 2 (e3 ) 0 -1 -2 0 -1 -2 0 0 0 így tehát (R3 ) = L((e1 ), (e2 )).

1. VEKTORTEREK LINEÁRIS LEKÉPEZÉSEI

15

4. Az elz feladatokhoz hasonlóan, ert: 1 2 3 -1 1 2 2 1 -1 2 0 -3 -1 1 4 -3 0 3 1 -1 -4 3 0 -3

megoldjuk a (x) = 0 egyenletrendsz 3 -1 1 2 3 -1 -7 4 0 -3 -7 4 , 7 -4 0 0 0 0 -7 4 0 0 0 0

ahol t1 , t2 tetszleges valós számok. Tehát

innen a megoldások halmaza x1 -5/3 5/3 x2 4/3 -7/3 = x3 0 t1 + 1 t2 x4 1 0

A képtér meghatározásához szükségünk van a természetes bázis vektorainak képeire: (1, 0, 0, 0) = (1, 2, -1, 1), (0, 1, 0, 0) = (2, 1, 1, -1), (0, 0, 1, 0) = (3, -1, 4, -4), (0, 0, 0, 1) = (-1, 2, -3, 3). A nullitás és rangtétel szerint a képtér dimenziója 2, így ki kell választani ebbl a 4 vektorból kett lineárisan független vektort. Látható, hogy bármely kett független, így például (R 4 ) = ((e1 ), (e2 )). 5. Mivel (x1 , x2 , x3 ) = (x1 , x1 , x1 , x3 ) = (0, 0, 0, 0) pontosan akkor teljesül, ha x1 = 0, x2 = 0 és x3 tetszleges valós szám, így Ker = L(0, 0, 1). A természetes bázis elemeinek képei: (1, 0, 0) = (1, 1, 1, 0), (0, 1, 0) = (0, 0, 0, 0) és (0, 0, 1) = (0, 0, 0, 1), tehát A leképezés defektusa 1, rangja 2. 6. A magtér meghatározásának esetén a kérdés az, hogy milyen A M n×n mátrixok esetén lesz (A) = O. (A) = A - A = O akkor és csak akkor teljesül, ha A = A azaz a szimmetrikus mátrixok esetén. A példatár els részének 4.12 feladata alapján a szimmetrikus mátrixok alterének dimenziója n(n + 1)/2, (egy lehetséges bázisa pedig azon mátrixokból áll, amelyekben egy darab 1-es szerepel és a többi elem nulla, az 1-es a fátlóban vagy a felett helyezkedik el). Jelölje E ij azt a mátrixot, aminek i. sorának j. eleme 1-es, a többi nulla. Ekkor tehát Ker = L({Eij |0 i, j n, j i}). Az Mn×n vektortér természetes bázisát az E ij mátrixok alkotják, ahol 0 i, j n. Ezen mátrixok általi képei (E ij ) = Eij - Eji (R3 ) = L((e1 ), (e3 )).

Ker = L((-5, 4, 0, 3), (5, -7, 3, 0)).

16

1. LINEÁRIS LEKÉPEZÉSEK

alakúak, (Eij ) és (Eji ) egymás (-1)-szeresei, továbbá (E ii ) = O. Ezen mátrixok által generált altér a ferdeszimmetrikus mátrixok altere (lásd 4.12 feladat), amelynek dimenziója (n - 1)n/2, tehát Látható, hogy a nullitás és rangtételnek megfelelen a defektus és a rang összege n2 , vagyis éppen az n×n-es mátrixok vektorterének dimenziója. 7. Mivel a1 x3 + a1 x2 + (a2 + a0 )x + a1 = 0 akkor és csak akkor teljesül, ha a1 = 0 és a0 = -a2 , így a leképezés nullterét az (ax2 - a) alakú polinomok alkotják, ahol a R. Tehát Ker = L(x2 - 1), a defektus pedig 1. A természetes bázis képei: (x2 ) = x, (x) = x3 + x2 + 1, (1) = x, amibl az els kett lineárisan független, így (P 2 ) = L((x2 ), (x)). A leképezés rangja 2. 1.9. Feladat. Legyen : Rn Rk lineáris leképezés. Igazoljuk, hogy ekkor létezik olyan A Mk×n mátrix, hogy (x) = Ax. Ezt a mátrixot a lineáris leképezés természetes bázisra vonatkozó mátrixának nevezzük. Megoldás. Jelölje (e) = e1 , . . . , en a természetes bázist Rn -ben. Ekkor x = x1 e1 + · · · + xn en , és a linearitás miatt ahol (ej ) R minden 1 j n esetén. Legyen Aij a (ej ) vektor i. koordinátája. Ekkor tehát a keresett mátrix j-edik oszlopába a j-edik bázisvektor képének koordinátái kerülnek. 1.10. Feladat. Határozza meg az alábbi lineáris leképezések mátrixát! 1. : R3 R2 , (x1 , x2 , x3 ) = (x1 + x2 + 2x3 , x2 + 3x3 ), 2. : R3 R4 , (x1 , x2 , x3 ) = (x1 - x2 , x2 + x3 , x2 , x1 + x2 - x3 ), 3. : R4 R, (x1 , x2 , x3 , x4 ) = (-x1 + x2 - x3 + x4 ), 4. az R2 -beli origóra tükrözés, 5. az R3 -beli [x, y] síkra való merleges vetítés. (Hasonló jelleg feladatokról bvebben a Lineáris transzformációk cím részben lesz szó.) (Ax)i = Ai1 x1 + · · · + Ain xn = x1 (e1 )i + · · · + xn (en )i = (x)i ,
k

(Mn×n ) = L({Eij - Eji |0 i, j n, j > i}).

(x) = x1 (e1 ) + · · · + xn (en ),

1. VEKTORTEREK LINEÁRIS LEKÉPEZÉSEI

17

Megoldás. 1. A keresett mátrix 2×3 típusú, els oszlopában az (1, 0, 0) vektor képének 1 koordinátái szerepelnek, azaz , második oszlopa a (0, 1, 0) vektor 0 1 képe: , hasonlóan határozható meg a harmadik oszlop is: 1 A= 1 1 2 . 0 1 3

2. Most a mátrix 4 × 3 típusú lesz: 1 0 A= 0 1

Látható, hogy ekkor valóban teljesül, hogy (x) = Ax : x 1 1 2 1 x1 + x2 + 2x3 x2 = Ax = = (x). x2 + 3x3 0 1 3 x3 -1 0 1 1 . 1 0 1 -1

3. A = -1 1 -1 1 . 4. Mivel az origóra való tükrözésnél a vektorok minden koordinátája ellentettjére változik a leképezés után, így (x 1 , x2 ) = (-x1 , -x2 ) és A= -1 0 . 0 -1

1.11. Feladat. A homomorfia tétel szerint egy : V 1 V2 lineáris leképezés esetén V1 / Ker (V1 ). = Állapítsuk meg, hogy az alábbi leképezések esetén milyen leképezés valósítja meg a fenti izomorfiát! 1. : R2 R2 , (x1 , x2 ) = (x1 + x2 , x1 - x2 ), 2. : R3 R3 , (x, y, z) = (x, y, 0).

5. Az [x, y] síkra való merleges vetítésnél a vektorok x és y koordinátája nem változik, míg a harmadik koordináta nulla lesz: (x, y, z) = (x, y, 0), így a leképezés mátrixa: 1 0 0 A = 0 1 0 . 0 0 0

18

1. LINEÁRIS LEKÉPEZÉSEK

Megoldás. 1. Elször meg kell határoznunk a leképezés nullterét. Mivel az 1.8 feladatban láttuk, hogy (x) = 0 akkor és csak akkor, ha x = 0, így Ker = 0. Ekkor V1 / Ker = V1 = R2 , a homomorfia tétel állítása ebben az esetben egyszeren a V1 (V1 ) kifejezést jelenti, az izomorfizmust a = leképezés valósítja meg. Ez minden olyan esetben igaz, ha injektív, mert ekkor : V1 (V1 ) leképezés már egy bijektív lineáris leképezés, azaz izomorfizmus. 2. Ennek a leképezésnek a nullterét a (0, 0, z) alakú vektorok alkotják, ahol z tetszleges valós szám, tehát Ker = L(0, 0, 1). Ekkor a V 1 / Ker faktortér elemei az x+Ker alakú lineáris sokaságok, azaz a z-tengellyel párhuzamos egyenesek (lásd a példatár els részének 3.25 feladatát). A (V1 ) altér, azaz a leképezés képtere itt az [x, y] sík lesz, azaz az (x, y, 0) alakú vektorok halmaza. A homomorfia tétel tehát azt állítja, hogy a z-tengellyel párhuzamos egyeneseknek (mint lineáris sokaságoknak) a vektortere izomorf az [x, y] sík vektorai által alkotott altérrel, és a feladat azt kéri, hogy adjuk meg ezt a kölcsönösen egyértelm megfeleltetést. Legyen f : V1 / Ker (V1 ) az a leképezés, amelynél f ((x, y, z) + Ker ) = (x, y, 0). PSfrag replacements Ker
z

(x, y, z) + Ker

f y x (V1 ) (x, y, 0) = f ((x, y, z) + Ker )

Belátjuk, hogy f valóban bijekció. A szürjektivitás nyilvánvaló, az injektivitás igazolásához tegyük fel, hogy f ((x 1 , y1 , z1 ) + Ker ) = f ((x2 , y2 , z2 ) + Ker ). Ekkor (x1 , y1 , 0) = (x2 , y2 , 0), így a két lineáris sokaság megegyezik, mert (x1 , y1 , z1 ) - (x2 , y2 , z2 ) = (0, 0, z1 - z2 ) Ker . Szemléletesen arról van szó, hogy a két vektor ugyanarra a z-tengellyel párhuzamos egyenesre mutat, hiszen csak a harmadik koordinátájuk tér el.

2. BÁZIS- ÉS KOORDINÁTATRANSZFORMÁCIÓ

19

Könnyen ellenrizhet, hogy az f leképezés lineáris, ugyanis tetszleges , , x1 , x2 , y1 , y2 , z1 , z2 valós számok esetén f ((x1 , y1 , z1 ) + Ker ) + ((x2 , y2 , z2 ) + Ker ) = f (x1 , y1 , z1 ) + (x2 , y2 , z2 ) + Ker = f (x1 + x2 , y1 + y2 , z1 + z2 ) + Ker = (x1 + x2 , y1 + y2 , 0) = (x1 , y1 , 0) + (x2 , y2 , 0) = f (x1 , y1 , z1 ) + Ker + f (x2 , y2 , z2 ) + Ker , tehát ez a keresett izomorfizmus.

2. Bázis- és koordinátatranszformáció
1.12. Feladat. Az (a) = (a1 , a2 , a3 ) és a (b) = (b1 , b2 , b3 ) vektorrendszerek R3 bázisai. Írja fel az (a)-(b) bázistranszformáció mátrixát. 1. a1 = (1, 0, 0), a2 = (0, 1, 0), a3 = (0, 0, 1), b1 = (3, 4, 5), b2 = (6, 7, 8), b3 = (9, 8, 8), 2. a1 = (-1, 2, 1), a2 = (1, -1, 3), a3 = (0, 1, 2), b1 = (1, -2, 1), b2 = (2, -1, 2), b3 = (-1, 1, 4), 3. a1 = (1, 2, 0), a2 = (1, 2, -1), a3 = (2, 1, 1), b1 = (2, 1, 0), b2 = (1, 3, 1), b3 = (-1, 2, 1), 4. a1 = (3, 2, 1), a2 = (1, 1, 0), a3 = (0, 1, 1), b1 = (1, 1, 1), b2 = (1, 2, 2), b3 = (1, 0, -1). Megoldás. 1. Az (a) - (b) bázistranszformáció mátrixa oszlopaiban tartalmazza a (b) vektorainak felírását az (a) bázisban. Mivel ennél a feladatnál az (a) bázis éppen a természetes bázis, így a (b) vektorai eleve az (a) bázisban vannak megadva. Ekkor a mátrix oszlopaiba rendre beírjuk S (b) vektorait, tehát (a) - (b), ahol 3 6 9 S = 4 7 8 . 5 8 8

20

1. LINEÁRIS LEKÉPEZÉSEK

2. Két megoldási módszert mutatunk meg. a) Ki kell számolnunk a b1 , b2 , b3 vektorok (a) bázisra vonatkozó koordinátáit. A b1 vektor esetén meg kell oldanunk az x 1 a1 +x2 a2 +x3 a3 = b1 lineáris egyenletrendszert, melynek egyértelmen létez x 1 , x2 , x3 megoldása adja a bázistranszformáció mátrixának els oszlopát. Hasonlóan kell eljárnunk b2 és b3 esetén, tehát három darab egyenletrendszert kell megoldanunk, melyekhez tartozó mátrixok: -1 1 0 1 -1 1 0 2 -1 1 0 -1 2 -1 1 -2 , 2 -1 1 -1 , 2 -1 1 1 . 1 3 2 1 1 3 2 2 1 3 2 4 Mivel a három egyenletrendszer alapmátrixa megegyezik, szimultán is megoldhatjuk ket úgy, hogy a jobboldalon lév vektorokat egymás mellé írjuk, és a -1 1 0 1 2 -1 2 -1 1 -2 -1 1 1 3 2 1 2 4 mátrixot Gauss-eliminációval olyan alakra hozzuk, hogy az els részében az egységmátrix szerepel (hasonlóan az inverzmátrix kiszámításánál alkalmazott szimultán Gauss-eliminációhoz): -1 1 0 1 2 -1 -1 1 0 1 2 -1 2 -1 1 -2 -1 1 0 1 1 0 3 -1 2 4 0 4 2 2 5 3 1 3 2 1 1 0 0 0 -3 7/2 -1 0 -1 1 -1 0 0 1 1 0 3 -1 0 1 0 1 -1 5/2 . 0 0 1 -1 4 -7/2 0 0 -2 2 -8 7 Ekkor a mátrix második részének oszlopaiban az egyes egyenletrendszerek megoldásai lesznek, hiszen például az els oszlop vonatkozásában ez éppen az x1 = 0 x2 = 1 x3 = -1
S

egyenletrendszernek felel meg. Így tehát az (a) - (b) bázistranszformáció mátrixa: 0 -3 7/2 S = 1 -1 5/2 -1 4 -7/2

2. BÁZIS- ÉS KOORDINÁTATRANSZFORMÁCIÓ

21

b.) Az S mátrix kiszámításának választhatjuk egy másik módját is. Az x1 a1 + x2 a2 + x3 a3 = b1 egyenletrendszer mátrixos felírása: As1 = b1 , ahol s1 a keresett bázistranszformációs mátrix els oszlopa és A az alapmátrix: -1 1 0 A = 2 -1 1 . 1 3 2 Ez felírható b2 és b3 esetén is, és mivel A invertálható, innen s1 = A-1 b1 , s2 = A-1 b2 , s3 = A-1 b3 . Tehát most a feladat A inverzének kiszámítása valamely tanult módszerrel: -5/2 -1 1/2 A-1 = -3/2 -1 1/2 , 7/2 2 -1/2 és a három szorzás elvégzése: -5/2 -1 1/2 1 0 s1 = A-1 b1 = -3/2 -1 1/2 -2 = 1 , 7/2 2 -1/2 1 -1 -3 7/2 s2 = A-1 b2 = 1 , s3 = A-1 b3 = 5/2 , 4 -7/2 természetesen ugyanazt kaptuk mint a másik esetben. (A három szorzást egyszerre is elvégezhetjük, ha a b1 , b2 , b3 vektorokat egy B mátrix oszlopaiba írjuk, és ekkor S = A-1 B.) 3. Az elzekben ismertetett módszerek valamelyikével: -1 3 4 S = 1 -4/3 -7/3 . 1 -1/3 -4/3 4. Hasonlóan: 1/2 1/2 0 S = -1/2 -1/2 1 . 1/2 3/2 -1

1.13. Feladat. Legyenek (a) és (b) bázisok a V vektortéren és (a) - (b). Ha az x vektor (a) bázisra vonatkozó koordinátáiból képzett vektort x(a) jelöli és a (b) bázisra vonatkozó koordinátáiból alkotott vektort pedig x(b) , akkor x(b) = S -1 x(a) , illetve x(a) = Sx(b) .

S

22

1. LINEÁRIS LEKÉPEZÉSEK

Ezek alapján oldjuk meg a következ feladatokat: 1. Legyen R3 -ban (e) a természetes bázis, és (b) pedig az alábbi vektorokból álló bázis: b1 = (2, 1, -1), b2 = (-1, 1, 1), b3 = (-1, 0, 1). (a) Ha az x vektor a természetes bázisban felírva x(e) = (4, 3, 2), akkor mi lesz az x vektor felírása a (b) bázisban? (b) Ha az y vektor felírása a (b) bázisban y (b) = (2, 3, 4), akkor mik lesznek az y vektor természetes bázisra vonatkozó koordinátái? 2. Tekintsük R3 -ban az (a) és (b) bázisokat, ahol a1 = (3, 2, -1), a2 = (-3, 2, 0), a3 = (-2, -3, 1), b1 = (1, 0, 1), b2 = (2, 1, 0), b3 = (0, 1, -1). (a) (b) Megoldás. 1. (a) Mivel ebben a feladatban a kiinduló bázis a természetes bázis, így az (e) - (b) bázistranszformáció mátrixát azonnal felírhatjuk: 2 -1 -1 1 0 . S= 1 -1 1 1
S

Ha az x vektor az (a) bázisban felírva x(a) = (1, 1, 1), akkor mik lesznek az x vektor koordinátái, ha áttérünk a (b) bázisra? Ha az y vektor felírása a (b) bázisban y (b) = (2, 2, 2), akkor mik voltak az y vektornak az eredeti, (a) bázisra vonatkozó koordinátái?

(b)

2. Elször a bázistranszformáció mátrixát kell meghatároznunk. Mivel az 3 -3 -2 2 -3 A= 2 -1 0 1

Ha a vektor új bázisbeli koordinátái adottak, és mi tudni szeretnénk az eredeti koordinátáit, akkor 2 -1 -1 2 -3 1 3 = 5 . 1 0 y (e) = Sy (b) = -1 1 1 4 5

Ha a régi bázisban a vektor koordinátái x(e) = (4, 3, 2), akkor az új bázisbeli koordinátákat az S mátrix alapján kiszámíthatjuk: 1 0 1 4 6 x(b) = S -1 x(e) = -1 1 -1 3 = -3 . 2 -1 3 2 11

2. BÁZIS- ÉS KOORDINÁTATRANSZFORMÁCIÓ

23

mátrix inverze A-1 így

-2 -3 -13 = -1 -1 -5 , -2 -3 -12



(a)

-2 -3 -13 1 2 0 -15 -7 10 S = -1 -1 -5 0 1 1 = -6 -3 4 . -2 -3 -12 1 0 -1 -14 -7 9

(b)

Végül

Az új koordináták meghatározásához ki kell még számítani az S inverzét, és ekkor -1 7 -2 1 4 x(b) = S -1 x(a) = 2 -5 0 1 = -3 . 0 7 -3 1 4 y (a) = Sy (b) -15 -7 10 2 -24 = -6 -3 4 2 = -10 . -14 -7 9 2 -24

1.14. Feladat. 1. R3 -ban áttértünk az (a) bázisról a (b) bázisra, és minden vektor koordinátái az új bázisban éppen a régi koordináták háromszorosai lettek. Mi volt a bázistranszformáció mátrixa? 2. R3 -ban olyan bázisra szeretnénk áttérni a természetes bázisról, amelyben egy adott x = (1, 2, 3) vektor felírása éppen (1, 1, 1) lesz. Mi legyen a bázistranszformáció mátrixa? Megoldás. 1. Ha minden x vektor esetén igaz, hogy S -1 x(a) = 3x(a) , akkor tehát (S -1 - 3E) a nullmátrix kell legyen. Innen S -1 = 3E és 1/3 0 0 S = 0 1/3 0 0 0 1/3 . 2. Teljesülnie kell, hogy 1 1 S -1 2 = 1 . 3 1 (S -1 - 3E)x(a) = 0,

24

1. LINEÁRIS LEKÉPEZÉSEK

akkor ez rendelkezik a kívánt tulajdonsággal. 1.15. Feladat. Oldjuk meg az alábbi feladatokat bázistranszformáció segítségével! 1. Bontsuk fel az R2 -beli (5, 6) vektort (1, 2) és (4, 1) irányú komponensek összegére. 2. Határozzuk meg az R2 -beli (1, 1) koordinátájú vektornak az y = -3x egyenesre vonatkozó tükörképét. Megoldás. 1. Keressük az x(e) = (5, 6) vektornak a b1 = (1, 2), b2 = (4, 1) bázisbeli felírását: x(b) = 1 4 2 1
-1

Ha az S-et úgy 1 S = 0 0

választjuk, hogy 0 0 2 0 , és így 0 3

S -1

1 0 0 = 0 1/2 0 , 0 0 1/3



x(e) =

Ekkor a felbontás: 5 = (19/7)b 1 + (4/7)b2 = 6

1 -7

1 -4 -2 1

5 6

=

19/7 . 4/7

19/7 16/7 + . 38/7 4/7

2. Ezt a feladatot többféleképpen meg lehet oldani, az egyik lehetséges út a bázistranszformáció használata. Ekkor a természetes bázisról áttérünk a b1 = (3, 1), b2 = (-1, 3) bázisra, mert ennek vektorai is merlegesek egymásra és a második vektor iránya megegyezik az egyenes irányával. Ebben a bázisban egyszeren elvégezhet a tükrözés, a vektor els koordinátáját kell ellentétes eljelre változtatni. Végül az így kapott vektort visszaírjuk az eredeti bázisba. Tehát az x(e) = (1, 1) vektor koordinátái a (b) bázisban x(b) = 3 -1 1 3
-1

x(e) =

1 10

Ekkor az x vektornak a (-1, 3) irányú egyenesre vonatkozó tükörképe a (b) bázisban x(b) = (-2/5, 1/5). Még vissza kell térnünk a természetes bázisra, ha egy vektor eredeti bázisra vonatkozó koordinátáit keressük, akkor az új koordinátákat a bázistranszformáció mátrixával szorozzuk: x(e) = 3 -1 x(b) = 1 3 3 -1 1 3 -2/5 1/5 = -7/5 . 1/5

3 1 -1 3

1 1

=

2/5 . 1/5

3. LINEÁRIS TRANSZFORMÁCIÓK

25

3. Lineáris transzformációk
1.16. Feladat. Írjuk fel a R2 -beli lineáris transzformáció természetes bázisra vonatkozó mátrixát, ha (a) az y tengelyre tükrözés; (b) az x tengelyre tükrözés; (c) az origóra való tükrözés; (d) az origó körüli szög forgatás. Megoldás. A transzformáció mátrixa oszlopaiban tartalmazza a bázisvektorok képének koordinátáit. R2 -ben a természetes bázist az (1, 0) és (0, 1) vektorok alkotják. (a) Mivel (1, 0) = (-1, 0) és (0, 1) = (0, 1), így a keresett mátrix A= -1 0 0 1 .

Ekkor egy (x, y) vektor y-tengelyre való tükrözése ezen mátrixszal való szorzásként megkapható: x y = -1 0 0 1 1 0 0 -1 x y = -x y .

(b) Hasonlóan, a keresett mátrix: A= .

(c) Az origóra való tükrözés mindkét koordinátát ellentétes eljelre változtatja: (1, 0) = (-1, 0) és (0, 1) = (0, -1), így a transzformáció mátrixa -1 0 A= . 0 -1 PSfrag replacements (d) Az ábráról leolvasható, hogy az e1 bázisvektor (e1 ) képének koordinátái (cos , sin ), az e2 bázisvektor (e2 ) képének koordinátái (- sin , cos ):
e2 (e2 ) sin cos
. .

(e1 )

- sin

cos

e1

26

1. LINEÁRIS LEKÉPEZÉSEK

Tehát mátrixa

1.17. Feladat. Határozzuk meg az R3 -beli x tengely körüli fokkal való forgatás mátrixát. Megoldás. Az x tengely körül forgatás esetén a vektorok els koordinátája nem változik, így (1, 0, 0) = (1, 0, 0). Az |y, z| síkban a transzformáció egy szög forgatást jelent, tehát ott az elz feladatban szerepl síkbeli forgatás szerint fognak változni a koordináták: (0, 1, 0) = (0, cos , sin ) és = (0, 0, 1) = (0, - sin , cos ), tehát a keresett mátrix 1 0 0 A = 0 cos sin . 0 - sin cos 1.18. Feladat. Írjuk fel a definíció alapján a : V V lineáris transzformáció mátrixát az (e) bázisra vonatkozóan az alábbi esetekben: 1. V = R3 , (e) a természetes bázis és (x1 , x2 , x3 ) = (2x1 + 3x2 - x3 , x2 + 4x3 , x1 + x2 ), 2. V = P3 , az (e) bázist az alábbi polinomok alkotják: x 3 , x2 , x, 1 és (a3 x3 + a2 x2 + a1 x + a0 ) = (a0 - a3 )x3 + (2a1 + a2 )x2 +(a0 + a1 + 3a2 ), 3. V = M2×2 , (e) = 1 0 0 1 0 0 0 0 , , , 0 0 0 0 1 0 0 1 (A) = A , 4. V = C, (e) = (1, i), (z) = z. Megoldás. Egy lineáris transzformáció mátrixa valamely (e) bázisra vonatkozóan a j. oszlopában tartalmazza a j. bázisvektor általi képének koordinátáit, azaz (e j ) koordinátáit (e)-re vonatkozóan. 1. Az (e) = ((1, 0, 0), (0, 1, 0), (0, 0, 1)) természetes bázis elemeinek általi képei: (1, 0, 0) = (2 · 1 + 3 · 0 - 0, 0 + 4 · 0, 1 + 0) = (2, 0, 1), (0, 1, 0) = (3, 1, 1), (0, 0, 1) = (-1, 4, 0), és

cos sin . - sin cos

3. LINEÁRIS TRANSZFORMÁCIÓK

27

tehát a transzformáció mátrixa: 2 3 -1 A = 0 1 4 . 1 1 0

2. Elször a bázist alkotó polinomok képeit kell meghatároznunk: (x3 ) = (1 · x3 + 0 · x2 + 0 · x + 0) (x2 ) = x2 + 3, (1) = x3 + 1. = (0 - 1)x3 + (0 + 0)x2 + (0 + 0 + 0) = -x3 ,

Láthatjuk, hogy tetszleges (x1 , x2 , x3 ) vektor általi képe kiszámítható úgy, hogy az A mátrixszal megszorozzuk a vektort: x1 2x1 + 3x2 - x3 2 3 -1 x1 x2 = x2 + 4x3 = 0 1 4 x2 . x3 x1 + x 2 1 1 0 x3

(x) = 2x2 + 1, A keresett mátrix oszlopaiba ezen polinomoknak az x 3 , x2 , x, 1 bázisra vonatkozó koordinátái kerülnek, például a 2x 2 +1 = 0·x3 +2·x2 +0·x+1·1 polinom koordinátáit az együtthatók adják: (0, 2, 0, 1). Tehát a keresett mátrix: -1 0 0 1 0 1 2 0 A= 0 0 0 0 . 0 3 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 = = = = 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 , , , .

3. A bázisvektorok képei:

28

1. LINEÁRIS LEKÉPEZÉSEK

4. Mivel (1) = 1 (1, 0) és (i) = -i (0, -1), így a konjugálás mátrixa: A= 1 0 0 -1 .

Könnyen láthatjuk, hogy ezen mátrixszal való szorzásként megvalósítható a transzponálás: 1 1 1 1 0 0 0 2 0 0 1 0 2 3 1 2 1 3 - 3 0 1 0 0 3 = 2 2 4 . 3 4 4 4 0 0 0 1 4

Itt az adott bázisra vonatkozó koordinátákat a mátrixok elemei adják "sorfolytonosan", így a transzponálásnak mint lineáris transzformációnak a mátrixa: 1 0 0 0 0 0 1 0 A= 0 1 0 0 0 0 0 1

1.19. Feladat. 1. Írjuk fel a : R3 R3 lineáris transzformáció mátrixát az (a) = (a1 , a2 , a3 ) bázisra vonatkozóan, ha a1 = (2, 1, -1), a2 = (-3, 1, 0), a3 = (-1, -2, 1), és (a1 ) = (1, 1, 2), (a2 ) = (1, 1, 1), (a3 ) = (1, 2, 3)! (a) Ha az x vektor (a) bázisra vonatkozó koordinátái (-2, -1, 2), akkor mivel egyenlek (x) koordinátái az (a) bázisra vonatkozóan? (b) Mik lesznek (x) koordinátái a természetes bázisra vonatkozóan? 2. Írjuk fel a : R3 R3 lineáris transzformáció mátrixát az (a) = ((3, 1, 1), (1, 1, 0), (-1, 2, -1)) bázisra vonatkozóan, ha (a 1 ) = (3, 0, 1), (a2 ) = (2, 1, 2), (a3 ) = (2, -2, 1)! (a) Ha az x vektor (a) bázisra vonatkozó koordinátái (3, 1, 3), akkor mivel egyenlek (x) koordinátái az (a) bázisra vonatkozóan? (b) Mik (x) koordinátái a természetes bázisra vonatkozóan? Megoldás. 1. A lineáris leképezések második alaptétele szerint egyértelmen létezik olyan lineáris transzformáció ami az (a) bázis elemeit rendre a megadott vektorokba viszi át. Ezen transzformáció mátrixának felírásához a (a 1 ), (a2 ), (a3 ) vektorokat kell lineárisan kombinálni az a1 , a2 , a3 vektorokból. Számolhatunk szimultán Gauss-eliminációval, amikor úgy alakítjuk

3. LINEÁRIS TRANSZFORMÁCIÓK

29

az (a1 , a2 , a3 |(a1 ), (a2 ), (a3 )) mátrixot, hogy az els három oszlopban az egységmátrix legyen (azaz (E|C) alakra hozzuk, ekkor a keresett mátrix C): 2 -3 -1 1 1 1 1 0 0 -9 -11/2 -14 1 1 -2 1 1 2 0 1 0 -4 -5/2 -6 . -1 0 1 2 1 3 0 0 1 -7 -9/2 -11

Másik lehetség a mátrix kiszámítására (hasonlóan mint a bázistranszformáció mátrixának kiszámításánál volt), hogy meghatározzuk az A = (a1 , a2 , a3 ) mátrix inverzét, és ezt szorozzuk a ((a 1 ), (a2 ), (a3 )) mátrixszal: 1 3 7 1 1 1 3 A-1 = -2 1 3 5 és 1 1 1 18 11 28 1 8 5 12 . A-1 1 1 2 = -2 14 9 22 2 1 3

(a)

(b)

A transzformáció (a) bázisra vonatkozó mátrixának segítségével azonnal kiszámíthatjuk a keresett koordinátákat: 18 11 28 -2 -9/2 1 8 5 12 -1 = -3/2 . (x)(a) = -2 14 9 22 2 -7/2

Az imént kapott vektor az y = (x)-nek az (a) bázisra vonatkozó koordinátáit tartalmazza. A természetes bázisra vonatkozó koordinátákat megkaphatjuk a bázis és koordináta transzformációnál tanultak alapján: y (e) = Sy (a) ahol (e) - (a) - (a) bázistranszformáció S vektorait tartalmazza oszlopai -1 -9/2 -1 -2 -3/2 = 1 . 1 -7/2 1
S

és azt is ismerjük, hogy az (e) mátrixa egyszeren az (a) bázis ban. Tehát 2 -3 1 (x)(e) = S(x)(a) = 1 -1 0

30

1. LINEÁRIS LEKÉPEZÉSEK

1.20. Feladat. 1. Ha a : R3 természetes bázisra vonatkozóan 1 A = -1 2

2. Teljesen hasonlóan adódik, hogy a transzformáció mátrixa 0 5 -1 C = 2 -10 3 , -1 3 -2 3 2 (a) (x)(a) = C 1 = 5 , 3 -6 3 1 -1 2 17 (b) (x)(e) = 1 1 2 5 = -5 . 1 0 -1 -6 8 3 2 2 0 , 0 -1

R3 lineáris transzformáció mátrixa a

akkor mivel egyenl mátrixa az (a) = ((1, -1, 1), (0, 1, -1), (0, -1, 2)) bázisra vonatkozóan? (a) Ha x koordinátái az (a)-ra vonatkozóan x(a) = (2, 0, 1), akkor mik (x) koordinátái az (e)-re vonatkozóan? (b) Ha y koordinátái az (e)-re vonatkozóan y (e) = (1, -1, 1), akkor mik (y) koordinátái az a-ra vonatkozóan? 2. Ha a : R3 R3 lineáris transzformáció mátrixa a természetes bázisra vonatkozóan 3 1 1 A = 2 0 1 , -1 1 -1 akkor mivel egyenl mátrixa az (a) = ((1, 2, 1), (0, 2, 1), (-1, 1, 0)) bázisra vonatkozóan? (a) Ha x koordinátái az (a)-ra vonatkozóan x(a) = (1, 0, 1), akkor mik (x) koordinátái az (e)-re vonatkozóan? (b) Ha y koordinátái az (e)-re vonatkozóan y (e) = (0, 1, -1), akkor mik (y) koordinátái az a-ra vonatkozóan?

Megoldás. 1. Jelölje transzformáció mátrixát az új bázisban B. Ekkor B = S -1 AS, ahol S az (e) (a) bázistranszformáció mátrixa, azaz az (a) vektoraiból

3. LINEÁRIS TRANSZFORMÁCIÓK

31

álló mátrix: 1 0 0 S = -1 1 -1 és 1 -1 2 S -1 1 0 0 = 1 2 1 , 0 1 1

tehát

(a) Ha x koordinátái az (a)-ra vonatkozóan x(a) = (2, 0, 1), akkor kiszámíthatjuk (x) koordinátáit az (a) bázisra vonatkozóan, hiszen már ismerjük a transzformáció mátrixát ebben a bázisban is, ez volt a B mátrix. Tehát 0 1 1 2 1 (x)(a) = Bx(a) = -5 6 -5 0 = -15 . -2 3 -4 1 -8 Ezután a bázistranszformáció mátrixának a segítségével kiszámíthatjuk ezen vektor természetes bázisbeli koordinátáit: 1 0 0 1 1 (x)(e) = S(x)(a) = -1 1 -1 -15 = -8 . 1 -1 2 -8 0

1 0 0 1 3 2 1 0 0 B = S -1 AS = 1 2 1 -1 2 0 -1 1 -1 0 1 1 2 0 -1 1 -1 2 0 1 1 -5 6 -5 . = -2 3 -4

Megjegyezzük, hogy többféle úton is eljuthatunk ehhez az eredményhez. Nincs szükség például a B mátrixra, ha elször az x vektort átszámítjuk az (e) bázisba (x(e) = Sx(a) ) és ezután hajtjuk végre a leképezést, ami a természetes bázisban az A mátrixszal való szorzást jelenti. Tehát 1 3 2 1 0 0 2 -1 2 0 -1 1 -1 0 (x)(e) = ASx(a) = 2 0 -1 1 -1 2 1 1 = -8 . 0 A két számítás egyenérték, hiszen SBx(a) = SS -1 ASx(a) = ASx(a) .

32

1. LINEÁRIS LEKÉPEZÉSEK

(b) Ha y koordinátái az (e)-re vonatkozóan y (e) = (1, -1, 1), akkor (y)(e) = Ay (e) és ha kiszámítjuk ezen vektor (a)-ra vonatkozó koordinátáit, akkor megkapjuk a keresett eredményt. Ha az (e) bázisról az (a)-ra térünk át, akkor az (e) (a) bázistranszformáció mátrixának inverzével kell szoroznunk, tehát 1 0 0 1 3 2 1 (y)(a) = S -1 Ay (e) = 1 2 1 -1 2 0 -1 0 1 1 2 0 -1 1 0 -5 . = -2 Természetesen ugyanezt az eredményt kapjuk, ha az y vektort elször átszámítjuk az (a) bázisba (y (a) = S -1 y (e) ) majd ezt a vektort a transzformáció ezen bázisra vonatkozó mátrixával szorozzuk meg: 0 (y)(a) = BS -1 y(e) = -5 . -2

2. A transzformáció mátrixa az új bázisban: 1 1 -2 3 1 1 1 0 -1 B = S -1 AS = -1 -1 3 2 0 1 2 2 1 0 1 -2 -1 1 -1 1 1 0 10 14 9 = -9 -15 -11 . 1 6 7 (a) (x)(e) = ASx(a) = 3 1 1 1 0 -1 1 4 2 0 1 2 2 1 0 = 1 , -1 1 -1 1 1 0 1 2

(b)

(y)(a) = S -1 Ay (e) = 1 1 -2 3 1 1 0 -5 -1 -1 3 2 0 1 1 = 7 . 0 1 -2 -1 1 -1 -1 -5

3. LINEÁRIS TRANSZFORMÁCIÓK

33

1.21. Feladat. Az alábbi állítások közül melyek igazak és melyek hamisak? (a) Ha egy lineáris transzformáció injektív, akkor szürjektív is. (b) Ha egy lineáris transzformáció automorfizmus, akkor mátrixa invertálható. (c) Ha egy 5-dimenziós vektortéren értelmezett lineáris transzformáció nulltere 1-dimenziós, akkor képtere is 1-dimenziós. (d) Ha egy transzformáció mátrixa valamely bázisban 1 0 2 A = -1 2 4 , 2 1 2 akkor a transzformáció automorfizmus. (e) Ha egy transzformáció mátrixa valamely bázisban 1 0 2 A = -1 -2 2 , 2 1 2 akkor defektusa 1 és rangja 2.

Megoldás. A nullitás és rangtétel (dim V = dim ker + dim (V )) következménye, hogy lineáris transzformációk esetén a nulltér dimenziója egyértelmen meghatározza a leképezés rangját, azaz a képtér dimenzióját. Ezt felhasználva lehet megválaszolni a fenti kérdéseket. (a) Igaz, hiszen ha a leképezés injektív, akkor dim ker = 0. Ebbl adódik, hogy dim (V ) = dim V tehát (V ) = V és a leképezés szürjektív. Megjegyezzük, hogy az állítás megfordítása is igaz. (b) Igaz. Ha a leképezés automorfizmus (azaz bijektív lineáris transzformáció) akkor nulltere csak a nullvektort tartalmazza, vagyis az Ax = 0 homogén lineáris egyenletrendszernek csak a 0 a megoldása. Ekkor az egyenletrendszer határozott, és így mátrixa invertálható. (c) Hamis, hiszen képterének dimenziója dim V - dim ker = n - 1. (d) Igaz, hiszen a mátrix reguláris (determinánsa nem nulla). (e) Igaz, hiszen a leképezés nulltere 1-dimenziós. Ezt az Ax = 0 homogén lineáris egyenletrendszer megoldásából kapjuk: x1 + +2x3 = 0 -x1 -2x2 +2x3 = 0 2x1 +x2 +2x3 = 0 x1 + +2x3 = 0 . -x2 +2x3 = 0

34

1. LINEÁRIS LEKÉPEZÉSEK

1.22. Feladat. Legyen lineáris transzformáció a T test feletti V vektortéren. Igazoljuk, hogy ha sajátértéke -nek, akkor a -hoz tartozó sajátvektorok halmaza a nullvektorral kiegészítve invariáns alteret alkot, azaz (L ) L . Megoldás. Legyen x, y L és , T. Ekkor (x + y) = (x) + (y) = x + y = (x + y), tehát x + y is sajátvektor, így L {0} altér. Ha x L , akkor ((x)) = (x) = (x), tehát (x) szintén sajátvektor, azaz (x) L , melybl következik, hogy L invariáns. L = {x V | (x) = x}

1.23. Feladat. Határozzuk meg az R3 beli x tengely körüli 60 fokkal való forgatás 1 sajátértékéhez tartozó sajátvektorokat.

Megoldás. Az 1.17. feladat alapján a transzformáció mátrixa 1 0 0 1 0 0 1/2 - 3/2 . A = 0 cos 60 - sin 60 = 0 0 sin 60 cos 60 0 3/2 1/2

Az 1 sajátértékhez tartozó sajátvektorok azon v R 3 vektorok, melyekre teljesül, hogy (v) = v, azaz (1) ( - id)(v) = 0,

ahol id jelöli az identikus transzformációt, amely egy vektorhoz önmagát rendeli. A - id transzformáció mátrixa A - E, tehát keressük azon v = (x1 , x2 , x3 ) vektorokat, melyek megoldásai az (A-E)v = 0 homogén lineáris egyenletnek. Gauss eliminációval számolva: 0 0 0 0 0 0 -1/2 - 3/2 0 -1/2 - 3/2 , A - E = 0 0 0 -2 0 3/2 -1/2 tehát az egyenlet ekvivalens a 1 3 - x2 - x3 =0 2 2 -2x3 =0

3. LINEÁRIS TRANSZFORMÁCIÓK

35

egyenletrendszerrel. Látható, hogy x 1 tetszlegesen megválasztható, továbbá x2 = x3 = 0, ezért x1 1 v = x2 = 0 (t R), 0 x3 azaz az 1 sajátértékhez tartozó sajátvektorok halmaza az (1, 0, 0) vektor által generált altér, amely az x tengely. 1.24. Feladat. Adjon példát olyan lineáris transzformációra R 2 -ben, melynek (a) nincs sajátvektora. (b) bármely két sajátvektorának az összege is sajátvektor. (c) minden nem nulla vektor sajátvektora. Megoldás. (a) Az origó körüli ]0, [ szög forgatás olyan lineáris transzformáció, amelynek nincsen sajátértéke, hiszen ha x sajátvektor, akkor képe xnek skalárszorosa, mely itt nyilván nem teljesül. Az állítás az 1.22. feladatból is következik, ugyanis a sajátalterek, ha léteznek, legalább 1 dimenziós invariáns alterek, de itt csak a 0 dimenziós {0} altér invariáns. (b) Egy R2 feletti lineáris transzformációnak legfeljebb 2 különböz sajátértéke lehet, hiszen a karakterisztikus polinomja másodfokú. Ha két különböz sajátértékünk van, akkor a hozzájuk tartozó sajátalterek origón átmen nem egyenl egyenesek:
x+y x

PSfrag replacements

y

Nyilván ebben az esetben nem teljesül a kívánt tulajdonság, hiszen az x+y vektor nincsen rajta az egyenesek egyikén sem, így nem sajátvektor. Tehát a mi esetünkben csak 0 vagy 1 sajátérték létezhet, és könynyen ellenrizhet, hogy ekkor teljesül a kívánt tulajdonság. Például a -nyújtások, azaz a : R2 R2 , (x) = x típusú transzformációk megfelelek. (c) Az elz pont alapján könnyen belátható, hogy csak a -nyújtások rendelkeznek ezzel a tulajdonsággal.

36

1. LINEÁRIS LEKÉPEZÉSEK

1.25. Feladat. Adjon példát olyan lineáris transzformációra R 3 -ban, melynek (a) nincs sajátvektora. (b) bármely két sajátvektorának az összege is sajátvektor. (c) minden nem nulla vektor sajátvektora. Megoldás. (a) Az R3 -beli transzformációk karakterisztikus egyenlete egy harmadfokú egyenlet, melynek mindig van valós megoldása, amely a transzformáció sajátértéke. Tehát nincs olyan transzformáció R 3 -ban, amelynek nem létezik sajátértéke. (b) Az 1.24. feladat (b) része alapján belátható, hogy az ilyen transzformációknak legfeljebb 1 sajátértéke lehet. Mivel azonban az elz pont szerint minden R3 -beli transzformációknak van legalább 1 sajátértéke, ezért pontosan az 1 sajátértékkel rendelkez transzformációk a megfelelek. Természetesen a -nyújtások ilyenek. (c) Pontosan a -nyújtások ezek a transzformációk. 1.26. Feladat. Határozzuk meg az alábbi mátrixokkal adott valós tér feletti lineáris transzformációk sajátértékeit és sajátvektorait: -2 4 -8 5 -3 0 -2 -3 (a) (b) -6 8 -14 (c) 6 -4 0 1 1 -3 3 -5 12 -12 2 (d) 1 0 -1 0 1 -1 (e) 2 1 0 1 0 -1 2 -1 -1 1 -1 0 (f ) -1 -1 1 -8 1 2 -12 -3 6

Megoldás. Az A mátrixú lineáris transzformáció sajátértékeit megkapjuk, ha kiszámoljuk a det(A - E) = 0 karakterisztikus egyenlet megoldásait. A sajátértékhez tartozó sajátvektorok halmaza az (A - E)x = 0 lineáris egyenletrendszer megoldásterével egyenl. (a) A transzformáció karakterisztikus polinomja: -2 - -3 = (-2 - )(1 - ) + 3 = 2 + + 1. 1 1- Tehát a transzformáció sajátértékei a 2 + + 1 = 0 karakterisztikus egyenlet megoldásai lennének, azonban az egyenletnek nincs valós megoldása.

3. LINEÁRIS TRANSZFORMÁCIÓK

37

(b) A karakterisztikus polinom: -2 - 4 -8 -6 8- -14 = (-2 - )(8 - )(-5 - ) + 168 + 144 - -3 3 -5 -

-24(8 - ) + 42(-2 - ) + 24(-5 - ) = -3 + 2 + 4 - 4, tehát az -3 + 2 + 4 - 4 = 0

egyenletet kell megoldanunk. Harmadfokú egyenletre van megoldóképlet, azonban ezzel számolni igen nehézkes. Lehetleg keressünk 1 gyököt próbálgatással (harmadfokú egyenletnek mindig van legalább 1 valós gyöke), ezután már csak egy másodfokú egyenletet kell megoldanunk. A próbálgatást kezdjük a 0-hoz közeli egész számokkal (0, 1, -1, 2, -2, . . . ). Könnyen ellenrizhet, hogy a 1 = 1 megoldása az egyenletnek, így - 1 kiemelhet a polinomból: -3 + 2 + 4 - 4 = ( - 1)(-2 + 4). Így a másik két megoldást a -2 +4 = 0 másodfokú egyenletbl kapjuk: 2 = -2, 3 = 2. Tehát a transzformáció sajátértékei: -2, 1, 2. A -2 sajátértékhez tartozó sajátvektorokat a -2 - (-2) 4 -8 x1 0 -6 8 - (-2) -14 x2 = 0 x3 -3 3 -5 - (-2) 0 kapjuk meg. Gauss-féle eliminációval 3 -3 -3 3 -3 10 -14 0 4 -8 4 -8 0 4 -8 3 -3 4 -8 . 0 0

homogén egyenlet megoldásával számolva: 0 4 -8 -3 -6 10 -14 -6 -3 3 -3 0 -3 0 0

Tehát az eredeti egyenletrendszer ekvivalens a -3x1 +3x2 -3x3 =0 4x2 -8x3 =0

38

1. LINEÁRIS LEKÉPEZÉSEK

azaz a -2 sajátértékhez tartozó sajátvektorok altere az (1, 2, 1) vektor által generált altér. Hasonlóan kapjuk, hogy az 1 sajátérték sajátvektorainak altere az L{(0, 2, 1)}, a 2 sajátérték sajátvektorainak altere pedig az L{(1, 1, 0)} altér. (c) A transzformáció karakterisztikus egyenlete - 3 +32 -4 = 0. Könnyen látható, hogy 1 = -1 megoldás, továbbá tehát a másik sajátérték a 2 = 2 kétszeres algebrai multiplicitással. A 2 = 2 sajátértékhez tartozó sajátvektorok megkeresésére a 0 3 -3 0 x1 6 -6 0 x2 = 0 0 12 -12 0 x3 homogén egyenletrendszert kell megoldani. Gauss-eliminációt végezve: 3 -3 0 3 -3 0 6 -6 0 0 0 0 1 -1 0 12 -12 0 0 0 0 Azonnal látható, hogy az egyenletrendszer megoldása az x1 1 0 x2 = 1 t1 + 0 t2 (t1 , t2 R), 1 x3 0 -3 + 32 - 4 = -( + 1)(2 - 42 + 4) = -( + 1)( - 2)2 ,

egyenletrendszerrel. Az x3 vektort válasszuk egy tetszleges t valós számnak. Innen x2 = 2t és x1 = t, tehát 1 x1 x2 = 2 t (t R), 1 x3

így a 2 = 2-höz tartozó sajátvektorok altere a L{(1, 1, 0), (0, 0, 1)} altér. Hasonlóan kapjuk, hogy a 1 = -1-hez tartozó sajátvektorok altere a L{(1, 2, 4)} altér. (d) A transzformáció karakterisztikus egyenlete -x 3 + 2x2 - 4x + 3 = 0. Látható, hogy 1 = 1 megoldás, továbbá Az x2 - x + 3 = 0 egyenlet diszkriminánsa negatív, így nincs megoldása a valós számok halmazán. Tehát a transzformációnak csak a = 1 a -x3 + 2x2 - 4x + 3 = -(x - 1)(x2 - x + 3).

3. LINEÁRIS TRANSZFORMÁCIÓK

39

1.27. Feladat. Határozzuk meg a következ lineáris transzformációk karakterisztikus polinomját, sajátértékeit, sajátaltereit. Vizsgáljuk meg a diagonalizálhatóságot, és teljesülése esetén adjunk meg sajátvektorokból álló bázist, továbbá azt az S mátrixot, amellyel S -1 AS diagonális alakú, ahol A jelöli a transzformáció természetes bázisra vonatkozó mátrixát. (a) : R3 R3 , (x, y, z) (4x + y + z, x + 2y + z, -3x - y); (b) : R3 R3 , (x, y, z) (-x, -6x + 11y + 9z, 6x - 12y - 10z); (c) : R3 R3 , (x, y, z) (3y + 3z, -2x + y + 2z, x - z); (d) : R3 R3 , (x, y, z) (x - y + 3z, 3x + 5y - 3z, 2z); (e) : R3 R3 , (x, y, z) (-9x + 14z, -7x - 2y + 14z, -7x + 12z); (f) : R3 R3 , (x, y, z) (x + y + 2z, 10x + 2y - 10z, -6x + y + 9z). Megoldás. Egy lineáris transzformáció mátrixa akkor és csak akkor diagonalizálható, ha létezik sajátvektorokból álló bázis. Ebben a sajátvektorokból álló bázisban mátrixa olyan, hogy a fátlóban a megfelel sajátértékek állnak. Ha tehát a természetes bázisból áttérünk a sajátvektorokból álló bázisra, akkor a bázistranszformáció mátrixának oszlopaiban az új bázis koordinátái állnak. A feladat elssorban ennek az S mátrixnak a meghatározása, amennyiben létezik.

melybl kapjuk, hogy a sajátvektorok altere a L{(1, -2, 0)} altér. (e) Karakterisztikus polinom: -3 - , sajátértékek: -1, 0, 1. 1 = -1 sajátvektorainak altere: L{(1, 3, 2)}. 2 = 0 sajátvektorainak altere: L{(1, 1, 1)}. 3 = 1 sajátvektorainak altere: L{(1, 1, 0)}. (f) Karakterisztikus polinom: -3 + 62 - 9, sajátértékek: 0, 3. 1 = 0 sajátvektorainak altere: L{(1, 2, 3)}. 2 = 3 sajátvektorainak altere: L{(1, 0, 4), (0, 1, 1)}.

homogén egyenletrendszer megoldásai. Gauss-eliminációt alkalmazva: 0 0 -1 2 1 -1 0 0 -1 0 0 -1 2 1 -1 , 0 0 -1 2 1 -1 0 0 -1

sajátértéke, a sajátvektorok pedig a 0 0 -1 x1 0 0 0 -1 x2 = 0 2 1 -1 x3 0

40

1. LINEÁRIS LEKÉPEZÉSEK

(a) (1, 0, 0) = (4, 1, -3), (0, 1, 0) = (1, 2, -1) és (0, 0, 1) = (1, 1, 0), így a transzformáció mátrixa: 4 1 1 2 1 . A= 1 -3 -1 0

(b) (1, 0, 0) = (-1, -6, 6), (0, 1, 0) = (0, 11, -12) továbbá (0, 0, 1) = (0, 9, -10), így a transzformáció mátrixa: -1 0 0 9 . A = -6 11 6 -12 -10

Az 1.26 feladatban leírt módon számolva kapjuk, hogy a karakterisztikus polinom a -3 + 62 - 11 + 6 polinom, melynek zérushelyei, így a transzformáció sajátértékei az 1, 2, 3 számok. Az 1 sajátértékhez tartozó sajátvektorok altere az L{(0, 1, -1)} altér, a 2 sajátértékhez tartozó sajátvektorok altere az L{(-1, 1, 1)} altér és a 3 sajátértékhez tartozó sajátvektorok altere az L{(-1, 0, 1)} altér. Nyilvánvalóan a mátrix diagonalizálható, ugyanis a spektrum teljes, továbbá mindhárom sajátérték algebrai és geometriai multiplicitása egyaránt 1, tehát megegyeznek. Egy sajátvektorokból álló bázist alkot a (0, 1, -1), (-1, 1, 1), (-1, 0, 1) vektorok rendszere, hiszen különböz sajátértékekhez tartozó sajátvektorok lineárisan függetlenek. A feladat elején leírtak alapján tehát 0 -1 -1 1 0 . S= 1 -1 1 1

A transzformáció karakterisztikus polinomja a - 3 + 3 + 2 polinom. Két sajátértéke van, a -1 kétszeres algebrai multiplicitással, továbbá a 2 egyszeres algebrai multiplicitással. A -1 sajátértékhez tartozó sajátvektorok altere az L{(3, 0, 2), (2, 1, 0), } altér, tehát a geometriai multiplicitása is 2. A 2 sajátértékhez tartozó sajátvektorok altere a L{(0, 1, -1)} altér. A transzformáció mátrixa tehát diagonalizálható, hiszen a spektrum teljes és a sajátértékek geometriai és algebrai multiplicitása egyenl. A {(3, 0, 2), (2, 1, 0), (0, 1, -1)} vektorrendszer sajátvektorokból álló bázis, így 3 2 0 S = 0 1 1 . 2 0 -1

3. LINEÁRIS TRANSZFORMÁCIÓK

41

(c) (1, 0, 0) = (0, -2, 1), (0, 1, 0) = (3, 1, 0) és (0, 0, 1) = (3, 2, -1), így a transzformáció mátrixa: 0 3 3 A = -2 1 2 . 1 0 -1

A transzformáció karakterisztikus polinomja a - 3 - 2 - 3 polinom, melynek csak egy valós gyöke van, a -1. A -1 sajátérték algebrai multiplicitása egyszeres, így a transzformáció spektruma nem teljes, ezért mátrixa nem diagonalizálható. A sajátvektorok altere a L{(0, -1, 1)} altér. (d) (1, 0, 0) = (1, 3, 0), (0, 1, 0) = (-1, 5, 0) és (0, 0, 1) = (3, -3, 2), így a transzformáció mátrixa: 1 -1 3 A = 3 5 -3 . 0 0 2

(f) A transzformáció karakterisztikus polinomja - 3 + 122 - 41 + 42, sajátértéke a 2, melynek sajátaltere: L{(1, -1, 1)}, a 3, melynek sajátaltere: L{(1, 0, 1)}, továbbá a 7, melynek sajátaltere: L{(0, -2, 1)}. Így 1 1 0 S = -1 0 -2 . 1 1 1

A transzformáció karakterisztikus polinomja a - 3 + 82 - 20 + 16 polinom. Két sajátérték van, a 2 kétszeres, a 4 pedig egyszeres algebrai multiplicitású. A 4 sajátértékhez tartozó sajátvektorok altere a L{(1, -3, 0)} altér. A 2 sajátértékhez tartozó sajátvektorok altere a L{(-1, 1, 0)} altér, tehát a geometriai multiplicitása 1, mely nem egyezik meg az algebrai multiplicitással, így a transzformáció mátrixa nem diagonalizálható. (e) A transzformáció karakterisztikus polinomja - 3 + 2 + 16 + 20, sajátértéke a -2 kétszeres algebrai multiplicitással, melynek sajátaltere: L{(0, 1, 0), (2, 0, 1)}, továbbá az 5 egyszeres algebrai multiplicitással, melynek sajátaltere: L{(1, 1, 1)}. Így 0 2 1 S = 1 0 1 . 0 1 1

42

1. LINEÁRIS LEKÉPEZÉSEK

Megoldás. A komplex számok teste felett minden n-edfokú egyenletnek multiplicitást is számolva pontosan n darab gyöke van, így itt a spektrum mindig teljes. Ezért egy mátrix diagonalizálhatósága csak attól függ, hogy a sajátértékek geometriai és algebrai multiplicitása megegyezik vagy sem. (a) A mátrix karakterisztikus polinomja: Látható, hogy a 1 = 0 a mátrix sajátértéke. A 2 - 4 + 9 = 0 egyenlet megoldása további két sajátértéket ad meg: 4 + ( 16 - 36)1,2 2 - 5i = 2 + ( -5)1,2 = 2,3 = 2 2 + 5i Mivel a mátrixnak 3 darab különböz sajátértéke van, így azok algebrai és a geometriai multiplicitása szükségképpen 1, tehát egyenlek. Ezért a mátrix diagonalizálható. (b) A mátrix karakterisztikus polinomja (-i - ) 2 (i - ), melyrl azonnal leolvasható, hogy két sajátérték van, a 1 = i egyszeres, a 2 = -i kétszeres algebrai multiplicitással. Azt kell csak megvizsgálnunk, hogy a 2 sajátérték geometriai multiplicitása 1 vagy 2. Ehhez meg kell oldanunk a -i - (-i) 1-i 1+i z1 0 z2 = 0 0 -i - (-i) 0 0 0 i - (-i) z3 0 egyenletrendszert. Azonnal leolvasható a megoldáshalmaz: 1 z1 z2 = 0 t (t C). z3 0 Így a 2 sajátérték sajátaltere a L{(1, 0, 0)} altér, így geometriai multiplicitása 1, mely nem egyezik meg az algebrai multiplicitással. Ezért a mátrix nem diagonalizálható. -3 + 42 - 9 = -(2 - 4 + 9).

1.28. Feladat. Vizsgáljuk meg, hogy diagonalizálhatóak-e az alábbi mátrixok C felett. 1 -1 -2 -i 1 - i 1 + i 0 (b) 0 -i 0 (a) 2 1 1 2 2 0 0 i

3. LINEÁRIS TRANSZFORMÁCIÓK

43

1.29. Feladat. Milyen esetén diagonalizálhatóak felett? 1 1 (a) A = (b) B = 0 -1

az alábbi mátrixok R 0 0 0 1 0

Megoldás. Mivel A diagonalizálható, ezért determinánsa egyenl sajátértékeinek szorzatával minden sajátértéket annyiszor véve, amennyi az algebrai multiplicitása (diagonalizálható mátrixnál ez egyenl a geometriai multiplicitással). (a) det A = 0; (b) det A = 2 vagy det A = 4. (c) det A = -6.

Megoldás. (a) Az A mátrix karakterisztikus egyenlete 2 - ( + 1) - 2 + = 0. Az egyenlet diszkriminánsa [-(1 + )]2 - 4(-2 + ) = 52 - 2 + 1, mely mindig pozitív, ezért minden R esetén két különböz sajátértéke van a mátrixnak, így szükségképpen azok algebrai és geometriai multiplicitása 1, azaz megegyezik. Az A mátrix tehát minden R esetén diagonalizálható. (b) A B mátrix karakterisztikus polinomja (1 - )( 2 - ). A mátrix spektruma akkor teljes, 0. Amennyiben > 0, 3 különböz ha sajátérték van, az 1, a és a - , és ezek algebrai és geometriai multiplicitása is 1, így ebben az esetben a mátrix diagonalizálható. Ha = 0, akkor két sajátérték van, az 1 és a 0. A 0 algebrai multiplicitása 2, így meg kell vizsgálni, hogy mennyi a geometriai multiplicitása. Az 1.26 feladatban leírt módon számolva kapjuk, hogy a 0 sajátérték sajátaltere a L{(0, 1, 0)} altér, tehát a geometriai multiplicitás csak 1, így a mátrix = 0 esetén nem diagonalizálható. Összefoglalva, B diagonalizálható pontosan akkor, ha > 0. 1.30. Feladat. Legyen A 3×3-as diagonalizálható mátrix. Mit mondhatunk A determinánsáról, ha (a) A-nak a 0 sajátértéke; (b) A-nak két sajátértéke van, az 1 és a 2. (c) A sajátértékei: -1, 2, 3.

44

1. LINEÁRIS LEKÉPEZÉSEK

Megoldás. Ha egy mátrix diagonális alakú, akkor az n-edik hatványa olyan diagonális mátrix, melynek diagonálisában az eredeti mátrix megfelel elemének n-edik hatványa szerepel. Ezért egy diagonalizálható A mátrix esetén érdemes a hozzá hasonló D diagonális mátrixot megkeresni, hiszen ekkor D = S -1 AS, így A = SDS -1 , ezért An = SD n S -1 . (a) Az 1.26 feladatban leírt módon számolva kapjuk, hogy az A mátrix sajátértéke az 0, melynek sajátaltere L{(-2, 1, -2)}, az 1, melynek sajátaltere L{(1, 3, 0)},továbbá a 2, melynek sajátaltere L{(1, 0, 1)}. Tehát a mátrix diagonalizálható, a hozzá hasonló diagonális mátrix átlójában a 0 0 0 sajátértékek szerepelnek, így D = 0 1 0. Az 1.27 feladat alapján 0 0 2 -3 1 3 -2 1 1 S = 1 3 0 , melynek inverze S -1 = 1 0 -1. Tehát -2 0 1 -6 2 7 An -2 1 1 0 1 3 0 0 = -2 0 1 0 n 0 1 2 -3 0 3 0 1 = 0 0 2n -6 -3 1 3 0 0 1 0 1 0 -1 -6 2 7 0 2n 1 3 1 - 6 · 2n 2n+1 -1 + 7 · 2n . 0 -1 = 3 0 -3 n n n -6 · 2 2·2 7·2 2 7

1.31. Feladat. Legyen n N. -11 4 0 (a) A = 3 -12 4

Számítsuk ki az A mátrix n-edik hatványát: 3 -3 -2 -2 -3 (b) A = 2 1 2 14 2 2 1

(b) Az A mátrix sajátértéke az 1, melynek sajátaltere L{(-1, 1, 1)}, továbbá a -1, melynek sajátaltere L{(-1, 0, 1), (-1, 1, 0)}. Tehát a mátrix 1 0 0 diagonalizálható és D = 0 -1 0 . 0 0 -1 n = E, így An = SES -1 = SS -1 = E. Ha n páros, akkor D Ha n páratlan, akkor D n = D, ezért An = SDS -1 . Az S mátrix -1 -1 -1 1 1 1 0 1 mátrix, melynek inverze S -1 = -1 -1 0 . a 1 1 1 0 -1 0 -1

3. LINEÁRIS TRANSZFORMÁCIÓK

45

1.32. Feladat. Melyek igazak az alábbi állítások közül? (a) Ha A + B = E, akkor A-nak és B-nek ugyanazok a sajátvektorai. (b) Ha AB = 0, akkor A-nak és B-nek ugyanazok a sajátvektorai. (c) Ha sajátértéke A-nak, akkor 2 sajátértéke A2 -nek. (d) Ha 0 sajátértéke A2 -nek, akkor 0 sajátértéke A-nak.

Tehát, ha n páratlan, akkor -1 -1 -1 1 0 0 1 1 1 0 1 0 -1 0 -1 -1 0 An = 1 1 1 0 0 0 -1 -1 0 -1 -1 1 1 1 1 1 -3 -2 -2 0 -1 -1 -1 0 = 2 1 2 = A. = 1 1 -1 0 -1 0 -1 2 2 1

Megoldás. (a) Legyen x sajátvektora A-nak. Ekkor létezik olyan sajátérték, melyre Ax = x, így (A + B)x = Ax + Bx = x + Bx. Viszont A + B = E, így teljesül az (A + B)x = x egyenlség is, ezért x = x + Bx, így Bx = (1-)x, azaz x a B mátrix 1- sajátértékhez tartozó sajátértéke. Hasonlóan kapjuk, hogy a B mátrix sajátvektorai is sajátvektorai az A mátrixnak, tehát az állítás igaz. (b) Az állítás nyilván nem igaz, hiszen például ha A a nullmátrix, akkor minden vektor sajátvektora, és az egyenlség tetszleges B mátrix esetén fennáll, így nyilván olyannál is, amelynek nem minden vektor sajátvektora. (c) Mivel sajátértéke A-nak, ezért létezik olyan x vektor, melyre Ax = x. Ekkor azonban A2 x = A · Ax = Ax = Ax = · x = 2 x, azaz 2 sajátértéke A2 -nek, tehát az állítás igaz. (d) Mivel 0 sajátértéke A2 -nek, így létezik olyan x sajátvektor, melyre A2 x = 0x, azaz A(Ax) = 0. Amennyiben az x vektor nem a 0-hoz tartozó sajátvektora az A mátrixnak, akkor Ax = 0, így A(Ax) = 0 miatt az Ax vektor a 0 sajátértékhez tartozó sajátvektora A-nak. Tehát vagy az x vektor, vagy az Ax vektor a 0-hoz tartozó sajátvektora az A mátrixnak, ezért az állítás igaz. 1.33. Feladat. Adjunk példát olyan nem hasonló mátrixokra, melyek karakterisztikus polinomja megegyezik. Megoldás. Legyen A és B két mátrix, melyek karakterisztikus polinomja megegyezik. Ekkor nyilván a sajátértékek is megegyeznek. Amennyiben mindkét mátrix diagonalizálható lenne, akkor mindketten hasonlóak volnának ugyanazon diagonális mátrixszal, így egymással is. Kézenfekv tehát

46

1. LINEÁRIS LEKÉPEZÉSEK

olyan mátrixokat keresni, amelyek közül A diagonalizálható, B pedig nem. Mivel a karakterisztikus polinom közös, A diagonalizálhatósága miatt a spektrum teljes. B nem diagonalizálható, ezért a sajátértékek valamelyikének geometriai multiplicitása a B mátrix esetén kevesebb, mint az algebrai. Az egyszerség kedvéért legyenek a mátrixok 2 × 2 típusúak. Nyilvánvaló, hogy a E egységmátrix sajátértéke az 1, melynek algebrai és geometriai multiplicitása is 2. Az egységmátrixhoz semelyik tle különböz mátrix sem hasonló, hiszen S -1 ES = E bármely S reguláris mátrix esetén. Így például 1 0 az nem hasonló hozzá, de karakterisztikus polinomja ugyanúgy a 1 1 2 - 2 + 1. (Az 1 sajátérték itt ugyanúgy kétszeres algebrai multiplicitású, de a geometriai multiplicitása csak 1.)

2. fejezet

Euklideszi és unitér terek
1. Lineáris, bilineáris és kvadratikus formák
2.1. Feladat. A definíció alapján ellenrizze, hogy az alábbi leképezések lineáris formák-e! 1. L : R3 R2 , L(x1 , x2 , x3 ) = (x1 , x3 ), 2. L : R3 R, L(x1 , x2 , x3 ) = x2 + 1, 3. L : R3 R, L(x1 , x2 , x3 ) = x2 , 1 4. L : R3 R, L(x1 , x2 , x3 ) = x1 + x2 + x3 , 5. L : R3 R, L(x1 , x2 , x3 ) = 2x1 - 4x3 , 6. L : R4 R, L(x1 , x2 , x3 , x4 ) = -x1 - x2 - x3 - x4 . Megoldás. 1. Egy R feletti vektortér lineáris formáinak értékkészlete R, így ez a leképezés lineáris ugyan, de nem lineáris forma. 2. Nem lineáris forma, nem teljesül például a homogenitás: L(x) = x2 + 1 = L(x) = (x2 + 1). De az additivitás sem teljesül, st, a nullvektor képe sem nulla. 3. Nem lineáris, hiszen például a homogenitás nem teljesül: L(x) = (x1 )2 = L(x) = (x2 ). 1 4. Lineáris forma, hiszen egyrészt additív: tetszleges x = (x 1 , x2 , x3 ), y = (y1 , y2 , y3 ) R3 esetén L(x + y) = x1 + y1 + x2 + y2 + x3 + y3 = L(x) + L(y) = x1 + x2 + x3 + y1 + y2 + y3 , és homogén: bármely valós szám és bármely x = (x 1 , x2 , x3 ) R3 esetén L(x) = x1 + x2 + x3 = L(x) = (x1 + x2 + x3 ). 5. Igen.
47

48

2. EUKLIDESZI ÉS UNITÉR TEREK

6. Igen. 2.2. Feladat. Írjuk fel a természetes bázisra vonatkozó bázis elállítását az elz feladatban szerepl leképezések közül azoknak, amik lineáris formák voltak! Megoldás. Egy lineáris forma bázis elállítását a forma bázisvektorokon felvett értékei adják. 1. Az L : R3 R, L(x1 , x2 , x3 ) = x1 + x2 + x3 természetes bázisra vonatkozó bázis elállítása 1,1,1, hiszen L(1, 0, 0) = 1 + 0 + 0 = 1, L(0, 1, 0) = 0 + 1 + 0 = 1, L(0, 0, 1) = 0 + 0 + 1 = 1. A bázis elállítás jelentése hasonló a leképezés mátrixának jelentéséhez, például ennek a lineáris formának a hatása megegyezik az (1 1 1) mátrixszal való szorzás hatásával: x1 L(x1 , x2 , x3 ) = 1 1 1 x2 = x1 + x2 + x3 . x3

2. Az L : R3 R, L(x1 , x2 , x3 ) = 2x1 - 4x3 forma bázis elállítása 2,0,-4, hiszen L(1, 0, 0) = 2 · 1 - 4 · 0 = 2, L(0, 1, 0) = 0, L(0, 0, 1) = -4. 3. Az L : R4 R, L(x1 , x2 , x3 , x4 ) = -x1 -x2 -x3 -x4 forma természetes bázisra vonatkozó elállítása: -1,-1,-1,-1. 2.3. Feladat. Mely lineáris formák (természetes bázisra vonatkozó) bázis elállításait adtuk meg az alábbiakban? Írjuk fel az x vektornak az adott lineáris forma általi képét! 1. L1 : R3 R bázis elállítása 1, 2, 3 és x = (4, 3, 2), 2. L2 : R3 R bázis elállítása 0, 0, -2 és x = (1, 1, 1), 3. L3 : R4 R bázis elállítása 1, 2, 1, 2 és x = (3, 3, 2, 2).

1. LINEÁRIS, BILINEÁRIS ÉS KVADRATIKUS FORMÁK

49

Megoldás. 1. L1 (x1 , x2 , x3 ) = L1 (x1 e1 +x2 e2 +x3 e3 ) = x1 L(e1 ) +x2 L(e2 ) +x3 L(e3 ) = x1 + 2x2 + 3x3 , és L(4, 3, 2) = 1 2 3
1 2 3

2. L2 (x1 , x2 , x3 ) = -2x3 és L(1, 1, 1) = -2. 3. L3 (x1 , x2 , x3 , x4 ) = x1 +2x2 +x3 +2x4 és L(3, 3, 2, 2) = 3+6+2+4 = 15. 2.4. Feladat. Lineáris formák-e az alábbi leképezések? Ha igen, adjuk meg bázis elállításukat a kanonikus bázisra vonatkozóan! 1. 2. 3. 4. 5. 6. L1 L2 L3 L4 L5 L6 : P2 P1 , L1 (a2 x2 + a1 x + a0 ) = a0 x, : P2 R, L2 (a2 x2 + a1 x + a0 ) = 2a2 - a1 + a0 , : P2 R, L3 (p) = p(2), 2 : P2 R, L4 (p) = 0 p(x)dx, : M2×2 R, L5 (A) = det(A), : M3×3 R, L5 (A) = tr(A) = a11 + a22 + a33 .

4 3 = 16. 2

Megoldás. 1. Nem, hiszen a képtér nem R. 2. Igen, hiszen additív: tetszleges p(x) = a 2 x2 + a1 x + a0 és q(x) = b2 x2 + b1 x + b0 legfeljebb másodfokú polinomok esetén L2 (p + q) = (a2 x2 + a1 x + a0 ) + (b2 x2 + b1 x + b0 ) = L2 (a2 + b2 )x2 + (a1 + b1 )x + (a0 + b0 ) = 2(a2 + b2 ) - (a1 + b1 ) + (a0 + b0 ) = L2 (p) + L2 (q) = 2a2 - a1 + a0 + 2b2 - b1 + b0 , és hasonlóan igazolható a homogenitás is. Az x 2 , x, 1 bázisra vonatkozó elállítás: 2, -1, 1, mert L2 (x2 ) = 2, L2 (x) = -1, és L2 (1) = 1. 3. L3 lineáris forma, hiszen additív: L3 (p + q) = = = L3 (p) + L3 (q) = = (a3 x3 + a2 x2 + a1 x + a0 ) + (b3 x3 + b2 x2 + b1 x + b0 ) L3 (a3 + b3 )x3 + (a2 + b2 )x2 + (a1 + b1 )x + (a0 + b0 ) 8(a3 + b3 ) + 4(a2 + b2 ) + 2(a1 + b1 ) + (a0 + b0 ) p(2) + q(2) 8a3 + 4a2 + 2a1 + a0 + 8b3 + 4b2 + 2b1 + b0 ,

50

2. EUKLIDESZI ÉS UNITÉR TEREK

és homogén: L3 (p) = L3 (a3 x3 + a2 x2 + a1 x + a0 ) = 8a3 + 4a2 + 2a1 + a0 = L3 (p) = p(2) = (8a3 + 4a2 + 2a1 + a0 ). A bázis elállítás: 8, 4, 2, 1. 2 4. Az L4 (p) = L4 (a2 x2 + a1 x + a0 ) = 0 p(x)dx leképezés lineáris, mely az integrál ismert tulajdonságaiból következik:
2 2 2

p(x) + q(x)dx =
0 2 0

p(x)dx +
0 2

q(x)dx

p(x)dx =
0 0

p(x)dx

A leképezés linearitása onnan is látható, hogy
2

L4 (p) =
0

a2 x2 + a1 x + a0 dx = a2

x3 x2 + a1 + a0 x 3 2

2 0

8 = a2 + 2a1 + 2a0 . 3 Innen a bázis elállítás is leolvasható: 8 , 2, 2. 3 5. Nem lineáris a leképezés, hiszen általában sem |A + B| = |A| + |B| sem |A| = |A| nem teljesül. 6. Egy négyzetes mátrix fátlójában álló elemek összegét a mátrix nyomának (trace) nevezzük. Ez a leképezés lineáris, hiszen homogén: tr(A) = a11 + a22 + a33 = tr(A), és hasonlóan látható, hogy teljesül az additivitás is. A bázis elállítás az E11 , E12 , E13 , E21 , . . . , E33 bázisra vonatkozóan (itt Eij jelöli azt a mátrixot, aminek i. sorának j. eleme 1, a többi elem nulla (i, j = 1, 2, 3)): 1, 0, 0, 0, 1, 0, 0, 0, 1, ezek a számok rendre az E11 , E12 , . . . , E33 mátrixokon felvett értékei az L6 lineáris formának, azaz a fátlóban lév elemek összegei. 2.5. Feladat. Adjon példát R3 -nak olyan nem triviális lineáris formájára, amely 1. az (1,2,3) vektorhoz 4-et rendel, 2. az (1,1,0) és az (1,0,1) vektorokhoz nullát rendel, 3. az (1,1,0) vektorhoz 1-et, az (1,0,1) vektorhoz 2-t rendel!

1. LINEÁRIS, BILINEÁRIS ÉS KVADRATIKUS FORMÁK

51

Megoldás. 1. Az R3 vektortér egy általános lineáris formája (x1 , x2 , x3 ) = l1 x1 + l2 x2 + l3 x3 alakú. Keresünk tehát olyan l1 , l2 , l3 valós számokat (a bázis elállítást), hogy l1 + 2l2 + 3l3 = 4. Ha tehát például a bázis elállítás 2, 1, 0, akkor a (x1 , x2 , x3 ) = 2x1 + x2 lineáris forma rendelkezni fog ezzel a tulajdonsággal, de természetesen végtelen sok ilyen leképezés van. 2. Keressük a (x1 , x2 , x3 ) = l1 x1 + l2 x2 + l3 x3 leképezést úgy, hogy (1, 1, 0) = 0 (1, 0, 1) = 0 teljesüljön, ami azt jelenti, hogy l 1 + l2 = 0 és l1 + l3 = 0. A lehetséges megoldások tehát a (x1 , x2 , x3 ) = x1 - x2 - x3 leképezés és konstansszorosai. 3. Az elz feladathoz hasonlóan, most (1, 1, 0) = l1 + l2 = 1 (1, 0, 1) = l1 + l3 = 2 feltételnek kell teljesülnie, tehát l 2 = 1 - l1 és l3 = 2 - l1 . Például l1 = 1 választással a (x1 , x2 , x3 ) = x1 + x3 lineáris forma adódik. 2.6. Feladat. Adjon meg egy bázist a V duális téren, ha: 1. V = R3 , 2. V = P2 , 3. V = M2×2 . Megoldás. A V valós számtest feletti vektortér V duális terét az összes V R lineáris formák alkotják. A duális tér dimenziója megegyezik V dimenziójával. 1. R3 lineáris formái (x1 , x2 , x3 ) = l1 x1 + l2 x2 + l3 x3 alakúak, és a lineáris formák vektortere illetve a számhármasok vektortere között kölcsönösen egyértelm megfeleltetést adhatunk meg, ha minden lineáris formához hozzárendeljük az (l1 , l2 , l3 ) bázis elállítását. Így a duális tér egy bázisát adják azok az m1 , m2 , m3 : R3 R lineáris formák,

52

2. EUKLIDESZI ÉS UNITÉR TEREK

amiknek a bázis elállításuk rendre (1,0,0), (0,1,0) és (0,0,1), azaz m1 (x1 , x2 , x3 ) = x1 m2 (x1 , x2 , x3 ) = x2 m3 (x1 , x2 , x3 ) = x3 . Látható, hogy az összes lineáris forma elállítható mint m 1 , m2 , m3 lineáris kombinációja. 2. P2 lineáris formái (a2 x2 + a1 x + a0 ) = l1 a2 + l2 a1 + l3 a0 alakúak. A duális terének egy bázisát adják azok az m 1 , m2 , m3 : P2 R lineáris formák, amiknek a bázis elállításuk rendre (1,0,0), (0,1,0) és (0,0,1), azaz m1 (a2 x2 + a1 x + a0 ) = a2 m2 (a2 x2 + a1 x + a0 ) = a1 m3 (a2 x2 + a1 x + a0 ) = a0 . 3. M2×2 lineáris formái (A) = a11 a12 a21 a22 = l1 a11 + l2 a12 + l3 a21 + l4 a22

alakúak, és a duális tér egy bázisát adják például az m 1 , m2 , m3 , m4 : M2×2 R lineáris formák, ahol m1 (A) m2 (A) m3 (A) m4 (A) = = = = a11 a12 a21 a22 .

2.7. Feladat. Adott egy B : V × V R bilineáris forma és x, y, z V vektorok. A bilineáris formák definíciója alapján bontsuk fel az alábbi kifejezéseket cB(x1 , x2 ) alakú kifejezések összegére, ahol c valós konstans, x1 , x2 pedig az x, y, z vektorok valamelyike. 1. 2. 3. 4. 5. B(3x, y), B(3x, 3x), B(x + y, x + y), B(3x + 2y - z, x - y + 2z), B(2x - 2y + 3z, 4x + 2y - z).

1. LINEÁRIS, BILINEÁRIS ÉS KVADRATIKUS FORMÁK

53

Megoldás. 1. Mivel B az els változójában homogén, így B(3x, y) = 3B(x, y). 2. Mivel B az els és a második változójában is homogén, így B(3x, 3x) = 3B(x, 3x) = 9B(x, x). 3. Mivel B els változójában additív: B(x + y, x + y) = B(x, x + y) + B(y, x + y), és az így kapott két tagot tovább bonthatjuk, mert a bilineáris formák a második változóban is additívak: B(x, x + y) + B(y, x + y) = B(x, x) + B(x, y) + B(y, x) + B(y, y). 4. Alkalmazva a homogenitást és additivitást: B(3x+2y-z, x-y+2z) = B(3x, x-y+2z)+B(2y, x-y+2z)+B(-z, x- y + 2z) = B(3x, x) + B(3x, -y) + B(3x, 2z) + B(2y, x) + B(2y, -y) + B(2y, 2z) + B(-z, x) + B(-z, -y) + B(-z, 2z) = 3B(x, x) - 3B(x, y) + 6B(x, z) + 2B(y, x) - 2B(y, y) + 4B(y, z) - B(z, x) + B(z, y) - 2B(z, z). 5. B(2x-2y +3z, 4x+2y -z) = 8B(x, x)+4B(x, y)-2B(x, z)-8B(y, x)- 4B(y, y) + 2B(y, z) + 12B(z, x) + 6B(z, y) - 3B(z, z). B1 B2 B3 B4 B5 : R2 × R2 R2 , B1 (x1 , x2 ), (y1 , y2 ) = (x1 + y1 , x2 + y2 ), : R2 × R2 R, B2 (x1 , x2 ), (y1 , y2 ) = x1 + y1 , : R2 × R2 R, B3 (x1 , x2 ), (y1 , y2 ) = x1 y1 , : R3 × R3 R, B4 (x1 , x2 , x3 ), (y1 , y2 , y3 ) = 5x1 y1 + 2x2 y3 , 2 : R3 × R3 R, B5 (x1 , x2 , x3 ), (y1 , y2 , y3 ) = 5x1 y1 + 2x2 y3 + x3 y1 .

2.8. Feladat. Bilineáris formák-e az alábbi leképezések? 1. 2. 3. 4. 5.

Megoldás. 1. Nem, egy bilineáris forma értékkészlete nem lehet R 2 . 2. Nem, egyik tulajdonság sem teljesül. Például nem homogén az els változóban: B2 (x1 , x2 ), (y1 , y2 ) B2 (x1 , x2 ), (y1 , y2 ) 3. Igen. Els változójában additív: B3 (x, y) + B3 (z, y) = x1 y1 + z1 y1 , B3 (x + z, y) = B3 (x1 , x2 ) + (z1 , z2 ), (y1 , y2 ) = (x1 + z1 )y1 , = x1 + y1 , = (x1 + y1 ).

54

2. EUKLIDESZI ÉS UNITÉR TEREK

els változójában homogén: B3 (x, y) = x1 y1 , B3 (x, y) = B3 (x1 , x2 ), (y1 , y2 ) = (x1 )y1 , és teljesen hasonlóan a második változójában is additív és homogén. 4. Igen. Els változójában additív: B4 (x1 , x2 , x3 ) + (z1 , z2 , z3 ), (y1 , y2 , y3 ) = 5(x1 + z1 )y1 + 2(x2 + z2 )y3 , B4 (x, y) + B4 (z, y) = 5x1 y1 + 2x2 y3 + 5z1 y1 + 2z2 y3 , els változójában homogén: B4 (x, y) = B4 (x1 , x2 , x3 ), (y1 , y2 , y3 ) = 5x1 y1 + 2x2 y3 , B4 (x, y) = B4 (x1 , x2 , x3 ), (y1 , y2 , y3 ) = (5x1 y1 + 2x2 y3 ). Az additivitást és a homogenitást most is ellenrizhetjük egyidejleg, például a második változóban való linearitást most igazoljuk egyetlen kifejezésben: B4 (x, y + µz) = B4 ((x1 , x2 , x3 ), (y1 + µz1 , y2 + µz2 , y3 + µz3 ) = 5x1 (y1 + µz1 ) + 2x2 (y3 + µz3 ) = (5x1 y1 + 2x2 y3 ) + µ(5x1 z1 + 2x2 z3 ) = B4 (x, y) + µB4 (x, z). 5. Nem. Például nem homogén a második változóban: B5 (x, y) = B5 (x1 , x2 , x3 ), (y1 , y2 , y3 ) = 5x1 y1 + 2x2 y3 + x3 (y1 )2 ,
2 B5 (x, y) = (5x1 y1 + 2x2 y3 + x3 y1 ).

Megoldás. A bilineáris forma mátrixa a formának a bázisvektor-párokon felvett értékeit tartalmazza. 1. Itt például a mátrix második sorának harmadik eleme B1 ((0, 1, 0), (0, 0, 1)) = 6x2 y3 = 6.

2.9. Feladat. Írja fel a B1 , B2 : R3 × R3 R bilineáris formák mátrixát a természetes bázisra vonatkozóan, és számítsa ki az (1, 2, 3), (-1, 2, -1) vektorpáron felvett értékeiket! 1. B1 ((x1 , x2 , x3 ), (y1 , y2 , y3 )) = 2x1 y1 + 3x1 y2 + 4x1 y3 - x2 y1 - 2x2 y2 + 6x2 y3 + x3 y3 , 2. B2 ((x1 , x2 , x3 ), (y1 , y2 , y3 )) = x1 y1 - 4x1 y3 + 3x2 y1 + 2x2 y2 + x2 y3 - x3 y2 - 5x3 y3 .

1. LINEÁRIS, BILINEÁRIS ÉS KVADRATIKUS FORMÁK

55

Tehát B mátrixa: 2 3 4 B = -1 -2 6 , 0 0 1 2 3 4 -1 -1 -2 6 2 0 0 1 -1

és így B1 (x, y) = x By miatt B1 ((1, 2, 3), (-1, 2, -1)) =

1 2 3

Természetesen ez ugyanazt jelenti, mintha a bilineáris formának a feladatban szerepl felírása alapján számolnánk: B 1 ((1, 2, 3), (-1, 2, -1)) = 2·1·(-1)+3·1·2+4·1·(-1)-2·(-1)-2·2·2+6·2·(-1)+3·(-1) = -21. 2. A bilineáris forma mátrixa: 1 0 -4 1 , B= 3 2 0 -1 -5 és B2 ((1, 2, 3), (-1, 2, -1)) = 1 2 3 1 0 -4 -1 3 2 1 2 = 12. 0 -1 -5 -1

= -21.

2.10. Feladat. Írja fel azt a B : R3 × R3 R bilineáris formát, aminek mátrixa a természetes bázisban 1 -1 2 -1 2 0 , 2 0 3 és számítsa ki B((1, 1, 1), (4, 2, 1)) és B((4, 2, 1), (1, 1, 1)) értékét! Megoldás. B((x1 , x2 , x3 ), (y1 , y2 , y3 )) = x1 y1 - x1 y2 + 2x1 y3 - x2 y1 + 2x2 y2 + 2x3 y1 + 3x3 y3 , és 1 -1 2 4 B((1, 1, 1), (4, 2, 1)) = 1 1 1 -1 2 0 2 = 15. 2 0 3 1 Mivel ez egy szimmetrikus bilineáris forma, így B((4, 2, 1), (1, 1, 1)) = 15. 2.11. Feladat. Igaz-e, hogy ha egy bilineáris forma mátrixa szimmetrikus valamely bázisra vonatkozóan, akkor minden bázisban szimmetrikus lesz?

56

2. EUKLIDESZI ÉS UNITÉR TEREK

Megoldás. Igen, hiszen ha a forma mátrixa valamely bázisban B = B , akkor tetszleges S bázistranszformációs mátrix esetén a bilineáris forma mátrixa az új bázisban S BS, ami szintén szimmetrikus mátrix: (S BS) = S B (S ) = S BS. 2.12. Feladat. Kvadratikus formák-e az alábbi leképezések? Ha igen, adja meg azt a szimmetrikus bilineáris formát, amibl a kvadratikus forma származik, azaz a poláris formáját! 1. Q1 : R2 R2 , Q1 (x1 , x2 ) = (x2 , x1 ), 2. Q2 : R2 R, Q2 (x1 , x2 ) = x1 + x2 , 3. Q3 : R2 R, Q3 (x1 , x2 ) = 2x1 x2 , 4. Q4 : R2 R, Q4 (x1 , x2 ) = x2 , 1 5. Q5 : R3 R, Q5 (x1 , x2 , x3 ) = x2 + 2x2 + x2 - x1 x2 + 6x2 x3 - 2x1 x3 . 1 2 3 6. Q6 : R3 R, Q6 (x1 , x2 , x3 ) = 4x2 - x2 + 4x1 x2 - 3x2 x3 + 2x1 x3 . 2 3 Megoldás. A feladat megválaszolásánál vegyük figyelembe, hogy valamely B szimmetrikus bilineáris formából származó kvadratikus forma: Q(x) = B(x, x). Ha például a B : R2 × R2 R szimmetrikus bilineáris forma esetén B((x1 , x2 ), (y1 , y2 )) felírásában az x1 y2 együtthatója 2, akkor x2 y1 együtthatója is 2, és így a B-bl származó Q kvadratikus forma ( tehát Q((x1 , x2 )) = B((x1 , x2 ), (x1 , x2 )) ) felírásában x1 x2 együtthatója 4 lesz. 1. Nem, hiszen az értékkészlet nem egy számtest. 2. Nem. 3. Igen, a szimmetrikus bilineáris forma amibl Q 3 származik megkapható az alábbi módon: 1 B(x, y) = (Q3 (x + y) - Q3 (x) - Q3 (y)), 2 de szükségtelen ezt kiszámolnunk, hiszen világos, hogy B((x1 , x2 ), (y1 , y2 )) = x1 y2 + x2 y1 . Valóban, ebben y helyére is x-et írva Q 3 adódik. 4. Igen, és Q4 poláris formája: B((x1 , x2 ), (y1 , y2 )) = x1 y1 . 5. Igen, és Q5 poláris formája: 1 1 B((x1 , x2 , x3 ), (y1 , y2 , y3 )) = x1 y1 + 2x2 y2 + x3 y3 - x1 y2 - x2 y1 + 2 2 3x2 y3 + 3x3 y2 - x1 y3 - x3 y1 .

1. LINEÁRIS, BILINEÁRIS ÉS KVADRATIKUS FORMÁK

57

6. Igen, és Q6 poláris formája: B((x1 , x2 , x3 ), (y1 , y2 , y3 )) = 4x2 y2 - x3 y3 + 2x1 y2 + 2x2 y1 + 3 3 - x2 y3 - x3 y2 + x 1 y3 + x 3 y1 . 2 2 2.13. Feladat. Írjuk fel az elz feladatban szerepl kvadratikus formák mátrixát, és számítsuk ki az (1, 2), illetve az (1, 2, 3) vektoron felvett értéküket. Megoldás. A Q kvadratikus forma C mátrixa megegyezik a poláris formájának mátrixával. Ha a forma az Rn vektortéren van értelmezve, akkor Q(x) kiszámítható az alábbi módon is: Q(x) = x Cx. 1. A Q3 : R2 R, Q3 (x1 , x2 ) = 2x1 x2 kvadratikus forma mátrixa és Q3 ((1, 2)) kiszámítása: C= 0 1 1 0 , Q((1, 2)) = 1 2 0 1 1 0 1 2 = 4.

2. A Q4 : R2 R, Q3 (x1 , x2 ) = x2 kvadratikus forma mátrixa 1 C= 1 0 0 0 ,

és Q4 ((1, 2)) = 12 = 1. 3. A Q5 (x1 , x2 , x3 ) = x2 + 2x2 + x2 - x1 x2 + 6x2 x3 - 2x1 x3 forma mátrixa: 1 2 3 1 -1/2 -1 -1/2 2 3 , -1 3 1 és Q5 ((1, 2, 3)) = 1 2 3 1 -1/2 -1 1 -1/2 2 3 2 = 46, -1 3 1 3

vagy közvetlenül is számolhatunk:

4. A Q6 (x1 , x2 , x3 ) = 4x2 - x2 + 4x1 x2 - 3x2 x3 + 2x1 x3 forma mátrixa: 2 3 0 2 1 2 4 -3/2 , 1 -3/2 -1 és Q6 ((1, 2, 3)) = 3.

Q5 ((1, 2, 3)) = 12 + 2 · 22 + 32 - 2 + 6 · 6 - 6 = 46.

58

2. EUKLIDESZI ÉS UNITÉR TEREK

2.14. Feladat. Mit mondhatunk az alábbi kvadratikus formákról definitség szempontjából a fminor-determinánsok alapján? 1. Q(x1 , x2 , x3 ) = x2 + x2 , 1 3 2. Q(x1 , x2 , x3 ) = x2 + 2x2 + 4x2 , 1 2 3 3. Q(x1 , x2 , x3 ) = x2 - x2 + x2 , 1 2 3 4. Q(x1 , x2 , x3 ) = x2 + 2x2 + 6x2 + 2x1 x2 - 4x1 x3 - 2x2 x3 , 1 2 3 5. Q(x1 , x2 , x3 ) = -x2 - 3x2 - 3x2 + 2x1 x2 + 2x1 x3 , 1 2 3 6. Q(x1 , x2 , x3 ) = x2 - 2x2 + 3x2 + 2x1 x2 - 4x1 x3 + 6x2 x3 , 1 2 3 7. Q(x1 , x2 , x3 ) = x2 + 4x2 + 4x1 x2 + 2x1 x3 . 1 2 Megoldás. Q pozitív definit, ha minden nem nulla vektoron felvett értéke pozitív, és Q pozitív szemidefinit, ha minden vektoron nemnegatív értéket vesz fel, de van nem nulla vektor, amit a nullába képez. Hasonlóan definiálható a negatív eset, és ha pozitív és negatív értéket is felvesz a forma, akkor indefinit. Egy Jacobitól származó tétel szerint, ha a kvadratikus forma mátrixában a fminor-determinánsokat 1 , . . . , n jelöli, és ezek egyike sem nulla, akkor létezik bázis, amelyben a kvadratikus forma az alábbi négyzetösszeg alakú: x2 + x2 . . . x2 . 2 n 1 1 1 n-1 Ennek következménye, hogy a forma pontosan akkor lesz pozitív definit, ha ezek a hányadosok mind pozitívak, és akkor negatív definit, ha mind negatívok. 1. Ez a kvadratikus forma elve normál alakú. Világos, hogy pozitív szemidefinit, hiszen Q(x) 0 minden x R3 esetén, de van olyan nem nulla vektor, amihez a nullát rendeli hozzá, például Q(0, 1, 0) = 0. 2. Ez a kvadratikus forma eleve kanonikus alakú, és pozitív definit, mert x2 + 2x2 + 4x2 0, és x2 + 2x2 + 4x2 = 0 csak akkor, ha x = 0. 1 2 3 1 2 3 3. Ez a normál alakú kvadratikus forma indefinit, hiszen pozitív és negatív értékeket is felvehet, például Q(1, 0, 0) = 1 és Q(0, 1, 0) = -1. 4. Írjuk fel a forma C mátrixát, és vizsgáljuk meg a fminor-determinánsokat: 1 1 -2 2 -1 , C= 1 -2 -1 6 Q(x) =
1 1 2 n

= |1| = 1,
1, 2,

2

=

1 1 1 2

= 1,

3

= |C| =

Mivel

3

mind pozitív, így Q pozitív definit.

1 1 -2 1 2 -1 -2 -1 6

= 1.

1. LINEÁRIS, BILINEÁRIS ÉS KVADRATIKUS FORMÁK

59

5. Írjuk fel a fminor-determinánsokat:
1

= | - 1| = -1, Mivel
1

2

=
2 1

-1 1 1 -3 1 = - , 2
3 2

= 2, = -

3

=

definit. 6. A fminor-determinánsok:
1

= -1,

2 mind negatív, így Q negatív 3

-1 1 1 1 -3 0 1 0 -3

= -3.

= |1| = 1,
1

2

=
2

1 1 1 -2 = -3,
3

= -3, =-

3

=

22 , így a forma indefinit. 3 1 2 7. Mivel a második fminor-determináns: 1 2 = 0, 2 = 2 4 Mivel = 1,

1 1 -2 1 -2 3 -2 3 3

= -22.

így ez a módszer itt nem mködik. A definitség eldönthet például a forma kanonikus alakra hozásával (lásd következ feladat). 2.15. Feladat. Hozzuk kanonikus alakra az alábbi kvadratikus formákat! (Adjuk meg a bázist is, amiben ez a kanonikus alak eláll, és döntsük el, hogy milyen definit a kvadratikus forma!) 1. Q(x1 , x2 , x3 ) = x2 - 2x2 - 4x2 + 2x1 x2 - 4x1 x3 + 8x2 x3 , 1 2 3 2. Q(x1 , x2 , x3 ) = x2 + x2 - 2x1 x2 + 4x1 x3 + 2x2 x3 , 2 3 3. Q(x1 , x2 , x3 ) = 2x2 + x2 + 2x2 - x1 x2 + 2x1 x3 , 1 2 3 4. Q(x1 , x2 , x3 ) = x2 + 2x2 + 6x2 + 2x1 x2 - 4x1 x3 - 2x2 x3 , 1 2 3 5. Q(x1 , x2 , x3 ) = -x2 - 3x2 - 3x2 + 2x1 x2 + 2x1 x3 , 1 2 3 6. Q(x1 , x2 , x3 ) = x2 + x2 + 4x2 + 2x1 x2 , 1 2 3 7. Q(x1 , x2 , x3 ) = x1 x2 + x1 x3 + x2 x3 , 8. Q(x1 , x2 , x3 ) = 2x1 x2 . 9. Q(x1 , x2 , x3 , x4 ) = x2 + x2 + 2x1 x3 + 2x2 x4 . 1 4 Megoldás. A feladat megoldásához a Lagrange módszert használjuk. 1. Az els lépésben a Q kvadratikus formát felbontjuk két másik összegére úgy, hogy az els négyzetes alakú, a második pedig egy kétváltozós kvadratikus forma, amiben az x1 változó már nem szerepel. Gyjtsük tehát össze a Q azon tagjait, amikben szerepel x 1 , és ezt a kifejezést alakítsuk teljes négyzetté: x2 + 2x1 x2 - 4x1 x3 = (x1 + x2 - 2x3 )2 - x2 - 4x2 + 4x2 x3 . 1 2 3

60

2. EUKLIDESZI ÉS UNITÉR TEREK

Tehát Q(x) = x2 + 2x1 x2 - 4x1 x3 - 2x2 - 4x2 + 8x2 x3 1 2 3 = (x1 + x2 - 2x3 )2 - 3x2 - 8x2 + 12x2 x3 , 2 3 = (x1 + x2 - 2x3 )2 - x2 - 4x2 + 4x2 x3 - 2x2 - 4x2 + 8x2 x3 2 3 2 3

és itt a négyzetes alakon kívül lév tagokban valóban nem szerepel x 1 . Most ezekre a tagokra vonatkozóan megismételjük az elz eljárást x 2 vel: Q(x) = (x1 + x2 - 2x3 )2 - 3x2 - 8x2 + 12x2 x3 2 3
y1 y2 y3 2 2 2 = (x1 + x2 - 2x3 )2 - 3(x2 - 2x3 )2 + 4 x2 = y1 - 3y2 + 4y3 . 3

Ezzel elértük, hogy a kvadratikus forma négyzetösszeg alakú (azaz kanonikus alakú), ha a régi (x1 , x2 , x3 ) koordinátákról áttérünk az (y1 , y2 , y3 ) új koordinátákra, ahol y1 = x1 +x2 -2x3 y2 = x2 -2x3 y3 = x3 a koordinátatranszformáció egyenletrendszere, aminek mátrixos alakja a következ: 1 1 -2 y = 0 1 -2 x. 0 0 1

Keressük tehát azt a (b) bázist, amire ha áttérünk az (e) természetes bázisról, akkor a vektorok koordinátái a fenti módon változnak meg. A koordinátatranszformáció és a bázistranszformáció kapcsolatáról tanultak alapján, a fenti egyenletben szerepl mátrix nem más, mint az (e) (b) bázistranszformáció S mátrixának az inverze, így -1 1 1 -2 1 -1 0 S = 0 1 -2 = 0 1 2 . 0 0 1 0 0 1

A feladat ezzel kész: az új bázis vektorai S oszlopvektorai, ebben a bázisban Q kanonikus alakú, a kanonikus alakban szerepl együtthatók 1,-3,4, tehát a forma indefinit.

1. LINEÁRIS, BILINEÁRIS ÉS KVADRATIKUS FORMÁK

61

tehát megkaptuk Q mátrixát az új bázisban, ami valóban diagonális alakú. 2. Hozzuk a kvadratikus formát négyzetösszeg alakra. Elször elérjük, hogy x2 ne szerepeljen négyzetes alakon kívül, majd a második lépésben elérjük, hogy x1 is csak négyzetes alakokban szerepeljen (a kiinduló alakban nincs x2 , ezért kezdünk x2 -vel): 1 Q(x) = x2 + x2 - 2x1 x2 + 2x2 x3 + 4x1 x3 2 3 = (x2 - x1 + x3 )2 - x2 + 6x1 x3 1
2 2 2 = (x2 - x1 + x3 )2 - (x1 - 3x3 )2 + 9x2 = y1 - y2 + 9y3 . 3

Számításaink helyességét leellenrizhetjük úgy, hogy kiszámítjuk az S CS mátrixot, ahol C jelöli a Q mátrixát a természetes bázisban: 1 0 0 1 1 -2 1 -1 0 1 0 0 -1 1 0 1 -2 4 0 1 2 = 0 -3 0 , 0 2 1 -2 4 -4 0 0 1 0 0 4

Látható, hogy a kvadratikus mátrixa meghatározható az -1 y= 1 0 egyenlet alapján:

forma indefinit, és a bázistranszformáció 1 1 0 -3 x = S -1 x. 0 1

Tehát a (0, 1, 0), (1, 1, 0), (3, 2, 1) vektorokból álló bázisban a kvadratikus forma kanonikus alakú, azaz mátrixa diagonális, a fátlóban az 1,-1,9 számok szerepelnek. 3. Hasonlóan, Q(x) = 2x2 - x1 x2 + 2x1 x3 + x2 + 2x2 1 2 3 1 1 = 2 x1 - x2 + x3 4 2 1 1 = 2 x1 - x2 + x3 4 2 7 2 10 2 2 = 2y1 + y2 + y3 . 8 7
2

0 1 3 S = 1 1 2 . 0 0 1



7 3 1 + x2 + x2 + x2 x3 2 3 8 2 2 + 7 8 2 x2 + x3 7
2

2

+

10 2 x 7 3

62

2. EUKLIDESZI ÉS UNITÉR TEREK

ennek oszlopvektorai adják az új bázis vektorait, és a kvadratikus forma pozitív definit, mert a kanonikus alakban szerepl együtthatók mind pozitívak. 4. Írjuk fel Q-t négyzetösszeg alakban: Q(x) = x2 + 2x2 + 6x2 + 2x1 x2 - 4x1 x3 - 2x2 x3 1 2 3 = (x1 + x2 - 2x3 )2 + x2 + 2x2 + 2x2 x3 2 3
2 2 2 = (x1 + x2 - 2x3 )2 + (x2 + x3 )2 + x2 = y1 + y2 + y3 . 3

A bázistranszformáció mátrixa: -1 1 -1/4 1/2 1 1/4 -4/7 1 2/7 = 0 1 -2/7 , S= 0 0 0 1 0 0 1

ennek oszlopvektorai adják az új bázis vektorait. Itt a kanonikus alak egyben normál alak is, és az ebben szerepl együtthatók mind pozitívak, így a kvadratikus forma pozitív definit. 5. Az elzekhez hasonlóan: Q(x) = -x2 - 3x2 - 3x2 + 2x1 x2 + 2x1 x3 1 2 3 1 = -(x1 - x2 - x3 )2 - 2 x2 - x3 2 = -(x1 - x2 - x3 )2 - 2x2 - 2x2 + 2x2 x3 2 3
2

A bázistranszformáció mátrixa: -1 1 -1 3 1 1 -2 S = 0 1 1 = 0 1 -1 , 0 0 1 0 0 1

3 3 2 2 2 - x2 = -y1 - 2y2 - y3 . 3 2 2

ennek oszlopvektorai adják az új bázis vektorait. Itt a kanonikus alakban minden együttható negatív, így a kvadratikus forma negatív definit. 6. Most egy lépés után négyzetösszeg alakot kapunk: Q(x) = x2 + x2 + 4x2 + 2x1 x2 1 2 3
2 2 = (x1 + x2 )2 + 4x2 = y1 + 4y3 . 3

A bázistranszformáció mátrixa: -1 1 -1 -1 1 1 3/2 S = 0 1 -1/2 = 0 1 1/2 , 0 0 1 0 0 1

1. LINEÁRIS, BILINEÁRIS ÉS KVADRATIKUS FORMÁK

63

és a kvadratikus forma pozitív szemidefinit, mert a kanonikus alakban szerepl együtthatók: 1,0,4. 7. Ebben az esetben úgy kell négyzetösszeg alakra hoznunk Q-t, hogy egyetlen négyzetes tag sem szerepel eredetileg benne, azaz mátrixának fátlójában csak nullák állnak. Ekkor végrehajtunk egy olyan koordinátatranszformációt, aminek eredményeként az x 1 x2 tagból négyzetes tagok keletkeznek, és ezután alkalmazhatjuk az elzekben már leírt módszert. Térjünk tehát át azon y1 , y2 , y3 koordinátákra, amikre teljesül, hogy x1 = y 1 + y 2 x2 = y 1 - y 2 x3 = y3 . Ekkor Q(x) = x1 x2 + x1 x3 + x2 x3 = (y1 + y2 )(y1 - y2 ) + (y1 + y2 )y3 + (y1 - y2 )y3
2 2 2 2 = y1 - y2 + 2y1 y3 = (y1 + y3 )2 - y2 - y3 2 2 2 = z1 - z2 - z3 .

Itt a koordinátatranszformációban y 2 = x2 , és y2 együtthatója a kanonikus alakban nulla. A bázistranszformáció mátrixa: -1 1 1 0 1 -1 0 S = 0 1 0 = 0 1 0 , 0 0 1 0 0 1

Megkaptuk tehát a négyzetösszeg alakot (ami most normál alak is egyben), de hogyan határozzuk meg a bázist, amiben a kvadratikus forma ilyen alakú lesz? Elször x-koordinátákról y-okra tértünk át, majd az y-okról z-kre. Az alábbi összefüggéseket ismerjük: 1 1 0 1 0 1 x = 1 -1 0 y = P y és z = 0 1 0 y = Ry. 0 0 1 0 0 1

Innen x = P y = P R-1 z, és itt a régi koordinátákat fejeztük ki az újakkal, így a bázistranszformáció mátrixa: 1 1 0 1 0 -1 1 1 -1 S = P R-1 = 1 -1 0 0 1 0 = 1 -1 -1 . 0 0 1 0 0 1 0 0 1

64

2. EUKLIDESZI ÉS UNITÉR TEREK

tehát eredményeink helyesek, a kapott diagonális mátrix a kvadratikus forma új bázisbeli mátrixa. 8. Alkalmazzuk most is azt a koordinátatranszformációt, aminek egyenletrendszere x1 = y 1 + y 2 x2 = y 1 - y 2 x3 = y3 .
2 2 Ekkor Q(x) = 2x1 x2 = 2y1 - 2y2 , és a bázistranszformáció mátrixa: 1 1 0 S = 1 -1 0 . 0 0 1

Ellenrzés céljából számítsuk ki az S CS mátrixot: 0 1 1 1 1 0 1 1 -1 1 0 0 2 2 1 -1 0 1 0 1 1 -1 -1 = 0 -1 0 , 2 2 1 1 -1 -1 1 0 0 1 0 0 -1 0 2 2

9. Az els lépésben az x1 -es tagokat gyjtjük össze, majd az x 4 -es tagokat: Q(x) = x2 + x2 + 2x1 x3 + 2x2 x4 1 4 = (x1 + x3 )2 - x2 + x2 + 2x2 x4 3 4 ahol
2 2 2 2 = (x1 + x3 )2 + (x4 + x2 )2 - x2 - x2 = y1 - y2 - y3 + y4 , 2 3

Valóban, ha kiszámoljuk 1 1 0 0 1 1 -1 0 1 0 0 0 1 0 0

az S CS mátrixot: 0 1 1 0 2 0 0 0 1 -1 0 = 0 -2 0 . 0 0 0 1 0 0 0

y1 = x 1 +x3 y2 = x2 y3 = x3 y4 = x2 +x4 . Ebben az egyenletrendszerben az új koordináták vannak kifejezve a régiekkel, így a bázistranszformáció mátrixát az alapmátrix inverzeként kapjuk meg: -1 1 0 1 0 1 0 -1 0 0 1 0 0 0 0 = 0 1 . S= 0 0 1 0 0 0 1 0 0 1 0 1 0 -1 0 1

1. LINEÁRIS, BILINEÁRIS ÉS KVADRATIKUS FORMÁK

65

2.16. Feladat. Módosítsuk úgy az elz feladat 1. 2. és 8. pontjában szerepl kvadratikus formák kanonikus alakra hozásának eljárását úgy, hogy normál alakot kapjunk. Megoldás. A kvadratikus forma normál alakja olyan kanonikus alak, amelyben csak +1, -1 és 0 együtthatók szerepelhetnek. 1. A kanonikus alakra hozás során az alábbi négyzetösszeg alakot kaptuk: Vigyük be a zárójelek eltt szerepl 3 és 4 együtthatókat a zárójeleken belülre: 2 2 2 Q(x) = (x1 + x2 - 2x3 )2 - ( 3x2 - 2 3x3 )2 + (2x3 )2 = y1 - y2 + y3 , ahol y1 = x 1 2 +x -2x3 y2 = 3x2 -2 3x3 , y3 = 2x3 így a bázistranszformáció mátrixa: -1 1 1 -2 1 -1/ 3 0 S= 0 3 -2 3 = 0 1/ 3 1 . 0 0 2 0 0 1/2
2 2 2 Q(x) = (x2 - x1 + x3 )2 - (x1 - 3x3 )2 + 9x2 = y1 - y2 + y3 , 3

Q(x) = (x1 + x2 - 2x3 )2 - 3(x2 - 2x3 )2 + 4x2 3

2. Hasonlóan:

3. Koordinátacsere után az alábbi alakot kaptuk: Ha azt a transzformációt hajtjuk végre, ahol x1 = x2 = x3 = akkor
1 y1 2 1 y1 2

ahol a bázistranszformáció mátrixa: -1 1 1 0 1 1 S = 1 0 -3 -1 = 1 1 2/3 . 0 0 3 0 0 1/3
2 2 Q(x) = 2x1 x2 = 2y1 - 2y2 .

+ -

1 y2 2 1 y2 2

y3 ,

2 2 Q(x) = (y1 + y2 )(y1 - y2 ) = y1 - y2 .

66

2. EUKLIDESZI ÉS UNITÉR TEREK

2.17. Feladat. Hogyan változik meg egy kvadratikus forma mátrixa, ha végrehajtunk egy olyan bázistranszformációt, aminek a mátrixa egy elemi oszlopátalakításhoz tartozó elemi mátrix? Megoldás. A kvadratikus forma mátrixán is végrehajtódik az elemi oszlopátalakítás, és egy ugyanilyen típusú sorátalakítás is. Lássunk elször egy példát! Legyen Q mátrixa valamely bázisban 1 0 -2 C = 0 2 1 . -2 1 -1 Tekintsük például azt az elemi átalakítást, mikor egy mátrix második oszlopához hozzáadjuk az els oszlop kétszeresét. Az ehhez tartozó elemi mátrix: 1 2 0 = 0 1 0 . 0 0 1 Ha végrehajtjuk azt a bázistranszformációt, aminek mátrixa mátrixa az új bázisban C, azaz 1 0 0 1 0 -2 1 2 0 1 2 2 1 0 0 2 1 0 1 0 = 2 6 0 0 1 -2 1 -1 0 0 1 -2 -3 -2 -3 , -1

Ekkor a bázistranszformáció mátrixa: 1/2 1/ 0 2 S = 1/ 2 -1/ 2 0 . 0 0 1

, akkor Q

tehát az eredeti C mátrixon végrehajtódik két elemi átalakítás: az els oszlop kétszeresének hozzáadása a második oszlophoz, és az els sor kétszeresének hozzáadása a második sorhoz. Ennek oka az, hogy az mátrixszal való jobbról szorzás a megfelel oszlop átalakítás végrehajtását jelenti, míg az mátrixszal való balról szorzás azon sorátalakítás végrehajtását jelenti, aminek mátrixa . Ez természetesen tetszleges esetén is igaz.

2.18. Feladat. Hozzuk kanonikus alakra az alábbi kvadratikus formákat eliminációval, az elz feladat alapján! Adjuk meg az új bázist is! 1. Q(x1 , x2 , x3 ) = x2 - 2x2 - 4x2 + 2x1 x2 - 4x1 x3 + 8x2 x3 , 1 2 3 2. Q(x1 , x2 , x3 ) = x2 + x2 - 2x1 x2 + 4x1 x3 + 2x2 x3 , 2 3 3. Q(x1 , x2 , x3 ) = x1 x2 + x1 x3 + x2 x3 .

1. LINEÁRIS, BILINEÁRIS ÉS KVADRATIKUS FORMÁK

67

Megoldás. Ha a kvadratikus forma mátrixa a természetes bázisra vonatkozóan C, és egymás után végrehajtjuk azon bázistranszformációkat, amiknek mátrixai az 1 , . . . , n elemi mátrixok, akkor az új bázisban Q mátrixa: n . . . 1 C1 . . . n = (1 . . . n ) C1 . . . n . Ha tehát elérjük, hogy ez a mátrix diagonális legyen, akkor abban a bázisban aminek elemei az 1 . . . n mátrix oszlopaiban találhatók, a Q kanonikus alakú lesz. Kiindulunk tehát a (C|E) mátrixból, és úgy eliminálunk, hogy C-n sor-oszlop átalakításokat végzünk (például ha a második sorhoz hozzáadjuk az els sor kétszeresét, akkor a második oszlophoz is hozzáadjuk az els oszlop kétszeresét), de E-n csak a sorátalakítást hajtjuk végre. Ha C helyén diagonális mátrix alakul ki, akkor E helyén a bázistranszformáció mátrixának transzponáltja fog szerepelni: (C|E) (D|S ).

1. Az els lépésben elérjük, hogy az aláhúzott értékek helyén nulla legyen. Kivonjuk C els sorát a másodikból, és az els sor kétszeresét hozzáadjuk a harmadik sorhoz, ugyanúgy, ahogy az inverzszámításos szimultán Gauss eliminációnál csináltuk, tehát ezeket az átalakításokat E-n is végrehajtjuk. Ezután oszlopokra is végre kell ugyanezt hajtani (csak C-n), 1 de mivel az els oszlop már 0 alakú, így ez csak annyit jelent, hogy 0 az els sor is (1, 0, 0) lesz. A szimmetria miatt mindig ilyen könny dolgunk lesz: 1 1 -2 1 0 0 1 0 0 1 0 0 1 -2 4 0 1 0 0 -3 6 -1 1 0 -2 4 -4 0 0 1 0 6 -8 2 0 1 1 0 0 1 0 0 0 -3 0 -1 1 0 . 0 0 4 0 2 1 1 -1 0 Azt kaptuk, hogy az 0 , 1 , 2 bázisban Q kanonikus 0 0 1 2 - 3y 2 + 4y 2 . Ugyanazt az eredményt kaptuk, mint a alakú: Q(y) = y1 2 3 2.15 feladatnál, ez azonban nem szükségszer. Hangsúlyozzuk azonban, hogy bárhogyan is hozzuk kanonikus alakra a kvadratikus formát, a pozitív, negatív és nulla együtthatók száma mindig ugyanannyi.

68

2. EUKLIDESZI ÉS UNITÉR TEREK

2. Most C-ben az els sort a második sorral, majd az els oszlopot a másodikkal megcseréljük, E-ben pedig csak a sorokat cseréljük. Ezután az elzekhez hasonlóan folytatjuk az eliminációt: 0 -1 2 1 0 0 1 -1 1 0 1 0 -1 1 1 0 1 0 -1 0 2 1 0 0 2 1 1 0 0 1 1 2 1 0 0 1 1 0 0 0 -1 3 0 3 0 0 1 0 1 0 0 0 -1 0 1 1 0 0 -1 1 0 0 9 0 1 0 1 1 0 . 3 2 1

3. Itt a sor-oszlop csere nem vezetne eredményre, az els sorhoz hozzáadjuk a második sort, és az els oszlophoz a másodikat: 1 1 0 0 1/2 1/2 1 0 0 1 1/2 1 1/2 0 1/2 0 1 0 , 0 1 0 1/2 0 1/2 0 0 1 1 1/2 0 0 0 1 1/2 1/2 0 megszorozhatjuk 2-vel 1 1 1 1 1 1 0 1 0 2 1 1 0 0 0 a második 0 0 1 sort és oszlopot: 1 0 0 0 -1 0 0 0 -1 1 1 0 -1 1 0 . -1 -1 1

2. Euklideszi terek
2.19. Feladat. Definiálhatnak-e bels szorzást R 3 -ban az alábbi bilineáris formák? Ha igen, akkor számítsuk ki az x = (1, 2, 3) vektor ||x|| B normáját! 1. B (x1 , x2 , x3 ), (y1 , y2 , y3 ) = x1 y1 + x2 y2 + x3 y3 , 2. B (x1 , x2 , x3 ), (y1 , y2 , y3 ) = 2x1 y1 - 2x1 y2 + x1 y3 - 2x2 y1 + x3 y1 + x3 y3 , 3. B (x1 , x2 , x3 ), (y1 , y2 , y3 ) = 6x1 y1 +x1 y2 +2x1 y3 +x2 y1 +x2 y2 +2x3 y1 + x3 y3 . Megoldás. Egy bilineáris forma akkor definiálhat bels szorzást egy vektortéren, ha szimmetrikus, és a belle származó kvadratikus forma pozitív definit. 1. Ennek a bilineáris formának a mátrixa az egységmátrix, ami szimmetrikus és valamennyi fminor-determinánsa pozitív, így ez bels szorzás. (Az Rn vektortéren alapértelemben ezt a bilineáris formát tekintjük bels

2. EUKLIDESZI TEREK

69

szorzásnak, és ekkor (x, y) = x y = x1 y1 + · · · + xn yn .) Az x = (1, 2, 3) vektor normája: ||x|| = B(x, x) = x2 + x2 + x2 = 12 + 22 + 32 = 14. 1 2 3 2. Ennek a bilineáris formának is szimmetrikus a mátrixa: 2 -2 1 C = -2 0 0 , 1 0 1 2 -2 -2 0

de a B-bl származó kvadratikus forma nem pozitív definit, mert ennek a mátrixnak a második sarokminor-determinánsa negatív:
1

= 2,

2

=

= -4.

3. Ezen bilineáris forma mátrixa szimmetrikus, és a fminor-determinánsok mind pozitívak: 6 1 2 6 1 = 5, 1 = 6, 2 = 3 = 1 1 0 = 1, 1 1 2 0 1 így B segítségével definiálhatunk 6 ||x||2 = (1 2 3) 1 B 2 bels szorzást, és ekkor 1 2 1 1 0 2 = 35. 0 1 3

2.20. Feladat. Határozzuk meg az R3 -beli x és y vektorok normáját, távolságát és az általuk bezárt szöget, ha 1. x = (2, 1, 2), y = (-1, 2, 0), 2. x = (3, -1, 1), y = (1, 1, 1), 3. x = (0, 2, 0), y = (2, -1, 4). Megoldás. Egy x vektor normája (x, x), két vektor távolsága a különbségük normája, és két vektor által bezárt szög cosinusát megkapjuk, ha a bels szorzatukat elosztjuk a normáikkal. 1. ||x|| = 22 + 12 + 22 = 3, ||y|| = (-1)2 + 22 = 5, d(x, y) = ||x - y|| = ||(3, -1, 2)|| = 14, (x, y) 2(-1) + 1 · 2 + 2 · 0 cos = = = 0, tehát a két vektor merle||x||||y|| 3 5 ges.

70

2. EUKLIDESZI ÉS UNITÉR TEREK

2. ||(3, -1, 1)|| = 11, ||(1, 1, 1)|| = 3, ||x - y|| = ||(2, -2, 0)|| = 2 2, (x, y) 3-1+1 3 cos = = = . ||x||||y|| 11 33 3. ||(0, 2, 0)|| = 2, ||(2, -1, 4)|| 21, = ||x - y|| = ||(-2, 3, -4)|| = 29, (x, y) -2 1 cos = = = - . ||x||||y|| 2 21 21 2.21. Feladat. Mit mondhatunk két adott vektor által bezárt szögrl, ha tudjuk, hogy bels szorzatuk 1. nulla, 2. pozitív, 3. negatív? Megoldás. 1. Két vektor pontosan akkor merleges, ha bels szorzatuk nulla. 2. Ha a vektor bels szorzata pozitív, akkor az általuk bezárt szög cosinusa is pozitív, így ez hegyesszög. 3. Ekkor tompaszöget zárnak be. 2.22. Feladat. Mi (x, e) geometriai jelentése az R n téren, ha ||e|| = 1? Megoldás. Ha jelöli az x és e által bezárt szöget, akkor cos = (x, e) , ||x||
x

így (x, e) = ||x|| cos , tehát az x vektor e irányú egyenesre vett merleges vetületének hossza. (Magát a merleges vetületet az (x, e)e vektor adja.) PSfrag replacements
e cos ||x||

2.23. Feladat. Határozzuk meg az x vektor e irányba es merleges vetületét, ha 1 1. x = (3, -1, 2), e = 3 (1, 1, 1), 2. x = (5, 5, -3), e = (1, 2, -1), 3. x = (6, 2, 6, 2), e = (1, 1, 1, 1).

2. EUKLIDESZI TEREK

71

Megoldás. 1. Mivel e egységvektor, így a vetületet x = (x, e)e adja: 3 1 1 1 1 1 3·1-1·1+2·1 -1 , 1 1 = 1 x = 3 3 1 3 1 2 1 4/3 = 4/3 . 4/3

(A jobb áttekinthetség érdekében most < > zárójellel jelöltük a skaláris szorzatot. Emlékezzünk, hogy a bels szorzás bilineáris, így a skalár kiemelhet mindkét változójából, itt az 1/ 3 számot kihoztuk a zárójel elé!) Ellenrizhetjük is, hogy helyesen számoltunk-e. Ha a vetületet x jelöli, akkor x := x-x merleges x -re. Valóban, x = (5/3, -7/3, 2/3) és x bels szorzata nulla. 2. (a) Most e nem egységhosszú, így elször lenormáljuk. Ez azt jeleni, hogy elosztjuk a hosszával, hogy egy vele egyez irányú de már 1 normájú vektort kapjuk: 1 e 1 2 . e := = ||e|| 6 -1 Most már e segítségével megkaphatjuk a vetületet: 5 1 1 1 3 1 18 5 , 2 2 2 6 . (x, e )e = = = 6 6 -1 -3 -1 -1 -3
x e x = e x =x +x

(b) Másképp is számolhatunk: tudjuk, hogy a vetület e konstansszorosa. PSfrag replacements

Keressük tehát azt az = 0 valós számot, amire igaz, hogy ha x = e, és x = x - x , akkor x és x merlegesek, azaz a bels szorzatuk nulla: 0 = (x , x ) = (e, x - e) = (e, x) - 2 (e, e) =

72

2. EUKLIDESZI ÉS UNITÉR TEREK

1 5 2 , 5 -1 -3





- 2



1 1 2 , 2 -1 -1
||e||2

= 18 - 62 .

Innen = 3 és a merleges vetület: x = 3e. 3. Keressük azt az = 0 valós számot, amire x = x és x = x - x ortogonálisak, tehát 0 = (e, x - e) = (e, x) - 2 ||e||2 = 16 - 42 . Innen = 4, és a merleges vetület (4, 4, 4, 4). 2.24. Feladat. Ha tudjuk, hogy ||x|| = 3, ||y|| = 5, és (x, y) = 1, akkor mivel egyenl ||x + y||? Megoldás. Mivel ||x + y||2 = (x + y, x + y) = (x, x) + 2(x, y) + (y, y) így ||x + y|| = 6. = ||x||2 + 2(x, y) + ||y||2 = 9 + 2 + 25 = 36,

2.25. Feladat. Milyen szám esetén lesz az x - y vektor minimális normájú, ha x = (-1, 10, 7), y = (-1, 2, 3)? Megoldás. (a) Akkor lesz minimális normájú, ha y éppen az x vektor y irányban vett merleges vetülete, x PSfrag replacements
x - y y y

tehát ha 0 = (x - y, y) = (x, y) - ||y|| 2 = 42 - 14. Innen = 3. (b) Ugyanezt az eredményt kapjuk, ha kiszámoljuk, hogy mennyi ||x-y|| 2 : ||(-1 + , 10 - 2, 7 - 3)||2 = (-1 + )2 + (10 - 2)2 + (7 - 3)2 = 142 - 84 + 150 = 14( - 3)2 + 24.

Látható, hogy ez a kifejezés = 3 esetén minimális. 2.26. Feladat. Milyen szöget zárnak be az x és y egységvektorok, ha tudjuk, hogy x + 2y és 5x - 4y merlegesek egymásra?

2. EUKLIDESZI TEREK (x,y)

73

Megoldás. Mivel cos = ||x||||y|| és x, y hossza 1, így csak (x, y)-t kell kiszámolnunk. Tudjuk, hogy 0 = (x + 2y, 5x - 4y) = 5(x, x) + 10(y, x) - 4(x, y) - 8(y, y) Innen cos = (x, y) = 1/2, tehát 60 -os szöget zárnak be. 2.27. Feladat. Mely vektorok lesznek merlegesek az n vektorra a megadott Euklideszi terekben? Milyen geometriai alakzatot alkotnak ezek a vektorok? 1. n = (1, 2) R2 , 2. n = (0, 0, 1) R3 , 3. n = (1, 2, -1) R3 , 4. n = (1, -1, -2, 1) R4 . Megoldás. Ha egy vektor merleges n-re, akkor a vektor tetszleges skalárszorosai is azok lesznek, illetve két n-re merleges vektor összege is merleges lesz n-re, így az ilyen vektorok egy alteret fognak alkotni. 1. Keressük azon x = (x1 , x2 ) vektorokat, amelyekre (n, x) = 0, azaz n1 x1 + n2 x2 = x1 + 2x2 = 0. Ez egy homogén lineáris egyenletrendszer, ami egy egyenletbl áll, és megoldásai az alábbi vektorok: x1 x2 = -2 t, 1 t R, = 5||x||2 + 6(x, y) - 8||y||2 = 6(x, y) - 3.

tehát a (-2, 1) irányú origón átmen egyenes pontjai. A fenti egyenlet az (1, 2) normálvektorú, 0-n átmen egyenes normálvektoros egyenlete. 2. Keressük azon x = (x1 , x2 , x3 ) vektorokat, amelyekre (n, x) = 0, azaz n1 x1 + n2 x2 + n3 x3 = x3 = 0. Ezen homogén lineáris egyenlet megoldásai az alábbi vektorok: 0 x1 1 x2 = 0 t1 + 1 t2 , t1 , t2 R, x3 0 0

tehát az [x, y] sík pontjai. A fenti egyenlet a (0, 0, 1) normálvektorú, 0-n átmen sík normálvektoros egyenlete. 3. A keresett vektorokat az alábbi egyenlet adja meg: n1 x1 + n2 x2 + n3 x3 = x1 + 2x2 - x3 = 0.

74

2. EUKLIDESZI ÉS UNITÉR TEREK

tehát az (1, 0, 1), (-2, 1, 0) vektorok által generált altér, ami egy origón átmen sík. 4. Keressük azon x = (x1 , x2 , x3 , x4 ) vektorokat, amelyekre (n, x) = n1 x1 + n2 x2 + n3 x3 + n4 x4 = x1 - x2 - 2x3 + x4 = 0, Innen x1 -1 2 1 x2 0 0 1 = t1 + t2 + t3 , x3 0 1 0 1 0 0 x4

Ezen homogén lineáris egyenlet megoldásai az alábbi vektorok: x1 -2 1 x2 = 0 t1 + 1 t2 , t1 , t2 R, x3 1 0

t 1 , t 2 , t 3 R,

tehát egy három dimenziós altér.

Általánosságban elmondható, hogy egy n-dimenziós Euklideszi térben adott vektorra merleges vektorok egy (n-1)-dimenziós alteret alkotnak, azaz egy origón átmen hipersíkot. 2.28. Feladat. Írjuk fel az n normálvektorú, r-re illeszked sík egyenletét R3 -ban! 1. n = (1, 2, 3), r = (1, 1, 1), 2. n = (-2, 1, 4), r = (2, 3, -1), 3. n = (1, 1, 1), r = (1, 1, 1). Állapítsuk meg, hogy a z = (2, -1, 2) vektor eleme-e a síkok valamelyikének! Megoldás. Egy x = (x1 , x2 , x3 ) vektor pontosan akkor lesz eleme az n normálvektorú és r-re illeszked síknak, ha az x - r vektor merleges az n normálvektorra, azaz ha teljesül, hogy (x - r, n) = 0. Átrendezés után (x, n) = (r, n) adódik, ami koordinátákkal írva: x1 n1 + x 2 n2 + x 3 n3 = r 1 n1 + r 2 n2 + r 3 n3 . (A középiskolás tananyagban szerepelt az egyenes normálvektoros egyenlete, ami analóg a fenti egyenlettel: x1 n1 + x2 n2 = r1 n1 + r2 n2 .)

2. EUKLIDESZI TEREK

75

n x-r x

PSfrag replacements

r

1. Helyettesítsük be a megfelel koordinátákat a fenti egyenletbe: x1 + 2x2 + 3x3 = 6. Mivel a (2, -1, 2) vektor koordinátái teljesítik az egyenletet, így z eleme a síknak. 2. A keresett egyenlet: -2x1 + x2 + 4x3 = -5, és z nem eleme a síknak. 3. Az egyenlet: x1 + x2 + x3 = 3, és z eleme a síknak. 2.29. Feladat. Írjuk fel annak a síknak az egyenletét, ami illeszkedik az alábbi három pontra! 1. a = (3, 2, 1), b = (2, 1, 2), c = (0, 0, 5), 2. a = (-1, 1, 1), b = (2, 2, 0), c = (-3, 1, -1), 3. a = (-5, 1, 1), b = (0, -2, 0), c = (-2, 1, 4). Megoldás. 1. Keresünk egy olyan n vektort, ami merleges a síkra, így merleges a b - a = (-1, -1, 1) és a c - a = (-3, -2, 4) vektorra is, tehát -n1 - n2 + n3 = 0 -3n1 - 2n2 + 4n3 = 0.

Ha ezt az egyenletrendszert megoldjuk, akkor azt kapjuk, hogy n = (2, -1, 1)t, t R. Válasszuk t-t 1-nek, ekkor a sík normálvektora (2, -1, 1), és a keresett egyenlet (x, n) = (a, n), azaz 2. Hasonlóan, b-a = (3, 1, -1), c-a = (-2, 0, -2), és a sík normálvektora megkapható az 3n1 + n2 - n3 = 0 -2n1 - 2n3 = 0 -x1 + 4x2 + x3 = 6. 2x1 - x2 + x3 = 5.

egyenletrendszerbl: n := (-1, 4, 1). A sík egyenlete

76

2. EUKLIDESZI ÉS UNITÉR TEREK

3. Most b - a = (5, -3, -1), c - a = (3, 0, 3), az egyenletrendszerre pedig 5n1 - 3n2 - n3 = 0 3n1 + 3n3 = 0 2.30. Feladat. Írjuk fel az R3 -beli r pontra illeszked és v irányvektorú egyenes egyenletrendszerét! 1. r = (1, 2, -1), v = (1, 3, 1), 2. r = (-1, 0, 4), v = (-1, 2, 3), 3. r = (-1, 3, 4), v = (2, -1, 0), 4. r = (1, 0, 0), v = (1, 0, 0). adódik. Legyen n = (-1, -2, 1), így a sík egyenlete: -x 1 -2x2 +x3 = 4.

Megoldás. R3 -ban egy egyenest nem egy, hanem két egyenlettel lehet jellemezni. Egy x = (x1 , x2 , x3 ) pont akkor és csak akkor lesz eleme az egyenesnek, ha x = r + tv valamely t valós szám esetén. Ez a három koordinátára egy-egy egyenletet jelent: x1 = r1 + tv1 x2 = r2 + tv2 x3 = r3 + tv3 . Ezekbl t-t kifejezve azt kapjuk, hogy x1 - r 1 x2 - r 2 x3 - r 3 = = , v1 v2 v3 ha v-nek nincs nulla koordinátája, ez az egyenes kanonikus egyenletrendszere. 1. Az egyenes egyenletrendszere: x2 - 2 = x3 + 1, 3 ami egy két egyenletbl álló lineáris egyenletrendszerrel egyenérték. Ugyanez az egyenes tehát megadható például az alábbi egyenletrendszerrel is: = 1 3x1 -x2 x1 -x3 = 2. x1 - 1 = x1 + 1 x2 x3 - 4 = = , -1 2 3

2. Az egyenes egyenletrendszere:

2. EUKLIDESZI TEREK

77

és ebbl például az alábbi egyenletrendszer írható fel: -2x1 -x2 = 2 3x2 -2x3 = -8

(A két egyenlet egy-egy síkot ad meg, az egyenes tehát ezen két sík metszete. Természetesen más egyenletrendszer is jellemezheti ugyanezen egyenest.) 3. Most v-nek van nulla koordinátája, ezért tekintsük elször a paraméteres alakot: x1 = -1 + 2t x2 = 3 - t x3 = 4, tehát az egyenes egyenletrendszere x2 - 3 x1 + 1 = , x3 = 4. 2 -1 4. Ez az egyenes az úgynevezett x-tengely. A paraméteres egyenletrendszer: x1 = 1 + t x2 = 0 x3 = 0, tehát x1 tetszleges lehet, és az egyenest meghatározó két egyenlet: x2 = 0, x3 = 0. 2.31. Feladat. Gram-Schmidt ortogonalizációs eljárással ortonormáljuk az alábbi vektorrendszereket! 1. b1 = (1, 2, 1), b2 = (-1, 2, 0), b3 = (2, -1, 1), 2. b1 = (1, 1, 1), b2 = (0, 1, 2), b3 = (2, 3, 1), 3. b1 = (1, 1, 1), b2 = (1, 1, 2), b3 = (1, 2, 3), 4. b1 = (1, 2, 1), b2 = (2, 1, 2), b3 = (-1, 1, 1), 5. b1 = (0, 1, 0, 1), b2 = (-1, 2, 0, 1), b3 = (2, -1, 1, 0). Megoldás. Az ortonormált vektorrendszer els elme e1 = elemet pedig az els k - 1 elem ismertében e k =
ek ||ek ||

adja, ahol

b1 ||b1 || ,

a k-adik

ek = bk - (bk , e1 )e1 - · · · - (bk , ek-1 )ek-1 .

78

2. EUKLIDESZI ÉS UNITÉR TEREK

e2 = b3 - (b3 , e1 )e1 - (b3 , e2 )e2 2 1 1 2 -3 -3 2 1 1 -1 , 2 2 - -1 , 2 2 = -1 - 6 14 1 1 1 1 -1 -1 1 2 1 -3 -2 1 -9 1 2 - 2 -1 , = -1 - = 6 1 14 -1 21 1 4 -2 1 e3 = -1 . 21 4 1 -1 -1 1 1 1 1 , e = 0 , e = 2 . 2. e1 = 3 2 3 2 6 1 1 -1 1 -1 -1 1 1 1 1 , e2 = -1 , e3 = 1 . 3. e1 = 3 6 2 1 2 0 1 1 -1 1 1 1 4. e1 = 6 2 , e2 = 3 -1 , e3 = 2 0 . 1 1 1 0 -2 1 1 1 1 1 1 1 5. e1 = 2 , e2 = 6 , e3 = 23 . 0 0 3 1 -1 -1

1. Helyettesítsük be a megfelel vektorokat a képletbe: 1 b1 1 2 , e1 = = ||b1 || 6 1 -1 -1 1 1 1 1 2 - 2 , 2 2 e2 = b2 - (b2 , e1 )e1 = 6 1 6 1 0 0 -1 -1 1 1 -1 1 -3/2 1 3 2 , 2 2 = 2 - 2 = 1 , = 2 - 6 6 1 0 0 1 1 0 -1/2 -3 1 e2 = 2 , 14 -1

2. EUKLIDESZI TEREK

79

2.32. Feladat. Adjunk meg R3 -ban egy olyan ortogonális bázist, amelynek egyik vektora b1 , ahol 1. b1 = (2, -1, 1), 2. b1 = (0, 1, -1)! Megoldás. Három lineárisan független vektorból Gram-Schmidt ortogonalizációs eljárással tudunk ortogonális bázist készíteni. Az adott b1 vektorhoz kell tehát találnunk még két vektort úgy, hogy együtt R 3 egy bázisát adják. 1. Válasszunk ki a b1 , e1 , e2 , e3 vektorrendszerbl egy bázist úgy, hogy b1 benne maradjon. Világos, hogy b1 , e2 , e3 lineárisan függetlenek, alkalmazzuk tehát az ortogonalizációs eljárást: 0 2 2 b b1 -1 1 -1 = 5 , b2 = e2 - e2 , 1 = 1 - ||b1 || ||b1 || 6 6 1 0 1 b b1 b b2 b3 = e3 - e3 , 1 - e3 , 2 ||b1 || ||b1 || ||b2 || ||b2 || 0 2 2 -2 1 1 1 5 = 0 , = 0 - -1 - 6 30 1 5 1 1 4

mivel itt a vektorokat nem kell normálnunk, egy megfelel ortogonális bázist alkotnak a b1 = (2, -1, 1), (2, 5, 1), (-1, 0, 2) vektorok. 2. Hasonlóan, most b1 , e1 , e2 bázis R3 -ban, és ebbl Gram-Schmidt ortogonalizációs eljárással készíthet ortogonális bázis: (0, 1, -1), (1, 0, 0), (0, 1, 1). 2.33. Feladat. Adjunk meg ortonormált bázist az alábbi alterekben: 1. H1 = L((-1, 2, 1), (1, 0, 3)), 2. H2 = L((1, -1, 2), (2, 1, 0), (0, -3, 4)), 3. H3 = L((1, -1, 0, 1), (1, -3, 4, 3), (0, 2, 0, 2), (2, -4, 4, 4)). Megoldás. Elször az alteret generáló vektorrendszerbl ki kell választani egy bázist, majd alkalmazható a Gram-Schmidt ortogonalizációs eljárás. 1. Mivel ez a két vektor lineárisan független, így az ortonormált bázis e 1 és e2 ahol: -1 2 1 -1 4 1 2 1 1 2 , e 2 = 0 - 2 -2 , e2 = -1 . e1 = = 6 3 6 21 1 3 1 8 4

80

2. EUKLIDESZI ÉS UNITÉR TEREK

2. Eliminációval válasszunk ki egy lineárisan független vektorrendszert: 1 -1 2 1 -1 2 2 1 0 0 3 -4 , 0 -3 4 0 -3 4
1 (11, 7, -2)akat 174

2.34. Feladat. Az E 9-dimenziós Euklideszi térben H egy 4-dimenziós altér. Mennyi H ortogonális komplementerének a dimenziója? Megoldás. Mivel H H = E, így dim H = 5. 2.35. Feladat. Adjuk meg egy-egy bázisát az alábbi alterek ortogonális komplementerének! 1. H1 = L(2, -1, 3), 2. H2 = L((1, -3, 2), (4, 1, 0)), 3. H3 = L((0, 1, -1, 0), (1, 2, 1, -1), (1, 0, 0, -1), (-1, 1, -1, 1)). Megoldás. Egy x vektor pontosan akkor lesz eleme az altér ortogonális komplementerének, ha az alteret generáló vektorok mindegyikére merleges. 1. Itt x H1 , ha ((x1 , x2 , x3 ), (2, -1, 3)) = 0, tehát a egy egyenletbl álló homogén lineáris egyenletrendszert kell megoldani, ennek megoldástere lesz az ortogonális komplementer. x1 -3/2 1/2 x2 = 0 t1 + 1 t2 , t1 , t2 R. x3 1 0 2x1 - x2 + 3x3 = 0

vektorok adják. 3. Eliminációval azt kapjuk, hogy az els három vektor a H 3 altér egy bázisát adja, ezen vektorokra alkalmazva az ortogonalizációs eljárást az 1 1 alábbiakat kapjuk: 3 (1, -1, 0, 1), 1 (-2, -1, 6, 1), 2 (0, 1, 0, 1). 42

tehát az els két vektor H2 egy bázisát adja. Alkalmazzuk a Gram1 Schmidt eljárást, és a kapott ortonormált bázist az 6 (1, -1, 2) és az

Tehát a H1 altér egy bázisát adják a (-3, 0, 2), (1, 2, 0) vektorok. (Ellenrizhetjük, hogy az eredményként kapott vektoroknak és a H 1 alteret generáló vektornak a bels szorzata valóban nulla.) 2. A H2 altér elemei azok a vektorok lesznek, amelyek mindkét H 2 -t generáló vektorra merlegesek, tehát ezekkel vett bels szorzatuk nulla: x1 - 3x2 + 2x3 = 0 4x1 + x2 = 0.

2. EUKLIDESZI TEREK

81

Innen (x1 , x2 , x3 ) = (-2/13, 8/13, 1)t, ahol t R, tehát az (-2, 8, 13) vektor bázis H2 -ben. 3. Hasonlóan, az x2 - x 3 x1 + 2x2 + x3 - x4 x1 - x4 -x1 + x2 - x3 + x4 = = = = 0 0 0 0

2.36. Feladat. Adjunk meg ortogonális bázist az alábbi alterek ortogonális komplementerében! 1. H1 = L(1, 2, -1), 2. H2 = L((1, -2, 0, 1), (1, 2, 1, 0)), 3. H3 = L((1, -1, 2, 0), (2, -1, 0, -1), (0, -1, 4, 1)). Megoldás. Az elz feladathoz hasonlóan kell eljárnunk, de a kapott vektorokat még ortonogonalizálnunk kell a Gram-Schmidt eljárással. 1. Az x1 +2x2 -x3 = 0 egyenlet megoldásterét a (-2, 1, 0), (1, 0, 1) vektorok generálják, ezekre alkalmazva az ortogonalizációs eljárást azt kapjuk, hogy 1 1 H1 = L (-2, 1, 0), (1, 2, 5) . 5 30 Ez egyben ortonormált bázis is. 2. A két egyenletbl álló egyenletrendszer megoldása után H2 = L((-2, -1, 4, 0), (-2, 1, 0, 4)), és ezen két vektor ortonogonalizálása után azt kapjuk, hogy H2 = L ((-2, -1, 4, 0), (-12, 8, -4, 28)) . 3. Els lépésben (2, 4, 1, 0), (1, 1, 0, 1) adódik, majd ortogonalizálás után (2, 4, 1, 0), (3, -1, -2, 7).

egyenletrendszer megoldása után azt kapjuk, hogy H 3 = L(1, 0, 0, 1).

2.37. Feladat. Adjuk meg az x vektor merleges vetületét a H = L(b 1 , b2 ) altérre, ahol 1. x = (-3, 7, 2), H = L((1, 2, 1), (-1, 0, 2)), 2. x = (3, 7, 6), H = L((1, 1, -1), (2, 0, 3), 3. x = (2, 5, -3, -3), H = L((5, 4, -1, -2), (3, -1, 2, 1)).

82

2. EUKLIDESZI ÉS UNITÉR TEREK

Megoldás. Az x vektor akkor lesz az x merleges vetülete, ha egyrészt x H (tehát eláll a H-t generáló vektorok lineáris kombinációjaként), másrészt az x := x - x vektor merleges H-ra (azaz merleges a H-t generáló b1 , b2 vektorokra). PSfrag replacements
x x H b1 b2 x

Keressük tehát azokat az 1 , 2 konstansokat, amelyekre teljesül, hogy ha x = 1 b1 + 2 b2 , akkor az x - x vektor merleges b1 -re és b2 -re is. Ekkor és hasonló egyenlet teljesül b2 -re is. Innen a keresett konstansok meghatározhatóak. 1. Helyettesítsük tehát be a megfelel vektorokat az 1 (b1 , b1 ) + 2 (b2 , b1 ) = (x, b1 ) 1 (b1 , b2 ) + 2 (b2 , b2 ) = (x, b2 ) egyenletrendszerbe: 61 + 2 = 13 1 + 52 = 7. Innen 1 = 2, 2 = 1, és így a merleges vetület: x = 2b1 +b2 = (1, 4, 4). 2. Hasonlóan, most 31 - 2 = 4 -1 + 132 = 24, 0 = (x - 1 b1 - 2 b2 , b1 ) = (x, b1 ) - 1 (b1 , b1 ) - 2 (b2 , b1 ),

innen 1 = 2 = 2, és így a merleges vetület: x = 2b1 + 2b2 = (6, 2, 4). 3. Az egyenletrendszer most 461 + 72 = 39 71 + 152 = -8,

1 = 1, 2 = -1, és a merleges vetület: x = b1 - b2 = (2, 5, -3, -3). 2.38. Feladat. Számítsuk ki az x vektor távolságát a H altértl az elz feladat adataival! Hogyan határozható meg az x vektornak a H altérrel bezárt szöge?

3. EUKLIDESZI TEREK LINEÁRIS OPERÁTORAI

83

Megoldás. Az elz feladat megoldásának jelöléseivel a távolságot az x = x - x vektor normája adja, a keresett szög pedig az x és az x által bezárt szög. 1. x = (-3, 7, 2) - (1, 4, 4) = (-4, 3, -2) és ||x || = 29. Az altérrel bezárt szög: (x, x ) 33 = , = arccos ||x||||x || 62 33 vagy másképpen a derékszög háromszög segítségével ||x || 33 = . = arccos ||x|| 62 2. x = (-3, 5, 2) és ||x || = 38, cos = 56/ 94. 3. x = (0, 0, 0, 0) és ||x || = 0, mert az x vektor eleme az altérnek. Természetesen = 0. 2.39. Feladat. Mennyi az x = (4, -3, 8) vektor távolsága attól a síktól, amelynek egyenlete x1 - 2x2 + 3x3 = 6? Megoldás. 1. A sík normálvektora n = (1, -2, 3). Keressük azon x = (x1 , x2 , x3 ) pontját a síknak, amire teljesül, hogy x + n = x valamilyen valós szám esetén (tehát szemléletesen x az x pontból a síkra állított merleges egyenes metszéspontja a síkkal.) Tehát innen x1 = 4 - , x2 = -3 + 2, x3 = 8 - 3. Mivel x teljesíti a sík egyenletét = 2 adódik, és a keresett távolság ||2n|| = 56. 2. Másik lehetség, hogy visszavezetjük a feladatot egy altértl vett távolság meghatározására. A sík egy reprezentánsvektora például az r = (0, 0, 2) vektor. A keresett távolság megegyezik az x - r vektornak a x1 - 2x2 + 3x3 = 0 egyenlet síktól vett távolságával, ez pedig már altér. (x1 , x2 , x3 ) + (1, -2, 3) = (4, -3, 8),

3. Euklideszi terek lineáris operátorai
2.40. Feladat. A : R3 R3 lineáris operátor mátrixa a természetes bázisra vonatkozóan A. Mi a adjungált operátor mátrixa? Megoldás. mátrixa A , hiszen . (Ax, y) = ((x), y) = (x, (y)) = (x, A y)

84

2. EUKLIDESZI ÉS UNITÉR TEREK

teljesül minden x, y R3 esetén. A kanonikus bels szorzat esetén (a, b) = a b, így (Ax) y = x A y = x A y, azaz A = A . (Ez az összefüggés tetszleges ortonormált bázis esetén teljesül, ekkor ugyanis a bels szorzás mátrixa az E egységmátrix.) 2.41. Feladat. A 1 , 2 : Rn Rn lineáris operátorok mátrixa a természetes bázisra vonatkozóan A illetve B, és 1 önadjungált operátor, 2 pedig ortogonális operátor. Az alábbi állítások közül melyek igazak, és melyek hamisak? 1. A szimmetrikus. 2. B szimmetrikus. 3. B -1 = B . 4. det B = 1. 5. A nem lehet ortogonális mátrix. 6. 1 minden sajátértéke valós. 7. 2 -nek van valós sajátértéke. 8. 1 sajátvektorai egymásra merlegesek. 9. B oszlopvektorai egymásra merlegesek. 10. A diagonalizálható mátrix. 11. B diagonalizálható mátrix. 12. x és Bx normája megegyezik. Megoldás. 1. Igaz. 2. Nem feltétlenül igaz, például az R 2 -beli origó körüli forgatás mátrixa: cos sin . - sin cos

3. Igaz. 4. Nem igaz. Az állítás helyesen: det B = +1 vagy -1. 5. De lehet. Például az identikus transzformáció mátrixa (az egységmátrix) szimmetrikus és ortogonális is. 6. Igaz. 7. Nem igaz. Például az R2 -beli origó körüli forgatásnak nincs valós sajátértéke. 8. Nem igaz. Helyesen: 1 különböz sajátértékeihez tartozó sajátvektorai merlegesek egymásra. 9. Igaz. St, egységhosszúak is, és ugyanez igaz sorvektoraira is. 10. Igaz. 11. Nem feltétlenül igaz.

3. EUKLIDESZI TEREK LINEÁRIS OPERÁTORAI

85

12. Igaz. 2.42. Feladat. Írjuk fel a lineáris operátor természetes bázisra vonatkozó mátrixát. Állapítsuk meg, hogy önadjungált illetve ortogonális operátore! 1. az R2 -beli y tengelyre tükrözés, 2. az R3 -beli origóra tükrözés, 3. az R3 -beli [x, y]-síkra való merleges vetítés, 4. az R2 -beli origó körüli szög forgatás, 5. az R2 -beli origó középpontú háromszoros nagyítás. Megoldás. Az önadjungált operátorok mátrixa ortonormált bázisban szimmetrikus, az ortogonális operátorok mátrixa pedig ortogonális mátrix, azaz sorai (oszlopai) egymásra merleges egységvektorok. 1. A transzformáció mátrixa oszlopaiban tartalmazza a bázisvektorok képének koordinátáit: Mivel (1, 0) = (-1, 0) és (0, 1) = (0, 1), így a keresett mátrix -1 0 A= . 0 1 Ez az operátor önadjungált is és ortogonális is. A mátrix diagonális, a természetes bázis itt sajátvektorokból álló orotonormált bázis is egyben. 2. Az operátor mátrixa: -1 0 0 A = 0 -1 0 , 0 0 -1 önadjungált és ortogonális is. 3. Az operátor mátrixa: 1 0 0 A = 0 1 0 , 0 0 0

tehát önadjungált operátor, de nem ortogonális. 4. Most mátrixa cos sin A= , - sin cos

ez ortogonális mátrix. Valóban, sorvektorai egységhosszúak cos 2 + sin2 = 1 miatt, és merlegesek egymásra, mert bels szorzatuk nulla. 5. Mivel az operátor mátrixa A= 3 0 , 0 3

86

2. EUKLIDESZI ÉS UNITÉR TEREK

így ez szimmetrikus, de nem ortogonális transzformáció. 2.43. Feladat. Írjuk fel a : R3 R3 lineáris operátor mátrixát, ha az x1 + 2x2 + x3 = 0 egyenlet síkra való tükrözés. Önadjungált illetve ortogonális-e ez az operátor? Megoldás. Az ortogonális felbontás szerint x = x +x , ahol x az x merleges vetülete a síkra, x pedig az x merleges vetülete az n irányú egyenesre, 1 ahol n = 6 (1, 2, 1) a sík normál-egységvektora. A 2.23 feladat alapján x = (x, n)n, így (x) = x - 2x = x - 2(x, n)n. PSfrag replacements
n 0 x x x

(x)

Innen 1 1 (1, 0, 0) = (1, 0, 0) - 2 (1, 2, 1) = (2/3, -2/3, -1/3), 6 6 2 (0, 1, 0) = (0, 1, 0) - (1, 2, 1) = (-2/3, -1/3, -2/3), 3 1 (0, 0, 1) = (0, 0, 1) - (1, 2, 1) = (-1/3, -2/3, 2/3), 3 így az operátor mátrixa: 2/3 -2/3 -1/3 -2/3 -1/3 -2/3 , -1/3 -2/3 2/3 tehát ez egy szimmetrikus és ortogonális operátor. 2.44. Feladat. Írjuk fel a : R3 R3 lineáris operátor mátrixát, ha az x1 + x2 - 3x3 = 0 egyenlet síkra való merleges vetítés. Önadjungált illetve ortogonális-e ez az operátor? Megoldás. Az elz feladat jelöléseivel: (x) = x = x - x = x - (x, n)n,

3. EUKLIDESZI TEREK LINEÁRIS OPERÁTORAI

87

ahol n =

1 (1, 1, -3). 11

Ekkor

1 (1, 1, -3) = (10/11, -1/11, 3/11), 11 1 (0, 1, 0) = (0, 1, 0) - (1, 1, -3) = (-1/11, 10/11, 3/11), 11 - (0, 0, 1) = (0, 0, 1) - 11(1, 1, -3) = (3/11, 3/11, 2/11), 3 és a keresett mátrix 10 -1 3 1 -1 10 3 . 11 3 3 2 Ez egy önadjungált operátor. 2.45. Feladat. Diagonalizáljuk a önadjungált operátor mátrixát, és adjuk meg azt az ortonormált bázist, amelyben mátrixa diagonális alakú, ha mátrixa a természetes bázisra vonatkozóan 2 1 0 -1 0 -3 3 1 (1) (2) 1 2 0 (3) 0 2 0 1 3 0 0 2 -3 0 1 (1, 0, 0) = (1, 0, 0) - (4) 2 1 -1 1 2 -1 (5) -1 -1 2 1 1 1 1 1 1 (6) 1 1 1 1 0 -1 0 7 0 -1 0 1

Megoldás. Elször a lineáris transzformációknál tanult módon meghatározzuk a leképezés karakterisztikus egyenletét. Ebbl megkapjuk a sajátértékeket, majd meghatározzuk a sajátértékekhez tartozó sajátaltereket. Mivel önadjungált operátorokról van szó, minden sajátérték valós, mindig létezik sajátvektorokból álló bázis, st, sajátvektorokból álló ortonormált bázis is. Ennek megadásához a kapott sajátvektorokat normáljuk, illetve többdimenziós sajátaltér esetén Gram-Schmidt ortogonalizációs eljárást alkalmazunk. 1. Határozzuk meg a sajátértékeket: 3- 1 = (3 - )2 - 1 = 2 - 6 + 8 = ( - 4)( - 2), 1 3-

tehát a sajátértékek a 2 és a 4. A = 2 sajátértékhez tartozó sajátvektorok az alábbi egyenletrendszerbl határozhatóak meg: x1 + x 2 = 0 , x1 + x 2 = 0

88

2. EUKLIDESZI ÉS UNITÉR TEREK

tehát L2 = L(1, -1). A = 4 esetben -x1 + x2 = 0 , x1 - x 2 = 0 tehát L4 = L(1, 1). Látható, hogy a két altér vektorai merlegesek egymásra, ezen alterekbl kell kiválasztani egységhosszú vektorokat. A 1 1 keresett sajátvektorokból álló ortonormált bázis: 2 (1, -1), 2 (1, 1). A bázistranszformáció S mátrixa ekkor ortogonális mátrix, és S -1 AS = S AS diagonális: 1 2 1 -1 1 1 3 1 1 3 1 2 1 -1 1 1 = 2 0 . 0 4

2. A karakterisztikus polinom x3 - 6x2 + 11x - 6, és három különböz sajátérték van: 1,2,3. A sajátértékekhez tartozó sajátalterek egymásra ortogonálisak: L1 = L(-1, 1, 0), L2 = L(0, 0, 1), L3 = L(1, 1, 0), tehát a bázistranszformáció ortogonális mátrixa (ennek oszlopaiban szerepelnek a sajátvektorokból álló ortonormált bázis vektorai): -1/ 2 0 1/2 S = 1/ 2 0 1/ 2 . 0 1 0

3. A karakterisztikus polinom x3 - 12x + 16, a sajátértékek: -4,2,2. A sajátértékekhez tartozó sajátalterek: L-4 = L(1, 0, 1), L2 = L((-1, 0, 1), (0, 1, 0)). Mivel itt az L2 altér generáló vektorai ortogonálisak, rögtön felírhatjuk a sajátvektorokból álló ortonormált bázist: (1/ 2, 0, 1/ 2), (-1/ 2, 0, 1/ 2), (0, 1, 0). 4. A karakterisztikus polinom x3 - 6x2 + 9x - 4, a sajátértékek: 4,1,1. A sajátértékekhez tartozó sajátalterek: L4 = L(-1, -1, 1), L1 = L((-1, 1, 0), (1, 0, 1)).

3. EUKLIDESZI TEREK LINEÁRIS OPERÁTORAI

89

5. A karakterisztikus polinom x3 -3x2 , a sajátértékek: 3,0,0, a sajátalterek: L3 = L(1, 1, 1), L0 = L((-1, 0, 1), (-1, 1, 0)). Mivel itt az L0 altér generáló vektorai nem ortogonálisak, így GramSchmidt ortogonalizációs eljárással meghatározunk egy ortonormált bá1 1 zist ebben az altérben: 2 (-1, 0, 1), 6 (-1, 2, -1). Tehát 1/3 -1/ 2 -1/ 6 S = 1/3 0 2/ . 6 1/ 3 1/ 2 -1/ 6

Mivel itt az L1 altér generáló vektorai nem ortogonálisak, így GramSchmidt ortogonalizációs eljárással meghatározunk egy ortonormált bá1 1 zist ebben az altérben: 2 (-1, 1, 0), 6 (1, 1, 2). Tehát -1/3 -1/ 2 1/6 S = -1/ 3 1/ 2 1/6 . 1/ 3 0 2/ 6

6. A karakterisztikus polinom x3 - 9x2 + 14x, a sajátértékek: 0,7,2. A keresett ortonormált bázis: 1 1 (-1, 0, 1), (0, 1, 0), (1, 0, 1). 2 2 2.46. Feladat. Mi a geometriai jelentése annak a : R 3 R3 ortogonális operátornak, amelynek valós sajátértékei pontosan: (1) 1, 1, 1, (2) 1, 1, -1, (3) 1, -1, -1, (4) - 1, -1, -1, (5) 1, (6) - 1 Megoldás. Ha három valós sajátérték van, akkor létezik ortonormált bázis, melyben mátrixa diagonális, fátlóban ezen sajátértékekkel. 1. Identikus leképezés. 2. Síkra tükrözés (A bázis három egymásra merleges sajátvektora közül kett fix marad, egy ellentétes irányú lesz hatására). 3. Egyenesre tükrözés. 4. Origóra tükrözés. 5. Csak egy valós sajátérték van (és az 1), így ez egy tengely körüli forgatás. 6. Forgatva tükrözés. 2.47. Feladat. Mi a geometria jelentése a ortogonális operátornak, ha a természetes bázisra vonatkozó mátrixa:

90

2. EUKLIDESZI ÉS UNITÉR TEREK

(1)

(3)

1/2 - 3/2 (2) 3/2 1/2 2/3 -1/3 2/3 2/3 2/3 -1/3 (4) -1/3 2/3 2/3



2/3 2/3 -1/3 -1 0 0 0 0 1

2/3 -1/3 -1/3 2/3 2/3 2/3 0 -1 0

Megoldás. cos - sin alakú, ahol = 60 , tehát ez egy origó sin cos körüli szög forgatás. 2. Határozzuk meg a mátrix karakterisztikus polinomját és a sajátértékeket: x3 -x2 -x+1, illetve -1, 1, 1. Ez tehát egy síkra tükrözés. Megkaphatjuk a sík normálvektorát, ha meghatározzuk a -1-hez tartozó sajátvektorokat: L-1 = (1, -2, 1), tehát az x1 - 2x2 + x3 = 0 egyenlet síkra tükrözés. (Az 1-hez tartozó sajátalteret éppen ennek a síknak a vektorai adják, ezek fixpontjai.) 3. A karakterisztikus polinom x3 - 2x2 + 2x - 1 = (x - 1)(x2 - x + 1), tehát csak egy valós sajátérték van, ez tehát egy tengely körüli forgatás, a tengely vektorait (ezek fixen maradnak) az 1-hez tartozó sajátvektorok adják: L1 = (1, 1, 1). Eszerint az invariáns sík egyenlete x 1 +x2 +x3 = 0, ebben a síkban origó körüli forgatásként hat. Mi a forgatás szöge? Az egyszerség kedvéért vegyünk egy vektort az invariáns síkból, például az x = (0, -1, 1)-et, és nézzük meg mi lesz a általi képe: 2/3 -1/3 2/3 0 -1 2/3 -1/3 -1 = 0 . (x) = 2/3 -1/3 2/3 2/3 1 1 1. Ez a mátrix A forgatás szöge az x és (x) által bezárt szög: cos = 212 = 1 , tehát 2 = 60 . 4. A karakterisztikus polinom x3 + x2 + x + 1 = (x + 1)(x2 + 1), tehát az egyetlen valós sajátérték -1. A leképezés forgatva tükrözés, az invariáns sík normálvektora (1, 0, 0), mert L-1 = L(1, 0, 0). Tehát az [y, z]-síkban forgatásként hat , enne szöge 90 , hiszen például x = (0, 1, 0) esetén (x) = (0, 0, 1). Ha az eredeti mátrixot megfigyeljük, felfedezhetjük 0 -1 benne a 90 -os forgatás mátrixát. A leképezés tehát az [y, z]1 0 síkra való tükrözés, és az x-tengely körüli 90 -os forgatás együttese.

3. fejezet

Gráfelmélet
1. Gráfelméleti alapfogalmak
3.1. PSfrag replacements Feladat. Rajzolja fel a G = (E, , C) irányított gráfot, ha 1. E = {e1 , e2 , e3 , e4 }, C = {c1 , c2 , c3 , c4 }, (e1 ) = (c4 , c1 ), (e2 ) = (c1 , c4 ), (e3 ) = (c2 , c1 ), (e4 ) = (c4 , c2 ), (e5 ) = (c3 , c3 ). 2. E = {e1 , e2 , e3 , e4 , e5 , e6 , e7 , e8 , e9 , e10 }, C = {c1 , c2 , c3 , c4 , c5 , c6 }, (e1 ) = (c5 , c1 ), (e2 ) = (c5 , c4 ), (e3 ) = (c4 , c3 ), (e4 ) = (c3 , c2 ), (e5 ) = (c2 , c5 ), (e6 ) = (c3 , c3 ), (e7 ) = (c2 , c1 ), (e8 ) = (c6 , c1 ), (e9 ) = (c1 , c6 ), (e10 ) = (c6 , c6 ). 3. E = {e1 , e2 , e3 , e4 , e5 , e6 }, C = {c1 , c2 , c3 , c4 , }, (e1 ) = (c2 , c1 ), (e2 ) = (c1 , c3 ), (e3 ) = (c3 , c2 ), (e4 ) = (c1 , c3 ), (e5 ) = (c4 , c4 ), (e6 ) = (c4 , c4 ). Megoldás.
e5 c3 c4 e1 e2 e4 c1 1. c2 e3 c4 e2 c5 e3 c3 e5 e7 e4 c2 e8 e9 2. e10 c6 e5 c4 e6 e4 c1 3. e2 e1 e6 c3 e3 c2

e1 c1

3.2. Feladat. Adja meg a 3.1. feladatban szerepl gráfok csúcsainak kifokát és be-fokát. Megoldás. Egy irányított gráf c csúcsának ki-foka azon élek száma, amelyeknek c a kezdpontja, be-foka pedig a csúcsba irányuló élek száma. A ki-fok jele ki (c), a be-fok jele be (c). 1. ki (c1 ) = 1, ki (c2 ) = 1, ki (c3 ) = 2, ki (c4 ) = 3, be (c1 ) = 2, be (c2 ) = 2, be (c3 ) = 2, be (c4 ) = 1.
91

92

3. GRÁFELMÉLET

2. ki (c1 ) = 1, ki (c2 ) = 2, ki (c3 ) = 2, ki (c4 ) = 1, ki (c5 ) = 2, ki (c6 ) = 2. be (c1 ) = 3, be (c2 ) = 1, be (c3 ) = 2, be (c4 ) = 1, be (c5 ) = 1, be (c6 ) = 2. 3. ki (c1 ) = 2, ki (c2 ) = 1, ki (c3 ) = 1, ki (c4 ) = 2, be (c1 ) = 1, be (c2 ) = 1, be (c3 ) = 2, be (c4 ) = 2. 3.3. Feladat. Rajzolja fel a G = (E, , C) irányítatlan gráfot, ha PSfrag replacements 1. E = {e1 , e2 , e3 , e4 , e5 , e6 , e7 , e8 , e9 , e10 , e11 }, C = {c1 , c2 , c3 , c4 , c5 , c6 }, (e1 ) = (c1 , c2 ), (e2 ) = (c1 , c4 ), (e3 ) = (c4 , c6 ), (e4 ) = (c3 , c4 ), (e5 ) = (c2 , c4 ), (e6 ) = (c2 , c3 ), (e7 ) = (c3 , c2 ), (e8 ) = (c2 , c3 ), (e9 ) = (c4 , c5 ), (e10 ) = (c5 , c6 ), (e11 ) = (c5 , c5 ). 2. E = {e1 , e2 , e3 , e4 , e5 , e6 , e7 , e8 , e9 }, C = {c1 , c2 , c3 , c4 , c5 , c6 }, (e1 ) = (c1 , c2 ), (e2 ) = (c2 , c3 ), (e3 ) = (c3 , c4 ), (e4 ) = (c4 , c5 ), (e5 ) = (c5 , c6 ), (e6 ) = (c2 , c6 ), (e7 ) = (c2 , c5 ), (e8 ) = (c2 , c4 ), (e9 ) = (c1 , c5 ). 3. E = {e1 , e2 , e3 , e4 }, C = {c1 , c2 , c3 , c4 , c5 }, (e1 ) = (c2 , c3 ), (e2 ) = (c3 , c4 ), (e3 ) = (c3 , c5 ), (e4 ) = (c2 , c2 ). Megoldás.
e11

PSfrag replacements
c6

e10 e3 e2 c1

c5 e9 e4 c4 e1 1. e5 e6 e7 e8 c2 e9 c3 c6 e5 e6 c5 e4 e7 e8 c2 e2 2. c4 e3 c3

c4 e2 c3 e3 c5 e1 c1 c2 e4 3.

c1 e1

3.4. Feladat. Állapítsa meg az alábbi gráfok csúcsainak fokát, továbbá a gráf átmérjét:
c8 c9 c10 c7 c4 c8 c9 c10 c7 c8 c9 c5 c1 c10 c11 c12 c6 c2 3. c7 c3

c5 c1 c2 1.

c6 c3

c4 c1

c5 c6 c2 c3 2.

c4

Megoldás. Egy G gráf c csúcsának fokán a csúcsára illeszked élek számát értjük. Jele (c). Egy G gráf átmérje a csúcsok távolságának maximuma, melyet diam(G)-vel jelölünk.

1. GRÁFELMÉLETI ALAPFOGALMAK

93

1. (c4 ) = (c8 ) = 1, (c1 ) = (c2 ) = (c3 ) = (c5 ) = 2, (c6 ) = (c7 ) = (c9 ) = (c10 ) = 3. diam(G) = d(c2 , c8 ) = 5. 2. (c1 ) = (c2 ) = (c3 ) = (c4 ) = 1, (c7 ) = 2, (c8 ) = (c9 ) = (c10 ) = 3, (c5 ) = (c6 ) = 5. diam(G) = d(c1 , c3 ) = d(c2 , c3 ) = d(c4 , c3 ) = 4. 3. (c1 2) = 0, (c4 ) = (c8 ) = 1, (c2 ) = (c5 ) = (c7 ) = (c10 ) = 2, (c1 ) = (c3 ) = (c9 ) = (c11 ) = 3, (c5 ) = 4. diam(G) = , hiszen például c1 és c5 között nincsen út, így távolságuk végtelen. 3.5. Feladat. Igazoljuk, hogy egy G gráf akkor és csak akkor páros, ha nem tartalmaz páratlan hosszúságú kört. (Egy gráf páros gráf, ha csúcsait két részre oszthatjuk úgy, hogy a gráf minden éle az egyik részbl a másikba vezet, azaz fehér és fekete színnel kiszínezhetek a csúcsai úgy, hogy minden él két különböz szín csúcsot köt össze.) Megoldás. Az, hogy páros gráf nem tartalmazhat páratlan hosszúságú kört, nyilvánvaló, hiszen a gráf bármely körének bejárásakor felváltva fordulnak el a fehér illetve fekete szín csúcsok. Azt, hogy páratlan hosszúságú kört nem tartalmazó gráf páros, a csúcsok száma szerinti teljes indukcióval igazoljuk. Az állítás nyilvánvalóan igaz n = 1 csúcspontú gráfra. Tegyük fel, hogy igaz az állítás minden n = k csúcspontú gráfra (k N), ebbl látjuk be, hogy teljesül minden k +1 csúcspontú gráfra is. Legyen tehát G egy k + 1 csúcspontból álló gráf, amelyben nincsen páratlan hosszúságú kör. Töröljük G-nek egy tetszlegesen választott c csúcsát a hozzá illeszked élekkel együtt. Az így keletkezett G gráfnak k csúcsa van, továbbá szintén nem tartalmaz páratlan hosszúságú kört, így az indukciós feltevés szerint páros gráf. Színezzük ki G csúcsait fehérekre és feketékre a megfelel módon. Belátjuk, hogy c-nek G ugyanazon K komponensébe es szomszédai azonos színek. Indirekt tegyük fel ugyanis, hogy c-nek két szomszédja, s 1 és s2 a K komponensben vannak, és s1 fehér, s2 pedig fekete. A K komponens összefügg, így van benne s1 -et s2 -vel összeköt L út, melynek hossza páratlan, hiszen végpontjai különböz színek, és G párossága miatt minden szomszéd különböz szín. Azonban a (c, s 1 ) és (c, s2 ) éleket az L úthoz csatolva G-nek egy páratlan hosszúságú körét kapjuk, ez pedig lehetetlen. Tehát a komponenseket kiszínezhetjük úgy, hogy c minden szomszédja fehér legyen, így c-t feketének tekintve a G gráf párosságát kifejez színezést kaptunk. Ezzel az állítást beláttuk. 3.6. Feladat. Páros gráfok-e az alábbi gráfok? Ha igen, adjuk meg a csúcsok egy diszjunkt felosztását.

94

3. GRÁFELMÉLET

c9 c5 c11 c1 c12

c10 c8 c4

c8 c4 c1 c5

c9

c10 c6 c3 2. c7

c6 c4 c1

c7 c5 c2 3.

c8

c6 c2

c7 c3

c2

c3

1.

PSfrag replacements Megoldás. A megoldásban felhasználjuk a 3.5. feladatot. 1.
2.

1. Könnyen látható, hogy a gráf körei csak 4, 8 vagy 12 élbl állhatnak, 3. így a gráf páros. A csúcsok egy felosztása: C 1 = {c1 , c3 , c6 , c8 , c10 }, C2 = {c2 , c4 , c5 , c7 , c9 }. 2. Könnyen látható, hogy a gráf körei csak 2, 4 vagy 6 élbl állhatnak, így a gráf páros. A csúcsok egy felosztása: C 1 = {c1 , c3 , c6 , c8 , c9 }, C2 = {c2 , c4 , c5 , c7 , c10 }. 3. Az ábrán látható, hogy a gráfnak van páratlan hosszúságú köre:
c6 c9 c10c4 c11 c12 c1 c7 c5 c2 c3 c8

Tehát a gráf nem páros. 3.7. Feladat. Izomorfak-e az alábbi gráfok? Ha igen, írjuk fel a csúcsok és élek közötti megfeleltetést.

PSfrag replacements
1. 2.

PSfrag replacements
3. 4.

1. GRÁFELMÉLETI ALAPFOGALMAK

95

PSfrag replacements
5. 6.

Megoldás. A G = (E, , C) és a G = (E , , C ) gráf izomorfak, ha léteznek olyan : E E és : C C bijektív leképezések, melyekre teljesül, hogy tetszleges, a c1 és c2 csúcsokat összeköt e él (e) képe a (c 1 ) és (c2 ) csúcsokat köti össze (irányított gráf esetén az irányítottságot is megrizve, tehát ha az e él a c1 csúcsba mutat, akkor az (e) él a (c 1 ) csúcsba mutat). Két gráf izomorfiája PSfrag replacements szemléletesen azt jelenti, hogy az egyik gráfból a csúcsok elmozgatásával (az éleket tetszlegesen hajlítva és nyújtva) el tudom állítani a másikat. 1. A két gráf nem izomorf, hiszen az els gráfnak több csúcspontja van mint a másodiknak, így a csúcspontok között nem adható meg bijektív leképezés. 2. Nyilvánvaló, hogy egy gráf egy n hosszúságú körének az és leképezések által megfeleltetett, úgynevezett izomorf képe szintén egy n hosszúságú kör. Mivel az els gráfban van 3 hosszúságú kör, csak olyan gráffal lehet izomorf, amiben van 3 hosszúságú kör. Tehát a két gráf nem izomorf. 3. A két gráf izomorf. A csúcsok és élek közötti megfeleltetés felírásához jelöljük el a gráfok csúcsait és éleit:
c4 c4 e4 e5 e1 c1 c2 e2 c3 c1 e3 c5 c5 e5 e1 e2 c2 e4 e3 c 3

Az élek megfeleltetése: (e1 ) = e1 , (e2 ) = e3 , (e3 ) = e5 , (e4 ) = e2 , (e5 ) = e4 . A csúcsok megfeleltetése: (c1 ) = c1 , (c2 ) = c3 , (c3 ) = c5 , (c4 ) = c2 , (c5 ) = c4 . 4. A két gráf izomorf. A csúcsok és élek közötti megfeleltetés felírásához jelöljük el a gráfok csúcsait és éleit:

PSfrag replacements
96 3. GRÁFELMÉLET

c4 e3 e2 e1

e8 e7 e5 e6 c3 e4 c2

c5 c5 e1 c2 e6 e8 e7 c4 e2 c3 e5 e3 c1 e4

c1

Az élek megfeleltetése: (e1 ) = e1 , (e2 ) = e2 , (e3 ) = e3 , (e4 ) = e4 , (e5 ) = e7 , (e6 ) = e8 , (e7 ) = e5 , (e8 ) = e6 . A csúcsok megfeleltetése: (c1 ) = c1 , (c2 ) = c5 , (c3 ) = c3 , (c4 ) = c4 , (c5 ) = c2 . 5. A két gráf nem izomorf, hiszen az els gráfnak van olyan csúcsa, amely irányába nem mutat él, míg a másodiknak nincs ilyen csúcsa. 6. A két gráf izomorf. A csúcsok és élek közötti megfeleltetés felírásához jelöljük el a gráfok csúcsait és éleit:
e2 c4 e6 e1 e5 c1 e4 e7 c5 e8 c2 c3 e3 c4 e1 e6 c1 e2 e5 c5 e4 e8 c3 e7 c2 e3

Az élek megfeleltetése: (e1 ) = e1 , (e2 ) = e2 , (e3 ) = e3 , (e4 ) = e4 , (e5 ) = e5 , (e6 ) = e6 , (e7 ) = e7 , (e8 ) = e8 . A csúcsok megfeleltetése: (c1 ) = c4 , (c2 ) = c3 , (c3 ) = c2 , (c4 ) = c1 , (c5 ) = c5 . 3.8. Feladat. Adja meg az alábbi gráfok egy feszítfáját:

PSfrag replacements

1.

2.

3.

Megoldás.

PSfrag replacements

1. GRÁFELMÉLETI ALAPFOGALMAK

97

PSfrag replacements
1. 2.

A harmadik gráf nem összefügg, így nincs feszítfája. 3.9. Feladat. Adja meg az alábbi irányított gráfok gyökereit:
c9 c7 c3 c1 c8 c6 c7 c3 c1 1. c11 c8 c9 c10 c4 c5 c2 2. c6 c13 c9 c5 c1 c10 c6 c2 c14 c12 c11 c7 c3 3. c8 c4

c4 c5 c2

Megoldás. 1. A c6 csúcsba nem vezet irányított út, így csak lehet gyökér. Könny leellenrizni, hogy belle mindenhova el lehet jutni, tehát a c 6 csúcs az egyetlen gyökér. 2. A gráfnak nincs gyökere. 3. A gráf gyökerei a c1 , c2 , c3 , c5 , c6 , c7 , c11 , c12 csúcsok. 3.10. Feladat. Adjuk meg az alábbi egyszer gráfok komplementerfáit: PSfrag replacements

1.

2.

3.

4.

Megoldás. A gráfokból alkotható teljes gráfok: PSfrag replacements

1.

2.

3.

4.

Így a komplementer gráfok:

98

3. GRÁFELMÉLET

PSfrag replacements

1.

2.

3.

4.

3.11. Feladat. Hány olyan 6 csúcspontú egyszer gráf van (izomorfiától eltekintve), amelyben minden pont foka legalább 4? Megoldás. A feladatnak megfelel gráfok áttekinthetetlenül sok élt tartalmaznak, azonban komplementereik keveset. Így áttérünk a komplementerek vizsgálatára, és felhasználjuk azt, hogy a keresett gráfok száma nyilvánvalóan megegyezik a komplementereik számával. A teljes 6-gráfban minden pont foka 5, így a keresett gráfok komplementereiben minden csúcs fokszáma maximum 1. Izomorfiától eltekintve a következ lehetségek vannak: PSfrag replacements

1.

2.

3.

4.

Tehát összesen 4 féle gráf van, amely a kívánt tulajdonsággal rendelkezik. 3.12. Feladat. Igazoljuk, hogy (a) legalább két csúcsot tartalmazó egyszer gráfnak van két azonos fokú csúcsa. (b) legalább két csúcsot tartalmazó összefügg gráfnak kevesebb éle van, mint csúcsa, akkor van a gráfnak elsfokú csúcsa. n(n - 1) (c) n csúcspontú teljes gráf éleinek száma . 2 (d) amennyiben egy legfeljebb 2n csúcspontú egyszer gráf minden pontjának foka legalább n, akkor a gráf összefügg. (e) ha egy n csúcsú gráfnak legalább n + 1 éle van, akkor van a gráfnak legalább 3-adfokú pontja. (f) ha egy összefügg gráf minden csúcsának foka 2, akkor a gráf kör. (g) egy n csúcspontú összefügg gráfnak legalább n - 1 éle van. (h) ha egy n csúcspontú gráfnak legalább n éle van, akkor van a gráfban kör. (i) egy összefügg n csúcspontú gráf pontosan akkor fagráf, ha éleinek száma n - 1. (j) egy n csúcspontú n él összefügg gráf pontosan 1 kört tartalmaz. Megoldás.

1. GRÁFELMÉLETI ALAPFOGALMAK

99

(a) Legyen az n csúcsú G gráf egyszer. Mivel egyszer gráfban nincsen hurokél és párhuzamos élek, ezért bármely csúcsot csak a többi n - 1 csúccsal köthet össze maximum egy ál, így a csúcs fokszáma n - 1. Tehát a fokszámok a következek lehetnek: 0, 1, 2, . . . , n - 1.

Azonban, ha G-ben van izolált pont, akkor nem lehet n - 1-edfokú pont, hiszen ez az összes többi ponttal, így az izolált ponttal is szomszédos lenne, amely nem lehetséges. Tehát a következ fokszámok fordulhatnak el G-ben: 0, 1, 2, . . . , n - 2 vagy 1, 2, 3, . . . n - 1.

Mindkét esetben legfeljebb n-1 különböz fokszám lehetséges, így a gráf n darab csúcsa közül szükségképpen lesz legalább 2, amelyek fokszáma megegyezik. (Ezt az úgynevezett skatulyaelv alapján mondhatjuk: Ha n - 1-nél több tárgyak n - 1 dobozba rakunk be, akkor legalább 1 dobozba egynél több tárgyat raktunk.) (b) Legyen az n csúcsú G gráf összefügg. Indirekt tegyük fel, hogy G-nek nincs elsfokú csúcsa. Mivel G-nek nincsen izolált pontja sem, minden pont foka legalább 2, így a fokszámok összege 2n. Ekkor azonban a fokszámok összege legalább n, hiszen az élek száma éppen a fokszámok összegének fele. Tehát ellentmondásra jutottunk, melynek oka az indirekt feltevés volt. (c) A teljes n-gráf minden csúcsának foka n - 1, így a fokszámok összege n(n - 1). A kézfogási tétel alapján az élek száma éppen a fokszámok összegének fele, melybl következik az állítás. (d) Indirekt tegyük fel, hogy a kívánt tulajdonságokkal rendelkez G gráf több komponensbl áll. Ekkor van olyan komponens, amelynek nincsen n-nél több pontja. Mivel a gráf egyszer, ebben a komponensben egy csúcs fokszáma maximum n - 1 lehet, amely ellentmond a feladat fokszám kikötésének. (e) Ha az n csúcsú G gráf minden pontjának foka legfeljebb 2, akkor Gben a fokszámok összege legfeljebb 2n, így az élek száma legfeljebb n, ellentétben a feladat feltevésével. (f) A feladat az összefüggség felhasználásával az élek bejárásából adódik. (g) Az állítást n-szerinti teljes indukcióval igazoljuk. Az állítás n = 1-re nyilvánvaló. Tegyük fel, valamely k N esetén az állítás igaz, azaz minden k csúcsú összefügg gráfnak van k - 1 éle. Legyen G egy k + 1 csúcspontú összefügg gráf. Ha G-nek nincsen k + 1 éle, akkor a feladat (b) része alapján van elsfokú pontja. Egy

100

3. GRÁFELMÉLET

ilyen pontot a hozzá illeszked éllel törölve egy k csúcspontú összefügg gráfot kapunk, amelynek indukciós feltevésünk szerint van k - 1 éle, ami a törölt éllel együtt adja, hogy G-nek van k éle. Ezzel az állítást beláttuk. (h) Az állítást n-szerinti teljes indukcióval igazoljuk. n = 1-re az állítás nyilvánvalóan teljesül. Tegyük fel, hogy valamely k N esetén az állítás igaz, azaz minden k pontú és legalább k él gráfban van kör. Legyen G egy k +1 él gráf, melyben legalább k +1 él van. A feladat igazolásához azt kell tehát belátni, hogy G tartalmaz kört. Tekintsünk G-ben egy L leghosszabb utat (olyan utat, amelyben az élek száma maximális). Ha az L út valamely c1 végpontja G-nek nem elsfokú útja, akkor máris adódik, hogy G-ben van kör. Ugyanis ha veszünk egy olyan c 1 végpontú e élt, amely nincs benne az L útban, annak másik, c 2 végpontja szükségképpen olyan csúcs, amelyen az L út áthalad, hiszen ellenkez esetben az L utat növelni tudnánk az e éllel, amely ellentmondana L maximalitásának. Így az L út c1 -bl c2 -be vezet része kiegészítve az e éllel egy kört alkot. Ha L végpontjai elsfokúak, akkor töröljük G-nek valamely elsfokú csúcsát a hozzá tartozó éllel együtt. Az így kapott gráfnak k pontja van és legalább k éle, amely az indukciós állítás szerint tartamaz kört. Ez a kör azonban benne van G-ben is, mellyel az állítást beláttuk. (i) Az állítás a feladat (g) és (h) részének következménye. (j) A feladat (h) része szerint a gráfunk tartalmaz kört. Jelöljünk el egy kört K-val. Nyilvánvaló, hogy ha a gráfból kiveszünk egy olyan élt, mely benne van K-ban, az összefüggséget nem rontjuk el. Tehát az így kapott összefügg n csúcsú gráfnak n - 1 éle van, amely a feladat (i) része alapján fa, azaz nem tartalmaz kört. A fentiekbl már adódik, hogy a gráfnak csak egy köre van, K. 3.13. Feladat. Egy társaság bizonyos tagjai kézfogással köszöntötték egymást. Bizonyítsuk be, hogy páros azoknak a száma, akik páratlan sok emberrel fogtak kezet. Megoldás. Képezzünk egy gráfot, amelynek pontjai a társaság tagjainak felelnek meg, a gráf egy éle pedig jelentse azt, hogy a végpontjainak megfelel emberek kezet fogtak egymással. Nyilván egy ember annyi emberrel fogott kezet, ahány él illeszkedik a neki megfelel csúcsra, ami nem más, mint a csúcs fokszáma. Azt kell tehát bizonyítanunk a feladat állításának belátásához, hogy a gráf páratlan fokszámú csúcsainak száma páros, amely a kézfogási tétel következménye.

1. GRÁFELMÉLETI ALAPFOGALMAK

101

3.14. Feladat. Bizonyítsuk be, hogy nincs olyan 7 tagú társaság, ahol rendre 5, 5, 5, 4, 3, 1, 1 ismerse van az embereknek. Megoldás. A feladatnak megfelel gráf csúcsai jelöljék a társaság tagjait. Két csúcs akkor legyen összekötve, ha a megfelel tagok ismerik egymást. Tehát azt kell bebizonyítanunk, hogy nincs olyan egyszer gráf, amely csúcsainak fokszáma rendre 5, 5, 5, 4, 3, 1, 1. Belátjuk, hogy az olyan 7 csúcspontból álló gráfokban, melyekben 5 fokszámú csúcsokból 3 van, maximum 1 darab elsfokú csúcs lehetséges. Legyenek ugyanis az 5 fokszámú csúcsok c 1 , c2 és c3 . Ezen csúcsok mindegyike a gráfnak csak 1 csúcsával nem szomszédos. Indirekt tegyük fel, hogy két darab els fokú csúcs van, s 1 és s2 . Mivel (c1 ) = 5, ezért c1 az s1 és s2 csúcsok valamelyikével szomszédos. Legyen ez a csúcs az s1 . c2 szintén szomszédos s1 és s2 valamelyikével, de ez csak s2 lehet, hiszen (s1 ) = 1 és s1 szomszédos c1 -gyel. Viszont c3 is szomszédos s1 és s2 valamelyikével, amely lehetetlen. Ezzel az állítást beláttuk. 3.15. Feladat. Egy sakkversenyen bármely két játékos legfeljebb egyszer játszott egymással. Bizonyítsuk be, hogy a verseny bármely pillanatában volt két versenyz, akik addig ugyanannyi mérkzést játszottak le. Megoldás. A feladatnak megfelel gráf csúcsai jelöljék a játékosokat. Két csúcs akkor legyen összekötve, ha a megfelel játékosok játszottak egymással. Látható, hogy a feladat a 3.12. feladat (a) részével azonos. 3.16. Feladat. Egy futball bajnokságon n csapat vett részt, és mindenki játszott mindenkivel. Hány mérkzés volt összesen? Megoldás. A feladatnak megfelel gráf csúcsai jelöljék a csapatokat, két csúcs akkor legyen összekötve, ha a megfelel csapatok játszottak egymással. A kérdés tehát az, hogy az n csúcspontú teljes gráfunknak hány éle van, amely n(n - 1) a 3.12. feladat (c) része alapján . 2 3.17. Feladat. Egy futball bajnokságban 18 csapat vesz részt. Minden hétvégén lezajlik egy forduló, amelyben valamilyen párosításban kilenc mérkzést rendeznek. Igazoljuk, hogy 8 forduló után van legalább 3 olyan csapat, amelyek egyáltalán nem játszottak még egymással. Megoldás. Rendeljük azt a gráfot a feladathoz, melynek csúcsai a csapatokat reprezentálják, továbbá két csúcs akkor van összekötve, ha a csapatok már játszottak egymással. A feladat tehát három olyan csúcs keresése, amelyek egyike sem szomszédos a másik kettvel. Legyen c egy tetszleges csúcs, és legyenek c1 , c2 , . . . , c9 azok a csúcsok, amelyekkel nem szomszédos. Belátjuk, hogy ezen kilenc csúcs között van 2 olyan, amelyeket egymással nem köt össze él, tehát a c csúcs és ezen két csúcs a kívánt tulajdonságúak.

102

3. GRÁFELMÉLET

Indirekt tegyük fel, hogy nincs két olyan csúcs a c 1 , c2 , . . . , c9 pontok között, amelyek egymással nem szomszédosak, tehát a gráfban ez a 9 csúcs egy különálló, 9-szögpontú teljes gráfot alkot. (Azért mondhatjuk, hogy különálló, mert tudjuk, hogy a gráfban minden csúcs foka pontosan 8.) Ez azt jelenti, hogy ez a 9 csapat nem játszott meccset a többi csapattal, ami lehetetlen, hiszen egy adott fordulóban mindenki pályára lép, és a 9 csapatot lehetetlen egymás között párosítani. Ezzel az állítást beláttuk. 3.18. Feladat. Bizonyítsuk be, hogy ha 2n számú telefonközpont mindegyikének van a többiek közül legalább n-nel közvetlen összeköttetése, akkor bármely két központ között létesíthet telefonkapcsolat. Megoldás. Legyen G olyan gráf, melynek csúcsai a telefonközpontoknak felelnek meg, két csúcs pedig akkor van összekötve, ha a megfelel központoknak van egymással közvetlen kapcsolata. Így megfogalmazva, a feladat a 3.12. feladat (d) részével azonos. 3.19. Feladat. Egy kosárlabda bajnokságra n csapat nevezett be. Eddig n + 1 mérkzés zajlott le. Igazoljuk, hogy van olyan csapat, amely legalább 3 mérkzést játszott. Megoldás. A feladat a 3.12. feladat (e) részének következménye.

2. Euler-kör, Euler-vonal, Hamilton-kör
3.20. Feladat. Euler gráfok-e az alábbi gráfok? Ha igen, adjuk meg egy zárt Euler-vonalukat. PSfrag replacements

4.

1.

2.

3.

Megoldás. Felhasználjuk azt a tételt, miszerint egy gráf akkor és csak akkor Euler-gráf, ha összefügg, és minden csúcsának foka páros. 1. A gráf nem összefügg, így nem Euler-gráf. 2. A gráf összefügg, továbbá minden csúcsának foka páros, így Euler-gráf. Egy zárt Euler-vonal megadásához jelöljük el a gráf éleit:

PSfrag replacements

2. EULER-KÖR, EULER-VONAL, HAMILTON-KÖR

103

e11 e9 e3 e4 e1 e5

e10 e7 e2 e8

PSfrag replacements

e6

A gráf egy zárt Euler-vonala: {e1 , e2 , e8 , e10 , e7 , e6 , e5 , e4 , e9 , e11 , e3 }. 3. A gráf nem Euler-gráf, hiszen van páratlan fokszámú csúcsa. 3.21. Feladat. Írja fel az alábbi gráfok egy Euler-vonalát. Hány Eulervonala van a gráfoknak?
e10 e e6 8 e2 e3 1. e7 e9 e3 e9 e7 e4 e1 2. e5 e2 e8 e6 e4 e1 3. e8 e9

e5 e6 e7 e2 e3

e4 e5 e1

Megoldás. A feladatban felhasználjuk, hogy amennyiben egy gráfnak van Euler-vonala, akkor csak az Euler-vonalban szerepl els és az utolsó csúcs fokszáma lehet páratlan, hiszen a többi csúcs esetén, ha oda "bemegy" a vonal, akkor onnan tovább is kell mennie. 1. A gráfnak 4 darab páratlan fokszámú csúcsa van, így nem létezik Eulervonala. 2. A gráf egy Euler-vonalának els és utolsó csúcsa csak a gráf bal fels vagy jobb fels csúcsa lehet, hiszen ezek fokszáma páratlan. Nyilvánvalóan irányítatlan gráf esetén, ha egy Euler-vonal éleinek sorrendjét megfordítjuk, akkor ismét Euler-vonalat kapunk, így ha felírjuk az összes jobb fels csúcsból kiindulót, azok éleinek sorrendjét megfordítva megkapjuk a bal fels csúcsból kiindulókat is. A jobb fels csúcsból a bal fels csúcsba 16 Euler-vonal húzható, tehát a gráfnak összesen 32 darab Euler-vonala van. Pár példa: {e 9 , e8 , e7 , e3 , e1 , e2 , e6 , e5 , e4 }, {e9 , e8 , e5 , e2 , e6 , e7 , e4 , e1 , e3 }, {e9 , e8 , e6 , e2 , e4 , e3 , e1 , e5 , e7 }. 3. Természetesen definiálható irányított gráfok esetén is az Euler-vonal, ekkor az élek irányítottsága nyilván korlátozza a lehetségeket. A gráf Euler-vonalainak kezd csúcsa a jobb fels csúcs, hiszen oda nem vezet él. Befejez csúcsa pedig szükségképpen az e 9 él végpontja, mivel annak fokszáma páratlan. A gráfnak 8 darab Euler-vonala van, például: {e9 , e8 , e4 , e2 , e6 , e5 , e1 , e3 , e7 }, {e9 , e5 , e1 , e3 , e7 , e8 , e4 , e2 , e6 }.

104

3. GRÁFELMÉLET

3.22. Feladat. Bizonyítsuk be, hogy a nevezetes königsbergi hét híd mindegyikén pontosan egyszer áthaladó sétaút nem létezik. Megoldás. A feladathoz elkészítünk egy gráfot a következképpen: feleltessünk meg a folyó két partjának és a szigeteknek a gráf egy-egy csúcsát, és legyenek az összeköt élek az egyes hidaknak megfelelek: A PSfrag replacements C A D C D

B B A feladat tehát egyenértékú a gráfunk egy Euler-vonalának megkeresésével. PSfrag replacements Azonban a gráfnak mind a négy csúcsa páratlan fokszámú, így az elz feladatban leírtak miatt nincsen Euler-vonala. 3.23. Feladat. Írja fel az alábbi gráfok Hamilton-útjait és Hamilton-köreit:
e6 e4 e3 e1 e2 e2 e5 e3 e1 1. 2. e4 e2 e3 e4 e7 e5 e6

e1 3.

Megoldás. 1. A gráf Hamilton-útjai: {e2 , e4 , e1 }, {e2 , e3 , e1 },{e1 , e4 , e2 }, {e1 , e3 , e2 }. Hamilton-köre nem létezik a gráfnak, hiszen a jobb alsó csúcs fokszáma 1, így nem lehet tagja egy körnek sem. 2. Irányított gráfok esetén a Hamilton-út és Hamilton-kör definíciója analóg az irányítatlan gráfos definícióval, azonban az élek irányítottsága miatt az utak és körök száma kevesebb. A gráf bal alsó csúcsába nem mutat él, így a Hamilton-utak csak onnan indulhatnak. Két Hamilton-út van: {e1 , e2 , e5 }, {e4 , e3 , e2 }. Hamilton-köre viszont nincs a gráfnak, hiszen a jobb alsó csúcsba nem vezet él, így ez a csúcs nem szerepelhet körben. 3. A gráf Hamilton-útjai: {e5 , e4 , e2 , e7 }, {e4 , e2 , e7 , e6 }, {e2 , e7 , e6 , e5 }, {e7 , e6 , e5 , e4 }, {e6 , e5 , e4 , e2 }. A gráfnak van Hamilton-köre is, az {e 5 , e4 , e2 , e7 , e6 } élsorozat:

PSfrag replacements
1. 2. EULER-KÖR, EULER-VONAL, 3. e4 e7 e2 e3 e1 e6 e5

2.

HAMILTON-KÖR

105

3.24. Feladat. Igazoljuk, hogy (a) ha a G összefügg gráfból k számú pontjának a hozzájuk illeszked élekkel együtt való törlése révén keletkezett k-nál több komponens, akkor G-nek nincs Hamilton köre. Továbbá, ha e törlés révén k + 1-nél több komponensbl álló gráfot nyerünk, akkor G-nek nincsen Hamiltonútja sem. (b) ha egy G egyszer gráfban minden csúcspont foka legalább k 2, akkor van a gráfban egy legalább k + 1 hosszúságú kör. (c) ha a G összefügg gráf G részgráfja nem tartalmazza G minden pontját, akkor van G-nek olyan G -be nem tartozó éle, amelynek egyik végpontja G -beli, a másik nem. (d) ha egy G összefügg gráf K körébl egy élt törölve, a gráf egy L leghosszabb útját kapjuk, akkor K Hamilton-köre a gráfnak. (e) ha egy n csúcsú G egyszer gráf egy L leghosszabb útja két végpontjának fokszám összege legalább n, akkor van a gráf leghosszabb útjai között olyan, amelynek végpontjai szomszédosak. (f) ha egy n csúcspontú (n 3) G egyszer gráf bármely két nem szomszédos pontjának fokszám összege legalább n, akkor van a gráfnak Hamiltonköre (Ore tétele). (g) ha egy n csúcspontú (n 3) G egyszer gráf minden csúcsának foka n legalább , akkor van a gráfnak Hamilton-köre (Dirac tétele). 2 Megoldás. (a) Egy összefügg gráf k számú csúcsát törölve a gráf bármely köre legfeljebb k komponensre, útjai pedig legfeljebb k + 1 komponensre esnek szét. Mivel a Hamilton-kör illetve Hamilton-út tartalmazza a gráf minden pontját, adódik az állítás. (b) Legyen L egy leghosszabb út G-ben. Jelöljük L csúcsait sorrendben c1 , c2 , . . . , cl -lel. A c1 csúcs minden szomszédja L-ben van, hiszen L leghosszabb út. De c1 -nek legalább k szomszédja van, így van olyan c j szomszédja is, melyre j k + 1. Ekkor azonban L-nek a c 1 és cj közötti részútja a (c1 , cj ) éllel kiegészítve egy k-nál hosszabb kört alkot.

106

3. GRÁFELMÉLET

(c) Legyen c1 G-nek egy G -beli, c2 pedig egy nem G -beli pontja. c1 bl vezet egy L út c2 -be, hiszen G összefügg. A c1 pontból kiindulva haladjunk L élein addig, amíg G -be kerülünk. Nyilván az utoljára bejárt él a kívánt tulajdonságú. (d) Amennyiben K nem tartalmazza G minden pontját, akkor a feladat (c) állítása szerint van olyan e = (c 1 , c2 ) él, amelynél c1 K-beli, c2 pedig nem K-beli. Ha a K élei közül elhagyunk egy c 1 -hez illeszkedt és hozzávesszük e-t, akkor egy olyan utat kapunk, amely az L út hosszánál nagyobb, amely ellentmond annak, hogy L leghosszabb út. Így K áthalad G minden pontján, azaz Hamilton-kör. (e) Jelöljük L csúcsait sorrendben c 1 , c2 , . . . , cl -lel. Legyen és A := {c | c a G olyan csúcsa, mely nem szomszédos c l -el} B := ck | ck+1 szomszédja c1 -nek (k {1, 2, . . . l - 1}) .

A feladat feltétele szerint (c1 ) + (cl ) n, azaz (cl ) n - (c1 ). Tehát cl G-nek legfeljebb (c1 ) számú csúcsával nem szomszédos, azaz |A| (c1 ), továbbá cl A. A c1 csúcs minden szomszédja L-ben van, hiszen L leghosszabb út. Ezért |B| = (c1 ) és cl B, hiszen cl az utolsó csúcs a sorozatban, így nem lehet c1 egy szomszédja eltt. A fentiek alapján van olyan eleme B-nek, amely nincs benne Aban. Legyen ez a csúcs a ci csúcs (ci {1, 2, . . . l - 1}). Tehát ci olyan szomszédja cl -nek, amelynek az L útban lév ci+1 szomszédja a c1 -nek PSfrag replacements is szomszédja. Ezért, ha az L útból elhagyjuk a (c i , ci+1 ) élt és hozzávesszük a (ci , cl ) élt, akkor a kívánt utat állítottuk el, azaz olyan l hosszúságú (így leghosszabb) L utat, amelynek végpontjai szomszédosak. Az elmondottakat a következ ábra szemlélteti:
c1 c2 ci ci+1 L cl-1 cl c1 c2 ci ci+1 L cl-1 cl

(f) Ha G nem volna összefügg, akkor különböz komponensbe tartozó két pontja nem lenne szomszédos és nem lenne olyan csúcs sem, amelybe mindkét csúcsból él vezet, így az ilyenek fokszám összege legfeljebb n-2 lenne, amely ellent mondana a feltevésünknek. Tehát G összefügg. Jelöljük L-lel G egy leghosszabb útját. Ha L végpontjai szomszédosak, akkor a feladat (d) része szerint van G-nek Hamilton-köre (az L út és az út végpontjait összeköt él). Ha L végpontjai nem szomszédosak, akkor

2. EULER-KÖR, EULER-VONAL, HAMILTON-KÖR

107

ezek fokszám összege legalább n, így a feladat (e) része szerint van olyan leghosszabb út G-ben, amelynek végpontjai szomszédosak, amibl a (d) rész miatt ismét adódik, hogy van a gráfnak Hamilton-köre. (g) Az állítás a feladat (f ) részébl azonnal adódik. PSfrag replacements 3.25. Feladat. Állapítsuk meg, teljesítik-e az alábbi gráfok Ore és Dirac tételét, továbbá amennyiben létezik, adjuk meg egy Hamilton-körüket:
c5 c6 c4 c3 c7 c3 c1 2. c2 c5 c7 c4 c3 c1 3. c2 c5 c7 c4

c1

c2 1.

PSfrag ezért Dirac tételét nem teljesíti, hiszen az csak páros 1. A gráf rendje 7, replacements 1. csúcsszámú gráfokra alkalmazható. Nem teljesül Ore tétele sem, ugyanis 2. például a c3 és c7 egymással nem szomszédos csúcsok fokának összege 3. csak 4. A gráfnak viszont létezik Hamilton-köre:
c5 c6 c4 c1 c2 c3 c7

PSfrag replacements 2. A gráf rendje 6, viszont a c4 csúcs foka csak 2, így Dirac tétele nem teljesül. Azonban minden más csúcs foka 4, így Ore tétele teljesül, tehát 1. a gráfnak van Hamilton-köre. Például: 2.
3. c5 c7

c3 c6 c1 c2

c4

3. A gráf rendje 6, és minden csúcsának foka 3, így Dirac és Ore tétele egyaránt teljesül, azaz a gráfnak van Hamilton-köre. Például:

PSfrag replacements
108

1. 2. 3.

3. GRÁFELMÉLET

c5

c7

c3 c6 c1 c2

c4

3.26. Feladat. Bizonyítsuk be, hogy ha egy társaság minden tagja ismeri a társaságnak legalább k tagját (k 2), akkor leültethet közülük legalább k + 1 egyetlen kerek asztal körül úgy, hogy mindenkinek ismerse legyen a szomszédja. Megoldás. Legyen G egy olyan gráf, melynek csúcsai a társaság tagjainak felelnek meg. Két csúcs akkor van összekötve, ha a két tag ismeri egymást. A feladat tehát megmutatni, hogy ebben a gráfban van egy k + 1 hosszúságú kör, amely a 3.24. feladat (b) részébl következik. 3.27. Feladat. Bizonyítsuk be, hogy ha egy 8 tagú társaság minden tagja ismeri a társaságnak legalább 4 tagját, akkor valamennyien leültethetk egy kerek asztal köré úgy, hogy mindenkinek ismerse legyen a szomszédja. Megoldás. Az elz feladatban leírt gráffal dolgozva azt kell belátnunk, hogy a gráfnak van Hamilton-köre, amely a 3.24. feladat (g) részébl következik. 3.28. Feladat. Legyen n egy páratlan szám és legyen adott egy n × n-es "sakktábla". Igazoljuk, hogy egy lóval lóugrásokban nem tudjuk bejárni a sakktáblát úgy, hogy a kiindulási helyre érkezzünk a végén, és közben minden mezt csak egyszer érintünk. Megoldás. Legyenek a G gráf csúcspontjai a sakktábla mezinek megfelelek. Két csúcs akkor legyen összekötve, ha a megfelel mezkrl el lehet jutni 1 lólépésben egymásra. A feladat a tekintett gráfról belátni, hogy nincsen Hamilton-köre. Azt kell csak észreveni, hogy fehér mezrl csak feketére tudunk eljutni lóugrásban, és viszont. Így a G gráf egy Hamilton-körét bejárva fekete meznek megfelel csúcsot fehérnek megfelel követ, és viszont, ezért páros sok csúcsnak kellene lennie. Azonban ez nem teljesül, hiszen a G gráfnak n2 számú csúcsa van, ami páratlan.

3. GRÁFOK CSÚCSMÁTRIXA

109

3. Gráfok csúcsmátrixa
3.29. Feladat. Írjuk fel az alábbi gráfok csúcsmátrixát: PSfrag replacements
c3 c2 c1 1. c1 2. c2 c1 3. c2 c3 c4 c3 c4 c5

Megoldás. Az n csúcsú irányított gráf csúcsmátrixa azon A = (a ij ) Mn×n mátrix, melynek aij általános eleme egyenl a ci csúcsból a cj csúcsba vezet élek számával. 1. A gráf csúcsmátrixa 0 2 1 0 0 0 . 1 1 1 2. A gráf csúcsmátrixa 0 1 1 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0 0 . 1 0 1 0 0 . 0 0

3. A gráf csúcsmátrixa

3.30. Feladat. Ábrázoljuk az alábbi csúcsmátrixú gráfokat: 0 0 1 0 1 0 0 2 0 0 1 0 0 3. 1 1. 1 0 0 2. 1 1 1 1 1 1 0 2 1 0 0 1 0 Megoldás.

1 0 1 0 1

1 0 0 0 1

0 1 0 1 0

1 0 0 1 0

110

3. GRÁFELMÉLET

PSfrag replacements
c3 c3 c4 c3 c2 c1 1. c1 2. c2 c1

c5 c4

c2 3.

3.31. Feladat. Hány 2, 3 illetve 4 hosszúságú töröttvonal rajzolható az alábbi csúcsmátrixú gráfok c2 csúcsából a c3 csúcsába, illetve a c3 csúcsából a c2 csúcsába? 1 1 1 1 1 1 2 0 1 1 0 0 1 0 (a) A = 1 0 3 (b) B = 0 0 2 (c) C = 0 0 0 2 0 1 1 1 1 0 0 1 1 0 Megoldás. Az A Mn×n csúcsmátrixú gráf (Al )ij eleme megadja a ci csúcsból a cj csúcsba vezet l hosszúságú töröttvonalak számát. 2 3 7 5 9 20 14 25 57 (a) A2 = 1 4 5, A3 = 5 6 19 és A4 = 11 24 47, tehát a 1 1 4 2 5 9 7 11 28 c2 -bl c3 -ba vezet 2, 3 illetve 4 hosszúságú töröttvonalak száma rendre 5, 19 és 47, a c3 -ból c2 -be vezetk száma pedig 1, 5 és 11. (b) 1 1 2 2 3 3 3 5 8 (c) B 2 = 2 2 0, B 3 = 0 2 6 és B 4 = 6 6 4, tehát a 0 1 3 3 3 2 2 5 9 c2 -bl c3 -ba vezet 2, 3 illetve 4 hosszúságú töröttvonalak száma rendre 0, 6 és a c3 -ból c2 vezetk száma pedig 1, 3 és 5. 4, -be 1 2 3 3 1 4 6 7 1 8 12 13 0 0 0 2 3 0 2 2 0 , C = és C 4 = 0 0 2 4 , (d) C 2 = 0 2 2 0 0 0 2 4 0 4 4 4 0 0 1 2 0 2 2 2 0 2 4 4 tehát a c2 -bl c3 -ba vezet 2, 3 illetve 4 hosszúságú töröttvonalak száma rendre 0, 2 és 2, a c3 -ból c2 -be vezetk száma pedig 2, 0 és 4. 3.32. Feladat. Tartalmaznak-e az alábbi csúcsmátrixú gráfok irányított kört?

3. GRÁFOK CSÚCSMÁTRIXA

111

(a)

0 1 0 1 0 1 0 1 0

(b)

0 2 1 0

0 0 0 0

0 1 0 0

1 0 1 0

(c)



0 0 0 0 0

1 0 0 0 0

1 1 0 0 0

1 1 1 0 0

1 1 1 1 0



Megoldás. Felhasználjuk azt a tételt, miszerint egy n csúcspontú irányított gráf pontosan akkor tartalmaz kört, ha csúcsmátrixának n-edik hatványa nem azonosan nulla. (a) A gráf tartalmaz irányított kört, ugyanis csúcsmátrixának harmadik 0 2 0 hatványa 2 0 2 , tehát nem az azonosan nulla mátrix. 0 2 0 (b) Könnyen kiszámolható, hogy a mátrix negyedik hatványa az azonosan nulla mátrix, így a gráf nem tartalmaz irányított kört. (c) A gráf nem tartalmaz irányított kört, ugyanis csúcsmátrixának ötödik hatványa az azonosan nulla mátrix. 3.33. Feladat. Határozzuk meg az alábbi csúcsmátrixú gráfok különböz csúcsai közötti legrövidebb irányított út hosszát, és az ilyen számát. utak 1 0 2 0 1 0 1 0 0 1 0 0 0 1 (a) A = 1 0 0 (b) B = 0 2 1 (c) C = 0 1 0 0 0 1 1 0 1 1 1 1 1 1 Megoldás. Felhasználjuk, hogy egy A csúcsmátrixú n csúcspontú gráf c i csúcsából a cj csúcsba (i = j) vezet legrövidebb út hossza az a legkisebb k pozitív egész szám, amelyre (Ak )ij = 0, és ekkor az ilyen hosszúságú utak száma éppen (Ak )ij . Nyilvánvaló, hogy ez a k szám nem lehet nagyobb, mint n - 1, hiszen az n - 1-nél nagyobb élszámú töröttvonal már legalább 1 csúcson többször is átmegy, így az nem lehet út. Ebbl következik, hogy ha egy csúcsból egy másikba nem tudok eljutni n-1 élen keresztül, akkor sehogy sem, azaz a legrövidebb út hossza végtelen. A c i csúcsból a cj csúcsba vezet legrövidebb út hosszát d(ci , cj )-vel jelöljük, és nevezhetjük a ci csúcs cj csúcstól való távolságának, de fontos megjegyezni, hogy irányított gráfok esetén ez a távolság nem metrika, hiszen nem biztos, hogy teljesül a d(c i , cj ) = d(cj , ci ) egyenlség.

112

3. GRÁFELMÉLET

0 0 1 (a) A1 = 1 0 0, azaz d(c1 , c3 ) = d(c2 , c1 ) = d(c3 , c2 ) = 1. 0 1 1 0 1 1 A2 = 0 0 1, tehát két élen keresztül már el tudok jutni c 1 -bl c2 1 1 1 be, c2 -bl c3 -ba és c3 -ból c1 -be, így d(c1 , c2 ) = d(c2 , c3 ) = d(c3 , c1 ) = 2. Mivel a mátrixokban a nem nulla elemek mind 1-esek voltak, így bármely két csúcs esetén a legrövidebb utak száma 1. 1 0 1 (b) B 1 = 0 2 1, tehát d(c1 , c3 ) = d(c2 , c3 ) = d(c3 , c2 ) = 1. A c2 -bl 0 1 1 c3 -ba vezet legrövidebb utak száma 2, a c 1 -bl c3 -ba és a c3 -ból c2 -be vezetké pedig 1. 1 1 2 B 2 = 0 5 3, tehát d(c1 , c2 ) = 2 és a c1 -bl c2 -be vezet legrövidebb 0 3 2 utak száma 1. Mivel c2 -bl és c3 -ból nem tudunk eljutni kett hosszúságú úton a c1 -be és a gráfnak 3 csúcsa van, ezért c 1 -be a c2 és c3 csúcsokból nem vezet (irányított) út, így d(c2 , c1 ) = d(c3 , c1 ) = . 1 0 2 0 0 0 0 1 (c) C 1 = 0 1 0 0, tehát d(c1 , c3 ) = d(c2 , c4 ) = d(c3 , c2 ) = d(c4 , c1 ) = 1 1 1 1 d(c4 , c2 ) = d(c4 , c3 ) = 1. c1 -bl c3 -ba 2 legrövidebb út van, a többi 5 esetben pedig 1. 1 2 2 0 1 1 1 1 C2 = 0 0 0 1, ennélfogva d(c1 , c2 ) = d(c2 , c1 ) = d(c2 , c3 ) = 2 2 3 2 d(c3 , c4= 2. c1 -bl2 -be 2 legrövidebb út van, a másik 3 esetben 1. ) c 1 2 2 2 2 2 3 2 C3 = 1 1 1 1, így d(c1 , c4 ) = d(c3 , c1 ) = 3. c1 és c4 között 2 4 5 6 4 legrövidebb út van, c3 és c1 között pedig 1.





Irodalomjegyzék
[1] Andrásfalvi Béla: Ismerkedés a gráfelmélettel, Budapest, Tankönyvkiadó (1971). [2] Feladatlapok II. matematikából (közgazdász hallgatók számára), Debrecen, Matematika Intézet (2004). [3] Kovács Zoltán: Feladatgyjtemény lineáris algebra gyakorlatokhoz, Debrecen, Kossuth Egyetemi Kiadó (1998). [4] Solt György: Valószínségszámítás, Budapest, Mszaki könyvkiadó (1995).

113



Hasonló témájú dokumentumok

Hozzászólások

... 3.óra 7. 8. előadás acélgyártás algoritmus állatszervezettan alternatív energiaforrások ásvány- és kőzettan beadandó bioetika biokémia biztonság biztonsgtecnika éptöri épületfizika eredménykimutatás filozófiai antropológia funkcionalizmus gazdaságtörténelem gazdpol glikoneogenezis helyi társadalom hull idősorok jogfosztás kémia kérdések kórtan kosztolányi közigazgatás közigazgatás alapintézményei kronológia liliidae logisztika mechanika 2 metafora montázs növényrendszertan outsourcing öko 1 ökológia pdf pr elmélet szintay szótár technika tűzvédelem újság valószínűség