Tartalomjegyzék

• Előadások
• ZH, konzultáció
• Házi feladatok
• 1. Hibajavító kód (2 pont, határidő: 2017-02-28 kedd 10:15 IB026)
• 2. Lineáris leképezések (2 pont, határidő: 2017-03-07 kedd 10:15 IB026)
• 3. Optimális megoldás (2 pont, határidő: 2017-03-14 kedd 10:15 IB026)
• 4. Dokumentumok rangsorolása (2 pont, határidő: 2017-03-21 kedd 10:15 IB026)
• 5. Információtömörítés SVD-vel (2 pont, határidő: 2017-04-04 kedd 10:15 IB026)
• 6. A főirány megkeresése (2 pont, határidő: 2017-04-11 kedd 10:15 IB026)
• 7. Mátrixfüggvények (3 pont, határidő: 2017-04-25 kedd 10:15)
• 8. Egy sztochasztikus folyamat – csöncsön gyűrű (3 pont, határidő: 2017-05-02 kedd 10:15 IB026)
• 9. Lineáris mátrixegyenlet (2 pont, határidő: 2017-05-09 kedd 10:15 IB026)

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

• 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: R^m → Rⁿ 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

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 :-).

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ó.]

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.

Í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?)

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.

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).

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?

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?

$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.

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].$$