1
Diszkrét matematika II., 1. el®adás
Lineáris leképezések Dr. Takách Géza NyME FMK Informatikai Intézet
[email protected] http://inf.nyme.hu/takach/ 2005. február 6
Gyakorlati célok Ezen el®adáson, és a hozzá kapcsolódó gyakorlaton való
aktív részvétellel Ön képes lesz
egy képlettel vagy geometriai leírással adott leképezés linearitását eldönteni az
R
n
vektortérben;
egy képlettel megadott leképezés linearitását eldönteni a valós sorozatok körében; egy képlettel megadott leképezés linearitását eldönteni a valós polinomok körében; egy lineáris leképezés képterének és magterének meghatározására, és ezzel az injektivitás és szürjektivitás eldöntésére; vektorterek izomor ájának eldöntésére a dimenzió segítségével; egy lineáris leképezés mátrixának felírására és ennek segítségével konkrét vektorok képének meghatározására; lineáris leképezések kompozícióját megadó mátrixok megadására.
Elméleti, fogalmi célok Ezen el®adáson, és a hozzá kapcsolódó gyakorlaton való
aktív részvétellel Ön
a linearitáson keresztül megérti a m¶velettartó leképezés fogalmát, és el tudja képzelni, hogy ez más struktúrák esetén is értelmes fogalom; érzékeli, hogy a linearitás igen er®s megkötés egy leképezésre; érzékeli annak a jelent®ségét, hogy egy lineáris leképezés egy mátrixszal is megadható, és így a gyakorlatban könnyen végrehajtható; megérti, hogy az izomorf struktúrák lényegében ugyanazok; a dimenziótétel kapcsán megtapasztalja az inejtivitás és a szürjektivitás közti kapcsolatot; látja a mátrixszorzás egy alkalmazási lehet®ségét.
A téma jelent®sége A vektorok körében ugyanolyan fontosak a lineáris leképezések, mint a számok körében a szokásos lineáris függvények, azaz az f (x) = ax + b alakú függvények. Gyakran van szükség arra, hogy valamilyen mért értékekb®l álló vektorokat egy programmal (lineárisan) transzformáljuk; látni fogjuk, hogy ez mátrixok segítségével könnyen elvégezhet®. A többváltozós függvények körében is fogunk találkozni lineáris függvényekkel. A függvénygra kon egyenessel való közelítéséhez hasonlóan itt a síkkal való közelítést alkalmazhatjuk, ami kiindulási ponttól való eltérésvektor lineáris függvénye.
2 A kódoláselméletben is fontos szerepet játszanak a lineáris leképezések. A legegyszer¶bb hibajelz® kódolás abban áll, hogy egy számsorozat után biggyesztjük a számok összegét is, így ha a számsorozat továbbítása során valamelyik szám "megsérül", azaz a címzett mást kap helyette, akkor ezt az ellen®rz® összegb®l azonnal észreveszi. Ez, és ennek a módszernek a nagyobb hibákat is jelz® általánosításai mind lineáris leképezések.
Szükséges fogalmak és módszerek korábbról
vektortér; altér; zártsági feltételek ellen®rzése; lineáris kombináció; injektív ill. szürjektív leképezés; ekvivalenciareláció; bázis, dimenzió, szám n-esek tere; dimenzió meghatározása; mátrix mátrixok szorzása;
Formális de níció De níció. Legyenek V1 és V2 ugyanazon T test feletti vektorterek. A V1 -b®l V2 -be ható A függvényt lineáris leképezésnek nevezzük, ha m¶velettartó, azaz (i) (ii)
8u; v 2 V1 -re A u v Au Av; 8u 2 V1 ; 8 2 T -re A u Au
Írásmód:
(
+
) =
(
) =
+
(
)
A(u) helyett Au.
Szavakkal megfogalmazva: (i) összeg képe egyenl® a képek összegével; (ii) konstansszoros képe egyenl® a kép konstansszorosával;
Forgatás, mint lineáris leképezés A forgatás a síkot önmagára képezi le. Ha egy függvény értelmezési tartománya és képhalmaza megegyezik, transzformációról beszélünk. Azaz a forgatás egy geometriai transzformáció. A lineáris transzformáció egy olyan lineáris leképezés, ahol ... Vajon az origó körüli forgatás lineáris transzformáció-e? Itt nem pontokkal, hanem a megfelel® helyvektorokkal dolgozunk, így értelmezhet® az összeg és a konstansszoros. a) Két helyvektor összegét elforgatjuk. b) A két helyvektort elforgatjuk, majd a képeiket összeadjuk. Ugyanoda jutunk?
3 ÁBRA: Igen, a forgatás egybevágósági transzformáció, így a két háromszög egybevágó! Hasonlóan: a) Egy helyvektor konstansszorosát elforgatjuk. b) A helyvektort elforgatjuk, majd megszorozzuk ugyanazzal a konstanssal. Ugyanoda jutunk?
További példák Példa. 1. A síkon az x-tengelyre vonatkozó vetítés lineáris transzformáció. Ez igazolható geometriai úton is (ábra), de egyszer¶en koordinátákkal való számolással is: Tipp: A vetítés az
x = (x1 ; x2 ) vektorhoz hozzárendeli a V x = (x1 ; 0) vektort.
TÁBLÁN
Példa.
2. A síkon az eltolás nem lineáris transzformáció.
Tipp: szinte tetsz®leges két vektor az összeadásra nézve, itt is számolhatunk koordinátákkal. Az eltolás mértéke is tetsz®leges, válasszunk valami egyszer¶t!
Példa.
3. A polinomok körében a deriválás lineáris leképezés-e?
Tipp: Ellen®rzésképpen írjuk fel a linearitás két axiómáját erre a konkrét esetre, és gondoljuk meg, igazak-e ezek a deriválásra!
Formális de níció De níció. Legyenek V1 és V2 ugyanazon T test feletti vektorterek. A V1 -b®l V2 -be ható A függvényt lineáris leképezésnek nevezzük, ha m¶velettartó, azaz (i) (ii)
8u; v 2 V1 -re A u v Au Av; 8u 2 V1 ; 8 2 T -re A u Au (
+
) =
(
) =
+
(
)
Szavakkal megfogalmazva: (i) összeg képe egyenl® a képek összegével; (ii) konstansszoros képe egyenl® a kép konstansszorosával;
Megjegyzés.
(ii)-ben.
Az (i)-beli
Megjegyzés. V1
+
jelek nem ugyanazt a m¶veletet jelölik, hasonlóan a skalárral való szorzás sem ugyanaz
minden eleméhez egyértelm¶ a kép, hiszen függvény.
Megjegyzés. V2 -beli elem ®sképe nem feltétlenül egyértelm¶ és nem feltétlenül létezik (nem feltétlenül injektív, szürjektív).
Egyszer¶ következmények Tétel.
I. A01 = 02 , ahol 0i a Vi vektortér nulleleme. (Nullvektor képe nullvektor) II. A( u) = (Au)
Bizonyítás. I. Trükk: u + 01 = u =A() Au = A(u + 01 ) /linearitás a jobb oldalon = Au Au = Au + A01
ill.
4
Au Au = (Au + A01 ) Au /komm. és asszoc. /vektortérax. (V2 -ben!) Au Au = (Au Au) + A01 02 = 02 + A01 = 02 02 = A01 II.
0
}
2 = A01 = A(u + ( u)) = Au + A( u)= Au
Egyszer¶ következmények Tétel. III. A(1 u1 + : : : + u k
Bizonyítás.
k
) =
1 Au1 + : : : + Au . k
k
Speciálisan két tényez®re az összefüggés:A( a + b) = A(a) + (b).
Bizonyításban felhasználjuk a két axiómát:
A( a + b) = A( a) + A( b) = A(a) + A(b) Következmény. Egy leképezés akkor és csak akkor lineáris, ha megtartja a kéttagú lineáris kombinációt, azaz A( a + b) = A(a) + A(b). Bizonyítás.
A lineáris leképezések a tétel szerint megtartják a lineáris kombinációt.
Fordítva, az összeg megkapható
= 1; = 1-gyel, a skalárszoros pedig = c; = 0-ként.
Megjegyzés. A következmény segítségével egy lendülettel ellen®rízhet®, hogy egy leképezés lineáris-e.
Képtér, magtér De níció. Legyen A lineáris leképezés V1 -b®l V2 -be. A képtere: a képelemek halmaza. A magtere: a 02 -re képezett elemek halmaza.
Jelölés: ImA = fy
Tétel.
2 V2 j 9x 2 V1 Ax yg fAxj x 2 V1 g a képtér, KerA fx 2 V1 j Ax :
ImA altér
Bizonyítás. óra?
=
=
=
2 g.
= 0
V2 -ben, KerA altér V1 -ben.
Magtér: zárt-e az összeadásra és a skalárral való szorzásra? Egyszer¶bben: zárt-e a lineáris kombináci-
u; v 2 KerA )? u + v 2 KerA Au = Av = 0 )?A( u + v) = 0 A( u + v) = A(u) + A(v) = 0 + 0 = 0
}
Képtér esetén hasonlóan. (HF)
Példák Példa.
Legyen
V1 = V2 a sík.
Ekkor lineáris leképezés:
origó körüli elforgatás: Ez egy injekció, azaz origó csak az origónak a képe, vagyis KerF Mivel szürjekció is, minden pontnak van ®se, azaz ImF = V2 . vetítés az x-tengelyre: Az egész y -tengely az origóba megy, azaz KerV Az értékkészlet ImV = x-tengely.
=
=
f ; ; y j y 2 Rg. ( 0
)
f g. 0
5
deriválás: KerD: Milyen polinomok deriváltja a 0? ImD: Milyen polinomok kaphartóak meg deriválással?
Tetsz®leges V1 és V2 esetén V1 minden elemének feleltessük meg a V2 nullelemét. Ez a nulla leképezés jelölés: O. V1 V2 V és minden elem képe önmaga. Ez az identikus leképezés, id . =
=
V
Izomor zmus De níció. V = Z.
Izomor zmus: bijektív lineáris leképezés.
V
vektortér izomorf Z -vel, ha van V
! Z izomor zmus. Jelölés:
Izomorf vektorterek a mi szempontunkból megkülönböztethetetlenek. Izomor zmus eldönthet® a kép- és magtere alapján:
Tétel. Az A : V1 ! V2 lineáris leképezés akkor és csak akkor izomor zmus, ha KerA = f0g és ImA = V2 . Bizonyítás. ImA = V2 pontosan azt jelenti, hogy V2 minden eleme kép, azaz A szürjektív. KerA = f0g ) injektivitás: Tfh. Au = Av , következik-e, hogy u = v ? A(u v) = Au Av = 0, tehát u v 2 KerA = f0g, így u = v. Fordítva, tfh. A injektív, és legyen u 2 KerA. Ekkor Au = 0 = A0, így az injektivitás miatt u = 0!, vagyis KerA = f0g.
}
Megjegyzés. f0g helyett az egyszer¶bb 0 jelölést használjuk.
Izomor zmus Tétel. Az izomor a ekvivalenciareláció, azaz
V V V Z esetén Z V V Z és Z W esetén V W = =
=
=
=
Bizonyítás.
=
Identikus leképezés, izomor zmus inverze, izomor zmusok szorzata (összetett függvény)...
}
Mik az osztályok? Mivel azonosítható egy osztály? Mi az osztályok jellemz® reprezentánsa? Sejtés:
T
n
, az n-komponens¶ vektortér a jellemz® n-dimenziós vektortér.
n-dimenziós vektorterek Tétel. Ha V a T test feletti n-dim. vektortér, akkor V Bizonyítás.
izomor zmus: Legyen
Rendeljük egy
u1 ; ; u 2 ; : : : ; u
n
u
2V
egy bázis
T =
n
.
vektorhoz egy el®re rögzített bázisban adódó koordinátáit. Ez a hozzárendelés
V -ben és legyen A:V 1 u1 + : : : + u n
n
! T 7 ! 1 ; : : : ; n
(
n)
Ez bijektív, hisz a ránézésre megadható az inverze. (Mi az?) Továbbá lineáris leképezés is, ld. TÁBLA!
}
6
Következmény. Két azonos dimenziós vektortés izomorf. Bizonyítás. fak.
Ha mindkett® n-dimenziós, akkor mindkett® izomorf
T
n
-nel. A tranzitivitás miatt egymással is izomor-
}
Tehát az azonos dimenziós vektorterek egy osztályba esnek. Már csak azt kell belátni, hogy a különböz® dimenziós vektorterek nem lehetnek izomorfak. Kontrapozícióval:
Tétel. Ha két vektortér izomorf, akkor azonos dimenziósak. Tfh. U = V . Ekkor van egy A : U bázis V -ben. (Bázis képe bázis) n
!V
Bizonyítás. Au1 ; : : : ; Au
Generátorrendszer: Legyen
v 2V.
Szürjektivitás
u1 ; : : : ; u
izomor zmus. Legyen
n
bázis
U -ban, azt állítjuk, hogy
) létezik u 2 U , hogy Au v. A linearitása miatt =
v = Au = A(1 u1 + : : : + u n
n
) =
1 (Au1 ) + : : : + (Au ): n
n
Független:
1 (Au1 ) + : : : + (Au ) = 0 ) A(1 u1 + : : : + u ) = 0 = A0: Az injektivitás miatt 1 u1 + : : : + u = 0, s mivel u -k függetlenek, 1 = : : : = = 0. n
n
n
n
n
n
}
n
i
Dimenziótétel !V
Tétel. Legyen U véges dimenziós és V tetsz®leges vektortér T test felett, A : U dim
KerA + dim ImA = dimU:
Bizonyítás. Legyen dim U = n; dim KerA = s. b1 ; : : : ; b bázis KerA-ban. U bázisává. Állítjuk, hogy Ab +1 ; : : : ; Ab ImA bázisa lesz.
Ezt kiegészítjük
s
s
Generátorrendszer: Ha
lineáris leképezés. Ekkor
b +1 ; : : : ; b s
Au egy tetsz®leges elem ImA-ban, és u = 1 b1 + : : : + b n
n
n
) =
1 Ab1 + : : : + Ab n
=
n
n
. Ekkor
+1 Ab +1 + : : : + Ab : s
s
n
n
Függetlenség: Tegyük fel, hogy s+1 Abs+1 + : : : + n Abn = 0. Ekkor A(s+1 bs+1 + : : : + n bn ) s+1 bs+1 + : : : + n bn 2 KerA. Viszont így x felírható x = 1 b1 + : : : + s bs alakban is. Tehát
1 b 1 + : : : + b b1 ; : : : ; b
n
vektorokkal
n
Au = A(1 b1 + : : : + b
ami a
n
s
s
bázis volta miatt azt jelenti, hogy
+1 b +1 : : : b s
i = 0
n
s
n
= 0
, azaz
x
=
= 0
}
minden i-re.
Következmény. Legyen A a véges dimenziós V vektortér lineáris transzformációja (önmagára való lineáris leképezé-
se). Ekkor
ImA = V
, KerA
:
= 0
Más szavakkal: egy lineáris transzformáció akkor és csak akkor injektív, ha szürjektív is.
Lineáris leképezések szorzása De níció. Legyenek U; V és W ugyanazon T test feletti vektorterek, A : V ! W; B : U ! V B szorzata, másképpen kompozíciója: AB : U ! W leképezés, melyre (AB )u = A(Bu).
és
El®ször a másodiknak írt leképezésekre használjuk.
B -t
lineáris leképezések.
A
alkalmazzuk!! Ez ugyanaz a leképezésszorzás, mint els® félévben, csak itt speciális
Teljesül a zártság a szorzásra:
Tétel. Lineáris leképezések szorzata is lineáris leképezés.
7
Bizonyítás.
HF.
A linearitás szabadsági foka Az, hogy egy leképezés lineáris, nagyon er®s megkötés.
Tétel. Legyen b1 ; : : : ; bn bázis az U vektortérben, valamint legyenek c1 ; : : : ; cn tetsz®leges elemek az ugyanazon test feletti V vektortérben. Ekkor pontosan egy olyan A : U ! V lineáris leképezés létezik, melyre
Ab
i
=
c
i = 1; 2; : : : ; n
i
(1)
Tehát a lineáris leképezés egy rögzített bázis elemeinek képével jellemezhet®.
Bizonyítás. Egyértelm¶ség: Legyen u 2 U . Ekkor u = 1 b1 + : : : + b egyértelm¶en. Ha (1) teljesül A-ra, akkor n
n
Au = A(1 b1 + : : : + b n
azaz
n
) =
1 c1 + : : : + c ; n
n
Au egyértelm¶en meghatározott.
Létezés: az a leképezés, ami egy lineáris ...
u = 1 b1 + : : : + b U -beli vektorhoz a 1 c1 + : : : + c V -beli vektort rendeli, n
n
n
n
}
Lineáris leképezés mátrixa Egy lineáris leképezés megadható Ezek a
U -beli báziselemek képével.
V -beli képek felírhatók V -beli báziselemek lineáris kombinációiként.
Ezeket az együtthatók egyértelm¶en meghatározzák. Legyen U egy rögzített bázisa a1 ; : : : ; an , a V egy r®gzített bázisa pedig b1 ; : : : ; bk . Egy A : U ! V lineáris leképezés a1 ; : : : ; an és b1 ; : : : ; bk bázispár szerinti mátrixán azt a k n-es mátrixot értjük, amelyiknek j -ik oszlopában az Aaj vektornak a b1 ; : : : ; bk bázis szerinti koordinátái állnak. Jele [A]a;b .
De níció.
Példa Példa.
Az origó középpontú,
szög¶ forgatás mátrixa a standard bázisban:
Példa.
Az x-tengelyre való vetítés mátrixa:
Példa.
A legfeljebb harmadfokú polinomok terében a deriválás mátrixa:
Lineáris leképezés mátrixa
8 Legyen
Aa1 Aa2 Aa
n
= =
.. . =
Ekkor
A]
[
a;b =
11 b1 + 21 b2 + : : : + 1 b 12 b1 + 22 b2 + : : : + 2 b k
k
k
k
1 b1 + 2 b2 + : : : + b n
0 B B B @
n
kn
k
1
11 12 : : : 1 21 22 : : : 2 C C n
.. .
n
.. .
1 2 ::: k
k
.. .
C A
kn
Vektor mátrixa Ahhoz, hogy a mátrix segítségével könnyedén tudjuk végrehajtani a lineáris leképezéseket, szükséges értelmezni egy vektor mátrixát.
De níció.
alakban. A
Legyen c1 ; : : : ; c bázis a V vektortérben. Minden v 2 V vektor egyértelm¶en írható v = g1 c1 + : : : + g c v vektornak a c1 ; : : : ; c bázis szerinti mátrixán (koordináta vektorán) a r
r
r
v
[ ]c =
0 B B B @
r
1
1
2 C C .. .
C A
r
(oszlop)mátrixot értjük.
Mátrix és leképezés Tétel. Legyen az U bázisa a1 ; : : : ; a a V egy bázisa pedig b1 ; : : : ; b . Legyen A 2 Hom(U; V ) és v 2 U . Ekkor [v ] : [Av ] = [A] n
k
b
a;b
a
A bázis a gyakorlatban általában a standard bázis. Egy korábbi tétel szerint tetsz®leges mátrixhoz pontosan egy olyan lineáris leképezés létezik, aminek ez a mátrixa. A fenti tétel szerint ez éppen a mátrixszal való balrólszorzás. Ahhoz, hogy megállapítsuk egy leképezés linearitását, a következ®t is tehetjük: 1. Felírjuk a "mátrixát" a báziselemek képei alapján. 2. Ellen®rizzük, hogy a mátrixszal való szorzás az eredeti leképezést valósítja-e meg.
Példák Lineáris leképezés-e az x-tengelyre való tükrözés? Az
e1 = (1; 0) képe önmaga, az e2 = (0; 1) képe (0;
.
1)
A képeket beírva egy mátrix oszlopaiba:
T
=
1
0
0
1
9 Ekkor egy tetsz®leges vektor képe:
T (x; y) = (x; y) =?
1
0
0
1
x y
Ez teljesül, azaz ez egy lineáris leképezés, a mátrixa pedig a fenti.
Lineáris leképezések kompozíciója Tétel. Legyen az U bázisa a1 ; : : : ; a , a V egy bázisa b1 ; : : : ; b , W egy bázisa pedig c1 ; : : : ; c . Legyen továbbá A 2 Hom(V; W ); B 2 Hom(U; V ). Ekkor [AB ] = [A] [B ] : n
k
a;c
b;c
r
a;b
Azaz a szorzatleképezés mátrixa a leképezések mátrixainak szorzata.
Bizonyítás.
Egy tetsz®leges
u2U
vektor képe az
AB )(u) = A(B (u)) = A([B ]
(
Azaz az
AB lineáris leképezést az [A]
b;c
B [
a;b
]a;b
u [
AB leképezés mellett: ]a ) = [
A]
b;c
B ([
]a;b
u [
]a ) = ([
A]
b;c
B [
]a;b )
u : [
]a
mátrixxal való szorzás valósítja meg, tehát ez a leképezés mátrixa!
}
Összefoglalás Ezen az el®adáson megismerkedtünk a lineáris leképezés fogalmával. Készen állunk arra, hogy a gyakorlaton eldöntsük egy leképezés linearitását akár a de níció alapján, akár a mátrixa segítségével. A képtér és a magtér egy új eszközt ad a kezünkbe az injektivitás és a szürjektivitás vizsgálatához, amit a dimenziótétel tesz teljessé. Megismerkedtünk az izomor a fogalmával, és megtudtuk, hogy az izomor a igen egyszer¶en, a dimenzió segítségével dönthet® el. Megtanultuk, hogy a lineáris leképezést meghatározzák a báziselemek képei, azaz n-dimenziós értelmezési tartomány esetén egy lineáris leképezést elegend® n független vektor képével megadni. Ennek alapján egyértelm¶en lehet kódolni egy lineáris leképezést egy mátrixban is, ehhez persze rögzíteni kell egy bázist mind az értelmezési tartományban, mind a képhalmazban. Ezek után a lineáris leképezés végrehajtása nagyon könny¶, egyszer¶en balról kell szorozni a mátrixszal a kérdéses vektort, illetve annak koordináta-mátrixát.
Ellen®rz® kérdések 1. Mikor nevezünk egy leképezést lineárisnak, és mikor izomor zmusnak? 2. Mondjon egy geometriai transzformációt, ami lineáris, és egy olyat, ami nem. 3. Mi a lineáris leképezés képtere és magtere? 4. Mondja ki a vektorterek izomor ájának szükséges és elegend® feltételét! 5. Hogy kapjuk egy lineáris leképezés mátrixát? 6. Milyen összefüggés van egy
L lineáris leképezés M
mátrixa, és egy
Megoldások Példa. 1. V (u + v)? =?V (u) + V (v) V (u + v) = V ((u1 ; u2 ) + (v1 ; v2 )) = V (u1 + v1 ; u2 + v2 ) = (u1 + v1 ; 0) V (u) + V (v) = V (u1 ; u2 ) + V (v1 ; v2 ) = (u1 ; 0) + (v1 ; 0) = (u1 + v1 ; 0)
x vektor képe között?
10
Példa. 2. Válasszuk a jobbra egy egységgel való eltolást: T (x1 ; x2 ) = (x1 + 1; x2 ) Legyen u = (1; 2); v = (2; 3). Ekkor T (u + valsznsgivltoz ) = T (3; 5) = (4; 5) és T (u) + T (v ) = (2; 2) + (3; 3) = (5; 5).
nem lineáris a leképezés.
Példa. 3. Igen, lineáris leképezés: D(f + g) = (f + g) és D(f ) + D(g) = f + g , a kett® egyenl®. D(cf ) = (cf ) illetve cD(f ) = cf , a kett® egyenl®. 0
0
0
0
0
A kett® nem egyenl®, azaz
