위키득계정 ↗
과학

순열의 순환 분해

순열의 순환 분해과학
영어
Cycle decomposition of a permutation
표기 예
(1 4 2)(3 5)
분해 대상
유한집합의 순열
고정점
길이 1인 순환
순열의 순환 분해는 유한집합의 순열을 서로 겹치지 않는 순환들의 곱으로 나타내는 방법이다. 각 순환은 원소가 순열을 반복 적용받으며 차례로 이동하다가 출발점으로 돌아오는 경로를 기록한다.

괄호 안의 이동 읽기

(1 4 2)는 1을 4로, 4를 2로, 2를 1로 보내는 순환이다. 괄호에 없는 원소는 이 순환에서 고정된다. (1 4 2)(3 5)에서는 서로 다른 두 묶음이 독립적으로 움직인다. 이는 배열에 적힌 숫자들을 그대로 나열하는 표기와 구별된다.

분해를 구하는 절차

아직 기록하지 않은 원소 x에서 출발해 x, σ(x), σ²(x)를 따라간다. 처음 원소로 돌아오면 순환 하나가 완성된다. 그 순환에 없던 원소에서 같은 과정을 반복하면 모든 원소가 정확히 한 순환에 들어간다.

같은 순열의 여러 표기

(1 4 2), (4 2 1), (2 1 4)는 시작점만 다른 같은 순환이다. 또한 서로 겹치지 않는 순환들은 합성 순서를 바꾸어도 결과가 같다. 이 두 가지 표기의 자유를 제외하면 순환 분해는 유일하다. 고정점은 생략할 수 있지만 전체 원소 수를 셀 때는 포함해야 한다.

반복 횟수와 연결

(1 4 2)(3 5)를 여섯 번 적용하면 각 순환이 모두 제자리로 돌아온다. 세 번만 적용하면 3과 5는 여전히 바뀌고 두 번만 적용하면 첫 순환이 돌아오지 않는다. 일반적으로 순열의 위수는 서로 겹치지 않는 순환 길이들의 최소공배수로 계산된다.

관련 문서

대칭군 / 전치 (순열) / 위수 (군론) / 최소공배수 / 제1종 스털링 수 / 켤레류