Cycle decomposition(순환마디분해)

 Cycle(순환)이란 연속된 정수의 집합으로 S_n으로 나타낸다. 만약 집합 S_n이

일 경우 집합 S_n은 다음과 같은 순서로 연결된다.

위와 같이 Cycle은 마지막 component가 다시 첫 번째 component로 이어지면서 순환을 이루게 된다. 이를 다음과 같이 좀 더 쉽게 나타낼 수 있다.

 첫 번째 row는 순서를 나타낸 것이며 두 번째 row는 연결되는 다음 component를 나타낸 것이다.

 다음으로 σ ∈ S_n 일 때 만약 σ의 action이 다음과 같이 나타났다고 하자.

 위 결과는 총 k개의 Cycle을 생성하였고 각 Cycle이 어떻게 연결되어 있는지를 도식적으로 확인할 수 있다. 

 x ∈ { 1, 2, 3, ... ,n }에서 x의 값이 위의 가장 오른쪽에 있는 괄호 속에 값이 존재하지 않을 때(즉 위의 action에서 a_m 의 괄호 속으로 bold로 강조된 부분) c(x)는 x가 포함되어 있는 특정 괄호 속에서 바로 오른쪽에 위치한 정수값을 의미한다. 예를 들어 σ가 다음과 같이 주어졌을 때

 만약 σ(1)의 값을 구할 경우 위에서 가장 오른쪽에 있는 괄호의 component는 2와 4뿐이다. 그러므로 σ(1) = 3이다.

 x ∈ { 1, 2, 3, ... ,n }에서 x의 값이 위의 가장 오른쪽에 있는 괄호 속에 값이 존재하게 될 경우 σ(x)는 바로 오른쪽에 있는 정수 y를 확인한 후 해당 정수를 왼쪽의 괄호들에서 찾은 후 정수 y 값의 바로 오른쪽에 있는 정수값이다. 예를 들어

 만약 σ(1)의 값을 구할 경우 오른쪽에 있는 괄호에서 1의 바로 오른쪽에 있는 값 4를 선택한 후 왼쪽에 위치한 괄호에서 4를 찾은 후 4의 바로 오른쪽에 위치한 5가 σ(1)의 값이다. 즉 σ(1) = 5임을 알 수 있다. 이러한 방식으로 σ(x)의 값을 찾은 후 k개의 Cycle에서 중복되는 정수를 최대한으로 줄인 cycle을 찾는 과정을 cycle decomposition(순환마디분해)라고 한다.

 간단한 예제를 통해 윈리를 이해하여보자. n = 13이고.  σ ∈ S_n일 때 각 σ(x)의 값들이 다음과 같다고 가정하자.

 σ(1) = 12, σ(2) = 13, σ(3) = 3, σ(4) = 1, σ(5) = 11, σ(6) = 9, σ(7) = 5,

 σ(8) = 10, σ(9) = 6, σ(10) = 4, σ(11) = 7, σ(12) = 8,σ(13) = 2.

 이를 2개열의 행렬로 표현하면 다음과 같다.

 이를  Cycle S_n으로 나타내면 다음과 같다.

 총 5개의 cycle이 만들어졌으며 각각 5-cycle, 2-cycle, 1-cycle, 3-cycle, 2-cycle이다. 이 때 1-cycle은 1로 나타내어 생략할 수 있다. 따라서 cycle decomposition인 σ는

 Cycle decomposition인 σ가 σ ∈ S_n 를 만족할 때, σ^-1를 구할 수 있으며 이 때 σ^-1는 σ의 괄호 내부의 component의 순서를 반대로 하면 된다.

Reference : David S. Dummit, Richard M. Foote(2003), Abstract Algebra, WILEY