Lineáris algebra/Permutáló mátrixok II.

• Témák jegyzéke
• Előző fejezet (Permutáló mátrixok)
• Következő fejezet (?)

Permutáló mátrixok csoportelmélete

Az előző fejezetben bevezettük a permutáló mátrix (p.m.) fogalmát, megvizsgáltuk, mit jelent a velük való szorzás, és bizonyítottuk, hogy a szorzásra nézve egységelemes csoportot alkotnak. Jelen fejezet (továbbra is, de az előzőnél még inkább) azzal foglalkozik, hogyan helyettesíthető a kombinatorikai „permutáció” fogalma a lineáris algebra „permutáló mátrix” fogalmával, hogyan lehet bizonyos (nemcsak a determinánsok elméletében, de pl. a polinomok algebrájában is fontos) eredményeket lineáris algebrai nyelvezetben is megfogalmazni. Melléktermékként (avagy, „konkrétabban ez azt jelenti, hogy”) főleg a permutáló mátrixok csoportjának bizonyos alapvető csoportelméleti jellegzetességeit világítjuk meg, pl. a rend és a ciklus fogalmát.

Transzpozíció

Ha egy (n×n-es) permutáló mátrix egy vele szorzott mátrixsort (-oszlopot) eredeti helyzetéhez képest áthelyez, akkor azt a sort meg, ahová az áthelyezett sor került, szintén máshová kell helyeznie („két sor nem lehet egy helyen”). Eme gondolat egyik elemi következményeképp azt mondhatjuk, bizonyos szempontból a „legegyszerűbb” p.m.-ok azok, melyek két sort „egymás közt” csereberélnek. Vagyis, amelyek főindexe kettőt kivéve minden (i) sorindexre megegyezik az illető (i) sorindexszel (ezen sorok azonosak az egységmátrix megfelelő sorával), viszont két másik sorindexre, mondjuk g-re és h-ra (g,h∈N_n) érvényes f(g)=h és f(h)=g. Az ilyen mátrixokat transzpozíciónak (avagy transzpozíció-mátrixnak, magyarul: „áthelyezés”) fogjuk nevezni.

Inverzió

E kombinatorikában használt fogalomnak ezúttal semmi köze a mátrixok szorzás szerinti inverzéhez. Egy mátrixsorok közti relációról lesz szó.

Definíció: legyen P n×n-es permutáló mátrix. Két (különböző) sor inverzióban áll egymással, ha a felsőbb sor 1-ese hátrébb (jobbra) áll, mint az alább lévő sor 1-ese, precízebben: az i,j indexű sorok, ahol i<j, inverzióban állnak akkor és csak akkor, ha a kisebb indexű főeleme nagyobb, mint a nagyobb indexű főeleme, azaz ha f(i)>f(j).

Ha egy permutáló mátrix sorinverzióinak száma páros, akkor azt páros mátrixnak nevezzük, míg ha páratlan, akkor páratlan p.m.-ról beszélünk.

Példa

Az $X\ =\ {\begin{pmatrix}0&0&1&0\\1&0&0&0\\0&0&0&1\\0&1&0&0\\\end{pmatrix}}$ első sora két sorral (1. és a 4.) áll inverzióban, a második sor csak az elsővel, de semmilyen másikkal, a harmadik sor egy sorral, a negyedikkel áll inverzióban, a negyedik a harmadikon kívül semmilyen inverzióban nincs másik sorral. Ez összesen 3 különböző inverzió. A mátrix páratlan.

Ciklusok és mátrixok rendje

Bevezetés

Megvizsgálva, mit csinál a fenti, $X\ =\ {\begin{bmatrix}3\\1\\4\\2\end{bmatrix}}$ főindexalakban megadható mátrix, ha vele tetszőleges mátroxot balról szorzunk, a következőket állapíthatjuk meg: a harmadik sort felpakolja az első sorba, az első sort a másodikba, a harmadik sorba a negyediket rakja, a negyedikbe meg a másodikat. Mi történik egy adott sorral, ha többször szorzunk a mátrixszal (azaz,a mátrix hatványával szorzunk)? Nézzük:

1. az első sor az első szorzás után a másodikba kerül, azután a következő szorzás a másodikat a negyedikbe teszi, tehát az eredeti első sor leesik a negyedik helyére; a következő lépésben viszont a harmadik sor helyére kerül, hogy végül, négy szorzás után, a harmadik sor, ami eredetileg az első volt, visszakerüljön az első sorba. Ellenőrizhető, hogy a többi sor is hasonlóan viselkedik:
2. a második sor a negyedikbe, onnan a harmadikba, onnan az elsőbe, onnan vissza a másodikba kerül.
3. a harmadik sor az elsőbe, onnan a másodikba, onnan a negyedikbe, onnan a harmadikba (azaz vissza-) kerül.
4. A negyedik sor a harmadikba kerül, innen már tudjuk az útját (ld. előző pont): az elsőbe, majd a másodikba, majd a negyedikbe megy, és ezzel a negyedik sor is a helyére kerül vissza.

Az első három lépés során minden sor helye megváltozik, de végül (a mátrix negyedik hatványával szorozva) visszakerül a helyére, azaz X⁴=E_n egységmátrix. Mindezt úgy mondjuk röviden, hogy az X permutáló mátrix rendje 4, jele o(X). Ez egy alapvető csoportelméleti fogalom. A rend azért hasznos, mert rávilágít arra, hogy egy permutáló mátrix végtelen sok hatványa valójában véges sok hatvány: a hatványok értékei o(X) lépésenként periodikusan ismétlődnek; más megfogalmazásban: ha i és j kongruensek egymással mod(o(X)), akkor az i-edik és j-edik hatvány értéke megegyezik, ugyanaz a mátrix.

Csábító ezek után a lehetőség, hogy egy mátrix rendjét úgy állapítsuk meg, hogy vesszük - találomra tetszőleges sorát, megnézzük, hány lépés múlva kerül a helyére, és azt mondjuk, ez a lépésszám a rend. Amint a következő példa mutatja, ezt mégsem tennénk feltétlenül helyesen!

Példa

Az 5×5-ös $Y\ =\ {\begin{pmatrix}0&0&1&0&0\\1&0&0&0&0\\0&1&0&0&0\\0&0&0&0&1\\0&0&0&1&0\end{pmatrix}}\ =\ {\begin{bmatrix}3\\1\\2\\5\\4\end{bmatrix}}$ első sora a főindexek tanúsága szerint a második, majd a harmadik sorba kerül, és a harmadik lépésben jut vissza az eredeti helyére. Ugyanez történik az ebben a soráthelyezési folyamatban - szakszóval: permutációs ciklusban - résztvevő többi sorral is, ezek mind három lépésenként kerülnek vissza az eredeti helyükre. Egészen más történik viszont a negyedik és ötödik sorokkal! Ezek ugyanis minden lépésben áthelyeződnek, csereberélődnek, tehát az ötödik sor már két lépésben visszakerül az eredeti helyére!

Vezessük be tehát a sorokra vonatkozó rendfogalmat is: egy X (permutáló) mátrix i-edik sorának rendje, o_i(X) az a legkisebb n pozitív egész, melyre igaz, hogy az illető sort n lépés után eredeti helyére teszi vissza; algebrailag ez azt jelenti (ld. lentebb); hogy a legkisebb olyan egész. Xⁿ i-edik sora megegyezik az egységmátrix i-edik sorával (ugyanis a permutáló mátrix pontosan akkor hagy helyben egy sort, ha a sorbeli főindexe megegyezik a sorindexszel, ez pedig az egységmátrix definíciója alapján pont az egységmátrix i-edik sorára jellemző). Az első három sor három lépésenként, az utolsó kettő két lépésenként kerül helyére, a hatodik tehát az első olyan lépésszám, hogy mindegyik sor egyszerre a helyén van (o(X) = 6 = [2 ,3], ahol [] a legkisebb közös többszöröst jelöli). Szemléletesen is könnyen belátható tehát, hogy egy mátrix rendje sora rendjeinek legkisebb közös többszöröse.

Definíció (P.3.):

---

Egy n×n-es P permutáló mátrix rendjének nevezzük azt a legkisebb pozitív egész számot (ha létezik), amelyre igaz Pⁿ = E_n. Jele o(P)

Azaz: ha Ω(P) := {n∈N: Pⁿ = E_n}, akkor o(P) := min(Ω(P)).

Tételek:

1. Minden permutáló mátrixnak létezik rendje.
   1. Lemma: n! darab n×n-es permutáló mátrix van.
2. A p. m. rendje sora rendjei legkisebb közös többszöröse.