순열: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 →반전수 |
편집 요약 없음 |
||
18번째 줄:
:<math>\cdots\mapsto x_{-1}\mapsto x_0\mapsto x_1\mapsto\cdots</math>
:<math>x\mapsto x\qquad\forall x\in X\setminus\{\dots,x_{-1},x_0,x_1,\dots\}</math>
여기서 <math>x_i\in X</math>는 서로 다른 원소이다. 특히, '''호환'''(互換, {{llang|en|transposition}}) <math>\begin{pmatrix}x&y\end{pmatrix}</math>은 2-순환이다. 특히, 유한 집합 <math>\{1,2,\dots,n\}</math>의 '''인접 호환'''(隣接互換, {{llang|en|adjecent transposition}}) <math>\begin{pmatrix}x&x+1\end{pmatrix}</math>은 인접한 두 수에 대한 호환이다.
=== 궤도 ===
순열 <math>\sigma\in\operatorname{Sym}(X)</math>의 [[순환군]] <math>\langle\sigma\rangle</math>은 <math>X</math>의 왼쪽에서 자연스럽게 [[군의 작용|작용]]한다. 이 작용의 궤도 <math>\langle\sigma\rangle(x)</math> (<math>x\in X</math>)들을 <math>\sigma</math>의 '''궤도'''(軌道, {{llang|en|orbit}})라고 한다.
순열 <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
=== 반전 ===
줄 29 ⟶ 35:
=== 부호 ===
▲순열 <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>
줄 73 ⟶ 77:
=== 순환 분해 ===
순열 <math>\sigma\in\operatorname{Sym}(X)</math>의 궤도 <math>\langle\sigma\rangle(x)</math> (<math>x\in X</math>)들은 <math>X</math>의 [[집합의 분할|분할]]을 이루며, 각 궤도에서의 제한은 다음과 같이 어떤 순환이다.
:<math>\sigma|_{\langle\sigma\rangle(x)}=
\begin{cases}
\begin{pmatrix}\cdots&\sigma^{-1}(x)&x&\sigma(x)&\cdots\end{pmatrix}|_{\langle\sigma\rangle(x)}
&|\langle\sigma\rangle(x)|\ge\aleph_0\\
\begin{pmatrix}x&\sigma(x)&\cdots&\sigma^{|\langle\sigma\rangle(x)|-1}(x)\end{pmatrix}|_{\langle\sigma\rangle(x)}
&|\langle\sigma\rangle(x)|<\aleph_0
\end{cases}</math>
만약 비자명 궤도(=크기가 1이 아닌 궤도)의 개수가 유한하다면, <math>\sigma</math>는 이러한 서로소 비자명 순환들의 곱으로 분해할 수 있다. 서로소 순환들은 항상 가환한데, <math>\sigma</math>의 서로소 비자명 순환 분해는 곱하는 순서를 따지지 않으면 유일하다. 이러한 분해를 <math>\sigma</math>의 '''순환 분해'''(循環分解, {{llang|en|cycle decomposition}})라고 한다. 순환 분해의 길이(=곱해지는 비자명 순환의 개수)는 비자명 궤도의 개수
:<math>|\{\langle\sigma\rangle(x)\colon\sigma(x)\ne x\}|</math>
와 같다. 특히, [[쌍대 유한]] [[고정점]] 집합을 갖는 순열은 항상 서로소 비자명 유한 순환들의 곱으로 유일하게 분해할 수 있다. 특히, 유한 집합의 순열 <math>\sigma\in\operatorname{Sym}(n)</math>의 순환 분해는 구체적으로 다음과 같다.
:<math>\sigma=
\begin{pmatrix}
\begin{pmatrix}\min(\{
=== 호환 분해 ===
줄 112 ⟶ 125:
:<math>\operatorname{inv\,num}(\sigma)=\min\{l\in\mathbb N\colon\sigma=
\begin{pmatrix}x_1&x_1+1\end{pmatrix}\cdots
\begin{pmatrix}x_l&x_l+1\end{pmatrix},\;x_i\in\{1,2,\dots,n-1\}\}</math>
=== 군론적 성질 ===
줄 118 ⟶ 131:
:<math>\operatorname{ord}(\sigma)=
\begin{cases}
\operatorname{lcm}_{x\in X}|\langle\sigma\rangle
\aleph_0&\{|\langle\sigma\rangle
특히, 순환의 위수는 그 길이와 같다.
줄 226 ⟶ 239:
:<math>3=1+1+1</math>
순열의 반전수의 몇 가지 예는 다음과 같다.
:<math>\operatorname{inv\,num}(\operatorname{id}_n)=0</math>
:<math>\operatorname{inv\,num}(
\begin{pmatrix}x&y\end{pmatrix})=|\{(y,x+1),(y,x+2),\dots,(y,y-1),(x+1,x),(x+2,x),\dots,(y-1,x),(y,x)\}|=2|y-x|-1</math>
:<math>\operatorname{inv\,num}
\begin{pmatrix}1&2&\cdots&n\\n&n-1&\cdots&1\end{pmatrix}
== 관련 개념 ==
| |||