- Gráfelméleti alapok
- Gráfok izomorfiája és síkbarajzolhatósága
- Gráfok bejárása és gráfalgoritmusok
- Kromatikus szám, klikk, perfekt gráfok
- Gráfparaméterek, párosítások
- Mátrixok és vektorok
- Vektorterek, független és összefüggő vektorok
- Lineáris egyenletrendszerek, mátrixok rangja és inverze
- Determináns, adjungált, kvadratikus alakok
- Sajátérték, sajátvektor, sajátfelbontás
- Lineáris leképezések
- Síkbeli és térbeli leképezések és mátrixaik
- Csoportok, gyűrűk, testek
Lineáris algebra NIK
MÁTRIXOK DETERMINÁNSA, SAJÁTÉRTÉKE ÉS SAJÁTVEKTORA
DEFINÍCIÓ: Ha az egy -es mátrix, akkor determinánsa
ahol p az oszlopindexek permutációi, I(p) pedig ezen permutációk inverziószáma.
Ez egy igazán remek definíció, de egy kis magyarázatot igényel.
Valójában a mátrixok determinánsa sokkal egyszerűbb fogalom.
Arról van szó, hogy a mátrix minden sorából és oszlopából kiválasztunk egy és csak egy elemet, és ezeket az elemeket összeszorozzuk. Ezt az összes lehetséges módon
megtesszük, és a szorzatokat ellátjuk egy előjellel, végül az így kapott előjeles
szorzatokat összeadjuk.
EGY 2x2-ES MÁTRIX DETERMINÁNSA
Nézzünk erre egy példát. Itt van egy mátrix:
aminek a determinánsa
A determináns tehát azt tudja, hogy minden mátrixból csinál
egyetlen számot.
Hamarosan az is kiderül, hogy mindez mire jó, de most lássuk
mi a helyzet egy 3X3-as mátrix determinánsával!
EGY 3x3-AS MÁTRIX DETERMINÁNSA
A 3X3-as mátrixok determinánsának kiszámolására van egy szabály,
ami szarrusz szabály néven ismert.
A szabály lényege, hogy fogjuk a mátrixot
és leírjuk saját maga mögé még egyszer,
majd vesszük a főátlókat és a mellékátlókat.
A főátlók elemeit összeszorozzuk és pozitív előjellel vesszük,
aztán a mellékátlók elemeit is összeszorozzuk, de azokat negatív előjellel vesszük.
Ez a mátrix determinánsa.
A módszer sajnos csak 3x3-as mátrixokra működik és nem túl kellemes.
Sokkal több értelme van megjegyezni az úgynevezett kifejtési tételt,
ami minden nxn-es mátrixra jó és most jön.
Ha az egy -es mátrix, akkor determinánsa
Itt a elemhez tartozó aldetermináns.
Semmi ok az aggodalomra, a gyakorlatban mindez sokkal egyszerűbb.
Nézzünk egy példát!
Van itt ez a 3x3-as mátrix:
Ennek a determinánsát fogjuk kiszámolni, és mondjuk az első sora
szerint fejtjük ki.
Kifejthetjük a második sor szerint is, majd megnézzük azt is,
a végeredmény ugyanaz kell, hogy legyen.
Az első sor elemeit váltakozó előjellel kell venni, ez a bizonyos
de egyszerűbb, ha az úgynevezett sakktábla-szabályt jegyezzük meg.
Az aldeterminánst majd mindjárt megnézzük!
A sakktábla-szabály miatt a második elem mínusszal van.
A harmadik megint plusszal.
Most jönnek az aldeterminánsok, amik úgy keletkeznek,
hogy az adott elem sorát és oszlopát kihúzzuk.
Végül kiszámoljuk a 2X2-es mátrixok determinánsait.
És kész is.
Nézzük meg, hogy mi történik, ha a második sor szerint fejtünk ki!
Ha a második sor szerint fejtünk ki, akkor a sakktábla-szabályban is
a második sort kell nézni.
És kifejthetjük a harmadik sor szerint is,
de ami még ennél is izgalmasabb, hogy oszlop szerint is ki lehet fejteni.
Mondjuk nézzük meg a harmadik oszlop szerint!
A KIFEJTÉSI TÉTEL
A kifejtési tétel lényege az, hogy bármilyen nagy -es mátrix
determinánsának meglehetősen kellemetlen kiszámolását visszavezeti
-es mátrixok determinánsára, amit már könnyen ki tudunk számolni.
Maga a tétel első ránézésre kicsit barátságtalannak tűnik,
de mindjárt nézünk rá egy konkrét példát.
Nézzük a példát!
Van itt ez a 4x4-es mátrix:
Ennek a determinánsát fogjuk kiszámolni, és mondjuk fejtsük ki
a második sora szerint.
Kifejthetnénk az első sor szerint is, majd megnézzük azt is,
a végeredmény így is úgy is ugyanaz lesz.
A második sor elemeit váltakozó előjellel kell venni, ez a bizonyos
de egyszerűbb, ha az úgynevezett sakktábla-szabályt jegyezzük meg.
A sakktábla-szabály miatt a második sor első eleme mínusszal van.
Az aldeterminánst majd mindjárt megnézzük!
A sakktábla-szabály miatt a második sor első eleme mínusszal van.
A második elem plusszal van.
Aztán a harmadik elem ismét mínusszal, mellesleg ő eleve negatív.
A negyedik elem pedig megint plusszal.
Most jöhetnek az aldeterminánsok, amik úgy keletkeznek, hogy mindig
az adott elem sorát és oszlopát kihúzzuk.
És aztán mindegyik aldeterminánst egyenként kiszámoljuk. Ez eltart egy darabig.
Próbáljuk meg érdekesebbé tenni a dolgot azzal, hogy az első sor szerint fejtünk ki.
Megint jön a sakktábla.
Itt jön aztán a következő aldetermináns kiszámolása.
Ezt kifejthetjük mondjuk a harmadik sor szerint,
de ami még ennél is izgalmasabb, hogy oszlop szerint is ki lehet fejteni.
Mondjuk nézzük meg a harmadik oszlop szerint!
És kifejthetjük a harmadik sor szerint is,
de ami még ennél is izgalmasabb, hogy oszlop szerint is ki lehet fejteni.
Mondjuk nézzük meg a harmadik oszlop szerint!
Térjünk rá a következő 3x3-as determinánsra.
Kifejthetjük bármelyik sor szerint, vagy bármelyik oszlop szerint,
de alkalmazhatunk egy kis varázslást is.
Ez bevált, úgyhogy az utolsó megmaradt determinánst is így intézzük el.
Ezzel kész az eredeti 4x4-es mátrix determinánsa!
Kiszámolhattuk volna úgy is, hogy nem a második sor szerint fejtjük ki, hanem mondjuk a negyedik oszlop szerint. Nézzük meg ezt is!
számolunk…
És tényleg így is 0 jön ki!
AZ MÁTRIX DETERMINÁNSA NULLA, HA
VAN CSUPA NULLA SORA
VAN KÉT AZONOS SORA
EGYIK SORA MÁSIK SOR SZÁMSZOROSA
EGYIK SORA MÁS SOROK LINEÁRIS KOMBINÁCIÓJA
MINDEZ SOR HELYETT OSZLOPRA IS ELMONDHATÓ
HA A MÁTRIX ÚGY KELETKEZIK AZ MÁTRIXBÓL, HOGY
EGY SORÁNAK VAGY OSZLOPÁNAK MINDEN ELEMÉT -VAL SZOROZZUK,
MINDEN SORÁNAK MINDEN ELEMÉT -VAL SZOROZZUK,
KÉT SORÁT VAGY OSZLOPÁT FÖLCSERÉLJÜK
EGY SORÁHOZ VAGY OSZLOPÁHOZ MÁS SOROK VAGY OSZLOPOK LINEÁRIS KOMBINÁCIÓJÁT ADJUK
Néhány nagyon izgalmas dolog fog kiderülni a mátrixok determinánsával kapcsolatban.
Vannak olyan speciális mátrixok, amiknek a determinánsát különösebb szenvedés nélkül ki tudjuk számolni. Ilyenek például az úgynevezett alsó vagy felső háromszögmátrixok.
Ezek determinánsa a főátló elemek szorzata.
Az egységmátrix is háromszögmátrix.
Vannak aztán a determinánsoknak különböző érdekes tulajdonságaik.
Nézzük ezeket meg, egy-egy példával.
Végül itt van egy fontos tétel, a determinánsok szorzási tétele, ami szerint
Ha a tételben a mátrix helyére is az mátrixot írjuk
sőt
Ha pedig az mátrixnak létezik inverze, akkor a szorzási tétel alapján
SZINGULÁRIS ÉS REGULÁRIS MÁTRIXOK
Az -es mátrixokat két nagy csoportba sorolhatjuk. Vannak azok a mátrixok melyeknek a determinánsa nulla és vannak azok, amiknek nem.
Ez a kis eltérés valójában hatalmas szakadékot jelent a kétféle csoport között.
AZ MÁTRIX REGULÁRIS
LÉTEZIK INVERZ MÁTRIX
RANG=n
AZ MÁTRIX OSZLOPVEKTORAIBÓL ÁLLÓ
VEKTORRENDSZER LINEÁRISAN FÜGGETLEN
AZ EGYENLETRENDSZERNEK
CSAK EGY MEGOLDÁSA VAN
AZ HOMOGÉN LINEÁRIS
EGYENLETRENDSZERNEK CSAK EGY
MEGOLDÁSA VAN (A TRIVIÁLIS MEGOLDÁS)
AZ MÁTRIX SZINGULÁRIS
NEM LÉTEZIK INVERZ MÁTRIX
RANG<n
AZ MÁTRIX OSZLOPVEKTORAIBÓL ÁLLÓ
VEKTORRENDSZER LINEÁRISAN ÖSSZEFÜGGŐ
AZ EGYENLETRENDSZERNEK
VAGY VÉGTELEN SOK MEGOLDÁSA VAN
VAGY NINCS MEGOLDÁSA
AZ HOMOGÉN LINEÁRIS
EGYENLETRENDSZERNEK VÉGTELEN
SOK MEGOLDÁSA VAN
Itt van például egy mátrix.
Nézzük meg milyen paraméter esetén létezik inverze, milyen paraméterre lesz a determinánsa éppen 0, illetve milyen paraméterre lesz az
egyenletrendszernek végtelen sok megoldása.
Az összes kérdésre egyszerre megkapjuk a választ, ha kiszámoljuk a mátrix determinánsát.
Akkor létezik inverz, ha a mátrix reguláris, vagyis a determinánsa nem nulla:
Akkor lesz a determináns éppen nulla, ha
És akkor lesz az egyenletrendszernek végtelen sok megoldása, ha a mátrix szinguláris, vagyis a determinánsa nulla,
Néhány nagyon vicc es mátrixokkal kapcsolatos fogalommal fogunk megismerkedni.
Az első ilyen fogalom a sarokdetermináns vagy másnéven sarokfőminor.
Van itt egy mátrix:
Ennek a mátrixnak az első sarokfőminora ez a 2-es
A második sarokfőminor a
bal felső -es determináns
A harmadik sarokfőminor a
bal felső -as determináns
Ennek kiszámolása elég unalmas, de a kifejtési tétellel az jön ki, hogy
A negyedik sarokfőminor pedig
az egész mátrix determinánsa
Amit még az előzőnél is unalmasabb kiszámolni, de a kifejtési tétel szerint
A másik nagyon vicces fogalom a mátrixok definitsége lesz.
A definitség megállapításához pedig éppen ezek a főminorok fognak nekünk kelleni, pontosabban az, hogy milyen előjelűek.
Most éppen az első sarokfőminor pozitív, a második szintén pozitív,
a harmadik és negyedik pedig negatív.
Lássuk a definitséget.
Az -es mátrix
pozitív definit,
ha
negatív definit,
ha
pozitív szemidefinit,
ha
negatív szemidefinit,
ha
indefinit,
ha
minden sajátérték:
minden sajátérték:
minden sajátérték:
minden sajátérték:
van és sajátérték
és
-es mátrixoknál a definitség a sarokfőminorok alapján is eldönthető:
mindkét sarokfőminor
pozitív
az első negatív, a
második pozitív
az első pozitív, a
második nulla
az első negatív, a
második nulla
a többi esetben
-es mátrixoknál a definitség már nehezebben dönthető el a sarokfőminorok alapján:
minden sarokfőminor
pozitív
váltakozva - + - +
de mínusszal indul
Ha és nem az előző két esettel van dolgunk,
akkor biztosan indefinit.
Ha akkor nem tudni, ilyenkor csak
a sajátértékek kiszámolásával dönthető el.
Lássunk néhány mátrixot és állapítsuk meg a definitségüket.
Vannak itt ezek a mátrixok, döntsük el, hogy milyen definitek.
A sajátértékeket csak a legvégső esetben számoljuk ki, ha a sarokfőminorokkal szerencsétlenül járunk. Kezdjük az -val.
első sarokfőminor:
második sarokfőminor:
harmadik sarokfőminor:
Az mátrixnak minden sarokfőminora pozitív, tehát pozitív definit.
Nézzük mi van a mátrixszal.
első sarokfőminor:
második sarokfőminor:
harmadik sarokfőminor:
Itt is jön a kifejtési tétel, de nem szeretnék senkit untatni vele, az eredmény -15
A mátrix sarokfőminorai váltakozó előjellel - + - + - … ezért negatív definit.
Jöhet a .
első sarokfőminor:
második sarokfőminor:
harmadik sarokfőminor:
Már megint a kifejtési tétel, de ne húzzuk az időt, az eredmény 1
A sarokfőminorok itt is váltakozó előjelűek, de most + - +
Negatív definit csak olyankor van, ha a váltakozás mínusszal indul, tehát ez most nem lehet negatív definit.
Pozitív definit sem, mert akkor minden sarokfőminor pozitív, tehát marad a két szemidefinit és az indefinit.
A szemidefiniteknél viszont a mátrix determinánsa nulla.
Most ami nem éppen nulla, tehát indefinit.
A mátrix sarokfőminorai alapján nem lehet pozitív vagy negatív definit,
viszont miatt szemidefinit sem lehet ezért indefinit.
Végül lássuk mi van -vel.
első sarokfőminor:
második sarokfőminor:
harmadik sarokfőminor:
Hát ennél rosszabb nem is történhetett volna.
Ha a mátrix determinánsa nulla, akkor vagy valamelyik
szemidefinit vagy indefinit, de csak úgy tudjuk eldönteni,
ha kiszámoljuk a sajátértékeit.
Lássuk tehát a sajátértékeket.
A determinánst a legalsó sor szerint fejtjük ki
Ez az egész nulla, úgyhogy talán hagyjuk is.
Nem tudunk semmit kiemelni, így hát felbontjuk a zárójeleket.
és összevonunk
végül kiemelünk
A sajátértékek:
Kiemelünk 3-at
Mindhárom sajátértékre teljesül, hogy
a mátrix tehát pozitív szemidefinit.
Itt is van három különböző sajátérték, mivel pedig
különböző sajátértékekhez mindig különböző saját-
vektorok tartoznak, van három független sajátvektor.
Így hát is diagonalizálható.
Lássuk a hasonló mátrixokat!
így hát három mátrix van, amelyek ugyanannak a leképezésnek a mátrixai,
csak más-más bázisban felírva, a negyedik mátrix viszont eltérő.
Ha szimmetrikus mátrix és egy vektor -ben, akkor a
kifejezést kvadratikus alaknak nevezzük.
Ezek a kvadratikus alakok nagyon barátságosak, nézzünk is meg egy példát.
Legyen mondjuk
és
A hozzájuk tartozó kvadratikus alak
Számoljuk ki. A szorzásokat kell hozzá elvégezni, kezdjük hátulról.
Aztán még ezeket is összeszorozzuk.
És felbontjuk a zárójeleket.
Íme itt a kvadratikus alak.
Azért hívják kvadratikusnak vagyis négyzetesnek, mert ez mindig egy homogén másodfokú kifejezés. Ez azt jelenti, hogy az x-ek vagy négyzeten vannak benne,
vagy elsőfokúak, de akkor meg vannak szorozva egy másik elsőfokúval és így az is négyzetesnek számít.
Nézzünk meg egy másik kvadratikus alakot is.
és
Most az mátrix -as, így az vektornak is 3 koordinátája van.
Rettenetes lenne viszont megint elvégezni a szorzásokat, főleg, hogy most -as.
Szerencsére van itt egy trükk. Nem is olyan nagy trükk.
A kvadratikus alak valahogy úgy fog kinézni, hogy lesz benne aztán lesz és , meg lesznek vegyes tagok.
A kérdés csak az, hogy hány darab lesz ezekből. A válasz pedig éppen az mátrix.
Hát ez kész.
A dolog fordítva is működik, tehát ha van egy kvadratikus alak, akkor abból fel tudjuk írni a mátrixát.
ez például jó is:
Van itt egy kvadratikus alak:
A feladatunk az, hogy találjunk két vektort,
egy olyan vektort amire
és egy olyan vektort amire
Olyan vektort könnyű találni,
amire a kvadratikus alak pozitív.
Olyat már nehezebb, amire negatív,
de azért ilyen is van.
Aztán van itt egy másik kvadratikus alak is:
A feladatunk az, hogy találjunk két vektort,
egy olyan vektort amire
és egy olyan vektort amire
Olyat most is könnyű találni,
amire a kvadratikus alak pozitív.
próbáljuk ki ezt:
Olyat viszont nehezebb, amire negatív.
Sőt, nemhogy nehezebb, hanem lehetetlen.
Ez a kvadratikus alak tehát
tud pozitív és negatív is lenni.
Ez a kvadratikus alak viszont
csak pozitív tud lenni
A kvadratikus alakoknak ezekkel az érdekes szokásaival fogunk most foglalkozni.
A kvadratikus alak
pozitív definit, ha minden
vektorra
negatív definit, ha minden
vektorra
pozitív szemidefinit, ha minden
vektorra
negatív szemidefinit, ha minden
vektorra
indefinit, ha van olyan és ,
hogy és
A definitség eldöntésében a kvadratikus alak mátrixa segít minket.
ha a kvadratikus alak mátrixa
pozitív definit
ha a kvadratikus alak mátrixa
negatív definit
ha a kvadratikus alak mátrixa
pozitív szemidefinit
ha a kvadratikus alak mátrixa
negatív szemidefinit
ha a kvadratikus alak mátrixa
indefinit
Van itt egy kvadratikus alak, a feladatunk az, hogy döntsük el a definitségét.
Lássuk a mátrixot!
Már csak annyi dolgunk van, hogy eldöntsük, a kvadratikus alak mátrixának definitségét.
Ehhez lássuk a sarokfőminorokat.
első sarokfőminor:
3
második sarokfőminor:
harmadik sarokfőminor:
ez tutira 13
Hát úgy tűnik ez egy pozitív definit mátrix, tehát a kvadratikus alak is pozitív definit.
Nézzünk meg egy másikat is.
Van itt egy másik kvadratikus alak is, döntsük el ennek is a definitségét.
Már csak annyi dolgunk van, hogy eldöntsük, a kvadratikus alak mátrixának definitségét.
Ehhez jönnek a sarokfőminorok.
első sarokfőminor:
-5
második sarokfőminor:
harmadik sarokfőminor:
Hát úgy tűnik ez egy negatív definit mátrix, tehát a kvadratikus alak is negatív definit.
Ez a vasúti hálózat egy gráf.
Megmutatja, hogy mely állomások között vezetnek vasútvonalak.
Ha ellátjuk az éleket súlyokkal…
Akkor az is kiderül, hogy milyen hosszúak az állomások közötti szakaszok.
Vagy hány percig tart a két állomás közötti út.
Vagy éppen mennyi pénzbe kerül a vasútvonal rekosntrukciója.
Ha például a rekonstrukció elvégzése során kezdetben elegendő az, hogy minden állomásról bármelyik másikra el lehessen jutni felújított vasútvonalon…
akkor a gráfnak egy feszítőfáját kapjuk.
Feszítőfából általában több is van.
És egészen biztosan van köztük egy olyan, ahol a költségek minimálisak…
Van itt ez a gráf, és rendeljünk hozzá az éleihez nem negatív valós számokat.
Ezeket a számokat súlyoknak nevezzük.
Képzeljük el, hogy ez a gráf egy úthálózat, vagy mondjuk egy elektromos hálózat, az élek súlyai pedig az áthaladás költsége.
Készítsük el ebben a gráfban a minimális súlyú feszítőfát.
Ez egy olyan hálózat lesz, amin keresztül bármely csúcsból bármely csúcsba el lehet jutni, de a benne szereplő élek súlyainak összege minimális.
Vagyis ez a legolcsóbban működtethető olyan hálózat, ami az összes csúcsot tartalmazza.
A minimális feszítőfát a Kruskal algoritmus segítségével lehet megtalálni.
Maga az algoritmus nagyon egyszerű.
Az első lépés, hogy keressük meg a gráfban a legkisebb súlyú élt.
Ha több azonos súlyú él van, akkor válasszuk ki azt, amelyikhez kedvünk van.
Ezek után belépünk egy ciklusba, ahol minden lépésben az eddig még ki nem választott élekre alkalmazzuk az előző lépést úgy, hogy ne keletkezzen kör.
Ha mégis kör keletkezik, akkor a legutolsó olyan élt, amelynek hozzávétele során a kört kapjuk, töröljük.
Most éppen van még egy 1-es él…
sőt még egy.
Aztán jönnek a 2-es élek.
Hopp, itt keletkezett egy kör.
Az nem jó, akkor ezt a legutóbbi élt töröljük.
A 2-esekbből kifogytunk, jönnek a 3-asok.
Elfogytak a 3-asok is, úgyhogy jöhetnek a 4-esek.
Ajaj, úgy tűnik mégse…
Hát akkor jöhet az 5-ös.
Aztán a 6-os.
Abból úgy tűnik csak ez az egy van.
Aztán itt jönnek a 7-esek.
A 8-asok…
Végül a 9-esek.
És voila, itt a minimális súlyú feszítőfa.
Az algoritmus röviden így írható le:
Legkisebb súlyú él kiválasztása
Kör keletkezik:
az élt töröljük
Nem keletkezik kör:
az élt megtartjuk
Vesszük a megmaradó
ki nem választott éleket
Egy gráfban lehet több minimális feszítőfa is.
Ez most is így van..
Van itt ez a gráf.
És szeretnénk föltérképezni egy adott pontjából kiindulva.
Az egyik módszer a gráf földerítésére a szélességi keresés.
A BFS algoritmus működése nagyon egyszerű.
Elindulunk egy adott pontból, és megkeressük az összes szomszédos pontot.
Ezek az 1 egység távolságra lévő szomszédok és mindegyikre ragasztunk egy 1-es címkét.
Most ezeknek keressük meg az 1 egység távoli szomszédjait.
De csak azokat, akiken még nincsen címke.
Ők a kiinduló ponttól 2 egység távolságra vannak és 2-es címkét kapnak.
Ha valamelyik 2-es szomszédba több él is vezet, akkor csak az egyiket hagyjuk meg.
Mindegy melyiket.
Itt jönnek aztán a kiindulóponttól 3 egység távolságra lévő pontok.
És persze itt is elég egy él.
Az algoritmus folytatódik. Most a 3-as címkéjű pontoknak keressük meg a szomszédjait.
És szép lassan végzünk.
A BFS algoritmus úgy működik, mint egy hullám, ami a gráf élein szétterjed.
Olyan, mint egy különleges alakulat, aminek a tagjai lépésről-lépésre átfésülik a gráfot.
Nyomozni persze nem csak a különleges alakulatok tudnak…
hanem a magányos detektívek is.
Akik idejüket nem kímélve egyedül bejárják a gráf minden zegzugát.
Ez egy egészen más mentalitást igényel, amit mélységi keresésnek nevezünk.
A gráfok bejárásának egyik lehetséges módját már láttuk.
Ez a BFS algoritmus, ami hullámszerűen fésüli át a gráfot.
Olyan, mint egy különleges alakulat, aminek a tagjai lépésről-lépésre teljes szélességben haladnak.
De nyomozni nem csak a különleges alakulatok tudnak, hanem a magányos detektívek is.
Ezt DFS algoritmusnak nevezzük.
A DFS algoritmus a gráf mélységi keresés.
A DFS algoritmus lényege, hogy elindulunk egy úton…
rendíthetetlenül.
És megyünk amíg csak tudunk.
Amikor elakadunk, mert már nem tudunk úgy továbbmenni, hogy olyan pontba jussunk, ahol még nem jártunk…
Akkor visszamegyünk egészen addig, ahonnan még lehet földerítetlen pontok felé haladni.
És megyünk a járatlan utakon tovább.
Amikor újra elakadunk, megint visszamegyünk.
Hopp.
Hát, ez ennyi.
Végül itt még vannak lehetőségek.
Így működik a mélységi bejárás.
A BFS és a DFS algoritmusok végrehajtása során a gráfnak egy-egy feszítőfáját kapjuk.
Ezeket rendkívül frappáns módon BFS és DFS fának nevezzük.
Mindketten az eredeti gráf feszítőfái.
Csak hát az a baj, hogy a BFS és DFS fák megalkotása során nagy szerepe van a véletlennek.
Ha például itt egy másik élt húzunk be…
akkor egy egészen más BFS fát kapunk.
Arról nem is beszélve, hogy az algoritmus elején a gráf bármelyik csúcsából indulhatunk.
Mindezen gubancok ellenére megpróbálhatjuk rekonstruálni az eredeti gráfot annak BSF és DSF fái alapján.
Íme, egy gráf két különböző kezdőpont alapján készített BFS fája:
A BFS és a DFS algoritmusok végrehajtása során a gráfnak egy-egy feszítőfáját kapjuk. Ezeket rendkívül frappáns módon BFS és DFS fának nevezzük. Mindketten az eredeti gráf feszítőfái. Csak hát az a baj, hogy a BFS és DFS fák megalkotása során nagy szerepe van a véletlennek. Ha például itt egy másik élt húzunk be… akkor egy egészen más BFS fát kapunk. Arról nem is beszélve, hogy az algoritmus elején a gráf bármelyik csúcsából indulhatunk. Mindezen gubancok ellenére megpróbálhatjuk rekonstruálni az eredeti gráfot annak BSF és DSF fái alapján. Íme, egy gráf két különböző kezdőpont alapján készített BFS fája: Adjuk meg az eredeti gráfot. Lássuk, hogyan tudnánk hasznosítani a BFS fákat. Készítünk egy ilyen kis szomszédsági táblázatot. Aztán pedig kezdjük is az első BFS fával. Eddig jó. Vannak még kétségek, de ezeket reméljük a másik BFS fa hamarosan eloszlatja. Az, hogy a C és D csúcsok között vezet él, immár biztosabb, mint a halál. Hát, ez kész. Már csak föl kell rajzolnunk. Csodás. Egy gráfban minden csúcs fokszáma páros, és két különböző kezdőpont alapján készített BFS fája: Hát, úgy tűnik eddig jutottunk. Nem baj, azért kezdjünk el rajzolgatni. Ezek itt a kérdőjeles élek. Viszont tudjuk még, hogy a gráf minden csúcsának a fokszáma páros. Ha mindkét élt elhagyjuk, az nem jó, mert akkor lesz páratlan fokszámú csúcs. És, ha mindkét élt behúzzuk, az se jó, mert akkor keletkezik harmadfokú csúcs. Ha csak az egyik élt húzzuk be… akkor így lesz egy elsőfokú csúcs. Így viszont minden csúcs páros fokszámú.
A gráfok csúcsainak bejárására van egy nagyon speciális módszer, amit Hamilton körnek hívunk.
A Hamilton kör lényege az, hogy egy olyan körön haladunk végig a gráfban, amely a gráf összes pontját pontosan egyszer tartalmazza.
Hamilton kör nem minden gráfban van.
Ebben a gráfban épp van.
Ha a gráfból ezt az élt elhagyjuk…
akkor a megmaradó gráfban már lehet, hogy nincs Hamilton kör.
De az is lehet, hogy van.
Olyan kritérium, ami egyértelműen meg tudja mondani, hogy egy gráfban van-e Hamilton kör,nem létezik.
Árulkodó jelek viszont vannak.
Ebben a gráfban egészen biztosan nincs Hamilton kör.
Ha a gráfban van legalább egy elsőfokú csúcs, akkor a Hamilton körnek annyi.
De Hamilton út még lehet.
A Hamilton út egy olyan út, amely a gráf minden csúcsát tartalmazza.
Lássuk, van-e ebben a gráfban Hamilton kör vagy Hamilton út.
Hamilton út biztosan van.
Viszont Hamilton kör…
Hát, az úgy ránézésre nincsen.
De ez a különbség a matematikusok és a csodadoktorok között.
Sajnos a ránézés itt kevés.
Van viszont egy remek kis tétel, ami segít.
Ehhez a tételhez azt kell megértenünk, hogy ha egy gráfnak bizonyos pontjait elhagyjuk…
akkor a gráf több komponensre esik szét.
Ebben a gráfban például most két csúcsot hagytunk el és három komponensre esett szét.
A Hamilton kör létezésének szükséges feltétele, hogy ha egy gráfból k darab csúcsot kitörlünk (a belőle kiinduló élekkel együtt), akkor a megmaradó gráfnak legfeljebb k darab komponense van.
Ez a feltétel most nem teljesül, mert 2 darab csúcsot töröltünk, a gráf mégis 3 komponensre esett szét.
Sajnos ehhez a tételhez azért kis szerencse is kell.
Ha például ezeket a csúcsokat töröljük ki…
Akkor 2 csúcsot töröltünk és a gráf 2 tartományra esik szét.
Vagyis teljesíti a feltételt, pedig nincs Hamilton köre.
Most lássuk, mit is kezdhetnénk az eredeti gráfunkkal.
Olyan csúcsokat érdemes elhagyni, amitől a gráf várhatóan tényleg szétesik.
Terrorista hajlamúak előnyben…
4 csúcs elhagyásával a gráf 5 komponensre esett szét.
Vagyis nem teljesül a szükséges feltétel, a gráfban biztosan nincs Hamilton kör.
Hamilton kör szükséges feltétele:
Ha egy gráfból k darab csúcsot kitörlünk (a belőle kiinduló élekkel együtt), akkor a megmaradó gráfnak legfeljebb k darab komponense lehet.
A Hamilton út szükséges feltétele hasonló:
Egy G gráfban akkor lehet Hamilton út, ha a gráfból k darab csúcsot kitörlünk (a belőle kiinduló élekkel együtt), akkor a megmaradó gráfnak legfeljebb k+1 darab komponense van.
Ennél a gráfnál például teljesül a feltétel.
1 csúcs elhagyásával a gráf 1+1=2 komponensre esett szét.
2 csúcs elhagyásával pedig 3 komponensre.
De minden hiába.
Vagyis a feltétel csak szükséges, de nem elégséges.
Attól, hogy teljesül, még nem biztos, hogy van Hamilton út.
És ezúttal például biztosan nincs.
A három darab első fokú csúcs miatt lehetetlen.
Vannak aztán elégséges feltételei is a Hamilton kör létezésének.
Ha egy gráfban minden csúcs foka elég nagy, akkor biztosan lesz benne Hamilton kör.
Nézzük, milyen elégséges feltételek vannak a Hamilton kör létezésére.
Az egyik ilyen feltétel a Dirac-tétel.
Ez azt mondja ki, hogy ha egy G egyszerű, n≥3 csúcsú gráfban minden csúcs foka legalább n/2, akkor a gráfban van Hamilton kör.
Vagyis ebben a gráfban például egészen biztosan van Hamilton kör.
Sőt, ebben is.
Dirac-tétel:
Ha egy G egyszerű, n ≥ 3 csúcsú gráfban minden csúcs foka legalább n/2, akkor a gráfban van Hamilton kör.
Egy másik elégséges feltétel az Ore-tétel.
Az Ore-tétel azt mondja, hogy ha egy G egyszerű, n≥3 csúcsú gráfban bármely Vi és Vj nem szomszédos csúcsra d(Vi)+d(Vj) ≥n teljesül, akkor a gráfban van Hamilton kör.
Remek. Most pedig lássunk néhány gráfot.
Nézzük, milyen elégséges feltételek vannak a Hamilton kör létezésére.
Az egyik ilyen feltétel a Dirac-tétel.
Ez azt mondja ki, hogy ha egy G egyszerű, n≥3 csúcsú gráfban minden csúcs foka legalább n/2, akkor a gráfban van Hamilton kör.
Vagyis ebben a gráfban például egészen biztosan van Hamilton kör, mert minden csúcs foka legalább 8/2.
Sőt, ebben is.
És ebben is.
De attól, hogy épp nem teljesül a feltétel…
még simán lehet, hogy van Hamilton kör.
A Dirac tétel egy elégséges, de nem szükséges feltétel.
Viszont attól, hogy egy gráfban
Dirac-tétel:
Ha egy G egyszerű, n ≥ 3 csúcsú gráfban minden csúcs foka legalább n/2, akkor a gráfban van Hamilton kör.
Egy másik elégséges feltétel az Ore-tétel.
Az Ore-tétel azt mondja, hogy ha egy G egyszerű, n≥3 csúcsú gráfban bármely Vi és Vj nem szomszédos csúcsra d(Vi)+d(Vj) ≥n teljesül, akkor a gráfban van Hamilton kör.
Nézzük, mire használhatnánk ezeket a tételeket, jóra vagy rosszra...
Bizonyítsuk be, hogy minden 4-nél nagyobb n számra van olyan n csúcsú G gráf, hogy G-ben és a komplementerében is van Hamilton kör.
Egy gráf és a komplementere együttesen kiadja a teljes gráfot.
Ebből fogunk kiindulni.
Olyan n pontú gráfot nagyon könnyű mondani, amiben van Hamilton kör.
A komplementerében pedig a Dirac tétel miatt biztosan van.
Hiszen minden csúcs foka n-3, vagyis legalább n/2.
Persze, ha n legalább 5.
Egy 100 csúcsú egyszerű gráfban két nem szomszédos csúcs foka 49, az összes többi csúcs foka legalább 50. Bizonyítsuk be, hogy van a gráfban Hamilton út.
Ha minden csúcs foka legalább 50 lenne…
Az jó lenne, mert akkor a Dirac tétel miatt Hamilton kör is lenne a gráfban.
Legyen a két 49 fokú csúcs Vi és Vj.
Vegyünk hozzá a gráfhoz plusz egy élt Vi és Vj között.
Így most minden csúcs foka 50.
A Dirac tétel miatt pedig van Hamilton kör.
A plusz élt elhagyva, a Hamilton körnek legfeljebb egy élét hagyjuk el.
Tehát van Hamilton út.
Itt az ideje emelni a tétet. Lássuk mit mondhatnánk arról a 101 pontú gráfról, amiben minden csúcs foka legalább 50. Van-e a gráfban Hamilton út?
Most egy másik trükköt fogunk használni.
Ezt a trükköt érdemes megjegyezni.
Mindig adódhatnak az életünkben olyan krízishelyzetek, amikor ez a trükk jelenti majd a megoldást.
A trükk ezúttal az lesz, hogy vegyünk hozzá a gráfhoz egy 102-edik csúcsot.
Hívjuk mondjuk Bobnak.
És kössük össze a gráf minden csúcsával.
Az így keletkező gráfban minden csúcs foka legalább 51.
Mivel minden csúcs legalább 102/2 fokú, teljesül a Dirac tétel, tehát a gráfban van Hamilton kör.
Ha Bobot elhagyjuk, a Hamilton körből kiesik egy csúcs és két él.
Ami így marad, egy olyan Hamilton út, ami az eredeti gráf élein és összes csúcsán halad.
És most pedig itt jön néhány gráf. Derítsük ki, hogy van-e bennük Hamilton kör. Ha nincs, akkor minimum hány újabb élt kell hozzávennünk ahhoz, hogy legyen?
Ezek a pontok eléggé gyanúsan viselkednek.
Nélkülük a gráf három részre esik szét.
A gráf nem teljesíti a szükséges feltételt, így aztán nincs benne Hamilton kör.
Húzzunk be egy új élt.
És aztán nézegessük egy kicsit a gráfot…
Így már van.
Egy új élt kell tehát hozzávenni az eredeti gráfhoz, hogy legyen benne Hamilton kör.
Nézzük, mi van ezzel:
Megint vannak gyanúsan viselkedő pontok.
Két pont elhagyásával a gráf három komponensre esett szét, így nincs benne Hamilton kör.
Nézzük, hány élt kell behúzni ahhoz, hogy legyen Hamilton kör.
Egyet…
Minimum hány élt kell behúznunk ebben a gráfban, hogy legyen benne Hamilton kör?
A gráf pillanatnyilag nem rendelkezik Hamilton körrel.
Nézzük, így már van-e…
Hát, ezzel a résszel még vannak gondok.
Mindez tudományosan is kimutatható.
Két pontot elhagyva a gráf négy komponensre esik szét, úgyhogy igencsak nem teljesül a szükséges feltétel.
Kénytelenek vagyunk behúzni még egy élt.
Valahol itt belül érdemes.
Na, most már csak jó lesz…
És most sem…
Persze az is lehet, hogy nem voltunk elég okosak…
Nézzük meg, mi van, ha ezt az élt…
inkább ide húzzuk be.
A megoldás tehát:
Sajnos nem voltunk elég okosak és 2 élt kell hozzávenni a gráfhoz.
Végül itt jön egy remek kis történet arról a 100 csúcsú egyszerű gráfról, amiben két szomszédos csúcs foka 49, az összes többi csúcs foka pedig legalább 50. Bizonyítsuk be, hogy van a gráfban Hamilton út.
Ha valahonnan ismerősnek tűnik a történet, az nem csak a véletlen műve.
Korábban már megoldottuk úgy, hogy Vi és Vj nem szomszédos csúcsok.
Most pedig megoldjuk úgy, hogy szomszédosak.
Így nehezebb…
Ha minden csúcs foka legalább 50 lenne, akkor a Dirac tétel miatt lenne Hamilton kör a gráfban.
Ennek érdekében vegyünk hozzá a gráfhoz egy Vi-ből és egy Vj-ből induló élt.
A Vi-ből induló extra él vezessen egy olyan X csúcsba, ami Vi-nek nem szomszédja, de Vj-nek igen.
A Vj-ből induló extra él pedig egy olyan Y csúcsba, ami eredetileg Vj-nek nem szomszédja, de Vi-nek igen.
Az extra élek behúzásával minden csúcs foka legalább 50, vagyis a Dirac tétel miatt van a gráfban Hamilton kör.
Hogyha a Hamilton kör legfeljebb egy extra élt tartalmaz, akkor nincsen semmi baj.
A két extra él elhagyásával ugyanis a Hamilton körnek legfeljebb egy élét hagyjuk el.
Tehát van Hamilton út.
De ha a Hamilton kör mindkét extra élt tartalmazza,
akkor nagy baj van.
A két extra él elhagyásával ugyanis a Hamilton kör két különálló darabra esik szét.
Az egyik darabja Vi és Vj között vezet, a másik darabja pedig X és Y között.
Ha ehhez a két különálló darabhoz hozzá vesszük a Vj-ből X-be vezető élt, akkor Hamilton utat kapunk.
De sajnos van itt még egy kis gubanc.
Előfordulhat, hogy nincsen a gráfban olyan X csúcs, ami Vi-nek nem szomszédja, de Vj-nek igen.
Ez úgy lehetséges, ha minden X csúcs vagy Vi-nek és Vj-nek egyszerre szomszédja… vagy pedig egyiknek sem.
És ha nincs ilyen X csúcs, akkor nem működik az a bizonyítás, amit az előbb csináltunk.
Ebben az esetben ki kell találni valami mást.
Válasszunk egy olyan X csúcsot, ami nem szomszédja sem Vi-nek, sem Vj-enk…
…és kössük össze velük.
Így most minden csúcs fokszáma legalább 50, vagyis a Dirac tétel miatt van Hamilton kör.
Ha a Hamilton kör legfeljebb egy extra élt tartalmaz, akkor az eredeti gráfban van Hamilton út.
De az is lehet, hogy mindkét extra él benne van a Hamilton körben.
Ebben az esetben viszont a Vi és Vj közti él biztosan nem.
Ez később még fontos lesz.
Az extra élek elhagyásával sajnos X kiesik a Hamilton körből.
És így a Hamilton útból is.
Úgy tudjuk visszaszerezni az elveszett X-et, hogy választunk egy tetszőleges Y csúcsot, ami X-nek szomszédja…
És itt megszakítjuk a Hamilton utat.
A Hamilton út Y-ba vezető egyik élét töröljük és helyette hozzávesszük az X-be vezető élt.
Végül a Vi és Vj közti élt bevesszük a Hamilton útba, és ezzel kész is.
Itt az ideje, hogy egy kicsit precízebben is elkezdjünk foglalkozni a gráfokkal. A G gráf csúcsainak halmazát V(G)-vel jelöljük. Itt a V az angol vertex=csúcs szóra utal. A G gráf éleinek halmazát E(G)-vel jelölünk. Itt E az angol edge=él. Teljesen tudományosan megfogalmazva a G gráf egy (V(G), E(G)) rendezett pár, ahol V(G) egy nem üres halmaz, E(G) pedig a V(G)-ből képezhető párok egy halmaza. Ha a gráf egyik csúcsából elindulunk, és teszünk egy sétát a gráfon… akkor egy élsorozatot kapunk. Azokat az élsorozatokat, amelyek a gráf semelyik pontján nem haladnak át többször útnak nevezzük. Ez itt nem egy út, mert V10-en kétszer is áthaladunk. Ez viszont igen. Ha egy élsorozat ugyanabból a csúcsból indul, mint ahova érkezik, akkor körsétának nevezzük. Ez itt például egy körséta. Egy gráfban körnek nevezünk egy olyan utat, amely csupa különböző csúcsokon és éleken haladva visszavezet a kiinduló csúcsba. Íme, itt egy kör. Egy gráf összefüggő, ha bármely csúcsából bármelyikbe vezet út. Ha ez nincs így, akkor a gráf több különböző komponensből áll. Idáig ez nem túl bonyolult. Ennyire még Piroska néni, a jósnő is járatos a gráfokban. De az izgalmak csak most jönnek. Egy csúcs fokszáma azt mondja meg, hogy hány él vezet az adott csúcsba. Ennek a csúcsnak itt, a fokszáma például három. Ennek pedig kettő. És ennek itt egy. Egy tetszőleges V csúcs fokszámát d(V)-vel jelöljük. Ha egy gráfban megszámoljuk a csúcsok fokszámait, akkor minden élt pontosan kétszer számolunk meg. Egyszer az egyik csúcsnál… aztán a másiknál. Vagyis minden gráfban a csúcsok fokszámainak összege az élek számának a kétszerese. Egy gráfot egyszerű gráfnak nevezünk, ha nincsen benne hurokél… és nincsen benne párhuzamos él. HUROKÉL PÁRHUZAMOS ÉL A csillagképek mindig egyszerű gráfok. Mert nincs olyan őrült csillagász, aki előállna azzal, hogy ugyanazt a két csillagot kétszer is összekösse. Vagy éppen egyetlen csillagot sajátmagával. A gráfelméletben viszont nem ritkák az olyan gráfok, ahol van hurokél, vagy párhuzamos él. Annyira nem, hogy a világ legelső gráfjában is voltak párhuzamos élek. Ezt a híres gráfot Leonhard Euler alkotta meg a königsbergi hidak problémájának megfejtésekor. A Königsberg nevű városka lakóit az a kérdés nyugtalanította, hogy körbe tudnak-e sétálni a város hídjain úgy, hogy minden hídon pontosan egyszer haladnak át és a séta végén visszaérnek a kiindulópontra. A kérdés úgy fogalmazható át, hogy létezik-e ebben a gráfban olyan körséta, amely minden élen pontosan egyszer halad át. Az ilyen körsétákat Euler-körnek (helyesen Euler-körsétának) nevezik. Euler bebizonyította, hogy egy gráfban pontosan akkor létezik Euler-körséta, ha minden csúcs fokszáma páros. Így aztán a königsbergieket el kellett keserítenie. A gráfokkal való ismerkedésünket néhány speciális gráffal fogjuk folytatni.
Ha egy gráfban nincs kör, de maga a gráf összefüggő, akkor fának nevezzük.
A fa egy olyan gráf, ahol a lehető legkevesebb él felhasználásával kötjük össze a csúcsokat.
És bármely csúcsból bármely másik csúcsba pontosan egy út vezet.
A másik véglet, ha bármely csúcsból bármelyik másik csúcsba közvetlen él is vezet.
Ezeket a gráfokat teljes gráfnak nevezzük.
Ez egy négypontú teljes gráf:
Ez pedig egy ötpontú teljes gráf:
FA
TELJES GRÁF
Egy n csúcsból álló fának mindig n-1 darab éle van.
Az n pontú teljes gráf éleinek száma:
Ezek az információk később még jól jöhetnek…
Például olyan esetekben, amikor egyik ismerősünk előáll azzal, hogy tegnap látott egy olyan 8 pontú összefüggő gráfot, aminek 6 darab éle van.
Biztosak lehetünk benne, hogy az illető hazudik.
Azért hazudik, mert a 8 pontból álló összefüggő gráfok közül a legkevesebb éle a fának van.
Egy 8 pontból álló fának pedig 8-1=7 éle van.
Íme, itt van néhány gráf.
Lássuk, melyik milyen...
Körmentes
Összefüggő
Fa
Mivel minden fa összefüggő és körmentes, ezért a helyzet
valójában valahogy így néz ki:
Az összefüggő gráfok közül a legösszefüggőbbek a teljes gráfok.
Íme, itt a teljes kollekció:
A nem összefüggő körmentes gráfok neve erdő.
Ez itt például egy erdő:
Végül itt jön még egy vicces dolog.
Nézzük meg ezt a gráfot.
Ezt a gráfot páros gráfnak nevezzük.
Miért hívjuk így?
Ezért.
A gráf csúcsai két csoportra oszthatók.
Az egyik csoportban is olyan csúcsok vannak, melyek között nem vezet él…
és a másikban is.
A legegyszerűbb páros gráf ez:
Aztán itt jön egy bonyolultabb:
De azért még ezt is túl lehet élni…
Ez még érdekesebb:
Így persze már nehezebb róla megállapítani, hogy ez egy páros gráf…
Csomagoljuk szépen vissza.
Ha minden csúcs az egyik oldalon össze van kötve minden csúccsal a másik oldalon…
Akkor ez egy K2,2 teljes páros gráf.
A dolog még tovább fokozható:
Őrület!
Most pedig jó lenne tudni, hogy ezek a gráfok tulajdonképpen mire jók a valóságban.
Mégis mi értelme van gráfokkal foglalkozni?
Lássunk erre néhány példát.
Ez a vasúti hálózat például egy gráf.
Megmutatja, hogy mely állomások között vezetnek vasútvonalak.
Ha ellátjuk az éleket súlyokkal…
Akkor az is kiderül, hogy milyen hosszúak az állomások közötti szakaszok.
Vagy hány percig tart a két állomás közötti út.
Vagy éppen mennyi pénzbe kerül a vasútvonal rekosntrukciója.
Ha például a rekonstrukció elvégzése során kezdetben elegendő az, hogy minden állomásról bármelyik másikra el lehessen jutni felújított vasútvonalon…
akkor a gráfnak egy feszítőfáját kapjuk.
Feszítőfából általában több is van.
És egészen biztosan van köztük egy olyan, ahol a költségek minimálisak…
Itt van ez a 6 csúcsú egyszerű gráf.
Biztosra mentünk, és minden csúcsot mindegyikkel összekötöttük.
Vagyis ez itt egy K6.
Egy gráf komplementere azt a gráfot jelenti, aminek csúcsai ugyanazok, mint az eredeti gráfnak, és két csúcs pontosan akkor szomszédos benne, ha az eredeti gráfban nem.
Ebben a gráfban mindenki mindenkivel szomszédos…
így aztán a komplementer ez.
Ha néhány csúcs van csak összekötve…
akkor a komplementerben is néhány csúcs lesz összekötve.
Azok, akik eredetileg nem.
Nem túl meglepő, hogy egy gráf és komplementere együtt kiadja a teljes gráfot.
Hiszen egy él vagy az eredeti gráfban van behúzva…
vagy, ha ott nincs, akkor a komplementerben.
Most pedig nézzünk egy nagyon hasznos dolgot.
Van ez a gráf, és válasszuk ki néhány csúcsát.
Mondjuk, válasszuk ki ezeket itt.
Ezek a csúcsok ötödfokú csúcsok.
De csak hárman vannak, ezért csúcsonként csak 2 fokszámnyi élt tudnak egymás közt elpasszolni…
a maradék többi él kénytelen valamilyen más csúcsba vezetni.
Itt vannak aztán ezek a csúcsok is.
Egymás közt itt sem túl sok él megy.
A maradék többi él itt is kénytelen másfelé szerencsét próbálni.
És éppen ugyanannyi elvándorló él van az egyik halmaz csúcsainál, mint a másiknál.
Így aztán nagy az öröm az egymásra találásnál.
Most nézzük, mi a helyzet ezzel az egyszerű gráffal.
Annyit tudunk róla, hogy van 3 ötödfokú csúcsa és 3 elsőfokú csúcsa.
Lássuk a gráf éleit.
Egyáltalán nem biztos, hogy itt mindenki mindenkivel össze van kötve.
De most képzeljük azt egy pillanatra, hogy igen.
A csúcsok fokszáma 5, így aztán még van jónéhány él, ami kivezet az A-n kívülre.
Amíg ezeket az éleket a többi csúcs képes fogadni, nincs is semmi baj.
De most úgy tűnik, hogy nagy baj van.
Sajnos a B halmaz legfeljebb 3 élt tud fogadni.
És az A-ból legalább 9 él indul.
Ha nincs mindenki mindenkivel összekötve, akkor még több is.
De a 9 él az biztos.
Így aztán nem lesz egyezség. Ilyen gráf nem létezhet.
Ha persze G nem egyszerű gráf, úgy könnyű…
De a megadott tulajdonságokkal rendelkező egyszerű gráf…
nem létezik.
Egy 24 csúcsú G egyszerű gráfban 12 csúcs foka 5, a másik 12 csúcs foka pedig 16. Összefüggő-e a G gráf komplementere?
A 12 csúcs, ahol mindenkinek a fokszáma 16 meglehetősen brutális.
Ha minden csúcs minden másikkal össze van kötve…
már az is elképesztően sok él.
És akkor itt minden csúcs fokszáma még csak 11.
Úgy jön ki a 16, ha van még csúcsonként plusz 5 él.
Most nézzük, a B halmaz mennyit képes közülük fogadni.
Pont ennyit.
Vagyis az A halmazból csúcsonként legalább 5 él kell, hogy kivezessen, a B pedig csúcsonként maximum ennyit képes fogadni.
Ez azt jelenti, hogy pontosan tudjuk, hogyan néz ki a gráf.
Van benne egy K12 és annak minden csúcsa össze van kötve a B halmaz 5 különböző csúcsával.
Most nézzük, hogy mi lesz ennek a gráfnak a komplementere.
Itt senki senkivel nem lesz összekötve, az egyszer biztos.
Aztán a csúcsonkénti 5 él helyett a többi csúcsba megy 7 él.
B-ben meg jó sok él be lesz húzva, de a lényeg…
ezek az élek.
Ez garantálja, hogy B-ben bármely két csúcs között vezet út.
Mivel pedig A-nak bármely csúcsa össze van kötve legalább egy B-beli csúccsal, így bármely két A-beli csúcs között is vezet út.
Így aztán a G gráf komplementere összefüggő.
Egy összefüggő egyszerű gráfnak 40 csúcsa és 42 éle van. Bizonyítsuk be, hogy van a gráfban 3 különböző kör. Két kör akkor különböző, ha van legalább egy olyan él, amelyiket az egyik kör tartalmazza, de a másik nem.
Nem fogunk itt bajlódni 40 darab csúccsal.
Azt kell megérteni, hogy lehetne 50 csúcsú és 52 élű is a gráf, vagy 1000 csúcsú és 1002 élű, a lényeg itt nem ez.
A lényeg itt az, hogy egy n csúcsú összefüggő gráfnak minimum n-1 darab éle van.
Ebben az esetben a gráf körmentes, hiszen fa.
Ha hozzáveszünk az n-1 darab élhez még egyet, akkor valahol kör keletkezik.
Ha még egy élt hozzáveszünk, akkor még egy kör keletkezik, ami biztosan különbözik az előző körtől, hiszen abban nem szerepelhetett az az él, amit most vettünk hozzá a gráfhoz.
És még egy él hozzávételével még egy kör keletkezik.
Az állítást bizonyítottuk, ráadásul nem csak a 40 csúcs 42 él esetre, hanem általánosan.
Még azon is el lehet filozofálni, hogy összesen hány kör keletkezik.
Van úgy, hogy csak 3…
Aztán lehet benne 4 kör is.
És maximum 6.
Egy összefüggő egyszerű gráfnak 1000 csúcsa és 1000 éle van. Bizonyítsuk be, hogy van a gráfban 3 különböző feszítőfa. Két feszítőfa akkor különböző, ha van legalább egy olyan él, amelyiket az egyik feszítőfa tartalmazza, de a másik nem.
Vegyük a gráfnak egy feszítőfáját. A feszítőfának 999 éle van.
Ha ezek után hozzávesszük az ezredik élt, akkor keletkezik egy kör.
Nem tudjuk, hogy a kör hány élt tartalmaz…
De három különböző élt egészen biztosan.
Bármelyiket elhagyva a gráfnak egy-egy különböző feszítőfáját kapjuk.
Van itt ez a három gráf…
ami valójában csak egy.
Ez a három gráf ugyanannak a gráfnak a három különböző vizualizációja.
A három gráf egymással
Van itt ez a három gráf…
ami valójában csak egy.
Ez a három gráf ugyanannak a gráfnak a három különböző vizualizációja.
A három gráf egymással izomorf.
A G(V(G), E(G)) gráf izomorf a G’(V(G’), E(G’)) gráffal, ha van egy bijekció a V(G) és V(G’) között…
amire teljesül, hogy G-ben pontosan akkor szomszédos két pont, ha G’-ben a nekik megfelelő pontok szomszédosak…
és szomszédos pontpárok esetén ugyanannyi él fut közöttük.
Szemléletesen két gráf akkor izomorf, ha mindkettőt ugyanúgy le tudjuk rajzolni.
De sajnos az izomorfia eldöntése sokszor igencsak nehéz feladat tud lenni.
Erről hamarosan személyesen is meggyőződhetünk.
Ha egy lépést hátrább lépünk…
És a gráfban csak az élek hálózatára koncentrálunk…
Akkor eljutunk egy másik fogalomhoz, amit topológiai izomorfiának neveznek.
Ez a két gráf topológiailag izomorf.
Sőt ez a három is.
Egy gráfban topologikusan ekvivalens átalakításnak nevezzük azt, ha egy élt egy másodfokú csúcs beiktatásával két élre bontunk…
vagy ha egy 2 fokú csúcsra illeszkedő éleket egybeolvasztunk, és a csúcsot elhagyjuk.
Két gráf akkor topologikusan izomorf, ha topologikusan ekvivalens lépések egymás utáni alkalmazásával el tudjuk érni, hogy a két gráf izomorf legyen.
Most pedig elérkezett az idő, hogy lássunk néhány trükköt…
aminek a segítségével el tudjuk dönteni, hogy két gráf izomorf-e vagy sem.
Van itt ez a néhány gráf.
És próbáljuk meg kitalálni, hogy melyek izomorfak egymással.
Titkos recept az izomorfia vizsgálatához.
A legegyszerűbb dolog, amit érdemes megnézni, a csúcsok fokszáma.
A másodfokú csúcsokból kicsit sok van, de nézzük a harmadfokú és negyedfokú csúcsokat.
Negyedfokú csúcs csak G4-ben van, így aztán ez nem izomorf semelyik másik gráffal sem.
Aztán itt van ez a G6, amiben két harmadfokú csúcs is van, a többiben csak egy.
Nyilvánvalóan ő sem lehet izomorf semelyik másikkal.
Nézzük, mit kezdhetnénk a megmaradt gráfokkal.
Számoljuk meg, a harmadfokú csúcsra milyen hosszú utak csatlakoznak.
2) Utak hossza
Egyetlen él hosszúságú út G1-en és G3-on van.
A megmaradt gráfokon pedig két darab 2 hosszú út indul.
Egy kis nézelődés után látni, hogy ezek izomorfak.
És ezek is.
Most pedig nézzük, hogy milyen fortélyok vannak még az izomorfia eldöntésénél.
Derítsük ki, hogy melyek izomorfak ezek közül a gráfok közül:
Kezdjük a fokszámokkal.
Mindenhol harmadfokú csúcsok vannak, kivéve a G3-ban.
Úgyhogy a G3-nak annyi…
Most nézzük, van-e kör.
3) Van-e kör?
Hát igen, csak az van.
Úgyhogy nézzük meg a körök hosszát.
4) Milyen hosszúak a körök?
Itt a G1-ben van 3 hosszú kör.
De G2-ben és G4-ben nincs, ott minden kör legalább 4 hosszú.
Vagyis G1 nem lehet izomorf sem G2-vel, sem G4-gyel.
A dolog most kezd érdekes lenni…
Egyre inkább valószínű, hogy ezek a gráfok izomorfak.
De valahogyan be kell ezt bizonyítani.
A két gráf akkor izomorf, ha tudunk létesíteni a csúcsaik között bijekciót.
Hát, próbáljuk meg.
Induljunk ki egy tetszőleges csúcsból a G2 gráfban.
És vegyük, mondjuk ezt a 4 hosszú kört.
Szép, egészséges harmadfokú csúcsok vannak rajta.
Éppen úgy, mint ezen.
Kezdjük el megalkotni a bijekciót.
Még két csúcs hiányzik.
Az egyik A6 harmadik szomszédja, aki nincs rajta a körön.
Neki B1 harmadik szomszédja felel meg.
Végül az utolsó csúcs kizárásos alapon…
Egyetlen dolgunk van még: a szomszédokat tesztelni.
És a többi csúcs is stimmelni fog.
Vagyis ezek a gráfok izomorfak.
Amit immár vizuálisan is igazoltunk.
Végül itt jön egy igazi rémtörténet.
Nézzük, ezek a gráfok izomorfak-e.
A fokszámok vizsgálatával nem jutunk túl messzire: sajna minden gráf minden csúcsa negyedfokú.
Ide komolyabb eszközök kellenek…
Ugorjunk egyből a 4-es pontra.
Figyeljük a 3 hosszúságú köröket.
G1-ben találni olyan szomszédos pontokat, akikhez három különböző kör is tartozik.
G2-ről és G3-ról ez nem mondható el.
Próbáljuk meg valahogyan földeríteni a 3 hosszú köröket a gráfokban.
Nézzük meg, hogy egy adott él hány különböző 3 hosszú körben szerepel.
5) Élek vizsgálata
Színekkel fogjuk jelölni, hogy egy adott él hány darab 3 hosszú körben vesz részt.
G1-ben hat darab 3 hosszú kör van.
Most nézzük, mi a helyzet G2-vel.
És G3-mal.
Úgy tűnik G2 és G3 izomorf.
Jó lenne mondjuk találni köztük egy bijekciót.
Végül teszteljük, hogy minden rendben van-e a szomszédokkal…
Aki még nem unja, nézze meg a többit is.
Réges-régen, egy messzi-messzi galaxisban létezett egy bolygó, amin különös lények éltek. Egy gátrendszert építettek a bolygó felszínére, a gátak végein tornyokkal. Ezekben a tornyokban laktak a fura lények, minden toronyban egy. A gátak medencékre osztották a bolygó felszínét. Mindegyik medence teljesen száraz volt, kivéve egyet, amiben viszont az egész bolygó felszínére elegendő víz volt. A fura lények egyszer elhatározták, hogy elárasztják bolygójukat vízzel. A terv az volt, hogy felrobbantják a medencéket elválasztó gátakat. És így medencéről medencére haladva szétterítik a vizet. A lények szerettek átjárni egymáshoz vendégségbe a tornyokat összekötő utakon. Az utak a gátak tetején vezettek. Így aztán a robbantások során vigyázniuk kellett, nehogy olyan gátat is felrobbantsanak, ami az egyik lény lakótornyát végleg elszigeteli. Arra jöttek rá, hogy ha mindig csak olyan gátat robbantanak föl, aminek az egyik oldalán víz van a másik oldalán szárazföld, akkor minden lakótorony megközelíthető marad. Legfeljebb nagyobb kört kell megtenni. A lények azt is kiszámolták, hogy ha a bolygón F darab medence van, akkor F-1 darab gátat kell felrobbantaniuk ahhoz, hogy mindent elárasszanak vízzel. Medencék száma: F Lakótornyok száma: V Gátak száma: E Felrobbantott gátak száma: F-1 Megmaradt gátak száma: V-1 V+F=E+2 Most nézzük, hogy hány darab gát marad meg. Amikor végeznek a robbantásokkal, a megmaradt gátak egy körmentes gráfot alkotnak. Ha ugyanis lenne benne kör, akkor lenne olyan rész, ahova még nem folyt volna be a víz. Ez a körmentes gráf egyben összefüggő is, mert a robbantásokat mindig úgy végzik, hogy ne szigeteljék el egyik lény lakótornyát sem. Vagyis a megmaradt gátak hálózata egy összefüggő körmentes gráf, tehát egy fa. Egy n csúcsú fának n-1 darab éle van. Ha a lakótornyok száma V, akkor a fel nem robbantott gátak száma V-1. A bolygón lévő E darab gát közül F-1 darabot felrobbantottak, V-1 darabot pedig nem, tehát: Ezt a képletet Euler-féle poliéder-tételnek hívjuk. Azt mondja az Euler-féle poliéder-tétel, hogy ha egy konvex poliéder csúcsainak száma V, lapjainak száma F és éleinek száma E… akkor csúcsok száma lapok száma élek száma Ez a tétel érvényes minden gömbre rajzolt gráfra is. Itt V a gráf csúcsainak a száma, E az élek száma, F pedig azoknak a tartományoknak a száma, amelyre a gráf felszabdalja a gömb felszínét. A gömbre rajzolt gráfot síkra tudjuk vetíteni egy ügyes kis trükk segítségével. Ezt sztereografikus vetítésnek nevezzük. A dolog oda-vissza működik, vagyis a gömb pontjait síkra tudjuk vetíteni, a sík pontjait pedig gömbre. Ez azt jelenti, hogy az Euler-tétel nem csak a gömbön, hanem a síkon is igaz. Azzal az apró kis módosítással, hogy a síkon a sok korlátos tartomány mellett létezik egy olyan tartomány is, amelyik nem korlátos. Mindez arra jó, hogy megpróbálhatunk találni néhány szabályt, hogy egy gráf mikor síkbarajzolható. Kezdjük az egyszerű gráfokkal. Ha egy gráf egyszerű gráf, legkevesebb 3 élre van szüksége ahhoz, hogy egy tartományt határoljon. Az is lehet, hogy többre, de 3 él mindenképpen kell. Ez azt jelenti, hogy Na persze egy él két tartományhoz is felhasználható. A helyzet tehát egy kicsit jobb. Ha egy egyszerű gráf síkbarajzolható, akkor meg kell felelnie ennek a feltételnek. Sajnos ez csak egy szükséges feltétel, tehát abból, hogy ez teljesül, még nem következik, hogy a gráf síkbarajzolható. Síkbarajzolható gráfok szükséges feltétele: Próbáljuk ki. Itt van K5. K5 nem teljesíti a feltételt, ezért nem síkbarajzolható. Most nézzük mi a helyzet K3,3-mal. Tudjuk, hogy ez sem síkbarajzolható, de lássuk, mit ad rá a kritérium. Hát, a kritérium K3,3-at átengedi… Ettől persze K3,3 továbbra sem síkbarajzolható. Ebből is látszik, hogy ez a kritérium csak szükséges feltétele a síkbarajzolhatóságnak, de nem elégséges. Ha még rémlik valami, a kritériumot úgy gyártottuk, hogy 3 hosszú körökkel számol. K3,3-ban, viszont minden kör 4 hosszú. Ez az oka annak, hogy nem működik itt. Ha egy egyszerű gráfban minden kör legalább k hosszú, akkor a tartományok száma így becsülhető felülről: És mivel egy él két tartományhoz is tartozik… Ha egy egyszerű gráfban minden kör legalább k hosszú, akkor a síkbarajzolhatóság szükséges feltétele: Gyorsan próbáljuk is ki ezt az új képletet. Lássuk, mi a helyzet K3,3-mal. Azért csak kijött, hogy K3,3 sem síkbarajzolható.
Egyszerű gráfok síkbarajzolhatóságnak szükséges feltételei:
ha minden kör hossza legalább k:
Van itt ez a gráf. Döntsük el, hogy síkbarajzolható-e. Ha igen, rajzoljuk síkba.
Nézzük, hátha van benne K5.
K5-ben minden csúcs negyedfokú. Vagyis F nem illik a képbe.
Az eredeti gráf tartalmaz egy K5-tel topologikusan izomorf részgráfot.
Így aztán nem síkbarajzolható.
Van itt aztán ez a másik gráf. Döntsük el, hogy síkbarajzolható-e. Ha igen, rajzoljuk síkba.
Úgy tűnik hiába fáradoztunk…
Maradt bent egymást keresztező él.
És bármelyiket rakjuk is ki, akkor kint fog gondot okozni.
Így aztán jó lenne találnunk a gráfban K5-öt vagy K3,3-at.
K5-re azért ne nagyon számítsunk, mert nem sok negyedfokú csúcs van.
És egy dolgot nagyon jegyezzünk meg.
K3,3 valójában egy hatszög három átlóval.
Hát persze, hogy akkor ez a részgráf kell…
Ez topologikusan izomorf K3,3-mal, így aztán az eredeti gráf nem síkbarajzolható.
Most lássuk, mi a helyzet ezzel. Legalább hány élt kell törölnünk ebből a gráfból, hogy a megmaradt gráf síkbarajzolható legyen?
Ez egy páros gráf, így minden kör hossza legalább 4.
Lássuk, milyen kritérium lenne jó ide.
A jelek szerint két élt egészen biztosan törölnünk kell.
És valószínűleg nem ezeket az ártatlan kis éleket…
Hanem ezeket a brutális éleket, akik keresztülgázolnak mindenkin.
A megmaradt gráfra már teljesül ez a kritérium.
Nagy kár, hogy ez csak egy szükséges feltétel.
Vagyis hiába teljesül, az még nem bizonyítja a síkbarajzolhatóságot.
Ha be akarjuk bizonyítani, hogy a megmaradt gráf síkbarajzolható, akkor nincs mese, síkba kell rajzolni.
Bárcsak mindennel így lenne szerencsénk…
Egy 100 pontú gráfról tudjuk, hogy 50 csúcs mindegyikének a foka legfeljebb 7 a másik 50 csúcs foka pedig legalább 56.
Kérdés: hány éle van ennek a gráfnak?
Ezek azok a feladatok, amiért az ember nagyon utálja a gráfelméletet…
vagy épp nagyon szereti.
Lássuk, mit kezdhetnénk az ilyen megfoghatatlannak tűnő kérdésekkel.
Az első fontos észrevétel, hogy egy egyszerű gráfban a csúcsok foka azért nem lehet olyan hatalmas.
K6-ban például minden csúcs foka 5.
És K50-ben minden csúcs foka 49.
Ezt már föl sem tudjuk rajzolni…
És nyilván ez a sötét gondolat motiválta a feladat készítőjét is.
Rajzolgatás helyett gondolkodnunk kell.
Ennek az 50 csúcsnak a fokszáma olyan nagy…
hogy csúcsonként csak 49 élt tudnak egymás közt elpasszolni.
a maradék 56-49=7 él kénytelen valamilyen más csúcsba vezetni.
Hívjuk a csúcsoknak ezen halmazát A halmaznak.
Ha az A halmazban valóban egy K50 lakozik és minden csúcs pontosan 56 fokú, akkor pontosan 350 él hagyja el az A halmazt.
De az is lehet, hogy ez az 50 csúcs nem egy teljes gráfot alkot.
Ilyenkor vannak további élek, amik kivezetnek A-ból.
A másik 50 csúcs halmaza legyen a B halmaz.
Ebben a B halmazban a csúcsok foka legfeljebb 7. Ha a halmazon belül semelyik két csúcs között nem vezet él, akkor...
legfeljebb ennyi él vezethet kívülről a B halmazba.
Ha az egyik halmaz legalább 350 éltől akar megszabadulni…
a másik pedig legfeljebb ennyit tud fogadni, akkor valami azt súgja, hogy itt a 350 lesz a végső egyezség.
Van tehát ez a 350 él.
B-ben további élek már nem lehetnek.
A-ban pedig még ezen a 350 élen kívül minden csúcs mindegyikkel össze van kötve:
Ez így akkor összesen annyi, mint 350+1225=1575 él.
Hát, ennyi éle van a gráfnak.
Nézzünk még egy ilyet.
Egy konferencián 60-an vesznek részt. A résztvevők közül 20-an már legalább 27 emberrel kezetfogtak, a többiek pedig még csak legfeljebb 4 emberrel.
Hány kézfogás történt eddig?
Ez a történet valahonnan nagyon ismerősnek tűnik…
Ja igen, ezt a feladatot oldottuk meg az előbb.
Van ez a 20 ember azzal a rengeteg kézfogással…
Ha itt mindenki mindenkivel kezetfog, akkor ez egy K20.
K20-ban a csúcsok fokszáma 19, de itt a csúcsok fokszáma 27, vagyis csúcsonként legalább 27-19=8 él kivezet a halmazból.
Hívjuk a csúcsoknak ezen halmazát A halmaznak.
Ha az A halmazban valóban egy K20 lakozik és minden csúcs pontosan 27 fokú, akkor pontosan 160 él hagyja el az A halmazt.
De az is lehet, hogy ez az 20 csúcs nem egy teljes gráfot alkot.
Ilyenkor vannak még további élek, amik kivezetnek A-ból.
A másik 40 csúcs halmaza legyen a B halmaz.
Ebben a B halmazban a csúcsok foka legfeljebb 4. Ha a halmazon belül semelyik két csúcs között nem vezet él, akkor...
legfeljebb ennyi él vezethet kívülről a B halmazba.
Ha az egyik halmaz legalább 160 éltől akar megszabadulni...
a másik pedig legfeljebb ennyit tud fogadni, akkor valami azt súgja, hogy itt a 160 lesz a végső egyezség.
Van tehát ez a 160 él.
B-ben további élek már nem lehetnek.
Ők a kockák. Elmennek úgy egy konferenciára, hogy még csak kezet se fognak egymással.
Az A-ban vannak a hiperaktívak, már mindenki mindenkivel kezetfogott, ami egy K20:
És már elkezdtek barátkozni a kockákkal is, 8 kézfogás/fő sebességgel.
Ez így akkor annyi mint 190+160=250 darab kézfogás.
Ennyi kézfogás történt eddig.
Végül nézzünk meg egy nagyon izgalmas ügyet.
Bizonyítsuk be, hogy egy G gráf és a komplementere közül legalább az egyik összefüggő.
Ha az eredeti G gráf összefüggő, akkor nincsen semmi baj.
Az állítás igaz.
Ha az eredeti G gráf nem összefüggő, akkor több komponensből áll.
Nézzük először azt az esetet, amikor kettőből.
Arról nem rendelkezünk információval, hogy a komponenseken belül mely csúcsok szomszédosak.
De az biztos, hogy a gráf komplementerében az A komponens egy tetszőleges csúcsa össze lesz kötve B minden csúcsával.
Mert a komplementerben minden olyan élt be kell húznunk, ami most nincs behúzva.
És mivel az A komponens bármely csúcsa össze lesz kötve B minden csúcsával…
az így keletkező gráf biztosan összefüggő.
Hiszen ennek a gráfnak részgráfja egy A és B pontosztályú páros gráf.
Ha pedig az eredeti G gráfnak több komponense van…
akkor az iménti gondolatmenet bármely két komponensre igaz.
Így a komplementer gráfban bármely két csúcsosztály pontjai összefüggő részgráfot alkotnak.
És emiatt a komplementer gráf összefüggő.
Itt jön egy egyenletrendszer.
Érdemes generáló elemet úgy választani, hogy a sorában és oszlopában jó sok nulla legyen.
Ennek előnyeit pillanatokon belül élvezhetjük.
Legyen mondjuk ez.
Hát ugye az nincs
az nincs és sincs
Érdemes generáló elemet úgy választani, hogy a sorában és oszlopában jó sok nulla legyen.
Ennek előnyeit pillanatokon belül élvezhetjük.
Legyen mondjuk ez.
A nulla miatt ebben az oszlopban minden elemből nullát vonunk ki,
tehát az egész oszlop marad.
Ezért érdemes úgy választani generáló elemet, hogy a sorában
és oszlopában jó sok nulla legyen.
Hát ezért éri meg így választani.
A nullák megkönnyítik az életünket.
Kiszámolni csak ezeket kell.
A nulla miatt ebben az oszlopban mindenki marad
Sőt, ebben a sorban is mindenki marad.
És ebben a sorban is.
Alig kell valamit számolni.
Ezt az egyet kell kiszámolni:
Nézzünk meg két nagyon izgalmas egyenletrendszert!
Ebben az egyenletrendszerben valójában
csak két egyenlet van.
A harmadik egyenlet ugyanis az első kettő összege.
Ilyen alapon lehetne még egy negyedik, ötödik,
sőt hatodik egyenlet is.
Valójában tehát csak két egyenlet van, vagyis több
az ismeretlen, mint ahány egyenlet, és ilyenkor
az egyenletrendszernek nincs egyértelmű megoldása.
Na ennyi elég
Ebben az egyenletrendszerben a harmadik egyenlet
szintén az első kettő összege, de van egy kis gond.
A jobb oldal ugyanis nem stimmel, mert 5 helyett 6 van.
Ilyenkor ugye nem tud egyszerre mindegyik egyenlet
teljesülni, vagyis az egyenletek ellentmondanak,
és ezért az egyenletrendszernek nincs megoldása.
Van tehát két egyenletrendszerünk, és mi előre tudjuk, hogy az egyiknek végtelen sok megoldása lesz, a másiknak pedig nem lesz megoldása.
Nézzük meg, hogy ha elkezdjük megoldani ezeket az egyenletrendszereket a jól bevált elemi bázistranszformációval, akkor vajon hogyan fog kiderülni, hogy az egyiknek
végtelen sok megoldása van, a másiknak pedig nincs megoldása.
Itt kezdődnek a problémák.
-at ugyanis nem tudjuk lehozni, mert 0-t nem választhatunk generáló elemnek.
A bázistranszformáció tehát úgy ér véget, hogy marad egy –s sor.
HA MARADNAK -S SOROK, AHOL MÁR NEM TUDUNK GENERÁLÓ ELEMET VÁLASZTANI, OLYANKOR MINDIG VÉGTELEN SOK MEGOLDÁS VAN, VAGY NINCS MEGOLDÁS.
HA A MEGMARADT -S SOR ILYEN,
AKKOR VÉGTELEN SOK MEGOLDÁS VAN
x-es oszlop
0
0
HA A MEGMARADT -S SOR ILYEN,
AKKOR NINCS MEGOLDÁS
x-es oszlop
0
NEM 0
A MEGOLDÁS LEOLVASÁSA A TÁBLÁZATBÓL
A fent maradt változók úgynevezett szabad változók, ők t, s és egyéb néven szerepelnek tovább a történetben.
A MEGOLDÁS:
ÁLTALÁNOS MEGOLDÁS:
SZABADSÁGFOK=ahány fönt marad
(most a szabadságfok 1)
RANG=ahány levihető
(most a rang 2)
A MEGOLDÁS LEOLVASÁSA A TÁBLÁZATBÓL
Itt már nincs további teendő
Az és paraméterek milyen értékeire lesz nulla darab, egy darab illetve végtelen sok megoldása a következő egyenletrendszernek?
Elkezdjük megoldani a bázistranszformációval.
Olyan sorban és oszlopban, ahol paraméter van, nem ajánlatos generáló elemet választani.
Ezeket tehát kerüljük el!
Van itt ez a marhajó 1-es, válasszuk ezt.
Elkerüljük a paramétereket, amíg lehet.
Most elkezdünk egy kicsit gondolkodni.
1.ESET és
végtelen sok megoldás
2.ESET és
nincs megoldás
3.ESET és
levihető és egy megoldás
Na ennyi gondolkodás elég is volt.
Az , és paraméterek milyen értékeire lesz nulla darab, egy darab illetve végtelen sok megoldása a következő egyenletrendszernek?
Amíg lehet ne válasszunk generáló elemet olyan sorban vagy oszlopban,
amiben paraméter van.
van itt ez a remek 1-e, válaszzuk ezt!
Aztán ezt a másik 1-est választjuk. Marha nagy szerencsénk van a nullákkal.
A nulla miatt ebben a sorban minden elemből nullát vonunk ki,
tehát az egész sor marad ahogy van,
meg itt is,
sőt itt is.
Ezért érdemes úgy választani generáló elemet, hogy a sorában
és oszlopában jó sok nulla legyen. A nullák megkönnyítik az életünket.
A bázistranszformáció itt elakad, a legalsó sorban ugyanis csupa nulla van, a felette
lévőben pedig paraméter.
Kezdjünk el kicsit gondolkodni!
1.ESET
nincs megoldás és bármi lehet.
2.ESET
nincs megoldás, és bármi lehet.
3.ESET és
ekkor levihető, végtelen sok megoldás, a szabadságfok egy
Van itt még valami.
Itt ugye, ha nem nulla van, akkor nincs megoldás.
De itt mindegy mi van, ha például ,
ennek akkor is van megoldása.
Ne felejtsük el ugyanis, hogy ezek
a feltételek csak -s sorokra vonatkoznak.
Ez -s sor, tehát itt
tényleg nincs megoldás.
Ebben a sorban viszont már x van,
így semmilyen szabálynak nem kell teljesülnie.
Számítsuk ki a
vektorokból álló vektorrendszer rangját, illetve állapítsuk meg, hogy előállítható-e segítségükkel az és vektor.
illetve
Akkor állítható elő az vektor, ha léteznek olyan számok, hogy
illetve
Ez tulajdonképpen két egyenletrendszer:
Ezeket kell megoldanunk. Ha van megoldás, akkor az adott vektor előállítható, ha nincs megoldás, akkor nem állítható elő.
megoldjuk:
van megoldás,
így az vektor előállítható
Például
Jön a szokásos, és persze nagyon izgalmas bázistranszformáció.
nincs megoldás,
ezért a vektor sajna nem állítható elő
A bázistranszformáció itt sajnos elakad, mert az -s sorokban már csak nullák vannak.
Ilyenkor vagy végtelen sok megoldás van vagy nincs megoldás.
Lássuk, hogyan áll elő az vektor!
Az egyenletrendszer megoldását a
szokásos módon olvassuk le.
és tetszőleges
Ha mondjuk és nulla, akkor
A vektorrendszer rangja annyi, ahány x-et lehoztunk, vagyis most éppen kettő.
A Gauss-elimináció pro változatát Gauss-Jordan eliminációnak nevezzük.
A lényege az, hogy nem csak a vezéregyesek alatt nullázunk ki, hanem felettük is.
Éppen itt is jön ez az egyenletrendszer.
Oldjuk meg, és nézzük meg, hogyan működik a Gauss-Jordan elimináció.
Ebben a mátrixban két független oszlopvektor van.
A harmadik oszlop ugyanis az első kettő összege…
A negyedik pedig a második kétszerese.
1 4 5 8
3 1 4 2
2 1 3 2
Egy mátrix oszloprangja az oszlopvektorai közül kiválasztható független vektorok maximális száma.
Most maximum két független oszlopvektor választható ki…
Így hát ennek a mátrixnak az oszloprangja kettő.
Független sorvektora persze lehetne akár három is…
De nincs.
Egy Gauss-Jordan eliminációval mindjárt az is kiderül, hogy miért nincs.
Mivel a harmadik sort ki tudtuk nullázni…
Ez azt jelenti, hogy az első két sornak a lineáris kombinációja.
Egy mátrix oszloprangja és sorrangja mindig megegyezik a vezéregyesek számával.
Most éppen két vezéregyes van, így ennek a mátrixnak az oszloprangja és a sorrangja is kettő.
Ezt hívjuk a mátrix rangjának, és a szokásos módon jelöljük:
Egy mátrixot teljes oszloprangúnak nevezünk, hogyha az oszlopvektorai lineárisan független rendszert alkotnak.
Ez a mátrix nem teljes oszloprangú…
Az oszloprang ugyanis csak 2 és a mátrixnak négy oszlopa van.
Egy mátrixot
Ebben a mátrixban két független oszlopvektor van.
A harmadik oszlop ugyanis az első kettő összege…
A negyedik pedig a második kétszerese.
1 4 5 8
3 1 4 2
2 1 3 2
Egy mátrix oszloprangja az oszlopvektorai közül kiválasztható független vektorok maximális száma.
Most maximum két független oszlopvektor választható ki…
Így hát ennek a mátrixnak az oszloprangja kettő.
Független sorvektora persze lehetne akár három is…
De nincs.
Egy Gauss-Jordan eliminációval mindjárt az is kiderül, hogy miért nincs.
Mivel a harmadik sort ki tudtuk nullázni…
Ez azt jelenti, hogy az első két sornak a lineáris kombinációja.
Egy mátrix oszloprangja és sorrangja mindig megegyezik a vezéregyesek számával.
Most éppen két vezéregyes van, így ennek a mátrixnak az oszloprangja és a sorrangja is kettő.
Ezt hívjuk a mátrix rangjának, és a szokásos módon jelöljük:
Egy mátrixot teljes oszloprangúnak nevezünk, hogyha az oszlopvektorai lineárisan független rendszert alkotnak.
Ez a mátrix nem teljes oszloprangú…
Az oszloprang ugyanis csak 2 és a mátrixnak négy oszlopa van.
Egy mátrixot teljes sorrangúnak nevezünk, hogyha a sorvektorai lineárisan független rendszert alkotnak.
Ez a mátrix nem is teljes sorragú…
A rang ugyanis még mindig 2, sor viszont három van.
Itt van aztán ez a másik mátrix. Számoljuk ki a rangját, és döntsük el, hogy teljes oszloprangú vagy teljes sorrangú-e.
Hát, túl nagy izgalmakra azért ne számítsunk.
Megint jön a Gauss-elimináció.
Három darab vezéregyes van, így hát a mátrix rangja 3.
Az oszlopok száma és a rang most ugyanannyi, mindkettő 3…
Ez a mátrix tehát teljes oszloprangú.
Sorokból viszont egy kicsit több van mint 3…
Tehát a mátrix nem teljes sorrangú.
A bázisfelbontás szemléletes jelentése egészen izgalmas...
Az eredeti A mátrix rangja most 2…
Tehát az oszlopvektorai közül két független vektort tudunk kiválasztani.
Mondjuk ezt a kettőt itt.
Ez a két vektor az A mátrix oszlop-vektorterének egy bázisa.
A bázisfelbontásban szereplő második mátrix azt írja le…
Hogy a két bázisvektor miként állatja elő az eredeti mátrix oszlopvektorait.
Ez a második mátrix tehát az eredeti A mátrix oszlopvektorainak a koordinátáit adja meg a bázisban.
Számoljuk ki az A mátrix rangját, keressük meg az oszlopvektorainak egy bázisát, és adjuk meg ebben a bázisban az A mátrix oszlopvektorainak koordinátáit.
Az független vektorok, és
Mekkora a vektorrendszer rangja, illetve előállítható-e velük a vektor?
A vektor akkor állítható elő, ha van olyan amire
A jobb oldalt átrendezzük úgy, hogy lássuk mennyi van az vektorokból
Mivel független vektorok, ha például a bal oldalon egy darab van,
akkor a jobb oldalon is egy darab kell, hogy legyen,
vagy ha a bal oldalon két van, akkor jobb oldalon is.
Érdemes megfigyelni, hogy ezt a táblázatot
rögtön a feladatból is felírhatjuk.
Nincs más dolgunk, mint összeszámolni, hány darab van,
aztán azt, hogy hány darab és végül hány .
A megoldás:
A vektor előáll:
A vektorrendszer rangja pedig, mivel mindhárom x-et lehoztuk,
így a jelek szerint három.
Most egy nagyon izgalmas dologgal, a mátrixok inverzével fogunk foglalkozni.
Az -es mátrix inverze egy olyan mátrix, ami azt tudja, hogy
A mátrixok szorzása nem kommutatív, tehát ha a szereplőket megcseréljük,
akkor lehet, hogy valami egészen más mátrixszal kell az -t szorozni ahhoz, hogy az egységmátrixot kapjuk.
Mindkét mátrixot inverznek nevezzük
ilyenkor jobb oldali inverz
ilyenkor bal oldali inverz
Az -es mátrixoknak azonban megvan az a remek tulajdonsága,
hogy a szorzás sorrendje az inverznél mindegy, vagyis
Tehát a jobb és bal inverz ilyenkor megegyezik.
Mi most ilyen -es mátrixok inverzét fogjuk kiszámolni,
és maradjunk ennél a sorrendnél.
Itt van például egy mátrix:
Próbáljuk meg kiszámolni az inverzét.
Egy olyan mátrixot kell találnunk, hogy az eredeti mátrixszal megszorozva az egységmátrixot kapjuk.
A kérdőjelek nem igazán segítenek a válasz megtalálásában.
Írhatnánk helyette betűket, hogy a, b, c, meg ilyenek.
Vagy hívhatnánk az elemeit a szokásos jelöléssel úgy, hogy meg meg stb.
De inkább egy másfajta jelölést fogunk használni, és hamarosan az is kiderül majd, hogy
miért.
A kettős indexezés túl bonyolult, ezért legyen csak , és .
Az oszlopokat pedig színekkel különböztessük meg.
Ez volna tehát az inverz mátrix. Már csak azt kell kiszámolni, hogy mennyi , és
Ehhez végezzük el a szorzást!
A dolog picit bonyolultnak tűnik, de csak első ránézésre.
Bármi legyen is az inverz mátrix, az elemeire teljesülnie kell ennek a három egyenletrendszernek.
Oldjuk őket meg! Ehhez elvileg három külön táblázatra van szükségünk.
Valójában elég egyetlen táblázat.
A három egyenletrendszert tehát egyszerre oldjuk meg, a szokásos bázistranszformációval.
A bázistranszformáció lépéseit most nem részletezzük, minden pontosan úgy megy, ahogyan eddig. Aki esetleg úgy érzi, hogy elhomályosultak az emlékei ezzel kapcsolatban, az nézze meg a bázistranszformációról szóló részt.
A kapott megoldás éppen az inverz.
Csak annyi dolgunk van, hogy
sorba rakjuk a sorokat:
Az inverz kiszámolása valójában tehát rettentő egyszerű. Itt van mondjuk ez a mátrix:
Mindössze annyit kell tennünk, hogy felírjuk a mátrixot, a szokásos táblázatba,
és mellé írjuk az egységmátrixot.
Ezek után jön a bázistranszformáció. Ha nem tudjuk mindegyik x-et levinni, akkor nincs inverz. Ha mindet le tudjuk vinni, akkor van.
Elérkezett az idő, hogy olyan mátrixok inverzét is kiszámoljuk, amelyek nem -esek.
Ilyenkor a jobb oldali inverz és a bal oldali inverz nem egyezik meg.
ilyenkor jobb oldali inverz
ilyenkor bal oldali inverz
Itt van például egy mátrix
A bal oldali inverz 3x2-es lesz
A jobb oldali inverz szintén 3x2-es lesz
Mindkettőt bázistranszformációval számoljuk ki
Itt sajnos van egy kis gond.
bal oldali inverz
most nincs
jobb oldali inverz
most épp van
Maradt egy -s sor, amiben nem
mindenki nulla, tehát nincs megoldás.
Itt viszont van megoldás,
a fönt maradt legyen mondjuk .
A leképezést lineáris leképezésnek nevezzük, ha bármely vektorokra és számra teljesül, hogy
Minden lineáris leképezés valahogy így néz ki:
Ha akkor a lineáris leképezést lineáris transzformációnak nevezzük.
A leképezés a vektoraihoz rendel -beli vektorokat, de egyáltalán nem biztos, hogy így az egész előáll képként. A -nek azt a részét, amely a leképezés során előáll, a leképezés képterének nevezzük és -vel jelöljük.
A nullvektorból minden lineáris leképezés nullvektort csinál, vagyis képe mindig ,
de előfordulhat, hogy más -beli vektorok képe is nullvektor lesz.
Ezen vektorok halmazát nevezzük a leképezés magterének és -vel jelöljük.
A magtér és a képtér nem csupán részhalmazok -ben és -ben, hanem alterek is. altér -ben és altér -ben.
A képtér és a magtér dimenziója összesen éppen kiadja dimenzióját.
Ezt az összefüggést dimenziótételnek nevezzük:
DIMENZIÓTÉTEL:
mateking.hu
Minden lineáris leképezést jellemezhetünk egy mátrixszal. Valójában mindegyiket végtelen sok mátrixszal jellemezhetjük, ezek a mátrixok pedig úgy keletkeznek, hogy veszünk egy tetszőleges bázist -ben és a bázisvektorok képeit egymás mellé írjuk. Nézzünk erre egy példát!
Minden lineáris leképezést jellemezhetünk egy mátrixszal. Valójában mindegyiket végtelen sok mátrixszal jellemezhetjük, ezek a mátrixok pedig úgy keletkeznek, hogy veszünk egy tetszőleges bázist -ben és a bázisvektorok képeit egymás mellé írjuk. Nézzünk erre egy példát!
Vegyük például a tengelyes tükrözést.
Ez egy lineáris leképezés.
A tükrözés mátrixát úgy kapjuk,
hogy a bázisvektorok képeit egymás mellé írjuk:
Vegyük például a tengelyes tükrözést. Ez egy lineáris leképezés.
Ez tehát a tükrözés mátrixa, legalábbis a szokásos bázisban.
Ha ugyanis egy másik bázis alapján írjuk föl ugyanennek a tükrözésnek a mátrixát, akkor egészen más mátrixot kapunk. Legyen például a másik bázis a következő:
A szokásos bázis alapján a tükrözés mátrixát úgy kapjuk, hogy a bázisvektorok képeit egymás mellé írjuk:
Ez tehát a tükrözés mátrixa, legalábbis a szokásos bázisban.
Ha ugyanis egy másik bázis alapján írjuk föl ugyanennek a tükrözésnek a mátrixát,
akkor egészen más mátrixot kapunk. Legyen például a másik bázis a következő:
A transzformáció mátrixa most is úgy keletkezik,
hogy egymás mellé írjuk a bázisvektorok képeit.
Van itt azonban egy izgalmas fordulat.
Addig minden stimmel, hogy a bázisvektorok képe:
Addig minden stimmel, hogy megkaptuk az új bázisvektorok képeit.
Csakhogy itt az új bázisvektorok képeit még mindig a régi bázisban adtuk meg.
Nekünk azonban a bázisvektorok képeit is az új bázisvektorok segítségével kell megadnunk.
Az tehát a kérdés, hogy mennyit vegyünk az és vektorokból,
hogy előálljanak és képei.
Az tehát a kérdés, hogy mennyit vegyünk az és vektorokból, hogy előálljanak és képei.
Ezúttal a szerencse megsegít bennünket, az vektor képe ugyanis
ami úgy tűnik éppen mínuszegyszerese.
Az vektor képe tehát úgy jön ki, hogy -ből 0 darab, -ből pedig -1 darab kell.
Lássuk mi a helyzet az vektor képével. Itt is szerencsénk van.
ami éppen az eredeti mínuszegyszerese, tehát -ből -1 darab, -ből 0 darab kell.
Lássuk a transzformáció mátrixát ebben az új bázisban!
A tükrözés mátrixa most is
úgy keletkezik, hogy egymás mellé
írjuk a bázisvektorok képeit.
Csakhogy új bázisvektorok képeinek
ezeket az új koordinátáit kell írnunk
a tükrözés mátrixába.
Na ezt kell írnunk a mátrix első oszlopába, ahova az vektor képe kerül.
Az új bázisvektorok képeinek ezek az új koordinátái kerülnek a transzformáció mátrixába.
Az vektor képe szintén szerencsésen előállítható, ugyanis
ami pedig éppen az eredeti mínuszegyszerese, tehát -ből -1db és -ből 0db kell.
Az új bázisvektorok képeinek ezek az új koordinátái kerülnek a transzformáció mátrixába.
Az új bázisban felírt mátrix:
Mindezt egyszerűbben is megkaphatjuk egy remek kis összefüggés segítségével.
ahol az új bázisra áttérés mátrixa a régi bázisban. Mit is jelent mindez?
Van ugye a transzformáció régi mátrixa, ez
és van ez a bizonyos , ami annak a transzformációnak a mátrixa, ami a régi bázisból új bázist csinál. Ez a bizonyos mátrix tehát
RÉGI BÁZIS
ÚJ BÁZIS
A képlet azt mondja, hogy az új mátrixot így kapjuk:
A leképezés mátrixa sokkal többet is tud annál, minthogy egyszerűen leírja magát a leképezést.
Minden vektorról megmondja, hogy mi lesz a vektor képe:
A vektor képe úgy lesz, hogy egyszerűen
megszorozzuk a vektort a leképezés mátrixával.
Nézzük meg például mi lesz a tükrözés során
ebből a remek vektorból:
A tükrözés mátrixa normál bázisban:
A vektor képe:
És tényleg!
Nézzük meg mi történik ugyanezzel a vektorral a másik bázisban.
Az új bázisban koordinátái megváltoznak.
A vektor éppen kétszerese -nek,
ezért az első koordinátája kettő,
a második koordináta pedig nulla.
A tükrözés mátrixa az új bázisban:
vagyis nulla darab -re és
–2 darab -re van szükség
Lássuk a leképezés mátrixának még néhány további izgalmas tulajdonságát.
Ha egy leképezés mátrixa akkor
a leképezés megfordításának mátrixa
A leképezés megfordítását nevezhetjük úgy,
hogy a leképezés inverze.
A leképezés megfordítását nevezhetjük úgy, hogy a leképezés inverze.
Egy leképezésnek pontosan akkor létezik inverze, ha a mátrixnak létezik inverze,
és az inverz leképezés mátrixa:
mátrixa
Ha van két leképezés, mondjuk és a leképezések mátrixa pedig és ,
akkor a leképezés mátrixa lesz.
Nézzünk meg erre egy példát.
Legyen az eddigi tükrözés az x tengelyre,
pedig mondjuk tükrözés az y tengelyre.
Ekkor a két tükrözés egymás utáni
alkalmazása.
A leképezés mátrixa:
Az x tengelyre tükrözés mátrixa:
Az y tengelyre tükrözés mátrixa:
Ez éppen az origó középpontú tükrözés mátrixa.
A leképezések egymás után alkalmazásáról szóló tétel
A leképezés mátrixa:
A leképezés a vektor
A leképezésben minden
vektor képét így kapjuk:
Ha létezik a leképezés
inverze, akkor mátrixa:
mátrixa
Ezek a tételek lehetővé teszik, hogy készítsünk egy remek kis képletet ami leírja, hogy miként változik meg egy leképezés mátrixa az új bázisra való átállásnál.
A leképezés mátrixa új bázisban felírva
ahol az új bázisra áttérés mátrixa a régi bázisban.
Lássuk, hogy mit is jelent mindez!
Van ugye a transzformáció régi mátrixa, ez
és van ez a bizonyos , ami annak a transzformációnak a mátrixa, ami a régi bázisból új bázist csinál. Ez a bizonyos mátrix tehát
és van ez a bizonyos ami annak a leképezés-
nek a mátrixa, ami a régi bázisból új bázist csinál.
Ez a bizonyos mátrix tehát egyszerűen
úgy keletkezik, hogy fogjuk az új bázis-
vektorokat és leírjuk egymás mellé.
A képlet azt mondja, hogy az új mátrixot így kapjuk:
Ez csodás, így is kijött a tükrözés új mátrixa, kevesebb gondolkodással és több számolással.
Mindezeket foglaljuk össze!
LINEÁRIS LEKÉPEZÉSEK MÁTRIXA
A lineáris leképezésnek a bázisban felírt mátrixát úgy kapjuk meg, hogy a bázisvektorok képeit egymásmellé írjuk:
Ha egy másik bázisban írjuk föl a mátrixot, akkor
A két mátrix közötti átjárást az alábbi tétel biztosítja:
Itt az új bázisra való áttérés mátrixa:
Egyszerűen úgy keletkezik, hogy az új bázisvektorokat
fogjuk és leírjuk egymás mellé.
Egyszerűen úgy keletkezik, hogy az új bázis
vektorait leírjuk egymás mellé.
Ha és olyan mátrixok, hogy létezik egy mátrix
úgy, hogy
akkor az előző tétel alapján és mindketten
ugyanannak a leképezésnek a mátrixa, csak éppen
más-más bázisban felírva.
Ezt a tényt úgy nevezzük, hogy a két mátrix egymáshoz hasonló.
Ez elvezet minket néhány nagyon izgalmas összefüggéshez, amik most fognak jönni!
és mátrixok hasonlók, tehát , ha létezik olyan mátrix, amire
Egy leképezést akkor nevezünk lineáris leképezésnek, ha bármely vektorokra és számra teljesül, hogy
A leképezés vektoraihoz rendel hozzá -ben lévő vektorokat.
A -nek ezt a részét képtérnek nevezzük és -vel jelöljük.
Vannak olyan vektorok, amikből a leképezés nullvektort csinál.
A -nek azt a részét amiben ezek a vektorok vannak magtérnek nevezzük
és -vel jelöljük.
lineáris leképezés, ha
és
Minden lineáris leképezést jellemezhetünk mátrixokkal. Ezeket a mátrixokat úgy kapjuk, hogy veszünk egy bázist -ben, és a bázisvektorok képeit egymás mellé írjuk.
Mivel végtelen sok bázis van -ben, ezért ugyanannak a lineáris leképezésnek végtelen sok mátrixa van.
A lineáris leképezésnek a bázisban felírt mátrixa
Lássunk néhány példát!
Vegyük azt a leképezést, amely és
Ellenőrizzük, hogy valóban lineáris leképezés-e, ha igen adjuk meg a képteret, a magteret és a transzformáció mátrixát.
Itt van két vektor
és vizsgáljuk meg, hogy teljesül-e:
Van itt azonban egy kis gond, ha elvégezzük az összeadást.
Úgy tűnik tehát nem teljesül, hogy ezért a másik tulajdonságot meg se nézzük, sajna nem lineáris leképezés.
Nézzünk meg egy másik leképezést is, amely és
Ellenőrizzük, hogy valóban lineáris leképezés-e, ha igen adjuk meg a képteret a magteret és a transzformáció mátrixát.
Itt vannak megint ezek a vektorok
és vizsgáljuk meg, hogy teljesül-e:
Nézzük, teljesül-e, hogy:
Mindkettő teljesül, tehát a leképezés lineáris.
Most, hogy ez kiderült, lássuk mi lesz a magtér és a képtér, illetve a leképezés mátrixa.
A magtérben olyan vektorok vannak, amelyek képe nullvektor, tehát
Ebből következik, vagyis a magtérben olyan vektorok vannak, amelyek első és második koordinátája megegyezik:
A képtérben olyan vektorok vannak, amelyek első koordinátája bármi, de második koordinátája nulla, vagyis:
A transzformáció mátrixa standard bázisban:
tehát a transzformáció mátrixa:
Ez igazán remek, úgyhogy nézzünk meg még egy leképezést is.
Vegyük azt az leképezést, hogy
Ellenőrizzük, hogy valóban lineáris leképezés-e, ha igen adjuk meg a képteret, a magteret és a transzformáció mátrixát.
Elsőként megnézzük, hogy valóban lineáris leképezés-e.
Itt van két vektor
és lássuk, hogy teljesül-e:
Ezek sajna nem egyenlők, így nem teljesül,
hogy tehát
nem lineáris leképezés.
A leképezést lineáris leképezésnek nevezzük, ha bármely vektorokra és számra teljesül, hogy
lineáris leképezés, ha
és
A lineáris leképezésnek a bázisban felírt mátrixát úgy kapjuk meg, hogy a bázisvektorok képeit egymásmellé írjuk
Ha egy másik bázisban írjuk föl a mátrixot, akkor
A két mátrix közötti átjárást az alábbi tétel biztosítja:
Itt az új bázisra való áttérés mátrixa:
Itt a sajátbázisra való áttérés mátrixa:
SAJÁTBÁZIS
Bármilyen bázist választunk is -ben, a leképezés mátrixa mindig egy -es mátrix lesz. Ha ennek a mátrixnak van n darab független sajátvektora, akkor ezek a sajátvektorok szintén egy bázist alkotnak -ben, amit sajátbázisnak nevezünk.
A leképezés sajátbázisa nagyon sok mindent tud.
Ha egy leképezésnek létezik sajátbázisa, az azt jelenti, hogy a leképezés mátrixának van n darab független sajátvektora, vagyis a mátrix diagonalizálható.
A diagonalizáló mátrix úgy keletkezik, hogy a sajátvektorokat egymás mellé írjuk.
Ez egyúttal a sajátbázisra való áttérés mátrixa is.
Ha létezik sajátbázis, akkor a leképezés mátrixa sajátbázisban felírva
mindig diagonális mátrix.
Ebben a mátrixban éppen az
sajátvektorokhoz tartozó sajátértékek.
Lássunk erre egy példát!
Van itt ez az leképezés:
Ellenőrizzük, hogy valóban lineáris leképezés-e, ha igen adjuk meg a képteret, a magteret és a transzformáció mátrixát, adjuk meg a sajátértékeit, sajátvektorait,
ha van, akkor a sajátbázisát és a diagonális alakját.
Elsőként megnézzük, hogy valóban lineáris leképezés-e.
Legyen
Nézzük meg, hogy teljesül-e:
Ez is teljesül, tehát a leképezés lineáris. Végre rátérhetünk az izgalmasabb részekre.
Nézzük mi lesz a magtér és a képtér.
A magtérben olyan vektorok vannak, amelyek képe nullvektor, tehát
A jelek szerint tehát és vagyis a magtérben olyan vektorok vannak, amelyek első és második koordinátája megegyezik, a harmadik koordinátája pedig nulla:
A magtérben olyan vektorok vannak, amelyek első és második koordinátája megegyezik, a harmadik koordinátája pedig nulla:
A képtérben olyan vektorok vannak, amelyek első koordinátája valami, a második koordináta ennek a mínuszegyszerese, a harmadik koordináta pedig bármi.
A transzformáció képtere tehát kétdimenziós:
Nézzük meg a leképezés mátrixát.
A mátrixot a standard bázisban írjuk fel:
vagyis a transzformáció mátrixa:
Lássuk van-e a leképezésnek sajátbázisa. Ehhez ki kell számolnunk a sajátértékeket
és meg kell keresni a hozzájuk tartozó sajátvektorokat.
A karakterisztikus egyenlet:
Az utolsó sor szerint fejtünk ki.
A sajátértékek:
A sajátértékekhez tartozó sajátvektorokat úgy kapjuk meg, ha megoldjuk a egyenletrendszert.
Ez három különböző egyenletrendszer lesz, amit megoldhatnánk elemi bázistranszformációval is, de most nincs kedvünk azzal megoldani.
Van 3 független sajátvektor, így létezik sajátbázis és a transzformáció mátrixa diagonalizálható.
A diagonalizáló mátrixot úgy kapjuk, hogy a sajátvektorokat egymásmellé írjuk, ami tulajdonképpen nem más, mit az új bázisra, való áttérés mátrixa.
Ez az új bázis éppen a sajátbázis.
És íme, a diagonális alak:
Nézzünk meg egy másik leképezést is!
Elérkezett az idő, hogy megnézzük néhány fontosabb lineáris leképezés mátrixát.
Olyan leképezésekét, amiket már régebbről mindenki ismer.
Az első ilyen leképezés a tengelyes tükrözés.
A mátrixot a szokásos bázis szerint írjuk fel:
x tengelyre tükrözés
Aztán itt van az leképezések közül az egyik
legfontosabb, az origó középpontú -szögű forgatás,
ami esetén éppen az origó középpontú tükrözés.
origó középpontú
-szögű forgatás
A szokásos bázisban az -szögű forgatás mátrixa:
Lássuk a koordinátákat!
Az -irányszögű egységvektor első koordinátája
második koordinátája
Az irányszög most éppen , ezért
az első koordináta
a második koordináta
Vannak itt aztán ezek a trigonometriai összefüggések,
amiket érdemes megjegyeznünk:
Az irányszög most , ezért
az első koordináta
a második koordináta
Az origó középpontú tükrözés mátrixát egyszerűen
úgy kapjuk, hogy
origóra tükrözés
A lineáris leképezések egy külön csoportját alkotják a vetítések, vagy más néven projekciók. Nézzük meg az x tengelyre való merőleges vetítést.
A szokásos bázis alapján a vetítés mátrixa:
x tengelyre vetítés
A LINEÁRIS LEKÉPEZÉSEK VEKTORTERE: HOM (V1,V2)
A lineáris leképezést másnéven homomorfizmusnak is nevezzük.
Ezek a homomorfizmusok és azok mátrixai maguk is egy vektorteret alkotnak,
ezt a vektorteret -nek nevezzük.
Injektívnek nevezzük azokat a homomorfizmusokat, ahol különböző vektorok képe is különböző:
Ha akkor
Ha tudunk mutatni olyan vektorokat amire
akkor a homomorfizmus nem injektív.
Lássuk milyen következményei vannak ennek.
Nevezzük el mondjuk valami -nek.
Viszont ugye
Tehát ami azt jelenti, hogy benne van a magtérben.
Vagyis az, hogy egy leképezés nem injektív, éppen azt jelenti, hogy -ben vannak a nullvektoron kívül más vektorok is, tehát
Az állítás megfordítása is igaz, ha akkor a magtérben kell, hogy legyen
a nullvektoron kívül valamilyen más vektor is,
aminek a képe viszont , mert ugye benne van a magtérben.
Vagyis két különböző vektor képe ugyanaz és így a leképezés nem injektív.
A homomorfizmus pontosan akkor injektív, ha
Ekkor a dimenziótétel alapján vagyis a leképezés dimenziótartó.
A sík szokásos transzformációi közül az x vagy y tengelyre tükrözés és az origó körüli forgatás dimenziótartó transzformáció, az x tengelyre vetítés nem.
Van aztán egy másik izgalmas tulajdonság is.
Egy leképezést szürjektívnek nevezünk, ha a teljes előáll képként.
Azok a homomorfizmusok, amelyek injektívek és szürjektívek is egyszerre,
a bijektív homomorfizmusok.
Ezekre külön elnevezés van forgalomban, őket nevezzük izomorfizmusoknak.
Ha izomorfizmus, akkor és a dimenziótétel miatt
Ráadásul a képtér éppen megegyezik -vel, ezért .
Ha izomorfizmus, akkor .
Az izomorfizmus tehát egy kölcsönösen egyértelmű megfeleltetés két vektortér vektorai között, az egyik vektortér minden vektorához tartozik a másik vektortérben pontosan egy bizonyos vektor, vagyis a két vektortér lényegében ugyanaz.
Ez a miatt is így kell, hogy legyen, hiszen egy vektorteret a dimenziója már jellemez.
Minden lineáris leképezést jellemezhetünk mátrixokkal.
Ezeket a mátrixokat úgy kapjuk, hogy veszünk egy bázist -ben, és a bázisvektorok képeit egymás mellé írjuk.
Mivel végtelen sok bázis van -ben, ezért ugyanannak a lineáris leképezésnek végtelen sok mátrixa van.
A lineáris leképezésnek a bázisban felírt mátrixa
Egy másik bázisban felírt mátrixa pedig
A két mátrix közötti átjárást az alábbi tétel biztosítja:
Itt az új bázisra való áttérés mátrixa:
Ez a bizonyos mátrix tehát egyszerűen úgy keletkezik,
hogy fogjuk az új bázisvektorokat és leírjuk egymás mellé.
Ha és olyan mátrixok, hogy létezik egy
mátrix, úgy, hogy
akkor az előző tétel alapján és mindketten ugyanannak a leképezésnek a mátrixa, csak más-más bázisban felírva.
Ezt a tényt úgy nevezzük, hogy a két mátrix egymáshoz hasonló.
és mátrixok hasonlók, vagyis , ha létezik olyan mátrix, amire
Ha még emlékszünk rá, az mátrix akkor diagonalizálható, ha létezik n darab független sajátvektora, vagyis sajátvektorokból álló bázisa és a diagonalizáló mátrix éppen a sajátvektorok egymásmellé írásából kaptuk.
Na ez nem más, mint az iménti új bázisra való átállás tétele:
ahol sajátvektorokból álló mátrix
Ezek szerint bármely mátrix hasonló a diagonális alakjával:
.
Ha pedig van egy másik mátrix, amelynek szintén létezik diagonális alakja és
akkor ebből következik, hogy .
Az állítás megfordítása is igaz, vagyis megállapíthatjuk, hogy ha és mindketten diagonalizálható mátrixok, akkor
Lássunk néhány példát!
Itt vannak ezek a mátrixok, a feladatunk pedig az, hogy döntsük el melyek hasonlóak közülük.
Próbáljuk meg előállítani a diagonális alakjukat, mert ha ugyanaz a diagonális alak,
akkor hasonlóak.
Előfordulhat köztük olyan mátrix is, amelyiknek nincs diagonális alakja,
de majd ott is biztosan történni fog valami. Szóval kezdjük el.
Az mátrix diagonális alakjával kezdjük. Kiszámoljuk a sajátértékeket:
Úgy tűnik van három különböző sajátérték,
mivel pedig különböző sajátértékekhez mindig
különböző sajátvektorok tartoznak, van három
független sajátvektor.
Így hát diagonalizálható.
Jöhet a diagonális alakja.
Ezzel nem lesz sok dolgunk, mert eleve diagonális mátrix.
Kiemelünk 3-at
sőt inkább legyen -3
és aztán is kiemelhető
Úgy tűnik van három különböző sajátérték, mivel pedig különböző sajátértékekhez mindig különböző sajátvektorok tartoznak, van három független sajátvektor.
Így hát diagonalizálható.
És itt van még ez a is.
A determinánst a legalsó sor szerint fejtjük ki
Ez az egész nulla, úgyhogy talán hagyjuk is.
Nem tudunk semmit kiemelni, így hát felbontjuk a zárójeleket.
és összevonunk
végül kiemelünk
A sajátértékek:
Itt is van három különböző sajátérték, mivel pedig
különböző sajátértékekhez mindig különböző saját-
vektorok tartoznak, van három független sajátvektor.
Így hát is diagonalizálható.
Lássuk a hasonló mátrixokat!
így hát három mátrix van, amelyek ugyanannak a leképezésnek a mátrixai,
csak más-más bázisban felírva, a negyedik mátrix viszont eltérő.
A mátrixok teljesen ártalmatlan teremtményei a matematikának.
Egy -as mátrix tulajdonképpen nem más, mint egy táblázat, ami n darab sorból és k darab oszlopból áll.
A mátrixokat az ABC nagy betűivel jelöljük. Itt van például ez:
Ez egy (2X3)-as mátrix.
A mátrixok elemeit kettős indexezéssel látjuk el. Az elemeknek van egy sorindexük,
és egy oszlopindexük.
A mátrixok elemeit kettős indexezéssel látjuk el. Az elemeknek van egy sorindexük,
és egy oszlopindexük.
Egy -as mátrix, ami n darab sorból és k darab oszlopból áll,
tehát valahogy így néz ki:
A mátrixok marhára hasznosak számunkra, erről fog szólni lényegében az egész lineáris algebra témakör.
Mielőtt azonban hasznosságukról személyesen is megbizonyosodhatnánk, előbb nézzük meg milyen műveleteket végezhetünk velük.
1.SKALÁRSZOROS
A skalár nem egy betegség, azt jelenti, hogy valamilyen szám, legtöbbször valós szám.
2.ÖSSZEADÁS
Egy -as mátrixhoz csak egy másik -as mátrixot adhatunk hozzá.
3.SZORZÁS
Na ez a legizgalmasabb.
Egy -as mátrixszal csak egy -es mátrixot szorozhatunk.
A szorzat mátrixnak annyi sora lesz, mint A-nak és annyi oszlopa, mint B-nek, elemei pedig úgy keletkeznek, hogy az A egyik sorát szorozzuk B-nek egy oszlopával
Jön a trükk, tudományos nevén Falk-séma. Ennek az a lényege, hogy a mátrixokat sarkosan helyezzük el, valahogy így:
Kész a szorzat!
A mátrixok szorzásának egyik érdekes tulajdonsága,
hogy nem kommutatív.
Ha például megpróbáljuk ezt a szorzást fordítva elvégezni,
kiderül, hogy nem is lehet.
Ismerkedjünk meg néhány speciális mátrixfajtával.
KVADRATIKUS MÁTRIX
négyzetes mátrix vagyis ugyanannyi sora van, mint oszlopa
példa:
DIAGONÁLIS MÁTRIX
olyan kvadratikus mátrix, aminek a főátlóján kívüli elemek nullák
példa:
A diagonális mátrixoknak tehát csak a főátlója érdekes, mivel az összes többi elem nulla.
Ezért aztán vannak akik csak a főátló elemeket írják le. Ez a fura jel
valójában egy diagonális mátrix
EGYSÉGMÁTRIX
olyan mátrix, ami azt tudja, hogy bármely mátrixra
az egységmátrixok olyan diagonális mátrixok, aminek minden főátló-eleme egy
INVERZ MÁTRIX
jele , és ez egy olyan mátrix, ami azt tudja, hogy
(jobb inverz) (bal inverz)
Később látni fogjuk, hogy nem is olyan egyszerű elővarázsolni egy mátrix inverzét.
Ez az inverz dolog valós számoknál sokkal könnyebb, ott ugyanis
inverze mert ugye
inverze mert ugye
TRANSZPONÁLT
a mátrix sorainak és oszlopainak a felcserélése, jele vagy
SOR OSZLOP OSZLOP SOR
példa:
vagy
Azokat a mátrixokat, amelyek transzponáltja önmaga szimmetrikus mátrixnak nevezzük.
Itt van például egy szimmetrikus mátrix:
Mindezek jelenleg nem tűnnek túl izgalmasnak, de hamarosan majd elérkezik az idő, amikor kelleni fognak.
Most viszont jöjjenek a vektorok!
Azokat a mátrixokat, amiknek csak egyetlen oszlopuk van, vektoroknak nevezzük.
A vektorokat az abc kis betűivel jelöljük és aláhúzzuk őket.
Itt van például két vektor:
Az vektor -es vektor, a pedig -es, de a megemlítése teljesen felesleges, hiszen éppen azért nevezzük őket vektoroknak, mert csak egyetlen oszlopuk van.
Bőven elegendő tehát csak arról említést tenni, hogy hány darab számot tartalmaz maga a vektor. Ezeket a számokat a vektor koordinátáinak nevezzük.
Megnyugtató, hogy amit a geometriában vektornak tekintünk,
és amit az imént vektorként definiáltunk megfeleltethetők egymásnak.
Ha ugyanis veszünk mondjuk a térben három egyenest úgy,
hogy egymásra merőlegesek legyenek majd pedig
ellátjuk őket egy skálázással, akkor a geometriai vektorok
egyértelműen megfeleltethetők számhármasoknak.
Vagyis amikor vektorokról beszélünk, egyszerre gondolhatunk
-es mátrixokra és geometriai alakzatokra.
Lássuk milyen műveleteket tudunk vektorokkal végezni.
MŰVELETEK VEKTOROKKAL
1. SKALÁRSZOROS
példa:
2. ÖSSZEADÁS
példa:
TULAJDONSÁGOK:
kommutatív:
asszociatív:
3. SZORZÁS
skaláris szorzat: diadikus szorzat:
TULAJDONSÁGOK:
kommutatív:
nem asszociatív:
és
és
a skaláris szorzat:
diadikus szorzat:
TULAJDONSÁGOK:
nem kommutatív
nem asszociatív
példa:
és
a diadikus szorzat:
A kétféle szorzás közül a skaláris szorzat
nekünk sokkal hasznosabb lesz, így hát
elbúcsúzunk a diadikus szorzattól.
A skaláris szorzatra pedig bevezetünk
egy egyszerű jelölést.
Ezzel megspóroltunk néhány *-ot.
De lássuk mire jó még a skaláris szorzat.
Van itt néhány mátrix és vektor és el kéne végezni velük pár műveletet.
Hát menjünk szépen sorban.
Ezzel van egy kis probléma. nem elvégezhető.
Mátrixok hatványozására sajnos nincsen semmilyen trükk, tehát ha ki kell számolnunk ennek a mátrixnak a négyzetét, akkor négyzetre emelést úgy tudjuk elvégezni, hogy megszorozzuk önmagával.
Ha mondjuk a negyedik hatványára lenne szükség, akkor az bizony elég sokáig tart.
De szerencsére csak a négyzete kell.
Már csak van hátra. Ezzel marhanagy mázlink van, ugyanis egy diagonális mátrix.
A diagonális mátrixokat pedig könnyű hatványozni, egyszerűen a főátló elemeit külön-külön hatványozzuk.
Ez a módszer sajnos csak diagonális mátrixokra működik, de ott szuperül.
Ha négyszer egymás után összeszoroznánk, persze akkor is ugyanez jönne ki,
csak kicsit lassabban, akinek van kedve próbálja ki és nézze meg.
A vektorok skaláris szorzása azon kívül, hogy remek szórakozás, arra is jó, hogy kiszámoljuk, két vektor mekkora szöget zár be egymással.
Van ugyanis a skaláris szorzásnak egy másik képlete is:
ahol a két vektor által bezárt szög,
vagyis az vektor hossza
vagyis a vektor hossza
A vektorok közti szöget úgy tudjuk kiszámolni, ha mindkét módon felírjuk a skaláris szorzatukat.
Itt van például
A skaláris szorzat a korábbi képlettel:
A skaláris szorzat az új képlettel:
Nézzük meg ennek a -as mátrixnak a sajátértékeit
és sajátvektorait.
A determinánst az első sora szerint fejtjük ki:
Az első sor elemeit a sakktábla-szabály alapján váltakozó előjellel kell venni.
Kifejtjük a 2x2-es determinánsokat is.
És kicsit összevonunk. Sőt nem is olyan kicsit.
Valahogyan meg kéne oldani ezt az egyenletet, hogy megkapjuk az egyenlet megoldásait, a sajátértékeket.
A karakterisztikus egyenlet megoldásai lesznek majd a sajátértékek.
Feltéve, hogy sikerül megoldanunk az egyenletet.
Íme, három hasznos megoldási ötlet ilyen típusú egyenletek megoldásához:
kiesik a konstans tag
Mindhárom esetben egy olyan szorzatot kaptunk, ami egy elsőfokú és egy másodfokú egyenlet szorzata, azokat pedig már külön-külön meg tudjuk oldani.
Vannak persze olyan harmadfokú egyenletek is, amiket nehezebb megoldani,
de szerencsére ezek általában elkerülnek bennünket.
Lássuk, a három közül melyik módszer válik be a mi egyenletünknél.
Emeljünk ki 2-t.
A kettes módszer itt nem működik,
ezért a fortélyos hármas módszert próbáljuk meg, hátha beválik.
A másodfokú részt felbontjuk,
aztán pedig megpróbáljuk szorzattá alakítani.
Van egy ilyen, hogy
emlékeztetőül:
A másodfokú izét szorzattá alakítjuk
Ez igazán remek, ugyanis most már ki lehet emelni,
aztán pedig hopp, már meg is oldottuk.
Itt összevonunk:
Három sajátérték van, ami valójában csak kettő,
mert a kétszeres sajátérték.
Jöhetnek a sajátvektorok!
Az egyenletrendszert a szokásos bázistranszformációval oldjuk meg.
Akinek esetleg elhalványultak az ezzel kapcsolatos emlékei, nézze meg a bázistranszformációról szóló témaköröket.
Belerakjuk a -et
Bázistranszformációval oldjuk meg:
Itt a bázistranszformáció elakad.
Ha két x is fönt mard,
az egyik t, a másik s
Most már itt se folytatható.
Itt csak egy x maradt fönt, de mivel a és
már foglalt, legyen .
A sajátvektor ha
ahol
És a -et
Bázistranszformációval oldjuk meg:
A sajátvektor ha
Nézzük meg ennek a -as mátrixnak a sajátértékeit
és sajátvektorait.
A determinánst az első sora szerint fejtjük ki:
Az első sor elemeit a sakktábla-szabály alapján váltakozó előjellel kell venni.
Kifejtjük a 2x2-es determinánsokat is.
És kicsit összevonunk. Sőt nem is olyan kicsit.
Valahogyan meg kéne oldani ezt az egyenletet, hogy megkapjuk az egyenlet megoldásait, a sajátértékeket.
A karakterisztikus egyenlet megoldásai lesznek majd a sajátértékek.
Feltéve, hogy sikerül megoldanunk az egyenletet.
Íme, három hasznos megoldási ötlet ilyen típusú egyenletek megoldásához:
kiesik a konstans tag
Mindhárom esetben egy olyan szorzatot kaptunk, ami egy elsőfokú és egy másodfokú egyenlet szorzata, azokat pedig már külön-külön meg tudjuk oldani.
Vannak persze olyan harmadfokú egyenletek is, amiket nehezebb megoldani,
de szerencsére ezek általában elkerülnek bennünket.
Lássuk, a három közül melyik módszer válik be a mi egyenletünknél.
Emeljünk ki 2-t.
A kettes módszer itt nem működik,
ezért a fortélyos hármas módszert próbáljuk meg, hátha beválik.
A másodfokú részt felbontjuk,
aztán pedig megpróbáljuk szorzattá alakítani.
Van egy ilyen, hogy
emlékeztetőül:
A másodfokú izét szorzattá alakítjuk
Ez igazán remek, ugyanis most már ki lehet emelni,
aztán pedig hopp, már meg is oldottuk.
Itt összevonunk:
Három sajátérték van, ami valójában csak kettő,
mert a kétszeres sajátérték.
Jöhetnek a sajátvektorok!
Az egyenletrendszert a szokásos bázistranszformációval oldjuk meg.
Akinek esetleg elhalványultak az ezzel kapcsolatos emlékei, nézze meg a bázistranszformációról szóló témaköröket.
Belerakjuk a -et
Bázistranszformációval oldjuk meg:
Itt a bázistranszformáció elakad.
Ha két x is fönt mard,
az egyik t, a másik s
Most már itt se folytatható.
Itt csak egy x maradt fönt, de mivel a és
már foglalt, legyen .
A sajátvektor ha
ahol
És a -et
Bázistranszformációval oldjuk meg:
A sajátvektor ha
Ha egy -es mátrixnak van darab független sajátvektora, akkor létezik a mátrixnak egy úgynevezett diagonális alakja.
A diagonális alak így néz ki:
a főátlóban vannak a sajátértékek és az összes többi elem nulla.
A diagonális alakot a következő módon állítjuk elő:
itt vagyis egyszerűen úgy keletkezik, hogy a sajátvektorokat fogjuk, és leírjuk egymás mellé.
Nézzünk meg erre egy példát!
Állítsuk elő ennek a -as mátrixnak a diagonális alakját.
1. A KARAKTERISZTIKUS EGYENLET FELÍRÁSA
A főátló elemeiből kivonogatjuk a -kat, és vesszük a determinánsát:
A determinánst az első sora szerint fejtjük ki:
2. A KARAKTERISZTIKUS EGYENLET MEGOLDÁSAI A SAJÁTÉRTÉKEK
Most három sajátérték van, ; és .
Mindhárom sajátértékhez megkeressük a hozzá tartozó sajátvektort.
3. A SAJÁTÉRTÉKEKHEZ TARTOZÓ SAJÁTVEKTOROK MEGKERESÉSE
A sajátvektorokat úgy kapjuk meg, ha megoldjuk az
egyenletrendszert:
Az egyenletrendszereket bázistranszformációval oldjuk meg.
Akinek a bázistranszformációval kapcsolatos emlékei sajnálatos módon
elhalványultak, az nézze meg az erről szóló részt.
A bázistranszformáció elakadt, -et nem tudjuk lehozni, így elnevezzük –nek.
Leolvassuk a megoldást.
A sajátértékhez tartozó sajátvektor:
ahol
Most jöhet a többi sajátvektor. Megint az egyenletrendszert kell megoldanunk:
Belerakjuk a -t
Bázistranszformációval oldjuk meg:
A sajátértékhez tartozó sajátvektor:
ahol
és a -et
Bázistranszformációval oldjuk meg:
A sajátértékhez tartozó sajátvektor:
ahol
Úgy tűnik van három független sajátvektor, tehát a mátrix
diagonalizálható, a diagonalizáló mátrix pedig
A diagonális alakot az eredeti mátrixból a diagonalizáló mátrix
segítségével állítjuk elő:
A szorzásokat elvégezni azonban felesleges, mert a diagonális alak mindig úgy néz ki, hogy a főátlóban vannak a sajátértékek, az összes többi elem pedig nulla.
A sajátértékeket már régóta tudjuk
A diagonális alak tehát:
Van egy leképezés, amit már réges-régóta ismerünk, mert minden általános iskolában tanítják.
Ez a leképezés a tengelyes tükrözés.
Na persze a tükrözés mátrixát már nem tanítják az általános iskolában…
Az x tengelyre tükrözés mátrixát úgy kapjuk, hogy vesszük a bázisvektorok képeit…
És ezeket szépen egymás mellé írjuk egy mátrixba.
Ez a mátrix azt is elárulja, hogy mi lesz egy vektor képe a tükrözés hatására.
Van itt például ez a vektor…
És a tükörképének a koordinátáit úgy kapjuk meg…
hogy a tükrözés mátrixát megszorozzuk a vektorral.
Az y tengelyre tükrözés mátrixa hasonló módon keletkezik…
Itt vannak a bázisvektorok…
És megnézzük, hogy melyikkel mi fog történni.
A dolog akkor válik izgalmasabbá, hogyha valamilyen ferde tengelyre tükrözünk.
Nézzük meg például ezt…
Amikor az tengelyre tükrözünk, az x és y koordináták helyet cserélnek…
Lássuk, mi történik ezzel a vektorral:
A tükörképét most is úgy kapjuk, hogy megszorozzuk szépen a tükrözés mátrixával…
És íme a tükörkép.
A koordináták itt is szépen fölcserélődtek.
De mi van akkor, ha az egyenesre tükrözünk?
Ez már sokkal izgalmasabb és ránézésre nem is lehet úgy kitalálni, mint az eddigieket.
Azzal kezdjük, hogy kiderítjük mi lehet ennek az egyenesnek a normálvektora.
Most, hogy ez megvan, itt jön egy kis geometriai bűvészkedés.
Kiszámoljuk a vektornak az vektorra eső merőleges vetületét…
egy skaláris szorzat segítségével.
Meg is van.
A dolog olyankor is működik, ha a vektorok szöge egy kicsit nagyobb…
Csak ilyenkor bejön ide ez a mínuszjel.
Hogyha szeretnénk tükrözni a vektort az egyenletű egyenesre…
Akkor egyszerűen csak fogjuk ezt az vektort…
Elosztjuk a saját hosszával, hogy egységnyi hosszú legyen…
Aztán pedig beszorozzuk q-val.
Pontosabban inkább a kétszeresével.
Hogyha ezt a vektort most hozzáadjuk az eredeti -hez…
Akkor meg is kapjuk a tükörképét.
Kizárólag esztétikai okokból ezt még átírjuk így…
Végül kiemeljük a vektort.
Hát igen, hogyha -t sajátmagából emeljük ki, az az egységmátrix lesz…
Meg is van a tükrözés mátrixa.
Az origón átmenő a normálvektorú egyenesre tükrözés mátrixa:
Hogyha már ennyit szenvedtünk vele, akkor próbáljuk is ki.
Meg is van a tükrözés mátrixa.
Ezt a mátrixot csak úgy ránézésre már valóban nem találtuk volna ki…
És most lássuk, mi történik ezzel a vektorral, ha tükrözzük az egyenesre.
Már jön is:
Van itt ez a 90o-os forgatás…
Aminek a mátrixát a szokásos módon kapjuk meg.
Vesszük az egyik bázisvektort…
és megnézzük, hogy a forgatás hatására mi lesz belőle.
Aztán vesszük a másikat is…
És meg is van a forgatás mátrixa.
Ha nem 90 fokkal, hanem 180 fokkal forgatunk…
Azt úgy hívjuk, hogy középpontos tükrözés.
A középpontos tükrözés mátrixa:
Ez a mátrix éppen az egységmátrix mínuszegyszerese.
A középpontos tükrözés úgy működik, hogy minden vektornak…
…elkészíti az ellentettjét.
És most nézzük, hogyan néz ki a forgatás mátrixa tetszőleges szögre.
is működik.
Hogyha az első bázisvektort elforgatjuk szöggel…
Akkor a koordinátái…
Hát, igen, az irányszögű egységvektor első koordinátája a koszinusz…
A második pedig a szinusz.
Eddig jó.
A második bázisvektor már izgalmasabb…
És végre kiderül, hogy ez a rengeteg trigonometrikus azonosság…
Még jó is valamire.
Meg is van az
Íme, az szögű forgatás mátrixa.
Most pedig nézzük, hogyan működik mindez térben.
Az origó körüli forgatás térbeli megfelelője egy tengely körüli forgatás lesz.
Hogyha például az x tengely körül forgatunk, akkor a forgatás a másik két koordinátatengely síkjában történik.
Az x, y és z tengelyek körüli forgatások mátrixai:
A forgatások mindhárom esetben egy síkban történnek.
A három tengely közül mindig az egyik tengely az, ami körül forgatunk…
és mindig a másik két tengely által kifeszített síkban.
Ezeket a koordinátasíkokban történő forgatásokat Givens forgatásnak nevezzük.
A dolog akkor válik izgalmasabbá, ha mindezt a négydimenziós térben csináljuk…
Az x és y tengelyek síkjában történő szögű forgatás mátrixát már ismerjük.
Éppen itt is van:
Hogyha van egy harmadik koordinátatengely is…
Az mindegy, a harmadik koordinátával a forgatás nem csinál semmit.
Sőt, tulajdonképpen lehet akárhány koordináta…
Egy négydimenziós térben az első két koordinátatengely síkjában történő forgatás mátrixa így néz ki:
És lehet akár ötödik vagy hatodik dimenzió is.
A forgatást pedig bármely két koordinátatengely síkjában végezhetjük…
Ha például a második és a harmadik tengely síkjában forgatunk…
Akkor a mátrix ilyen lesz:
Hogyha pedig a második és a negyedik tengely síkjában…
akkor ilyen.
Ezeket a forgatásokat, amelyeket két tetszőlegesen választott koordinátatengely síkjában végzünk Givens forgatásnak nevezzük.
Givens egyébként egy ember volt…
A Givens forgatások mátrixa tulajdonképpen egy egységmátrix…
Egykét apró módosítással.
Az i és j koordinátatengelyek síkjában történő Givens forgatás mátrixát úgy kapjuk…
Hogy arra a négy helyre, ahol az egységmátrix i-edik és j-edik sora és oszlopa metszi egymást…
Beírjuk szépen az alfa szögű forgatás mátrixának elemeit.
A Givens forgatásokat arra fogjuk használni, hogy mátrixok bizonyos elemeit kinullázzuk vele.
És hirtelen valamilyen különös vágyat érzünk arra, hogy ez az elem itt nulla legyen.
A Givens forgatásokkal mindez lehetséges…
Az első két koordinátatengely síkjában fogunk forgatni.
Ez pedig itt a forgatás mátrixa:
Egy olyan forgatás kéne, ami ezt a vektort…
szépen elforgatja az x tengely vonalába…
A forgatás szöge .
De van itt még egy kis gond.
A forgatás iránya.
Nekünk éppen az ellenkező irány kéne.
Mondjuk, ezen könnyen lehet segíteni…
Az szöget kicseréljük az ellentettjére, és a forgatás iránya máris megváltozik.
Végül vannak itt ezek az azonosságok…
Az teljesen mindegy, hogy mekkora az szög…
Berakjuk szépen ezeket ide a mátrixba.
És meg is vagyunk.
Hogyha ezt a mátrixot megszorozzuk az A mátrixszal…
Akkor minden álmunk valóra válik.
Ezzel a módszerrel tovább tudjuk folytatni a kinullázást, és az A mátrixot felső háromszögmátrixszá tudjuk alakítani.
Bizonyos mátrixok esetében ez az eljárás a leghatékonyabb különböző mátrixfelbontások végrehajtásához.
A tengelyes tükrözés térbeli megfelelője a síkra tükrözés.
Hát igen, itt már valódi házakat tükrözünk…
Nézzük meg például az x és y tengelyek által kifeszített síkra tükrözés mátrixát.
Itt vannak a bázisvektorok.
És a tükrözés hatására…
Meg is van a tükrözés mátrixa.
Ezt még nem volt nehéz kitalálni.
Egy fokkal izgalmasabb kérdés, hogy mi lehet az síkra tükrözés mátrixa.
Ehhez már kicsivel jobb térlátásra van szükség.
A z tengely benne van a síkban…
Így aztán a tükrözés a z tengelyen lévő vektorokkal nem csinál semmit.
Az x és y tengelyt pedig a tükrözés fölcseréli.
És íme, itt a tükrözés mátrixa.
De mi történik akkor, ha egy ferde síkra tükrözünk?
Mondjuk erre a síkra itt:
A síkbeli esetben volt már erre egy kis képletünk…
Éppen itt is van:
Ez volt az origón átmenő normálvektorú egyenesre tükrözés mátrixa a síkban.
Térben minden pontosan ugyanígy fog történni.
Hogyha egy origón átmenő sík normálvektora az vektor…
…akkor az erre a síkra tükrözés mátrixa:
Ezeket a tükrözéseket Householder-tükrözésnek nevezzük.
És most lássuk a tükrözés mátrixát.
Ehhez mindössze a sík normálvektorára van szükség.
Meg egy kis számolásra…
Az origón átmenő normálvektorú síkra történő tükrözés mátrixa:
Householder tükrözés:
Meg is van.
A Householder-tükrözéseket arra tudjuk használni, hogy egy vektort egy általunk kiszemelt másik vektorrá transzformáljunk át.
Mindjárt meg is látjuk, hogy mindezt hogyan.
Keressük azt a Householder-tükrözést, ami az vektort a vektorba transzformálja.
Na, ilyen tükrözés nem lesz, a két vektor ugyanis nem egyforma hosszú…
Ahhoz, hogy a Householder-tükrözéssel egy vektort egy másik vektorba tudjunk transzformálni az kell, hogy a két vektor hossza egyforma legyen.
Hát jó…
Vannak itt ezek az egyforma hosszú vektorok.
Keressük azt a Householder-tükrözést, ami az vektort a vektorba transzformálja.
Elkészítjük ezt a vektort:
Ez lesz a tükröző sík normálvektora…
És most jöhet a Householder-mátrix:
Íme, a Householder-mátrix:
Hogyha tükrözzük vele az vektort…
Akkor tényleg a vektort kapjuk.
Ha pedig a vektort tükrözzük…
Akkor az vektor jön ki.
A szokásos háromdimenziós térben az origón átmenő normálvektorú síkra tükrözés mátrixa egy Householder-mátrix.
Éppen itt is van:
A dolog tovább általánosítható négydimenziós, sőt n dimenziós térre.
Az normálvektorú hipersíkra tükrözés mátrixa is egy pontosan ugyanilyen Householder-mátrix lesz.
Az normálvektorú hipersíkra tükrözést Householder-tükrözésnek nevezzük. A tükrözés mátrixa:
A Householder-tükrözéseket arra fogjuk használni, hogy egy vektort egy általunk kiszemelt másik vektorrá transzformáljunk át.
Hogyha és különböző vektorok, és teljesül rájuk, hogy akkor létezik olyan Householder-tükrözés, ami az vektort a vektorba transzformálja.
ahol
Itt van például ez a mátrix.
És hirtelen leküzdhetetlen vágyat kezdünk érezni, hogy ezeket az elemeit kinullázzuk.
A Householder-tükrözés valóra váltja álmainkat.
Legalábbis az ilyen jellegűeket…
Vesszük ezt a vektort:
És szépen áttranszformáljuk ebbe a másikba.
Az első koordináta valami x, ez mindegy mennyi, a másik kettő pedig nulla, ahogyan ennek lennie kell.
Egyedül arra vigyázzunk, hogy a két vektor azonos hosszú legyen.
És most elkészítjük a Householder mátrixot.
Hogyha ezt beszorozzuk az eredeti A mátrixszal…
Akkor meg is van a kinullázás.
Egy újabb Householder-tükrözéssel pedig…
Itt is nullát tudunk gyártani.
Ezzel a módszerrel az A mátrixot felső háromszögmátrixszá tudjuk alakítani.
Ez pedig éppen jól jön akkor, ha szeretnénk egy trópusi szigeten tölteni a vakációt…
Ja, ahhoz mondjuk pont nem. Egyenletrendszerek megoldáshoz viszont igen.
VEKTORTEREK
Elérkezett az idő, hogy tisztázzunk néhány fontos fogalmat.
Az első és legfontosabb fogalom a vektortér fogalma, ami tulajdonképpen vektoroknak egy olyan halmaza, amely teljesít néhány speciális tulajdonságot.
Kétféle műveletet értelmezünk, egy összeadást és egy számmal való szorzást.
Az összeadás művelet szereplői vektorok, míg a számmal való szorzásnál egy vektort szorzunk meg egy számmal.
Ezek a bizonyos számok lehetnek valós számok, ilyenkor a vektorteret valós számok feletti vektortérnek nevezzük, de lehetnek például komplex számok is, és akkor a vektortér komplex feletti.
A kétféle műveleten kívül a vektortérben egyéb művelet nincsen, tehát nem értelmezzük a vektorok egymással való összeszorzását, sem a skaláris szorzatot sem pedig a diadikus szorzatot.
A kétféle művelettel kapcsolatban teljesülnie kell további tulajdonságoknak, amiket vektortér-axiómáknak nevezünk. Ezek jönnek most.
A nem üres halmazt vektortérnek nevezzük a valós számok felett, ha
a halmazon értelmezve van egy összeadás nevű művelet, úgy, hogy minden -beli és vektorhoz hozzárendelünk egy vektort, ami szintén eleme -nek.
1. Az összeadás kommutatív: bármely ; -beli vektorra
2. Az összeadás asszociatív: bármely ; ; -beli vektorra
3. Létezik nullelem: van olyan -beli vektor, hogy bármely -beli vektorra
4. Létezik ellentett: bármely -beli vektorra létezik olyan -bel vektor, hogy
és értelmezve van egy skalárral való szorzás nevű művelet, úgy, hogy minden -beli vektorhoz és bármely valós számhoz hozzárendelünk egy vektort, ami szintén -beli.
5. A skalárszoros asszociatív: bármely -beli vektorra és ; skalárra
6. A skalárszoros disztributív a vektorokra: bármely ; -beli vektorra és skalárra
7. A skalárszoros disztributív a skalárokra bármely -beli vektorra és ; skalárra
8. Egységszeres: bármely -beli vektorra és az 1 valós számra
A valós számok feletti vektorteret -el szokás jelölni, ahol ez a bizonyos n a vektorok koordinátáinak a számára utal.
Egy síkban elhelyezkedő vektorok két koordinátával is megadhatók, ezért minden sík egy vektortér.
A térbeli vektoroknak már három koordinátájuk van, így a tér .
Vannak persze háromnál több koordinátával rendelkező vektorok is, ezek geometriai megfelelői azonban a mi kis háromdimenziós világunkban nehezen elképzelhetők.
Érdemes azonban elgondolkodni azon, hogy egy sík vektorainak nem szükségszerűen csak két koordinátájuk lehet.
Megadhatjuk őket három vagy akár négy koordinátával is legfeljebb bizonyos koordináták nullák. A koordináták száma tehát csak a lehetőséget teremti meg az új irányok számára.
Ez elvezet bennünket két nagyon fontos fogalomhoz is, az egyik a dimenzió a másik az altér.
Az altér arról szól, hogy nem használjuk ki a vektorok összes koordinátáját, míg a dimenzió éppen a maximálisan kihasználható koordináták száma.
Például azok a vektorok -ban, amelyek harmadik koordinátája nulla egy altér, ráadásul kétdimenziós altér, mert két koordinátát használunk.
Mindezt jóval precízebben és matematikailag
megfogható módon is képesek leszünk meg-
fogalmazni, de ehhez előbb szükségünk
van néhány alapvető fontosságú
fogalom tisztázására.
Ezek jönnek most.
LINEÁRISAN FÜGGETLEN ÉS LINEÁRISAN ÖSSZEFÜGGŐ VEKTOROK
Kezdjük két izgalmas definícióval. Először lássuk mit is akarnak ezek pontosan, aztán rögtön nézünk is rájuk példákat, hogy mindez érthető is legyen.
A vektorok lineárisan függetlenek, ha
csak úgy teljesül, ha minden
A vektorok lineárisan összefüggők, ha
úgy is teljesül, hogy van olyan
Nézzünk ezekre példákat! Itt vannak mondjuk ezek a vektorok:
Nézzük meg, hogy ezek a vektorok melyik típusba tartoznak, vagyis hogyan lesz
Ha mindegyik akkor persze a nullvektort kapjuk.
Az már érdekesebb, hogy ha akkor
nos akkor is a nullvektort kapjuk.
Tehát úgy is ki tud jönni a nullvektor, ha nem minden , sőt most éppen egyik se. Ilyenkor azt mondjuk, hogy ezek a vektorok lineárisan összefüggők.
Ennek az a nagyon egyszerű magyarázata, hogy a harmadik vektor az első kettő összege.
Vagyis a harmadik vektor a másik két vektor segítségével előállítható, összefügg velük.
Ezt a tényt nevezzük úgy, hogy a vektorok lineárisan összefüggők és ezért kaphatunk nullvektort úgy, hogy nem mindegyik .
Vannak aztán olyan vektorok is, amik nem függnek össze.
Nézzük meg, mi a helyzet ezekkel:
Az, hogy ha mindegyik vektorból nullát veszünk, most is nullvektort kapunk nem túl meglepő.
Ami érdekesebb, hogy ezúttal semmilyen más esetben nem kaphatunk nullvektort.
Ha például az első vektorból nem nullát veszünk, biztosan nem kaphatunk nullvektort.
Nézzük meg! Vegyünk belőle mondjuk 6-ot.
A második és harmadik vektor első koordinátája nulla, ők tehát nincsenek hatással az első koordináta alakulására. A második és harmadik vektorból így vehetünk bármennyit, az első koordináta így is úgy is az lesz, hogy 6.
Ha tehát nullvektort szeretnénk, az első vektorból mindenképpen nullát kell vennünk.
Aztán jön a második vektor. Ha nem nullát veszünk belőle, akkor a második koordinátával adódnak problémák.
Az első és harmadik vektorok ugyanis nincsenek hatással a második koordináta alakulására.
És hasonló a helyzet a harmadik vektorral is. Ezek a vektorok tehát lineárisan függetlenek.
Csak úgy kaphatunk nullvektort, ha mindegyikből nullát veszünk.
Megkérdezhetjük persze, hogy tulajdonképpen miért ennyire fontos ez, hogy mindenféle vektorokból miként állítható elő a nullvektor. A válasz hamarosan kiderül. Nézzük meg a következő képsort!
Egy V vektortérben a vektorok generátor-rendszert alkotnak,ha minden
vektor a V vektortérben előáll alakban.
Vegyük például az vektorteret, vagyis a hétköznapi értelemben vett teret.
Ebben a vektortérben generátor-rendszert alkot a
mert segítségükkel minden vektor előáll.
Nézzük meg! Van itt mondjuk egy vektor
ami valóban előállítható a vektorokkal.
Bármilyen vektor előállítható. Ha mondjuk
Akkor íme, már meg is van:
Ha ezekhez a vektorokhoz egy újabb vektort hozzáveszünk, akkor ugyanúgy generátor-rendszert kapunk.
Vegyük hozzá mondjuk ezt:
Ha a vektort eddig elő tudtuk előállítani, akkor ezután is elő tudjuk:
Egyszerűen nullát veszünk az új vektorból, így olyan,mintha az új vektor ott se volna.
Ha viszont az eredeti generátorrendszerből egy vektort elveszünk, akkor az már nem generátor-rendszer.
Próbáljuk csak meg a vektort a megmaradt két vektorból előállítani. Nem fog menni.
Érdemes tehát megjegyezni, hogy egy generátor-rendszerhez újabb vektorokat hozzávéve ismét generátor-rendszert kapunk, ha viszont elveszünk belőle vektorokat, akkor már nem biztos.
A kérdés az, hogy -ban hány darab vektor lehet független és hány darab vektor lehet generátor-rendszer. Erről szól a következő remek táblázat.
vektorok
száma
megadható-e ennyi vektor úgy, hogy független legyen
-ban
megadható-e ennyi vektor úgy, hogy generátor-rendszer legyen -ban
1
2
3
4
5
Egy darab vektor biztosan megadható úgy, hogy független legyen, viszont nem elegendő ahhoz, hogy generáljon.
Ő egymaga, csak egy egyenest képes előállítani.
Két vektor is megadható úgy, hogy független legyen,viszont ezek sem generátor-rendszer.
Ezek ketten egy síkot feszítenek ki.
Vagyis a sík minden vektorát előállítják, de mást nem.
Három vektor még mindig megadható úgy, hogy független legyen, és ahogyan ezt már az előbb láttuk generátor-rendszer is lesz.
Ez a három vektor kifeszíti a teret.
Most vegyünk egy negyedik vektort is.
Mivel az eddigi három vektor generátor-rendszer, így bármi is ez a negyedik vektor, azt ők képesek előállítani.
Vagyis ezek négyen már nem függetlenek, de továbbra is generátor-rendszer.
Ugyanez a helyzet,ha hozzáveszünk még egy ötödik vektort is.
-ban pontosan három vektor adható meg úgy, hogy azok még éppen függetlenek legyenek,de már generáljanak.
A független generátor-rendszert nevezzük bázisnak.
Egy vektortér dimenziója a bázis elemszáma. Így jutunk el tudományosan arra az álláspontra, hogy a tér dimenziója éppen három.
Ha egy független rendszerből egy vagy több vektort elhagyunk,
független rendszert kapunk
(ha hozzáveszünk vektorokat, ki tudja, mi történik)
Ha egy generátor-rendszerhez egy vagy több vektort hozzáveszünk,
generátor-rendszert kapunk
(ha elveszünk vektorokat, ki tudja, mi történik)
Ha -ben van n darab független vektor, akkor az generátor-rendszer is
(mert bázis)
Ha -ben van n darab vektorból álló generátor-rendszer,
akkor ezek a vektorok függetlenek is
(mert bázis)
A bázis minden vektort egyértelműen állít elő, míg -ben azok a
generátor-rendszerek pedig, amelyek n-nél több vektorból állnak,
minden vektort végtelensokféleképpen
Az előzőekben megnéztük mit jelent az, hogy egy vektorrendszer független, mit jelent
az, hogy összefüggő.
Aztán megnéztük mi az a generátor-rendszer.
Kiderült, hogy ha egy generátor-rendszerhez egy vagy több vektort hozzáveszünk, szintén generátor-rendszert kapunk. Ha viszont elveszünk belőle vektorokat, akkor előbb utóbb már nem lesz generátor-rendszer.
Az is kiderült, hogy ha egy független rendszerből egy vagy több vektort elhagyunk, akkor továbbra is független rendszert kapunk, de ha újabb vektorokat veszünk hozzá, akkor előbb utóbb a vektorok már összefüggők lesznek.
Mindezt jól szemléltethetjük mondjuk az vektortérben,
vagyis a hétköznapi értelemben vett térben.
Ha egy független rendszerhez elkezdünk újabb vektorokat hozzávenni, az előbb utóbb összefüggő lesz.
Ha egy generátor-rendszerből elkezdünk vektorokat elhagyni, az előbb utóbb már nem lesz generátor-rendszer.
És van egy mágikus pont amikor már éppen elég vektorunk van ahhoz, hogy generáljanak, de még nincsenek túl sokan ezért függetlenek.
Ezt a független generátor-rendszert nevezzük bázisnak.
A bázis elemszámát pedig a vektortér dimenziójának.
Itt jön még egy fontos definíció, amit rangnak nevezünk.
Egy vektorrendszer rangja a benne lévő független vektorok
maximális száma.
-ban a rang például maximum három lehet.
A rang kiszámolására később remek módszereink lesznek majd, jelenleg csak kevésbé megnyugtató módon, ránézésre tudjuk megállapítani.
Van itt például ez a vektorrendszer:
A negyedik vektor az első kétszerese,
így legjobb esetben is három független
vektorunk van.
A harmadik vektor pedig az első kettő
összege, így már csak két független
vektor maradt.
Ezek már függetlenek, tehát a rang 2,
de később lesz egy igazán remek
technológiánk a rang kiszámolására.
Egy vektorrendszer rangja Itt jön még egy fontos definíció, amit rangnak nevezünk.
Egy vektorrendszer rangja a benne lévő független vektorok
maximális száma.
BÁZIS=FÜGGETLEN
GENERÁTOR-RENDSZER
A vektorok lineárisan függetlenek, ha
csak úgy teljesül, ha minden
A vektorok lineárisan összefüggők, ha
úgy is teljesül, hogy van olyan
Egy V vektortérben a vektorok
generátor-rendszer, ha minden vektor előáll
alakban.
Legyen vektorok.
Az alábbi állítások közül melyik igaz?
Ha lineárisan független, akkor
is lineárisan független.
Nézzük meg, hogy függetlenek-e.
Vegyük egy lineáris kombinációjukat:
Ha ez csak úgy teljesül, hogy mind nulla,
akkor függetlenek, ha úgy is lehetséges, hogy nem
mindegyik nulla, akkor összefüggők.
Vagyis az a kérdés, hogy mennyi .
Felbontjuk a zárójeleket :
Aztán összegyűjtjük hány darab , hány darab
és hány darab vektor van.
Mivel az vektorok lineárisan függetlenek,
itt egészen biztos, hogy minden együttható nulla, vagyis
[*]
Úgy tűnik mindegyike nulla, vagyis lineárisan függetlenek.
Ha generátor-rendszer,
akkor is az.
Az vektorok akkor generátor-rendszer,
ha minden vektort előállítanak:
A kérdés az, hogy ugyanez a előáll-e az
vektorokból is. Nézzük meg!
Felbontjuk a zárójeleket :
Aztán összegyűjtjük hány darab , hány darab
és hány darab vektor van.
A jelek szerint előáll.
Ha lineárisan független, akkor
is lineárisan független.
Ez egészen biztosan nem igaz, mert
Vagyis van olyan lineáris kombinációjuk,
ami a nullvektort adja, pedig egyik vektorból
sem nulla darabot vettünk.
Ha lineárisan független, akkor
is lineárisan független.
Nézzük meg, hogy függetlenek-e.
Ehhez vegyük egy lineáris kombinációjukat:
Ha ez csak úgy teljesül, hogy mindketten nulla,
akkor függetlenek, ha úgy is lehetséges,
hogy az egyik nem nulla, akkor összefüggők.
Vagyis az a kérdés, hogy mennyi .
Felbontjuk a zárójeleket :
Aztán összegyűjtjük hány darab , hány darab
és hány darab vektor van.
Mivel az vektorok lineárisan függetlenek,
itt egészen biztos, hogy minden együttható nulla,
vagyis és ami azt jelenti,
hogy is független.
Ha lineárisan független,
akkor is lineárisan független.
Ezúttal a
lineáris kombinációból indulunk ki.
Ezt kéne valahogy visszavezetni az
vektorok lineáris kombinációjára.
De néha nem árt kicsit gondolkodni.
Vegyük ugyanis például azt az esetet, amikor nullvektor.
Ekkor és ezek a vektorok függetlenek, de egészen biztosan összefüggő, mert köztük van a nullvektor.
Érdemes megjegyezni, hogy ha egy vektorrendszerben benne van a nullvektor, akkor az mindenképpen lineárisan összefüggő.
Ha generátor-rendszer,
akkor is az.
Nos az, hogy generátor-rendszer,
azt jelenti, hogy ők minden vektort előállítanak.
Mivel vektorokból viszont és
előáll, biztos, hogy generátor rendszer.
Az vektorokból először legyártjuk
és vektorokat, akik pedig, mivel generátor-
rendszer, már mindenki mást előállítanak.
Vagyis jegyezzük meg, hogy ha egy vektorrendszer vektoraiból elő tudunk állítani generátor-rendszert, akkor maguk a vektorok is generátor-rendszer.
ALTEREK
A vektortérnek altere, ha és maga is vektortér a -beli műveletekre.
Az altér tehát egy olyan részhalmaza a vektortérnek, ami a vektortér összes tulajdonságát átörökíti. Teljesülnek benne a vektortér-axiómák és a műveletek.
Van egy érdekes tétel ami megkönnyíti annak eldöntését, hogy egy részhalmaz valóban altér-e. A tétel azt mondja, hogy elegendő csak a műveleteket ellenőrizni és ha azok működnek, vagyis nem vezetnek ki a részhalmazból, akkor ennyi elég is, ahhoz, hogy altér legyen.
A vektortérnek altere, ha -beli műveletek nem vezetnek ki -ből.
Ennek az a magyarázata, hogy ha a műveletek nem vezetnek ki, vagyis és is benne van -ben akkor a vektortér-axiómák automatikusan teljesülnek.
nézzük meg!
A kommutativitás, asszociativitás és disztributivitás a vektortér minden elemére, tehát a -beli elemekre is teljesül. A többi axióma pedig, lássuk csak:
Létezik nullelem -ben.
Hát persze, hogy létezik, mert benne van -ben és
Létezik ellentett -ben.
Ez is létezik, mert benne van -ben és
Végül pedig teljesül -ben,
mert ez ugye az egész vektortér minden elemére igaz.
Ezzel kiderült, hogy valóban elegendő csak annyit megvizsgálni, hogy a műveletek nem vezetnek-e ki.
Nézzünk is meg egy ilyet!
Vizsgáljuk meg, hogy altere-e -nak, ha igen, adjunk meg egy bázist -ben.
Az előző tétel miatt elegendő annyit ellenőrizni, hogy a műveletek nem vezetnek-e ki.
Kezdjük az összeadással.
Azt nézzük meg, hogy két ilyen típusú vektor összege is ilyen típusú-e.
Hát ez probléma! Az összeadás úgy tűnik kivezet -ből.
A jelek szerint tehát nem altér.
Nézzünk meg egy másikat is!
Vizsgáljuk meg, hogy altere-e -nek, ha igen, adjunk meg egy bázist -ben.
Elegendő most is annyit ellenőrizni, hogy a műveletek nem vezetnek-e ki.
Kezdjük az összeadással.
Azt nézzük meg, hogy két ilyen típusú vektor összege is ilyen típusú-e.
itt
az összegük:
Mivel a két vektor összegére is teljesül a koordináták közti összefüggés, az összeadás nem vezet ki.
Lássuk mi a helyzet a -szorossal!
Úgy tűnik ez is stimmel, tehát altér.
A dimenzió a szabadon megadható paraméterek száma.
Két szabadon megadható paraméter van, az egyik az és akkor miatt már nem szabad, a másik pedig és akkor miatt már nem szabad.
A dimenzió tehát kettő, bázist pedig úgy kapunk, hogy a szabad paraméterek közül egyet egynek, a többit nullának vesszük és ezt végigjátsszuk az összes lehetséges módon.
A bázis tehát:
Vizsgáljuk meg, hogy a halmaz altér-e -ben. Ha igen, adjuk meg a dimenzióját és egy bázisát.
Elegendő annyit ellenőrizni, hogy a műveletek nem vezetnek-e ki.
Kezdjük az összeadással.
Azt kell megnéznünk, hogy két ilyen típusú vektor összege is ilyen típusú-e.
Mivel a két vektor összegére is teljesül a koordináták közti összefüggés, az összeadás nem vezet ki.
Lássuk mi a helyzet a -szorossal!
Úgy tűnik ez is stimmel, tehát altér.
A dimenzió annyi, ahány szabadon megadható paraméter van.
Most éppen két szabad paraméter van, és
A dimenzió tehát kettő, bázist pedig úgy kapunk, hogy a szabad paraméterek közül egyet egynek, a többit nullának vesszük és ezt végigjátsszuk az összes lehetséges módon.
A bázis tehát:
Legyen -beli vektor. Mely állítások igazak?
a) Ha lineárisan független, akkor is lineárisan független.
b) Ha lineárisan összefüggő, akkor is lineárisan összefüggő.
c) Ha generátor-rendszer, akkor is az.
d) Ha lineárisan független, akkor is az
a) Ha lineárisan független,
akkor is lineárisan független.
Vegyük egy lineáris kombinációjukat:
Ha ez csak úgy teljesül, hogy mind nulla,
akkor függetlenek, ha úgy is lehetséges, hogy nem
mindegyik nulla, akkor összefüggők.
Vagyis az a kérdés, hogy mennyi .
Felbontjuk a zárójeleket :
Aztán összegyűjtjük hány darab , hány darab
és hány darab vektor van.
Mivel az vektorok lineárisan függetlenek,
itt egészen biztos, hogy minden együttható nulla, vagyis
Úgy néz ki mind nulla, tehát a vektoraink függetlenek.
b) Ha lineárisan összefüggő,
akkor is lineárisan összefüggő.
Nézzük meg elsőként, hogy függetlenek-e.
Vegyük egy lineáris kombinációjukat:
Ha ez csak úgy teljesül, hogy mind nulla,
akkor függetlenek, ha úgy is lehetséges, hogy nem
mindegyik nulla, akkor összefüggők.
Vagyis az a kérdés, hogy mennyi .
Felbontjuk a zárójeleket :
Aztán összegyűjtjük hány darab , hány darab
és hány darab vektor van.
Mivel az vektorok lineárisan függetlenek,
itt egészen biztos, hogy minden együttható nulla, vagyis
Nézzük meg elsőként, hogy függetlenek-e.
Vegyük egy lineáris kombinációjukat:
Ha ez csak úgy teljesül, hogy mind nulla,
akkor függetlenek, ha úgy is lehetséges, hogy nem
mindegyik nulla, akkor összefüggők.
Vagyis az a kérdés, hogy mennyi .
Felbontjuk a zárójeleket :
Aztán összegyűjtjük hány darab , hány darab
és hány darab vektor van.
Mivel az vektorok lineárisan függetlenek,
itt egészen biztos, hogy minden együttható nulla, vagyis