|
# Két p.m. szorzata is p.m. (fentebb)
# P.m. inverze is p.m.
== 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 <math> X \ = \ \begin{pmatrix} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ \end{pmatrix} </math> 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, <math> X \ = \ \begin{bmatrix} 3 \\ 1 \\ 4 \\ 2 \end{bmatrix} </math> 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:
# 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:
# a második sor a negyedikbe, onnan a harmadikba, onnan az elsőbe, onnan vissza a másodikba kerül.
# a harmadik sor az elsőbe, onnan a másodikba, onnan a negyedikbe, onnan a harmadikba (azaz vissza-) kerül.
# 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<sup>4</sup>=E<sub>n</sub> egységmátrix. Mindezt úgy mondjuk röviden, hogy az X permutáló mátrix '''rend'''je 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úlve 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 <math> 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} </math> 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<sub>i</sub>(X) az a legkisebb n pozitív egész, melyre igaz, hogy az illető sort n lépés után eredeti helyére teaszi vissza; algebrailag ez azt jelenti (ld. lentebb); hogy a legkisebb olyan egész. X<sup>n</sup> 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.
<div style="border: solid 2px #ee0000; background: #d5e7cc; text-color: black; text-align: justify; margin: 1em; padding: 1em;">
=== <center> '''Definíció''' (P.3.): </center> ===
----
<br>
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<sup>n</sup> = E<sub>n</sub>. Jele o(P)
Azaz: ha Ω(P) := {n∈'''N''': P<sup>n</sup> = E<sub>n</sub>}, akkor o(P) := min(Ω(P)).
</div>
<br>
Tételek:
# Minden permutáló mátrixnak létezik rendje.
## Lemma: n! darab n×n-es permutáló mátrix van.
# A p. m. rendje sora rendjei legkisebb közös többszöröse.
== Külső hivatkozások ==
| 