Permutacja, rozkład na iloczyn cykli rozłącznych

PowerMan · Post autor: **PowerMan** » 25 cze 2011, o 18:45

Witam, mam permutację
\(\displaystyle{ {1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 \choose 5 \ 2 \ 4 \ 7 \ 8 \ 1 \ 3 \ 9 \ 6}}\)
i mam ją przedstawić jako iloczyn cykli rozłącznych. Oraz przedstawić jako iloczyn transpozycji.

Czy mógłby ktoś w miarę step-by-step opisać jakiś algorytm najwygodniejszy do rozwiązania kolejno pkt'u a i b ? thx

Lider Artur · Post autor: **Lider Artur** » 25 cze 2011, o 18:55

cykle rozłączne (patrzysz co na co przechodzi - jak się zapętla, to bierzesz następny wyraz, który jeszcze nie wystąpił):
\(\displaystyle{ (1 5 8 9 6) (3 4 7)}\)

ares41 · Post autor: **ares41** » 25 cze 2011, o 18:58

Bierzesz pierwszą liczbę. Jest nią \(\displaystyle{ 1}\).
Patrzysz w co ona przechodzi (w piątkę) i zapisujesz:
\(\displaystyle{ \left(1, \ 5,.....}\)
Teraz szukasz piątki i patrzysz w co ona przechodzi.
\(\displaystyle{ \left(1, \ 5, \ 8,.....}\)

Postępujesz tak dalej aż w końcu dochodzisz do:
\(\displaystyle{ \left(1, \ 5, \ 8, \ 9, \ 6 \right)}\)
i tutaj domykasz nawias i zaczynasz nowy cykl.:

Kolejną liczbą jest dwójka, która przechodzi sama w siebie więc ją pomijasz.

Następna liczba to trójka:
Masz więc:
\(\displaystyle{ \left(1, \ 5, \ 8, \ 9, \ 6 \right) \circ \left(3, \ 4 , \ 7\right)}\)

PowerMan · Post autor: **PowerMan** » 25 cze 2011, o 19:26

Understood. Dziękuję.
jeżeli chodzi zaś o część
b) przedstawienie jako iloczyn transpozycji to jeśli dobrze rozumiem robimy to tak:
dzielimy permutację na iloczyn cykli, sprawdzamy ktore sa transponowane i je zapisujemy jako iloczyn?

czyli:
\(\displaystyle{ \left( 1,6\right)\left( 3,7\right)\left( 4,3\right)\left( 5,1\right)\left( 6,9\right)\left( 7,4\right)\left( 8,5\right)\left( 9,8\right)}\)
mamy tutaj 5 transpozycji:
\(\displaystyle{ \left( 4,3\right),\left( 5,1\right),\left( 7,4\right),\left( 8,5\right),\left( 9,5\right)}\)
no i teraz jako iloczyn:
\(\displaystyle{ \left( 4,3\right) \cdot \left( 5,1\right) \cdot \left( 7,4\right) \cdot \left( 8,5\right) \cdot \left( 9,5\right)}\)

Parzystość: liczba transpozycji to 5, więc sgn(PERM)=(-1) czyli nieparzysta

Dobrze rozumiem?, poprawcie jeśli gdzieś jest błąd.

ares41 · Post autor: **ares41** » 25 cze 2011, o 20:27

Nie bardzo wiem, co chciałeś tutaj zrobić.
Wystarczy po prostu skorzystać, ze wzoru:
\(\displaystyle{ (i_1,\ i_2, \ ,...., \ i_{k-1}, \ i_k)=(i_1, \ i_k) \circ (i_1, \ i_{k-1}) \circ ....\circ (i_1, \ i_2)}\)

PowerMan · Post autor: **PowerMan** » 25 cze 2011, o 20:41

Więc uzyskam:
\(\displaystyle{ \left( 1,6\right)\left( 1,9\right)\left( 1,8\right)\left( 1,5\right)\left( 3,7\right)\left( 3,4\right)}\)
i jest to już iloczyn transpozycji ?.

Jest tego sztuk 6 => permutacja parzysta ?
[czy źle Ciebie zrozumiałem]

ares41 · Post autor: **ares41** » 25 cze 2011, o 20:45

PowerMan pisze:i jest to już iloczyn transpozycji ?.

Tak. Możesz to sprawdzić wykonując te transpozycje ( od prawej) dla wyjściowego układu liczb.

PowerMan pisze:Jest tego sztuk 6 => permutacja parzysta ?

Tak.

PowerMan · Post autor: **PowerMan** » 25 cze 2011, o 20:47

Trochę odchodzi od tematu, ale nie będę tworzył nowego.
Wydaje mi się że tak, lecz nie mam pewności:
rząd permutacji \(\displaystyle{ f}\) w grupie \(\displaystyle{ S_{9}}\) to \(\displaystyle{ NWW}\) długości jej cykli rozłącznych , czyli rzędem tej permutacji jest:
\(\displaystyle{ NWW(5,3)=15}\)
czyli
\(\displaystyle{ rz(P)=15.}\)

?

--Tu były głupoty--

ares41 · Post autor: **ares41** » 25 cze 2011, o 20:58

Ogólnie:
Rzędem cyklu jest jego długość. Jeśli permutacja jest iloczynem cykli rozłącznych to jej rzędem jest najmniejsza wspólna wielokrotność długości cykli wchodzących w jej skład.

PowerMan pisze: \(\displaystyle{ NWW(5,3)=15}\)
czyli
\(\displaystyle{ rz(P)=15}\).

Jeżeli u Ciebie \(\displaystyle{ 5}\) i \(\displaystyle{ 3}\) są długościami cykli rozłącznych, których iloczynem jest permutacja \(\displaystyle{ f}\) to to co napisałeś jest dobrze.