Permutáció paritása

A Wikipédiából, a szabad enciklopédiából

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 \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}{\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[szerkesztés | forrásszöveg szerkesztése]

Első bizonyítás[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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)\pm1. 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)\pm1,

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[szerkesztés | forrásszöveg szerkesztése]

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\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[szerkesztés | forrásszöveg szerkesztése]

  • 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