Permutáció paritása

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 $\pi$ permutációra $\operatorname {sgn}(\pi )={\begin{cases}1&{\text{ha }}\pi {\text{ páros}}\\-1&{\text{ha }}\pi {\text{ páratlan}}\end{cases}}$, és ${\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 $S_{n}$ az $\{1,2,\ldots ,n\}$ halmaz permutációinak halmazát jelöli.

A jóldefiniáltság bizonyítása

Első bizonyítás

Tekintsük a

$\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 $\pi$ páros,

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

viszont, ha $\pi$ páratlan,

$\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 $S_{n}$-t generálják a cserék. $S_{2}$ a $(1\,2)$ csere által generált szimmetrikus csoport. Tegyük fel, hogy $S_{n-1}$-et generálják a cseréi. Ekkor, mivel $S_{n-1}$ izomorf $S_{n}$ n-et fixen hagyó permutációival, $S_{n}$ cseréi generálják ezeket. Tegyük fel tehát, hogy $\pi \in S_{n}$ permutáció nem hagyja fixen $n$-t, és $\pi (i)=n$. Ekkor létezik olyan $\pi ^{*}$ permutáció, amelyre

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

azaz

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

Így

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

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

Második bizonyítás

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 $X$ halmazon adva van egy lineáris rendezés, és $\pi$ $X$ egy permutációja, akkor azt mondjuk, $i$ és $j$ inverzióban állnak, ha

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

Jelölje $N(\pi )$ $\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 $N(\pi (i\,i+1))=N(\pi )\pm 1$. Minden $(ij)$ cserére teljesül a következő azonosság:

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

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

$N(\pi (ij))=N(\pi )\pm 1$,

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

Tulajdonságok

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

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

leképezés csoporthomomorfizmus, így a páros permutációk $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.

Források

• 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