2014/12/21

置換と偶置換・奇置換に関する基礎的なこと

分野: 代数,情報・暗号理論  レベル: 大学数学

$n$ 個のものを並び替える操作を置換と言う。

置換は行列式の定義に使われていたり,ルービックキューブの理論などいろいろな対称性を扱うために使われたりと様々な場面で登場する重要な概念です。

追記:8パズル,15パズルの解析にも置換は活躍します。→8パズル,15パズルの不可能な配置と判定法

置換とは

・ $1,2,\cdots ,n$ を並び替える操作を $n$ 次の置換と言います。ここでは置換を $\sigma$ と表します(厳密には集合 $X$ から $X$ への全単射を置換と言う)。

・置換はもとの元を上に並べて行き先を下に並べたような形で表現されます。

$\sigma=\begin{pmatrix}
1 & 2 & 3 & 4 & 5\\
2 & 3 & 5 & 4 & 1
\end{pmatrix}$
置換 $\sigma$ によって $1$ は $2$ に,$4$ は $4$ に移される。
これを $\sigma(1)=2$,$\sigma(4)=4$ などと表す。

  • 置換によって「$(1,2,\cdots, n)$ を並び替えた後の状態」は $1$ から $n$ までの順列となっています。よって,順列と置換は対応しています。
  • よって,$n$ 次の置換は全部で $n!$ 個あります。

置換の積と対称群

  • 置換 $\sigma_1$ と置換 $\sigma_2$ の合成を置換の積と定義します。「置換を2回かます操作」は1回の置換で表現できるので置換の積もまた置換です。
  • $\sigma_1\sigma_2$ は先に $\sigma_2$ で置換してから $\sigma_1$ で置換したものです。

$\sigma_1=\begin{pmatrix}
1 & 2 & 3 & 4 \\
3 & 2 & 1 & 4
\end{pmatrix}$, $\sigma_2=\begin{pmatrix}
1 & 2 & 3 & 4 \\
1 & 3 & 2 & 4
\end{pmatrix}$

に対して
$\sigma_1\sigma_2=\begin{pmatrix}
1 & 2 & 3 & 4 \\
3 & 1 & 2 & 4
\end{pmatrix}$

例えば,$2$ は $\sigma_2$ で $3$ にうつって $\sigma_1$ でさらに $1$ にうつります。よって,$(\sigma_1\sigma_2)(2)=1$ です。

・ $n$ 次の置換全体の集合は群をなします。そのため $n$ 次置換群,対称群などと呼ばれることもあります。対称群と書くと仰々しいですが要はただの順列の集合みたいなものです。

互換とは

・置換の中でも二つの要素を交換するだけのものを特に互換と言います。

・ $i$ と $j$ を交換する互換を$(i,j)$ と書きます。

$\sigma=\begin{pmatrix}
1 & 2 & 3 & 4 \\
3 & 2 & 1 & 4
\end{pmatrix}$
は $1$ と $3$ を交換するだけの置換なので互換。 $\sigma=(1,3)$ と書く。

・どんな並べ替えも二つのものの交換を何回か行うことで実現できます。すなわち任意の置換はいくつかの互換の積で表現できます。

実際に与えられた置換を互換の積で表現するには,例えば以下のように左端から順々に揃えていけばOKです(これで置換が互換の積で表せることの構成的な証明になっていると思います)。

置換とあみだくじ

最初の例:
$\sigma=\begin{pmatrix}
1 & 2 & 3 & 4 & 5\\
2 & 3 & 5 & 4 & 1
\end{pmatrix}$
は「一つ目と二つ目を交換」「二つ目と三つ目を交換」「三つ目と五つ目を交換」という互換を順番にかますと実現できるので,$\sigma=(3,5)(2,3)(1,2)$ と書ける。
ジャンプ有りのあみだくじみたいな感じ。

奇置換と偶置換

任意の置換 $\sigma$ はいくつかの互換の積で表せますが,その表し方は何通りもあります。しかし,$\sigma$ を互換の積で表したときに,その互換の数の偶奇は表し方によらず $\sigma$ のみで決まります。(※)

よって,必要な互換の数が偶数であるものを偶置換,奇数であるものを奇置換と呼ぶことができます。

また,$\sigma$ が偶置換のとき $\mathrm{sgn}(\sigma)=1$,奇置換のとき $\mathrm{sgn}(\sigma)=-1$ と書き,$\mathrm{sgn}(\sigma)$ を置換の符号と言います。置換の符号は行列式の定義にも登場します。→行列式の3つの定義と意味

置換の偶奇の一意性(※)の証明には差積というものを用います。→差積の意味と置換の符号が定義できることの証明

偶奇性のことをパリティと言ったりもします。かっこいいですね。
分野: 代数,情報・暗号理論  レベル: 大学数学