2017년 7월 24일 (월) 03:54 판 편집 慈居 (토론 \| 기여) 장기인증된 사용자 18,476 편집 →‎성질 ← 이전 편집		2017년 7월 24일 (월) 06:18 판 편집 편집 취소 慈居 (토론 \| 기여) 장기인증된 사용자 18,476 편집 편집 요약 없음 다음 편집 →
22번째 줄: === 반전 === 순열 <math>\sigma\in\operatorname{Sym}(n)</math>에 대하여, [[튜플]] <math>(x,y)\in\{1,2,\dots,n\}^2</math>이 다음 두 조건을 만족시키면, <math>\sigma</math>의 '''반전'''(反轉 {{llang\|en\|inversion}})이라고 한다. * <math>\sigma^{-1}(x)<\sigma^{-1}(y)</math> * <math>~~\sigma(~~x)>~~\sigma(~~y)</math> 또한, <math>\sigma</math>의 '''~~반전수~~반전 벡터'''(反轉數-, {{llang\|en\|inversion ~~number~~vector}}) <math>\operatorname{inv\,vec}(\sigma)~~</math> 또는 <math>N(~~\~~sigma)</math>는 <math>~~in\~~sigma</math>의 모든 반전의 개수이다. <math>~~{0,1,\~~sigma</math>의 '''감소량'''(減少量~~dots, ~~{{llang\|en\|decrement~~n-1\}~~}) <math>\operatorname~~^{~~dec~~n-1}~~(\sigma)~~</math>는 그 <math>ny</math>에서번째 성분이 <math>~~\sigma~~y</math>의로 ~~[[군~~끝나는 ~~작용\|궤도]]의 개수를~~반전의 뺀개수인 ~~것이다~~벡터이다. 즉, 이는 다음과 같다. :<math>\operatorname{~~dec~~inv\,vec}(\sigma)_y=~~\min~~\|\{lx\in\~~mathbb N~~{1,2,\dots,n\}\colon\sigma=^{-1}(x)<\sigma^{-1}(y),\;x>y\}\|</math>▼ 또한, <math>\sigma</math>의 '''반전수'''(反轉數, {{llang\|en\|inversion number}}) <math>\operatorname{inv}(\sigma)</math> 또는 <math>N(\sigma)</math>는 <math>\sigma</math>의 모든 반전의 개수이다. 즉, 반전 벡터의 모든 성분의 합이다. === 부호 === 순열 <math>\sigma\in\operatorname{Sym}(n)</math>의 '''감소량'''(減少量, {{llang\|en\|decrement}}) <math>\operatorname{dec}(\sigma)</math>는 <math>n</math>에서 <math>\sigma</math>의 [[군 작용\|궤도]]의 개수를 뺀 것이다. 즉, 이는 다음과 같다. :<math>\operatorname{dec}(\sigma)=n-\|\{\langle\sigma\rangle\cdot x\colon x\in\{1,2,\dots,n\}\}\|</math> ~~또한,~~ 순열의 '''부호'''(符號, {{llang\|en\|sign}}) <math>\sgn\colon\operatorname{Sym}(n)\to\{-1,1\}</math>은 다음 조건을 만족시키는 유일한 [[군 준동형]]이다. :<math>-1=\sgn(\begin{pmatrix}1&2\end{pmatrix})=\sgn(\begin{pmatrix}2&3\end{pmatrix})=\cdots=\sgn(\begin{pmatrix}n-1&n\end{pmatrix})</math> 구체적으로, <math>\sigma</math>의 부호 <math>\sgn(\sigma)</math>는 다음의 두 값과 같다. 줄 32 ⟶ 37: === 홀짝성 === ~~반전수와~~ 반전수·감소량·부호를 통해 유한 집합의 순열의 '''홀짝성'''(-性, {{llang\|en\|parity}})을 정의할 수 있다. 순열 <math>\sigma\in\operatorname{Sym}(n)</math>에 대하여, 다음 두세 조건이 서로 [[동치]]이며, 이를 만족시키는 <math>\sigma</math>를 '''홀순열'''(-順列, {{llang\|en\|odd permutation}})이라고 한다. * <math>\operatorname{inv}(\sigma)</math>는 [[홀수]]이다. * <math>\operatorname{dec}(\sigma)</math>는 홀수이다. * <math>\sgn(\sigma)=-1</math> 홀순열이 아닌 순열을 '''짝순열'''(-順列, {{llang\|en\|even permutation}})이라고 한다. 즉, 순열 <math>\sigma\in\operatorname{Sym}(n)</math>에 대하여, 다음 두세 조건이 서로 [[동치]]이며, 이를 만족시키는 <math>\sigma</math>를 '''짝순열'''이라고 한다. * <math>\operatorname{inv}(\sigma)</math>는 [[짝수]]이다. * <math>\operatorname{dec}(\sigma)</math>는 짝수이다. 줄 48 ⟶ 53: * 임의의 <math>X</math>의 순열 <math>\sigma</math>에 대하여, 그 [[역함수\|역]] <math>\sigma^{-1}\colon\sigma(x)\mapsto x</math> 역시 <math>X</math>의 순열이다. (이는 군의 [[역원]] 연산이다.) === 순환 분해 === 순열 <math>\sigma\in\operatorname{Sym}(X)</math>의 [[순환군]] <math>\langle\sigma\rangle</math>은 자연스러운 <math>X</math> 위의 [[군 작용]]을 준다. 이 군 작용의 궤도 <math>\langle\sigma\rangle\cdot x</math>(<math>x\in X</math>)들은 <math>X</math>의 [[집합 분할]]을 이루며, 각 궤도에서의 제한 <math>\sigma\|_ {\langle\sigma\rangle\cdot x}</math>은 그 궤도의 순환이다. 만약 궤도의 개수가 유한하다면, <math>\sigma</math>는 이러한 서로소 순환들의 곱으로 분해할 수 있다. 서로소 순환들은 항상 가환한데, <math>\sigma</math>의 서로소 순환 분해는 곱하는 순서를 따지지 않으면 유일하다. 서로소 순환 분해의 길이(=곱해지는 순환의 개수)는 궤도의 개수와 같다. 특히, [[쌍대 유한]] [[고정점]] 집합을 갖는 순열은 항상 서로소 유한 순환들의 곱으로 분해할 수 있으며, 이러한 분해는 곱하는 순서를 무시하면 항상 유일하다. 특히, 유한 집합의 순열 ~~역시 유일한 서로소 유한 순환 분해를 가지며, 구체적으로~~ <math>\sigma\in\operatorname{Sym}(n)</math>의 순서를 무시하면 유일한 서로소 유한 순환 분해는 구체적으로 다음과 같다. :<math>\sigma= \begin{pmatrix}1&\sigma(1)&\cdots\end{pmatrix} \begin{pmatrix}\min(\{1,2,\dots,n\}\setminus\{1,\sigma(1),\dots\})&\sigma(\min(\{1,2,\dots,n\}\setminus\{1,\sigma(1),\dots\}))&\cdots\end{pmatrix}\cdots</math> 그 ~~밖의 여러 분해가 성립한다. 예를 들어~~밖에, 짝순열은 항상 3-순환들의 곱으로 나타낼 수 있다.▼ === 호환 분해 === 유한 순환은 항상 호환들의 곱으로 분해할 수 있다. 이러한 분해는 유일할 필요가 없다. 예를 들어, 어떤 호환의 짝수 제곱을 인수로 추가하면 새로운 호환 분해를 얻는다. 또한, 구체적으로 다음과 같은 분해식들이 성립한다. :<math> 줄 65 ⟶ 73: \begin{pmatrix}x_1&x_{k-1}\end{pmatrix}\cdots \begin{pmatrix}x_1&x_2\end{pmatrix}</math> 홀순열의 호환 분해의 길이는 항상 홀수이며, 짝순열의 호환 분해의 길이는 항상 짝수이다. 이를 순열의 홀짝성을 정의하는 데 쓸 수 있다.▼ 유한 집합의 호환은 항상 인접 호환들의 곱으로 분해할 수 있다. 이 역시 유일할 필요가 없으며, 구체적으로 다음과 같은 분해식이 성립한다.▼ 유한 집합의 순열의 호환 분해의 최소 길이는 감소량과 같다. 즉, 순열 <math>\sigma\in\operatorname{Sym}(n)</math>에 대하여, 다음이 성립한다.▼ :<math>\operatorname{dec}(\sigma)=\min\{l\in\mathbb N\colon\sigma= \begin{pmatrix}x_1&y_1\end{pmatrix}\cdots▼ \begin{pmatrix}x_l&y_l\end{pmatrix},\;x_i,y_i\in\{1,2,\dots,n\}\}</math>▼ === 인접 호환 분해 === ▲유한 집합의 호환은 항상 인접 호환들의 곱으로 분해할 수 있다. 이이러한 역시분해는 유일할 필요가 없으며, 구체적으로 다음과 같은 분해식이 성립한다. :<math> \begin{pmatrix}x&y\end{pmatrix}= 줄 74 ⟶ 90: \begin{pmatrix}y-1&y-2\end{pmatrix}\cdots \begin{pmatrix}x+1&x\end{pmatrix}</math> ▲그 밖의 여러 분해가 성립한다. 예를 들어, 짝순열은 항상 3-순환들의 곱으로 나타낼 수 있다. ▲홀순열의 호환 분해의 길이는 항상 홀수이며, 짝순열의 호환 분해의 길이는 항상 짝수이다. 이를 순열의 홀짝성을 정의하는 데 쓸 수 있다. ▲유한 집합의 순열의 호환 분해의 최소 길이는 감소량과 같다. 즉, 순열 <math>\sigma\in\operatorname{Sym}(n)</math>에 대하여, 다음이 성립한다. ▲:<math>\operatorname{dec}(\sigma)=\min\{l\in\mathbb N\colon\sigma= ▲\begin{pmatrix}x_1&y_1\end{pmatrix}\cdots ▲\begin{pmatrix}x_l&y_l\end{pmatrix},\;x_i,y_i\in\{1,2,\dots,n\}\}</math> 유한 집합의 순열의 인접 호환 분해의 최소 길이는 반전수와 같다. 즉, 순열 <math>\sigma\in\operatorname{Sym}(n)</math>에 대하여, 다음이 성립한다. :<math>\operatorname{inv}(\sigma)=\min\{l\in\mathbb N\colon\sigma= 줄 92 ⟶ 99: :<math>\operatorname{ord}(\sigma)= \begin{cases} \operatorname{lcm}_{x\in X}\|\langle\sigma\rangle\cdot x\|&\|\{x\|\~~in X\colon~~langle\sigma(\rangle\cdot x)\|\necolon x\in X\}\|\in\mathcal P_{<\aleph_0}(\mathbb Z^+)\\ \aleph_0&\|\{x\|\~~in X\colon~~langle\sigma(\rangle\cdot x)\|\necolon x\in X\}\|\genot\in\mathcal P_{<\aleph_0}(\mathbb Z^+)\end{cases}</math> 특히, 순환의 위수는 그 길이와 같다.

순열: 두 판 사이의 차이