Felsőbb matematika villamosmérnököknek - Haladó lieáris algebra (BMETE90MX54/V0 - 2016/17/2)

Oktató: 
Tantárgy követelmény: 
Kurzus típus: 
Elmélet
Nyelv: 
magyar
Félév: 
2016/17/2
Órarendi információ: 

Kedd 10:15-12:00 IB026

Tartalomjegyzék

  1. Vektorok, mátrixok, determinánsok (V.02-13)
  2. Lineáris leképezések (V. 02-24)
  3. Euklideszi terek, ortogonalitás (V. 03-12)
  4. Diagonalizálhatóság (V. 03-15)
  5. SVD, norma (V. 03-28 19:22)
  6. Jordan-féle normálalak (V. 04-20 22:34)
  7. Mátrixfüggvények (V. 04-11 14:24)
  8. Pozitív mátrixok
  9. Lineáris mátrixegyenletek

ZH, konzultáció

  • 1. ZH: kedd, március 21, 18-20 KF51,
        Borbély Gábor konzultációja: március 17, péntek, 14:00-, H. ép. 45A
        Kiss Sándor konzultációja: marcius 20, hétfő, 17:00-, E1A
  • 2. ZH: kedd, április 25, 18-20 IB028,IB025
        Konzultáció: április 24, hétfő, 17:00- E1A
  • PótZH: csütörtök, május 11, 18-20 Q-I

A házi feladatok és a ZH-k eredményei ebben a táblázatban találhatók.

A ZH-ra 40 pont kapható, melyből elmélet \(14\pm1\) pont, bizonyítások \(6\pm1\) pont, gyakorlati számítások \(20\pm1\) pont. A követelményeket lásd fönt a tantárgy követelményekben.

 

1. ZH követelményei

  • Gyakorlati feladattípusok
    1. Lineáris kapcsolatok meghatározása elemi sorműveletekkel (függetlenség, bázis, bázisra vonatkozó koordináták, altér dimenziója, mátrix bázisfelbontása, egyenletrendszer megoldása, mátrix inverze)
    2. egyenletrendszer megoldása LU vagy PLU felbontással valós vagy véges test fölött
    3. valamely lineáris leképezés mátrixának fölírása, (vetítés altérre egy másik altér mentén, tükrözés, forgatás a térben, altérre való merőleges vetítés (7.29)
    4. adott bázisban megadott mátrixú lineáris leképezés mátrixának fölírása másik bázisban
    5. egyenletrendszer optimális megoldásainak meghatározása és a legkisebb abszolút értékű optimális megoldás meghatározása,
    6. pszeudoinverz és alkalmazása egyenletrendszer optimális megoldásában
    7. Gram-Schmidt-ortogonalizáció
  • Elméleti témák
    1. a négy kitüntetett altér, dimenziótétel, a lineáris algebra alaptétele
    2. az elemi sorműveletek hatása a sortérre és az oszloptérre
    3. egyenletrendszer megoldhatóságának mátrixrangos feltétele
    4. a megoldások tereinek jellemzése
    5. (egyik bázisról a másikra való) áttérés mátrixa
    6. invertálhatóság és az egyenletrendszerek kapcsolata
    7. a determinánsfüggvény soronkénti linearitása, determináns és a mátrixműveletek kapcsolata, determináns értékének kiszámítása háromféle módon: elemi sorműveletekkel, sor vagy oszlop szerinti kifejtéssel, kígyók determinánsainak összegére bontással
    8. lineáris vektortér és euklideszi tér definíciója
    9. mátrixleképezés, lineáris leképezés
    10. merőleges vetítés és a legjobb közelítés, a legjobb közelítés ONB esetén
    11. polinomiális regresszió
    12. pszeudoinverz fogalma és a Moore-Penrose-tétel
    13. (szemi)ortogonális mátrixok, Givens-forgatás, Householder-tükrözés
    14. ortogonalizáció, QR-felbontás
    15. mátrix és lineáris leképezés sajátértéke, sajátaltere
    16. diagonalizálhatóság fogalma, mátrix diagonalizálhatóságának szükséges és elégséges feltétele
    17. szimmetrikus, ferdén szimmetrikus, ortogonális, nilpotens, önadjungált, ferdén önadjungált, unitér és normális mátrixok fogalma, sajátértékei és tulajdonságaik
  • Bizonyítások
    1. Minden A: Rm → Rn lineáris leképezéshez létezik olyan A mátrix, hogy minden x vektorra A(x) = Ax.
    2. Ortonormált vektorrendszer független.
    3. Ortogonális mátrix tulajdonságai
    4. Egyenletrendszer optimális megoldása QR-felbontással
    5. Mátrix diagonalizálhatóságának szükséges és elégséges feltétele

2. ZH követelményei

  • Gyakorlati feladattípusok
    1. Mátrix vagy lineáris leképezés diagonalizálása (karakterisztikus polinom, sajátérték, sajátvektor, sajátaltér meghatározása)
    2. Főtengelytranszformáció elvégzése kvdaratikus alakon
    3. Kvadratikus alak (vagy mátrixa) definitségének meghatározása a definíció, a sajátértékek, egy csak négyzetes tagokat tartalmazó alakja vagy a minorai segítségével
    4. Cholesky-felbontás
    5. Szinguláris érték szerinti felbontás teljes, redukált és diadikus alakjának felírása
    6. Polárfelbontás és pszeudoinverz kiszámítása a szinguláris felbontásból
    7. Vektorok normáinak, mátrixok Frobenius-, 1, 2, $\infty$-normáinak kiszámítása
    8. Mátrix legjobb $k$-rangú közelítésének számítása
    9. A Jordan-normálalak meghatározása az $\mathbf A-\lambda\mathbf I$-re vonatkozó ismeretekből
    10. Mátrix függvényének kiszámítása a Jordan-normálalakból
    11. Hermite-polinom meghatározása és segítségével mátrixfüggvény kiszámítása
  • Elméleti témák
    1. Gersgorin-körök
    2. Cayley–Hamilton-tétel
    3. Ortogonális és unitér diagonalizálás
    4. Schur-felbontás
    5. Kvadratikus formák, mátrixok definitsége
    6. Szinguláris értékek és vektorok fogalma, kapcsolatuk a négy alapvető altérrel
    7. Szinguláris érték szerinti felbontás geometriai „jelentése”
    8. Norma definíciója
    9. Normák ekvivalenciája (R-ben és C-ben)
    10. Vektornorma és vektornormák ekvivalenciája
    11. Frobenius-norma és ekvivalens alakjai
    12. Mátrixnorma és indukált mátrixnorma
    13. Eckart-Young-tétel
    14. Blokkdiagonális alakok és invariáns alterek
    15. Minimálpolinom és tulajdonságai
    16. Általánosított sajátvektor, Jordan-lánc, Jordan-bázis, Jordan-blokk, Jordan-féle normálalak
    17. Jordan-tétel
    18. Az „$f$ függvény definiálva van az $\mathbf A$ spektrumán” fogalmának definíciója
    19. Függvény mátrixban felvett értékének definíciója a Jordan-alakból
    20. Függvény mátrixban felvett értékének definíciója Hermite-polinommal
  • Bizonyítások
    1. Hasonló mátrixok karakterisztikus polinomjai azonosak
    2. Pozitív szemidefinit mátrixok faktorizációja
    3. Szinguláris értékek létezése és egyértelműsége
    4. Polárfelbontás létezése, kiszámítása a szinguláris érték szerinti felbontásból
    5. Pszeudoinverz kiszámítása a szinguláris érték szerinti felbontásból

Házi feladatok

Mindegyik feladat pontszámát és a beadás határidejét megadjuk. A megoldásokat papíron kérjük, de végszükség esetén, kizárólag kivételes esetekben lehet a felsobb pont mat kukac gmail pont com címre is. A megoldásokat mindig az előadás elején kell beadni, de ha valaki nem tudja, leadhatja a határidő előtt a tanszéken is (Algebra Tanszék, H. épület. V. em. 5.) a nevemre. Más megoldását lemásolni nem szabad!

A feladatok között lesz olyan, amelyik kézzel is kiszámolható (pl. az 1. feladat), de a többséghez számítógép szükséges. A legtöbb feladat megoldható lesz valamelyik mátrix alapú rendszerben (Matlab vagy Octave). Egy feladatban tetszőleges pontosságú moduláris aritmetikát tudó programot lesz érdemes használni: pl. valamelyik komputer algebra programot, a Sage, Geogebra, Mathematica, Maple,... jó erre (a Sage a felhőben is fut, nem kell telepíteni, ezt ajánlanám első helyen: https://cloud.sagemath.com/), de egyszerűbb online program is elég pl. http://ptrow.com/perl/calculator.pl vagy a sok mindent tudó Wolfram Alpha. Ez utóbbiban programozási ismeretek nélkül is jó eséllyel eredményre lehet jutni (wolframalpha.com).

Igyekszem olyan egyszerűbb feladatokat adni, amelyek a tanultakhoz nagyon közeli alkalmazásokhoz kapcsolódnak. Remélem elég érdekesek lesznek ahhoz, hogy úgy érezzék, akkor is szívesen megoldanák őket, ha épp nem kéne :-).

1. Hibajavító kód (2 pont, határidő: 2017-02-28 kedd 10:15 IB026)

Tekintsük a kételemű \(\mathbb{F}_2\) test fölötti következő mátrixot: $$ H=\left[\begin{array}{rrrrrrr} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{array}\right] $$

  • Határozzuk meg a \(H\) mátrix négy kitüntetett alterének egy-egy bázisát!
  • Valós mátrixok esetén a sortér és a nulltér kiegészítő alterei egymásnak, véges testek fölött azonban ez nem igaz, a két tér metszete nem mindig a zérustér. Határozzuk meg \(\mathcal S(H)\cap\mathcal N(H)\) alteret!
  • A \(H\) nullterének bázisvektoraiból – mint oszlopvektorokból – képezzük a \(G\) mátrixot. Ezt hibajavító kód konstruálására használják (Hamming-kód). Egy 4-dimenziós \(x\in\mathbb{F}_2^4\) üzenetvektor kódja a \(7\)-dimenziós \(y=Gx\) kódvektor. Mutassuk meg, hogy egy \(y\) vektor pontosan akkor kódvektor, ha \(Hy=0\).
  • [Szorgalmi (nem kötelező) feladat: mutassuk meg, hogy ha az \(y\) kódszó \(i\)-edik koordinátája megváltozik (azaz egyetlen bithiba történik a csatornán), akkor \(Hy\) megegyezik a \(H\) mátrix \(i\)-edik oszlopával, így a hiba javítható.]

2. Lineáris leképezések (2 pont, határidő: 2017-03-07 kedd 10:15 IB026)

Jelölje a legföljebb harmadfokú polinomok vektorterét \(\mathcal P\). Tegyük fel, hogy egy \(\mathcal P\)-beli \(p\) polinommal leírható mennyiségre végzünk ,,pontos'' mérést az \(x_0,x_1,x_2,x_3\) helyeken. Gondoljuk meg, hogy a \((p(x_0),p(x_1),p(x_2),p(x_3))\in\mathbb R^4\) vektorhoz a \(p\in\mathcal P\) polinomot rendelő leképezés lineáris! Minket azonban nem is maga a polinom érdekel, hanem csak a \(p'(0)\), az \(\int_0^1p(x)\,\mathrm dx\), és az \(\int_{-1}^1p(x)\,\mathrm dx\) értékek. Tehát a \[ (p(x_0),p(x_1),p(x_2),p(x_3)) \mapsto \left(p'(0),\int_0^1p(x)\,\mathrm dx, \int_{-1}^1p(x)\,\mathrm dx\right) \] leképezést szeretnénk megadni minél egyszerűbben.

  • Adjunk tömör indoklást arra, hogy e leképezés lineáris!
  • Mivel e leképezés lineáris, így megadható egy mátrixszal való szorzással. Válasszunk konkrét \(x_i\) értékeket (csupa különbözőt!), és határozzuk meg e mátrixot. (Aki e feladatot programmal oldja meg, válasszon nem egész \(x_i\) értékeket.)
  • Számításainkat ellenőrizzük a \(p_1(x)=x^3-x^2+x-1\) és a \(p_2(x)=1\) polinomból számolt értékekkel.

3. Optimális megoldás (2 pont, határidő: 2017-03-14 kedd 10:15 IB026)

Írjuk fel (számítógéppel generáljuk) egy \(n\)-ismeretlenes (\(n > 3\)) és \(m\) egyenletből álló (\(m > n\)) ellentmondásos lineáris egyenletrendszer bővített mátrixát véletlen együtthatókkal, teljes oszloprangú együtthatómátrixszal.

  1. Az együtthatómátrix (a) pszeudoinverzének valamint (b) QR-felbontásának segítségével határozzuk meg az egyenletrendszer optimális megoldását!
  2. Legyen \(\mathbf B\) az együtthatómátrix transzponáltja, és \(\mathbf b\) egy tetszőleges \(n\)-dimenziós vektor. Írjuk fel a \(\mathbf{Bx} = \mathbf b\) egyenletrendszer összes megoldását az \(\mathbf x=\mathbf B^+\mathbf b+(\mathbf I-\mathbf B^+\mathbf B)\mathbf y\) képlettel, ahol \(\mathbf y\) tetszőleges vektor.
  3. Igazoljuk, hogy a fenti képlet valóban megadja az egyenletrendszer összes megoldását!

A feladat numerikus részének megoldásához használjunk mátrixalapú programot (Octave, Matlab) vagy CAS programot (Sage, Mathematica, Maple). (Az utolsó ponthoz útmutatás: mit tudunk \(\mathbf B^+\mathbf B\)-ről és \(\mathbf B\) nullterének kapcsolatáról?)

4. Dokumentumok rangsorolása (2 pont, határidő: 2017-03-21 kedd 10:15 IB026)

E feladat célja, hogy a Google PageRank nevű algoritmusa alapötletének megvalósításán keresztül tapasztalatokat szerezzünk a hatványmódszer alkalmazásáról, valamint több később tanulandó fogalomról, tételről (Markov-lánc, Perron-tétel, vektornormák). Webes dokumentumokat kell fontosságuk alapján rangsorolni, ami legegyszerűbben úgy mérhető, hogy képzeletben követjük egy weben szörfölő útját, aki minden dokumentum linkjei közül véletlenszerűen választ és így dokumentumról dokumentumra bolyong a weben. Ha e bolyongást nagyon sokáig folytatja, kialakul egy természetes sorrend, melyben minden dokumentum azzal arányos számú pontot kap, ahányszor ott járt a szörfölő.

Legyen egy \(n\times n\)-es \(A=[a_{ij}]\) mátrix az \(n\) dokumentum közti áttérés mátrixa, azaz \[ a_{ij} = \begin{cases} \frac1k & \text{ha a \(j\)-edik dokumentumban \(k\) link van, és az egyik az $i$-edikre mutat}\\ \frac1n & \text{ha a \(j\)-edik dokumentumban nincs egyetlen link sem}\\ 0& \text{egyébként.} \end{cases} \] Így olyan mátrixot kapunk, melyben minden oszlop a dokumentumokba való átlépés valószínűségeloszlása, tehát minden oszlopösszeg 1. Ez a modell sem jó, ha vannak olyan dokumentumok, melyek csak egymásra hivatkoznak. A modellen ezért úgy módosítunk, hogy a szörfölő minden esetben \(d\) valószínűséggel egyenletes eloszlás szerint választ az összes dokumentum közül, és \(1-d\) valószínűséggel a dokumentum linkjei közül. A bolyongást leíró mátrix ekkor a következő alakú: \[ M=(1-d)A+d\frac1nJ, \] ahol \(J\) a csupa \(1\)-esből álló mátrix, és \(d\in(0,1)\). Tapasztalatok szerint érdemes \(d\)-t a \((0.1,0.2)\) intervallumból választani, példánkban legyen \(d=0.15\), így \(1-d=0.85\). (A későbbiekben bizonyítani fogjuk, hogy e mátrixnak 1 a maximális abszolút értékű sajátértéke, ami egyszeres algebrai multiplicitású és hogy a hozzá tartozó sajátvektorok közt pontosan egy olyan \(w\) sajátvektor van, melynek minden koordinátája pozitív és a koordináták összege 1, azaz a \(w\) sajátvektor egy valószínűségeloszlás.)

Könnyen meggondolható, hogy ha az \(n\)-dimenziós \(v\) vektor a dokumentumok közül való (első) választás valószínűségeloszlása, akkor \(M^kv\) annak valószínűségeloszlása, hogy a szörfölő melyik dokumentumban van a \(k\)-adik lépés után. Mindezek alapján a hatványmódszerből tudjuk, hogy \(\lim_{k\to\infty}M^kv=w\).

  1. Generáljunk számítógéppel (Octave, Matlab, Sage, Mathematica, Maple) egy \(n\times n\)-es \(A\) mátrixot, mely a fenti definíciónak megfelel, \(n>10\), és a képzeletbeli dokumentumokban 0-5 link van (de legalább egyben 0). Egy ekkora mátrix kinyomtatása már nehézkes, ezért vizualizáljuk egy szürkeárnyalatos ábrával úgy, hogy a 0-nak a fehér, 1-nek a fekete szín feleljen meg (Octave-ban Matlabban pl. az imshow függvény használható, csak a színezést kell megfordítani). Az első lépés kódját nem kell a házi feladathoz mellékelni ha az hosszadalmas, elég csak e szürkeárnyalatos képet.
  2. Képezzük a fentiek alapján az \(M\) mátrixot, és határozzuk meg az 1-het tartozó sajátvektorok közül azt a \(w\) vektort, amelyben a koordináták összege 1. Generáljunk 10 véletlen \(v\) eloszlásvektort, majd határozzuk meg mindegyikhez azt a legkisebb \(k\) számot, melyre \(M^kv-w\) legnagyobb abszolút értékű koordinátája kisebb az \(\frac1n10^{-2}\) számnál. Írjuk ki a \(k\) e 10 értéket!
  3. Határozzuk meg az előzők alapján a dokumentumok fontossági sorrendjét és írjuk ki.
  4. Végül az alábbi két feladat egyikét oldjuk meg:
    1. Rajzoljuk ki az \(A\) mátrixhoz tartozó dokumentumok linkjeinek irányított gráfját (azaz az \(i\)-edik csúcsból menjen él a \(j\)-edikbe, ha az \(i\)-edik dokumentum hivatkozik a \(j\)-edikre). E gráfnak tehát 10-nél több csúcsa van, de minden csúcs kifoka legföljebb 5. (pl. Matlab: digraph függvény)
    2. Igazoljuk, hogy minden olyan \(v\) vektorra, mely valószínűségeloszlás, az \(Mv\) is valószínűségeloszlás, és hogy az \(M\) mátrixnak az \(1\) sajátértéke.

5. Információtömörítés SVD-vel (2 pont, határidő: 2017-04-04 kedd 10:15 IB026)

Vegyen egy saját pixelformátumú szürkeárnyalatos fényképet (vagy egy színest konvertáljon szürkeárnyalatossá) és egy megfelelő programmal készítsen belőle egy mátrixot, melynek minden eleme a kép egy pontjának árnyalatát adja meg (Octave-ban/Matlabban az imread/imwrite paranccsal lehet beolvasni/kiírni, és van parancs a színesből szürkére való konverzióra, de használható a Sage vagy a Mathematica is). Legyen e mátrix rangja $r$. Írja fel a mátrix szinguláris felbontását, majd abból készítsen két olyan kép-mátrixot, melyek egyikének 10, másikának $r/2$ (egész része) a rangja, és ,,legközelebb'' van az eredeti mátrixhoz (ez úgy számolható, hogy az első 10, illetve első $r/2$ tagját adja össze a szinguláris felbontás diadikus alakjának). Jelenítse meg e két képet az eredeti mellett. Ezután mindkét képre számítsa ki az elhagyott szinguláris értékek négyzetösszegének gyökét (ez fogja mérni a két mátrix távolságát Frobenius-normában), és adja meg a legnagyobb elhagyott szinguláris értéket (ez fogja mérni a két mátrix távolságát 2-normában). (Akinek van kedve, és színes nyomtatója, megteheti hogy a három színösszetevő mindegyikére elvégzi a szinguláris felbontást, majd a fenti eljárást, és színes képeket jelenít meg).

6. A főirány megkeresése (2 pont, határidő: 2017-04-11 kedd 10:15 IB026)

Sok olyan alkalmazás van, melyben a valóság bizonyos dolgait $m$ paraméterrel jellemezzük, azaz egy $m$-dimenziós vektorral. Keressük azt az irányt, amely mentén haladva a legjobban szét tudjuk választani és sorba tudjuk rendezni a pontokat.

Adva van $n$ darab $m$-dimenziós $\mathbf{a}_i$ vektor. A belőlük képzett mátrix legyen $\mathbf{A}\in\mathbb{R}^{m\times n}$. Tegyük fel, hogy a vektorok átlaga a zérusvektor (ha nem, akkor vonjuk ki mindegyikből az átlagukat), azaz tegyük fel, hogy \[ \frac1n \sum_{i=1}^n \mathbf{a}_i=\mathbf0. \] Vizualizáljuk ezt a ponthalmazt egy origón átmenő egyenesre való merőleges vetítéssel. Ha az egyenes irányvektora $\mathbf x$ egységvektor, akkor az $\mathbf{a}_i$ vektor vetületének koordinátája az egyenesen $\mathbf{a}_i^T\mathbf x$. Nyilván kevessé jó a vetítés, ha a vetületek nagyon közel kerülnek egymáshoz, ezért azt az egyenest keressük, melynél a vetületek szórása a lehető legnagyobb. E számok átlaga (tapasztalati várható értéke) \[ M(\{\mathbf{a}_i^T\mathbf x: i=1,\dots,n\})= \frac1n \sum_{i=1}^n \mathbf{a}_i^T\mathbf x =\left(\frac1n \sum_{i=1}^n \mathbf{a}_i\right)^T\mathbf x =0, \] (tapasztalati) szórásnégyzetük pedig \[ S^2(\{\mathbf{a}_i^T\mathbf x: i=1,\dots,n\})= \frac1n \sum_{i=1}^n \left(\mathbf{a}_i^T\mathbf x - M(\mathbf{a}_i^T\mathbf x)\right)^2= \frac1n \sum_{i=1}^n\left(\mathbf{a}_i^T\mathbf x \right)^2 =\frac1n \mathbf{x}^T\mathbf A \mathbf{A}^T\mathbf x = \frac1n \|\mathbf{A}^T\mathbf{x}\|_2^2. \] Ennek maximuma megegyezik a $\frac1n \|\mathbf{A}^T\|_2^2$ értékkel (ld. az előadás anyagát).

A feladat: (a fenti szöveg megértése, majd) egy véletlen mátrixhoz (pl. rand függvénnyel az Octave/Matlab programokban generált legalább $n=6$ darab legalább $m=5$-dimenziós vektort adó mátrixhoz) keressük meg a legnagyobb szórást adó egyenes egységnyi irányvektorát, és vetítsük a vektorokat erre az egyenesre, majd írjuk ki a vetületül kapott számokat. A maximális szórást számoljuk ki többféleképp is! Mi köze mindennek a szinguláris értékekhez és vektorokhoz?

7. Mátrixfüggvények (3 pont, határidő: 2017-04-25 kedd 10:15 IB026)

  1. Vegyünk egy legalább 10×10-es valós $\mathbf J$ Jordan-mátrixot, amelyben nincsenek 1×1-es Jordan-blokkok, de van legalább egy legalább 3×3-as és melynek pontosan két különböző sajátértéke van, egyik pozitív, másik negatív. Legyen $\mathbf C$ egy $\mathbf J$-vel azonos méretű véletlen (tehát invertálható) valós mátrix, és legyen $\mathbf{A} = \mathbf{CJC}^{-1}$.
  2. Írjuk fel $\mathbf{A}$ minimálpolinomját! (számítógép használata nélkül, de géppel is ellenőrizhetjük)
  3. Írjuk fel az $e^{\mathbf{A}}$ kiszámításához használható Hermite-polinomot, majd számítsuk ki vele $e^{\mathbf{A}}$ értékét (utóbbit természetesen géppel)! A számítást ellenőrizzük az $e^{\mathbf{A}}=\mathbf{C}e^\mathbf{J}\mathbf{C}^{-1}$ mátrix kiszámításával!
  4. Számítsuk ki az $\mathbf{A}^{1/3}$ és a $\mathrm{sgn}(\mathbf{A})$ mátrixokat, ahol $\mathrm{sgn}$ az előjelfüggvény. Értelmezve volnának-e e függvények, ha az $\mathbf{A}$ egyik sajátértéke 0 lenne?

8. Egy sztochasztikus folyamat – csöncsön gyűrű (3 pont, határidő: 2017-05-02 kedd 10:15 IB026)

\(k=12\) (vagy több, de páros sok) gyerek körben ül, egyikük kezében rejtve egy gyűrű. Egy gyermekdal ritmusára mindenki úgy tesz, mintha egyik szomszédja kezébe adná a gyűrűt. Külső szemlélő nem látja hol a gyűrű, és hogy ki, mikor, kinek adja. Tegyük fel, hogy minden játékos a szomszédjai iránti szimpátia fix mértéke szerinti valószínűséggel, véletlenül választva adja át a gyűrűt. Ha az $n$-edik pillanatban a gyűrű helyzetének valószínűségeloszlását a \(k\)-dimenziós sztochasztikus $\mathbf{v}$ sorvektor írja le, akkor a következő pillanatban (a csere után) a $\mathbf{vP}$ vektor, ahol a $\mathbf P$ mátrix megadja, hogy ki milyen valószínűséggel kinek adja a gyűrűt. E mátrix (átmenetmátrix) alakja \[ \mathbf{P}= \begin{bmatrix} 0 &1-p_1&0 & 0 &\dots &0&p_1\\ p_2& 0 &1-p_2& 0 &\dots &0& 0\\ 0 & p_3& 0 & 1-p_3&\dots &0& 0\\ \vdots&\vdots&\vdots&\vdots&\dots&\vdots&\vdots\\ 1-p_k&0&0&0&\dots&p_k&0 \end{bmatrix} \] ahol $[\mathbf P]_{i,i-1}=p_i$, $[\mathbf P]_{i,i+1}=1-p_i$, és $p_i\in[0,1]$ ($i=1,2,\dots,k$) tetszőleges.

  1. Generáljunk véletlen elemekkel egy ilyen $\mathbf P$ mátrixot és egy véletlen nemnegatív $\mathbf v$ vektort (legyen $\|\mathbf{v}\|_1=1$)! Milyen pozitivitási osztályba tartozik a $\mathbf P$ mátrix (primitív, reducibilis, irreducibilis)?
  2. Vizsgáljuk meg a $\mathbf{vP}^n$ vektorok viselkedését, ha $n$ tart végtelenhez! Létezik-e e vektorsorozatnak határértéke vagy torlódási pontja? Létezik-e a $\mathbf{v}, \mathbf{vP},\dots, \mathbf{vP}^{m-1}$ vektorok átlagának határértéke? Mi ezek jelentése?
  3. Mi történik a fenti értékekkel, ha a $p_i$ valószínűségek egyike 0, egy másika 1, vagyis ha van olyan játékos, aki mindig jobbra, és olyan is, aki mindig balra adja a gyűrűt? Magyarázzuk meg az eredményeket.
  4. Határozzuk meg $\mathbf P$ Perron-vektorait! Mi köze van az előző eredményeknek a Perron-vektorokhoz?

A kérdésekre több módon is válaszolhatunk: a mátrixszal való számolással szerzett tapasztalatok alapján, a játék viselkedéséből levont következtetések és az elmélet alapján. Ahol lehet, világítsuk meg az eredményeket minden oldalról, de tömören! A feladat megoldásában segíthet a lineáris algebra alkalmazásairól szóló jegyzet.

9. Lineáris mátrixegyenlet (2 pont, határidő: 2017-05-09 kedd 10:15 IB026)

 

  1. Válasszunk olyan véletlen egész elemű $\mathbf{A}_1$, $\mathbf{A}_2$, $\mathbf{B}_1$, $\mathbf{B}_2$, $\mathbf{C}$ mátrixokat, melyek egyike sem négyzetes, és az \[\mathbf{A}_1\mathbf{X}\mathbf{B}_1+ \mathbf{A}_2\mathbf{X}\mathbf{B}_2=\mathbf{C}\] egyenletben szereplő műveletek elvégezhetőek. Oldjuk meg a fenti lineáris mátrixegyenletet (Octave/Sage/Matlab) a tanult módszerrel.
  2. Válasszunk egy egészelemű $m\times m$-es $\mathbf{A}$ és egy egész elemű $n\times n$-es $\mathbf{B}$ mátrixot ($2 \lt m\neq n \gt 2$) úgy, hogy $\mathbf{A}$-nak és $-\mathbf{B}$-nek legyen legalább egy közös sajátértéke. Válasszunk úgy egy $\mathbf{C}$ mátrixot, hogy az \[\mathbf{A}\mathbf{X}+ \mathbf{X}\mathbf{B}=\mathbf{C}\] egyenletnek legyen végtelen sok megoldása (határozzuk meg), és egy másikat úgy, hogy ne legyen megoldása.
  3. (*) Igazoljuk, hogy ha az előző mátrixegyenlet (Sylvester-egyenlet) megoldható, akkor fennáll az alábbi hasonlóság: \[ \left[ \begin{array}{rr} \mathbf{A} & \mathbf{C}\\ \mathbf{O} &-\mathbf{B} \end{array} \right] \sim \left[ \begin{array}{rr} \mathbf{A} & \mathbf{O}\\ \mathbf{O}& -\mathbf{B} \end{array} \right]. \]