순열의 동등성

4원소 순열

이상한 순열은 녹색 또는 주황색 배경을 가지고 있다.오른쪽 열의 숫자는 순열과 동일한 패리티를 갖는 반전 번호(OEIS의 순서 A034968)이다.

수학에서 X가 최소한 두 개의 원소를 가진 유한 집합일 때, X의 순열(즉, X에서 X까지의 주관적 함수)은 같은 크기의 두 종류, 즉 짝수 순열과 홀수 순열로 나뉜다.X의 전체 순서가 고정된 경우, X의 $\sigma$ 순열 $\sigma$ $\sigma$ 의 패리티(이상 또는 짝수)는 x < y>와 in(x) > σ(y)와 같은 X의 y인 σ에 대한 반전 수의 패리티로 정의할 수 있다.

순열 σ의 부호, 서명 또는 부호는 sgn(σ)으로 표시되며, σ이 짝수이면 +1, σ이 홀수이면 -1로 정의된다.서명은 대칭군 S의_n 교대 문자를 정의한다.순열의 부호에 대한 또 다른 표기법은 보다 일반적인 Levi-Civita 기호(ε_σ)에 의해 주어지는데, X에서 X까지의 모든 지도에 대해 정의되며, 비주사적 지도에 대해서는 값이 0이다.

순열의 기호는 다음과 같이 명시적으로 표현할 수 있다.

sgn(σ) = (-1) N (σ)

여기서 N(N)은 σ의 반전 수입니다.

또는 순열 σ의 부호는 그 분해로부터 다음과 같이 전이의 산물로 정의할 수 있다.

sgn(σ) = (-1) m

여기서 m은 분해의 전이 횟수다.그러한 분해는 고유하지 않지만, 모든 분해에서 전이 횟수의 동등성은 동일하므로 순열의 징후가 잘 정의되어 있음을 암시한다.^[1]

예

Consider the permutation σ of the set {1, 2, 3, 4, 5} defined by $\sigma (1)=3,$ $\sigma (2)=4,$ $\sigma (3)=5,$ $\sigma (4)=2,$ and ${\displaystyle \sigma (5)=1.$ $}}$ 한 줄 표기법으로 $\sigma (5)=1.$ 이 순열은 34521로 표시된다.1번 2번과 4번을 교환하고 3번과 5번을 교환하고 1번과 3번을 교환하는 등 3번의 전이를 통해 12345번 신원 순열에서 얻을 수 있다.이는 주어진 순열 σ이 이상하다는 것을 보여준다.사이클 표기법 글의 방법에 따라, 이것을 왼쪽에서 오른쪽으로 작곡하여 쓸 수 있었다.

\sigma ={\begin{pmatrix}1&2&3&4&5\\3&4&5&2&1\end{pmatrix}}={\begin{pmatrix}1&3&5\end{pmatrix}}{\begin{pmatrix}2&4\end{pmatrix}}={\begin{pmatrix}1&3\end{pmatrix}}{\begin{pmatrix}3&5\end{pmatrix}}{\begin{pmatrix}2&4\end{pmatrix}}.

예를 들어 전이의 구성으로서 σ을 쓰는 방법에는 여러 가지가 있다.

σ = (1 5)(3 4)(2 4)(1 2)(2 3)

,

하지만 짝수 전이의 산물로 쓰는 것은 불가능하다.

특성.

아이덴티티 순열은 짝수 순열이다.^[1]짝수 순열은 짝수 및 두 원소의 짝수 교환(일명 전이)의 구성으로 얻을 수 있는 반면 홀수 순열은 홀수 전이에 의해서만 얻을 수 있다.

다음 규칙은 정수의 추가에 관한 해당 규칙에서 직접 따른다.^[1]

짝수 순열의 구성은 짝수다.
두 개의 이상한 순열의 구성은 짝수다.
홀수와 짝수 순열의 구성이 이상하다.

이로부터 그것은 다음과 같다.

짝수 순열의 역행은 짝수다.
모든 홀수 순열의 역행은 이상하다.

세트 {1, ..., n}의 모든 순열의 대칭 그룹 S를_n 고려하면, 지도는 결론을 내릴 수 있다.

sgn n : S \to {-1, 1)

모든 순열화에 그것의 서명은 집단 동형상이다.^[2]

게다가, 우리는 짝수 순열이 S의_n 부분군을 형성한다는 것을 안다.^[1]이것은 A로_n 표기된 n글자로 교대하는 그룹이다.^[3]그것은 동형상 sgn의 알맹이다.^[4]홀수 순열은 두 개의 홀수 순열의 합이 짝수이기 때문에 부분군을 형성할 수 없지만 A_n(S_n)의 코세트를 형성한다.^[5]

n > 1이면 S에는_n 홀수 순열만큼 짝수 순열이 많다.^[3] 따라서 A에는_n n!/2 순열이 포함된다.(이유는 σ이 짝수일 경우 (1)σ이 홀수일 경우, ^[3]odd이 홀수일 경우 (1) even가 짝수일 경우, 이 두 지도가 서로 역수일 경우)

주기는 길이가 홀수인 경우에 한한다.이것은 다음과 같은 공식에서 온다.

{\displaystyle(a\ b\c\ d\ e)=(d\ e)(c\ e)(b\ e)(a\ e){\text{ 또는 }(a\ b)(b\c\ c)(d\ e).}

실제로 주어진 순열이 짝수인지 홀수인지를 판단하기 위해, 순열을 분리 주기의 산물로 쓴다.이 요인화에 홀수 수의 짝수 길이 사이클이 포함된 경우에만 순열이 홀수다.

주어진 순열이 짝수인지 홀수인지를 판단하는 또 다른 방법은 해당 순열 행렬을 구성하고 그 결정 인자를 계산하는 것이다.결정인자의 값은 순열의 동등성과 동일하다.

홀수 순서의 순열은 반드시 짝수여야 한다.A의₄ 순열(1 2)(3 4)은 그 역이 일반적으로 사실이 아님을 보여준다.

두 정의의 등가성

이 절에서는 순열 σ의 동등성이 두 가지 동등한 방법으로 정의될 수 있다는 증거를 제시한다.

(모든 주문에 따라) σ의 반전 횟수의 비율로서, 또는
σ이 분해될 수 있는 전이 횟수의 비례에 따라 (하지만 우리는 분해할 것을 선택한다.)

증명1길

S등급의 도메인에서 perm을 순열로 삼자.모든 순열은 일련의 전이(2-element Exchange)에 의해 생산될 수 있다.다음은 그러한 분해의 하나가 되게 하라.

σ = T T₁ T₂ ...T_k

우리는 k의 패리티가 σ의 역전 횟수의 패리티와 같다는 것을 보여주고 싶다.

모든 전치는 인접한 원소의 홀수 전이의 산물로 기록될 수 있다.

(2 5) = (2 3) (3 4) (4 5) (4 3) (3 2).

일반적으로 우리는 세트 {1, ..., i, i, ..., i+d, ...에 transposition(i+d)을 쓸 수 있다.} d:에 대한 재귀에 의한 2d-1 인접 트랜지션의 구성으로:

base case d=1은 사소한 것이다.

재귀의 경우에는 (i, i+1) (i, i+1) (i+1, i+d) (i, i+1)로 먼저 재작성한다.그런 다음 인접한 전이로서 재귀적으로 다시 쓰기(i+1, i+d)한다.

우리가 이런 식으로 분해한다면 각각의 전이 T₁...위_k T에서는 새로운 분해 과정을 볼 수 있다.

σ₁ = A₂ ...A을_m

A의₁ 모든 것이...A이_m 인접해 있다또한 m의 패리티는 k의 패리티와 같다.

이것은 사실이다: 모든 순열 τ과 인접 위치 a의 경우, aτ는 τ보다 한 개 또는 한 개의 역전을 더 가지고 있다.즉, 인접한 전위치로 구성했을 때 순열의 반전 횟수의 패리티가 전환된다.

따라서 σ의 반전 횟수의 패리티는 정확히 m의 패리티로, k의 패리티도 된다.이것이 우리가 증명하기 위해 시작한 것이다.

따라서 우리는 σ의 동등성을 모든 분해에서 그 구성적 전이 수의 동등하다고 정의할 수 있다.그리고 이것은 위에서 본 바와 같이 어떤 주문에 따른 반역 횟수의 비율과 일치해야 한다.그러므로 그 정의는 참으로 잘 정의되어 있고 동등하다.

증명2길

Vandermonde 다항식(다항식)을 사용하는 대안적 증거

P(x_{1},\ldots ,x_{n}}=\prod _{i}(x_{i}-x_{j}).

예를 들어, 사례 n = 3에서,

P(x_{1},x_{2},x_{3}=(x_{1}-x_{2}-x_{3})(x_{1}-x_{3})(x_{1}-x_{3}).

이제 {1, ..., n} 숫자의 주어진 순열 for에 대해 정의한다.

\operatorname {sgn}(\sigma )={\frac {P(x_{\sigma(1)},\ldots,x_{\sigma(n)}}}{P(x_{1},\ldots,x_{n}}}}}}.

Since the polynomial $P(x_{\sigma (1)},\dots ,x_{\sigma (n)})$ has the same factors as $P(x_{1},\dots ,x_{n})$ except for their signs, it follows that sgn(σ) is either +1 or −1.더군다나 σ과 τ이 두 순열이라면 우리는 그렇게 본다.

{\begin{aigned}\operatorname {sgn}(\sigma \tau )&={\frac {P(x_{\sigma (\tau (1))}},\dots,x_{n}}}}\\[4pt]&={\frac {P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}{P(x_{1},\ldots ,x_{n})}}\cdot {\frac {P(x_{\sigma (\tau (1))},\ldots ,x_{\sigma (\tau (n))})}{P(x_{\sigma (1)},\ldots ,x_{\sigma (n)})}}\\[4pt]&=\operatorname {sgn}(\sigma )\cdot \operatorname {sgn}(\tau ).\end{정렬}}

이 정의를 사용하면 두 요소의 어떤 전환도 -1 서명이 있으므로, 우리는 실제로 앞에서 정의한 서명을 복구한다.

증명3길

세 번째 접근방식은 발전기 τ₁, ..., τ_n−1 및 관계 측면에서 그룹 S의_n 표시를 사용한다.

$\tau _{i}^{2}=1$ $\tau _{i}^{2}=1$ $\tau _{i}^{2}=1$ = $\tau _{i}^{2}=1$ ${\displaystyle \tau_{i}^{2}=$ 1} $모든$ i에 대해 $\tau _{i}^{2}=1$
$\tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}$ $\tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}$ $\tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}$ i $\tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}$ + $\tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}$ $\tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}$ i $\tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}$ = $\tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}$ $\tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}$ + $\tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}$ $\tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}$ { i $\tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}$ + $\tau _{i}^{}\tau _{i+1}\tau _{i}=\tau _{i+1}\tau _{i}\tau _{i+1}$ {\ $displaystyle \tau _{i}^{}^{i+1}\tau _{i}=\tau$ _{ $i+1}\tau _{i}\$ 1}{i+1}{i $\tau_i^{}\tau_{i+1}\tau_i = \tau_{i+1}\tau_i\tau_{i+1}$ $+$ 1}:{i $+1$ }}}}}}}}}}}}}}}}.
$\tau _{i}^{}\tau _{j}=\tau _{j}\tau _{i}$ $\tau _{i}^{}\tau _{j}=\tau _{j}\tau _{i}$ $\tau _{i}^{}\tau _{j}=\tau _{j}\tau _{i}$ $\tau _{i}^{}\tau _{j}=\tau _{j}\tau _{i}$ = $\tau _{i}^{}\tau _{j}=\tau _{j}\tau _{i}$ $\tau _{i}^{}\tau _{j}=\tau _{j}\tau _{i}$ { $\tau _{i}^{}\tau _{j}=\tau _{j}\tau _{i}$ ${\$ j}=\ $tau _{j$ }\ $tau_{i},$ i $\tau _{i}^{}\tau _{j}=\tau _{j}\tau _{i}$ }, if $.$

교정4길

x < y와 σ(x) > σ(y)와 같은 쌍 x, y를 역행이라고 부르는 것을 상기한다.우리는 반전 개수가 2-element 스왑 개수와 동일한 패리티를 가지고 있다는 것을 보여주고 싶다.그러기 위해서는 어느 두 요소가 스와핑되고 있고 어떤 순열화가 이미 적용되었든 간에 모든 스왑이 반전 카운트의 패리티를 변화시킨다는 것을 보여줄 수 있다.ith와 jth 요소를 교환한다고 가정합시다.분명히, [i, j] 이외의 요소와 함께 i 또는 j에 의해 형성된 반전들은 영향을 받지 않을 것이다.n = j - i - 1 간격(i, j) 내의 원소에 대해, 이들_i 중 v가 i와 역전을 형성하고 v가_j j와 역전을 형성한다고 가정한다.i와 j를 교환하면 i와 그 v_i inversion은 사라지지만 n - v inversion은_i 형성된다.따라서 내가 얻은 역전 횟수는 n - 2v로_i, n과 동일한 패리티를 갖는다.

마찬가지로, 획득한 반전 j의 카운트도 n과 동일한 패리티를 가진다.따라서 두 개를 조합하여 얻은 역전 횟수는 2n 또는 0과 동일한 패리티를 가진다.이제 ith와 j번째 요소를 스와핑하여 얻은 반전(또는 손실)을 계산하면, 이 스왑이 반전 카운트의 패리티를 변경한다는 것을 알 수 있는데, 이는 페어(i,j)에 대해 획득한 반전(또는 손실된) 수에 1을 추가(또는 빼기)하기 때문이다.

처음에 스왑을 적용하지 않을 경우 반전 카운트는 0이라는 점에 유의하십시오.이제 순열의 동등성에 대한 두 가지 정의의 동등성을 얻는다.

교정5길

전환의 두 원소에 의해 샌드위치 된 원소를 고려하라.각각은 완전히 위쪽에 놓여 있고, 완전히 아래 또는 두 개의 전이 요소 사이에 놓여 있다.

완전히 위 또는 아래에 있는 요소는 전치 적용 시 반전 카운트에 아무런 기여도 하지 않는다.중간 요소는 $2$ $2$ 기여 $2$

전환 자체가

\pm 1

±

\pm 1

\pm 1

의

\pm 1

역전을 제공하고, 다른 모든

0{\pmod {2}}

은 0

0{\pmod {2}}

2

){\

0

{\pmod{2}}}

의

0{\pmod {2}}

역전을 공급하므로 전환 횟수의 패리티가 변경된다.

기타 정의 및 증명

$n$ $n$ 포인트의 $n$ 순열도 또한 사이클 구조로 암호화된다.

σ = (i₁ i₂ ... i_r+1)(j₁ j₂ ... j)로 하자_s+1...(ℓ₁ ℓ₂ ...ℓ_u+1) σ의 분해 사이클로 분해되는 고유 분해로서, 통근하기 때문에 어떤 순서로도 구성될 수 있다.사이클(a b c ... x y z)는 k transposition(2-주기)을 구성하여 항상 얻을 수 있다.

(a\displaystyle (a\ b\c\ x\ y\ z)=(a\ b)(b\ c)\display(x\ y)(y\ z),}

그러므로 주기의 크기 k를 호출하고, 이 정의에서 전이는 크기 1의 주기임을 관찰한다.분해에서 m 디스조인트 사이클로 우리는 σ을 k₁ + k + k₂ + ...로 분해할 수 있다. + k_m transitions, 여기서 k는_i ih 사이클의 크기.숫자 N(σ) = k₁ + k + k₂ + ... + k는_m σ의 판별이라고 불리며, as로도 계산할 수 있다.

{\displaystyle n{\text{}} }}분해에서 분리 주기 수를 뺀다.

σ의 고정 포인트를 1 사이클로 포함하도록 주의할 경우.

순열 σ 후에 전위(a b)가 적용된다고 가정한다.a와 b가 σ의 다른 주기에 있을 때

(a\ b)(a\ c_{1}\ c_{2}\dots c_{r})(b\ d_{1}\ d_{2}\dots d_{s})=(a\ c_{1}\ c_{2}\dots c_{r}\ b\ d_{1}\ d_{2}\dots d_{s})

,

그리고 a와 b가 σ의 동일한 사이클에 있다면

(a\ b)(ac_{1}c_{2}\dots c_{r}\ b\ d_{1}\ d_{2}\dots d_{s})=(a\ c_{1}\ c_{2}\dots c_{r})(b\ d_{1}\ d_{2}\dots d_{s})

.

어느 경우든 N((a b) = = N(σ) ± 1이므로 N(a b)σ의 패리티가 N(σ)의 패리티와 다른 것을 알 수 있다.

만약 = = tt₁₂ ... t가_r 순열 σ을 임의로 전이로 분해한 것이라면, identity(N이 0인 경우) 후 t_r ...후 ...에 $t_{1}$ ₂ r t $t_{1}$ 1 ${\$ }를 적용하여 N(σ)과 r이 동일한 패리티를 갖는 것을 관찰한다.σ의 패리티를 N(σ)의 패리티로 정의함으로써 짝수 길이 분해되는 순열은 짝수 순열이고 홀수 길이 분해되는 순열은 홀수 순열이다.

언급

위의 논거에 대한 면밀한 조사를 통해 r σ N(σ)을 알 수 있으며, r에 합한 크기를 r transitions의 구성으로 표현할 수 있는 사이클로 분해하기 때문에, N(σ)은 모든 사이클이 transition인 경우를 포함하여 σ의 분해에서 사이클 크기의 최소 합이다.
이 증거는 σ이 작용하는 점 집합에 (아마도 임의적인) 순서를 도입하지 않는다.

일반화

패리티는 Coxeter 그룹에 일반화할 수 있다. 하나는 길이 함수 ℓ(v)를 정의하는데, 이 함수는 생성자 선택(대칭 그룹, 인접 전이의 경우)에 따라 달라지며, 그 다음 v ↦(-1) ^ℓ(v)함수는 일반화된 기호 지도를 제공한다.

참고 항목

15개의 퍼즐은 고전적인 응용 프로그램이다.
졸로타레프 보조정리

메모들

^ ^a ^b ^c ^d 제이콥슨(2009년), 페이지 50.
^ 로트만(1995), 페이지 9, 정리 1.6.
^ ^a ^b ^c 제이콥슨(2009년), 페이지 51.
^ Goodman, 페이지 116 정의 2.4.21
^ 메이저 & 바우어(2004), 페이지 72

참조

Weisstein, Eric W. "Even Permutation". MathWorld.
Jacobson, Nathan (2009). Basic algebra. Vol. 1 (2nd ed.). Dover. ISBN 978-0-486-47189-1.
Rotman, J.J. (1995). An introduction to the theory of groups. Graduate texts in mathematics. Springer-Verlag. ISBN 978-0-387-94285-8.
Goodman, Frederick M. Algebra: Abstract and Concrete. ISBN 978-0-9799142-0-1.
Meijer, Paul Herman Ernst; Bauer, Edmond (2004). Group theory: the application to quantum mechanics. Dover classics of science and mathematics. Dover Publications. ISBN 978-0-486-43798-9.

[Jacobson-1] 제이콥슨(2009년), 페이지 50.

[2] 로트만(1995), 페이지 9, 정리 1.6.

[Jacobson_a-3] 제이콥슨(2009년), 페이지 51.

[4] Goodman, 페이지 116 정의 2.4.21

[5] 메이저 & 바우어(2004), 페이지 72

[1]

[2]

[3]

[4]

[5]

Search

순열의 동등성

네임스페이스

더

목차

예

특성.

두 정의의 등가성

기타 정의 및 증명

일반화

참고 항목

메모들

참조