Permutáció paritása

Ez a szócikk vagy szakasz lektorálásra, tartalmi javításokra szorul. A felmerült kifogásokat a szócikk vitalapja részletezi (vagy extrém esetben a szócikk szövegében elhelyezett, kikommentelt szövegrészek). Ha nincs indoklás a vitalapon (vagy szerkesztési módban a szövegközben), bátran távolítsd el a sablont! Csak akkor tedd a lap tetejére ezt a sablont, ha az egész cikk megszövegezése hibás. Ha nem, az adott szakaszba tedd, így segítve a lektorok munkáját!

A matematikában, azon belül is a csoportelméletben, egy véges halmaz egy permutációját párosnak, illetve páratlannak mondjuk, ha előáll páros, illetve páratlan sok csere szorzataként. Mint látni fogjuk, ez az illető halmaz permutációit két azonos számosságú, diszjunkt osztályra bontja, ezek közül a páros permutációk alkotják az alternáló csoportot. Bevezetjük továbbá a permutáció előjelének fogalmát, ami hasznos segédeszközül szolgálhat egy négyzetes determináns kifejtéséhez, amennyiben egy ${\displaystyle \pi }$ permutációra ${\displaystyle \operatorname {sgn}(\pi )={\begin{cases}1&{\text{ha }}\pi {\text{ páros}}\\-1&{\text{ha }}\pi {\text{ páratlan}}\end{cases}}}$, és ${\displaystyle {\begin{vmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{vmatrix}}=\sum _{\pi \in S_{n}}{\operatorname {sgn}(\pi )a_{1\pi (1)}\cdots a_{n\pi (n)}}}$, ahol ${\displaystyle S_{n}}$ az ${\displaystyle \{1,2,\ldots ,n\}}$ halmaz permutációinak halmazát jelöli.

Tekintsük a

${\displaystyle \Delta (x_{1},...,x_{n})={\begin{vmatrix}1&x_{1}&\cdots &x_{1}^{n-1}\\1&x_{2}&\cdots &x_{2}^{n-1}\\\vdots &\vdots &\ddots &\vdots \\1&x_{n}&\cdots &x_{n}^{n-1}\end{vmatrix}}}$

Vandermonde-determinánst. Ekkor, ha ${\displaystyle \pi }$ páros,

${\displaystyle \Delta (\pi (x_{1},\ldots ,x_{n}))=\Delta (x_{1},\ldots ,x_{n})\,}$,

viszont, ha ${\displaystyle \pi }$ páratlan,

${\displaystyle \Delta (\pi (x_{1},\ldots ,x_{n}))=-\Delta (x_{1},\ldots ,x_{n})\,}$,

így egy permutáció nem lehet egyszerre páros és páratlan.

Most lássuk, hogy minden permutáció vagy páros, vagy páratlan. Ehhez azt kell belátnunk, hogy ${\displaystyle S_{n}}$-t generálják a cserék. ${\displaystyle S_{2}}$ a ${\displaystyle (1\,2)}$ csere által generált szimmetrikus csoport. Tegyük fel, hogy ${\displaystyle S_{n-1}}$-et generálják a cseréi. Ekkor, mivel ${\displaystyle S_{n-1}}$ izomorf ${\displaystyle S_{n}}$ n-et fixen hagyó permutációival, ${\displaystyle S_{n}}$ cseréi generálják ezeket. Tegyük fel tehát, hogy ${\displaystyle \pi \in S_{n}}$ permutáció nem hagyja fixen ${\displaystyle n}$-t, és ${\displaystyle \pi (i)=n}$. Ekkor létezik olyan ${\displaystyle \pi ^{*}}$ permutáció, amelyre

${\displaystyle \pi =\pi ^{*}\circ (i\,n)}$,

azaz

${\displaystyle \pi ^{*}=\pi \circ (i\,n)}$.

Így

${\displaystyle \pi ^{*}(n)=\pi ((i\,n)(n))=\pi (i)=n}$,

tehát ${\displaystyle \pi ^{*}}$ fixen hagyja ${\displaystyle n}$-et, így az indukciós hipotézis szerint generálják ${\displaystyle S_{n}}$ cseréi, de ekkor ${\displaystyle \pi }$-t — felírása szerint — úgyszintén.

Hogy minden permutáció felírható cserék kompozíciójaként, felhasználjuk az előző bizonyításból, csak azt bizonyítjuk, hogy egy csere sem lehet egyszerre páros vagy páratlan. Ha ${\displaystyle X}$ halmazon adva van egy lineáris rendezés, és ${\displaystyle \pi }$ ${\displaystyle X}$ egy permutációja, akkor azt mondjuk, ${\displaystyle i}$ és ${\displaystyle j}$ inverzióban állnak, ha

${\displaystyle i<j}$, és ${\displaystyle \pi (j)<\pi (i)}$.

Jelölje ${\displaystyle N(\pi )}$ ${\displaystyle \pi }$ az adott rendezésre vonatkozó inverzióinak a számát. Azt fogjuk megmutatni, hogy páros, illetve páratlan permutációkban az inverziók száma rendre páros és páratlan. Nyilvánvaló, hogy ${\displaystyle N(\pi (i\,i+1))=N(\pi )\pm 1}$. Minden ${\displaystyle (ij)}$ cserére teljesül a következő azonosság:

${\displaystyle (ij)=(i\quad i+1\quad \ldots \quad j)(j-1\quad j-2\quad \ldots \quad i)=}$

${\displaystyle (i\quad i+1)(i+1\quad i+2)\ldots (j-1\quad j)\cdot (j-1\quad j-2)(j-2\quad j-3)\ldots (i+1\quad i)\qquad (i<j)}$ ,

ahonnan látszik, hogy minden csere előáll páratlan sok szomszédcsere szorzataként, amiből

${\displaystyle N(\pi (ij))=N(\pi )\pm 1}$,

minden ${\displaystyle \pi }$ permutációra.

Mivel az identitásban nincs inverzió, minden páros permutációban páros, és minden páratlan permutációban páratlan az inverziók száma. Ezzel nem csak azt mutattuk meg, amit akartunk, hanem mellékesen kiderült az is, hogy egy permutációban az inverziók számának paritása nem függ az alaphalmazon vett rendezéstől.

A definícióból adódik, hogy páros permutációk szorzata páros, két páratlan szorzata páros, páros és páratlan, így

${\displaystyle \pi \mapsto \operatorname {sgn} \pi }$

leképezés csoporthomomorfizmus, így a páros permutációk ${\displaystyle S_{n}}$-ben 2-indexű normálosztót alkotnak, az alternáló csoportot, amiből az is következik, hogy a páratlan permutációk egy alternáló csoport szerinti mellékosztályt alkotnak, tehát egy véges halmaznak ugyanannyi páros permutációja van, mint páratlan. Minden permutáció paritását könnyen meghatározhatjuk ciklusfelbontásából, hiszen minden páratlan hosszú ciklus páros, és minden páros hosszú páratlan.

• Fuchs László: Bevezetés az algebrába és a számelméletbe; Kézirat, Tankönyvkiadó, Budapest 1971.
• van der Waerden, B.L.: Moderne Algebra Bd. 1, 3. Aufl., Springer, Berlin, 1950.
• Jacobson, Nathan: Basic algebra. 1 2nd ed., Dover, 2009. ISBN 978-0-486-47189-1