Re:No permutation in Sn can be expressed both as a product of an even number of transpositions and as a product of an odd number of transpositions

[폭풍속으로]

[질문] No permutation in Sn can be expressed both as a product of an even number of transpositions and as a product of an odd number of transpositions

[보조정리1] τ = (ij) 이면 τ-¹ = τ 이다.
[보조정리2] σ∈S_n, τ = (ij) 이면 {στ의 궤도(orbit)} = {σ의 궤도(orbit)}±1 이다.

[증명] 귀류법으로 증명합니다.
결론은 부정하여 적당한 σ∈S_n 에 대하여 σ는 짝수개의 호환의 곱과 홀수개의 호환의 곱으로 표현하는 것이 가능하다고 가정합니다.

그러면 적당한 호환 τ_1, τ_2, ... , τ_2n, ρ_1, ρ_2, ... , ρ_2m+1 에 대하여
σ = τ_1 * τ_2 * ... * τ_2n 이고 σ = ρ_1 * ρ_2 * ... * ρ_2m+1 입니다.

이때, σ-¹σ = id 임을 이용합니다. 단, id 는 n 차 항등치환입니다.
여기서 좌측의 σ 는 σ = τ_1 * τ_2 * ... * τ_2n 로, 우측의 σ 는 σ = ρ_1 * ρ_2 * ... * ρ_2m+1 로 대입합니다.

그러면 id = σ-¹σ = {τ_1 * τ_2 * ... * τ_2n}-¹*{ρ_1 * ρ_2 * ... * ρ_2m+1} 입니다.
그러면 id = {τ_2n * τ_2n-1 * ... * τ_1}*{ρ_1 * ρ_2 * ... * ρ_2m+1} 입니다.
그러면 id = {τ_2n * τ_2n-1 * ... * τ_1}*{ρ_1 * ρ_2 * ... * ρ_2m+1}*id 입니다.

이때, 좌변 id 의 궤도는 n 입니다.
우변의 궤도를 계산하는 것이 쬐끔 복잡합니다.

우선, 오른쪽에서부터 결합법칙을 적용합니다.
(ρ_2m+1 *id 의 궤도) = (id 의 궤도) ± 1 입니다.
또, (ρ_2m * ρ_2m+1 *id 의 궤도) = (ρ_2m+1 *id 의 궤도) ± 1 입니다.

이러한 방법으로 우측에서 좌측으로 계속 계산을 하면...
{좌변 Id 의 궤도} = (id 의 궤도) ± 1 ± 1 ± ... ± 1 입니다.
그러면 n = n ± 1 ± 1 ± ... ± 1 입니다.
이때, 우변의 ± 는 순서에 관계없이 뒤죽박죽으로 나타납니다.
또, ± 1 의 갯수는 홀수개입니다.
그러면 [n = n ± 1 ± 1 ± ... ± 1] 이 등식은 성립할 수 없습니다.
즉, 모순입니다.

그러므로 임의의 치환에 대하여 짝수개의 호환의 곱과 홀수개의 호환의 곱으로 동시에 표현하는 것은 불가능합니다.