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

更新日時 2022/03/28

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

置換は,行列式の定義や,ルービックキューブの理論,8パズル・15パズルの不可能性判定など様々な場面で役立つ重要な概念です。

目次
  • 置換とは

  • 置換の積と対称群

  • 互換とは

  • 奇置換と偶置換

置換とは

  • 1,2,,n1,2,\cdots ,n を並び替える操作を nn 次の置換と言います(要素数 nn の集合から自分自身への全単射とも言えます)。ここでは置換を σ\sigma と表します。
  • 置換はもとの元を上に並べて行き先を下に並べたような形で表現されます。

σ=(1234523541)\sigma=\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 3 & 5 & 4 & 1 \end{pmatrix}

置換 σ\sigma によって 1122 に,4444 に移される。

これを σ(1)=2\sigma(1)=2σ(4)=4\sigma(4)=4 などと表すことにする。

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

置換の積と対称群

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

σ1=(12343214)\sigma_1=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 4 \end{pmatrix} , σ2=(12341324)\sigma_2=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4 \end{pmatrix}

に対して

σ1σ2=(12343124)\sigma_1\sigma_2=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{pmatrix}

例えば,22σ2\sigma_233 にうつって σ1\sigma_1 でさらに 11 にうつります。よって,(σ1σ2)(2)=1(\sigma_1\sigma_2)(2)=1 です。

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

互換とは

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

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

σ=(12343214)\sigma=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 4 \end{pmatrix}

1133 を交換するだけの置換なので互換。σ=(1,3)\sigma=(1,3) と書く。

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

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

最初の例

σ=(1234523541)\sigma=\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 3 & 5 & 4 & 1 \end{pmatrix}

は「1と2を交換」「1と3を交換」「1と5を交換」という互換を順番にかますと実現できるので,σ=(1,5)(1,3)(1,2)\sigma=(1,5)(1,3)(1,2) と書ける。

互換

奇置換と偶置換

任意の置換 σ\sigma はいくつかの互換の積で表せますが,その表し方は何通りもあります。しかし,σ\sigma を互換の積で表したときに, その互換の数の偶奇は表し方によらず σ\sigma のみで決まります。ここでは触れませんが,差積というものを用いて置換の偶奇の一意性の証明をすることができます。

必要な互換の数が偶数であるものを偶置換,奇数であるものを奇置換と呼ぶことにしましょう。

符号(sgn)

置換 σ\sigma に対し,符号 sgn\mathrm{sgn}

sgn(σ)={1(σが偶置換)1(σが奇置換) \mathrm{sgn} (\sigma) = \begin{cases} 1 &(\sigma \text{が偶置換})\\ -1 &(\sigma \text{が奇置換}) \end{cases}

と定め,sgn(σ)\mathrm{sgn} (\sigma) を置換の符号と言います。置換の符号は行列式の定義にも登場します。 →行列式の3つの定義と意味

偶奇性のことをパリティと言ったりもします。かっこいいですね。