置換と偶置換・奇置換に関する基礎的なこと
個のものを並び替える操作を置換と言う。
置換は,行列式の定義や,ルービックキューブの理論,8パズル・15パズルの不可能性判定など様々な場面で役立つ重要な概念です。
置換とは
置換の積と対称群
互換とは
奇置換と偶置換
置換とは
- を並び替える操作を 次の置換と言います(要素数 の集合から自分自身への全単射とも言えます)。ここでは置換を と表します。
- 置換はもとの元を上に並べて行き先を下に並べたような形で表現されます。
置換 によって は に, は に移される。
これを , などと表すことにする。
- 置換によって「 を並び替えた後の状態」は から までの順列となっています。よって,順列と置換は対応しています。
- よって, 次の置換は全部で 個あります。
置換の積と対称群
- 置換 と置換 の合成を置換の積と定義します。「置換を2回かます操作」は1回の置換で表現できるので置換の積もまた置換です。
- は先に で置換してから で置換したものです。
,
に対して
例えば, は で にうつって でさらに にうつります。よって, です。
次の置換全体の集合は群をなします。そのため 次置換群,対称群などと呼ばれることもあります。対称群と書くと仰々しいですが要はただの順列の集合みたいなものです。→群の定義といろいろな具体例
互換とは
置換の中でも,2つの要素を交換するだけのものを特に互換と言います。
と を交換する互換を と書きます。
は と を交換するだけの置換なので互換。 と書く。
どんな並べ替えも,2つのものの交換を何回か行うことで実現できます。すなわち任意の置換はいくつかの互換の積で表現できます。
実際に与えられた置換を互換の積で表現するには,例えば以下のように左端から順々に揃えていけばOKです(これで置換が互換の積で表せることの構成的な証明になっています)。
は「1と2を交換」「1と3を交換」「1と5を交換」という互換を順番にかますと実現できるので, と書ける。
奇置換と偶置換
任意の置換 はいくつかの互換の積で表せますが,その表し方は何通りもあります。しかし, を互換の積で表したときに, その互換の数の偶奇は表し方によらず のみで決まります。ここでは触れませんが,差積というものを用いて置換の偶奇の一意性の証明をすることができます。
必要な互換の数が偶数であるものを偶置換,奇数であるものを奇置換と呼ぶことにしましょう。
符号(sgn)
置換 に対し,符号 を
と定め, を置換の符号と言います。置換の符号は行列式の定義にも登場します。 →行列式の3つの定義と意味
偶奇性のことをパリティと言ったりもします。かっこいいですね。