置換

置換について、線形代数の教科書に出てきたけど、授業ではあまり触れられなかったので自分で勉強してみる。以下はそのメモ。 置換の定義 定義(置換) $X_n$は$n$個の元を持つ集合とする。このとき、全単射写像 $\sigma: X_n \rightarrow X_n$ を$X_n$上の置換(Permutation)と呼ぶ。 言い換えると、$X_n$を適当に並べたとき、置換 $\sigma$ とはそれを並び替える方法を表したものである。 置換と聞くとReplacementがまず思い浮かぶけど、ここではPermutationなのね。 例 $X_3 = {1,2,3}$ とする。このとき、 $X_n$ の元を並べて $(1,2,3)$ としよう。このとき、 $\sigma(1)=2,\sigma(2)=3,\sigma(3)=1$ とすれば、写像 $\sigma$ は $X_3$ 上の置換となる。このとき、 $(1,2,3)$ という列が $\sigma$ によって $(2,3,1)$ に並び替えられたように見える。 $X_n$の元はなんでも良いが、以後説明のため$X_n = \lbrace 1,2,\ldots,n \rbrace$とする。 置換は以下のように表示することがある：$\sigma(i) = p_i\ (i=1,\ldots,n)$について、 $$ \sigma = \begin{pmatrix} 1 & 2 & \ldots & n \\ p_1 & p_2 & \ldots & p_n \end{pmatrix} $$ 先ほど置換とは $X_n$ を適当に並べたとき、置換 $\sigma$ とはそれを並び替えたもの、と表現した。実際、$\sigma$はただの写像なので、並び替えというより対応関係だけが大事である。上の表示方法はあくまで「上の段の元と下の段の元の対応関係」にだけ着目している。従って、上の段が$1,2,\ldots n$という並びになるとは限らない。...