置換の基礎（互換・偶置換・奇置換・符号の意味）

更新日時 2022/03/28

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

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

置換とは

$1,2,\cdots ,n$ を並び替える操作を $n$ 次の置換と言います。
置換は記号 $\sigma$ で表すことが多いです。
置換は「もとの元」を上に並べて「行き先」を下に並べた形で表現されます。

例

$\sigma=\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 3 & 5 & 4 & 1 \end{pmatrix}$

は $5$ 次の置換の例である。

置換 $\sigma$ によって，例えば $1$ は $2$ に， $4$ は $4$ に移される。

これを $\sigma(1)=2$ ， $\sigma(4)=4$ などと表す。

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

置換の積と対称群

「置換 $\sigma_1$ と置換 $\sigma_2$ の合成」を考えます。
先に $\sigma_2$ で置換してから $\sigma_1$ で置換する操作です。
これを $\sigma_1\sigma_2$ と表し，置換の積と呼びます。

例

$\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$ を考える。例えば， $2$ は $\sigma_2$ で $3$ にうつって $\sigma_1$ でさらに $1$ にうつる。よって， $(\sigma_1\sigma_2)(2)=1$ である。他も同様に考えると，

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

となる。

このように，「置換を2回かます操作」は1回の置換で表現できるので置換の積もまた置換になります。

$n$ 次の置換全体の集合は群をなします。そのため $n$ 次置換群，対称群などと呼ばれます。対称群と書くと仰々しいですが要はただの順列の集合です。→群の定義といろいろな具体例

互換とは

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

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

例

$\sigma=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 4 \end{pmatrix}$

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

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

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

最初の例

$\sigma=\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 3 & 5 & 4 & 1 \end{pmatrix}$

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

奇置換と偶置換

任意の置換
σ\sigmaσ
 はいくつかの互換の積で表せますが，その表し方は何通りもあります。しかし，σ\sigmaσ
 を互換の積で表したときに，その互換の数の偶奇は表し方によらず σ\sigmaσ のみで決まります。
置換の偶奇の一意性の証明は，差積の意味と置換の符号が定義できることの証明で解説しています。
必要な互換の数が偶数であるものを偶置換，奇数であるものを奇置換と呼びます。
符号（sgn）置換 σ\sigmaσ に対し，符号 sgn\mathrm{sgn}sgn を
sgn(σ)={1(σ が偶置換)−1(σ が奇置換)
\mathrm{sgn} (\sigma) =
\begin{cases}
1 &(\sigma\:\text{が偶置換})\\
-1 &(\sigma\:\text{が奇置換})
\end{cases}sgn(σ)={1−1​(σが偶置換)(σが奇置換)​
と定め，sgn(σ)\mathrm{sgn} (\sigma)sgn(σ)
を置換の符号と言います。置換の符号は行列式の定義にも登場します。
→行列式の3つの定義と意味
偶奇性のことをパリティと言ったりもします。かっこいいですね。