#rst2hooktail_source
======================================================
置換の計算
======================================================
前節 対称群_ に置換の計算が出てきましたが、あまり馴染みがない人のために置換の計算規則を補足します。分かっている人は、この記事は飛ばしてください。内容は 対称群_ の説明とも重複します。
以下の説明には、主に４文字の置換を使いますが、もちろん一般に $n$ 文字の置換でも同じ議論がなりたちます。
括弧の意味
------------------------------------------------------------
置換を次のように括弧で表わす表記法は既に見ました。
<tex>
\Big( \begin{array}{cccc}
1 & 2 & 3 & 4 \\
3 & 1 & 4 & 2 \\
\end{array}
\Big)
</tex>
この記号は、上の列の文字を下の列の文字に変換する、というように解釈します。上の例は『 $1$ を $3$ に、 $2$ を $1$ に、 $3$ を $4$ に、 $4$ を $2$ にに変える』という意味です。
まず、これは **行列ではありません** 。
巡回置換の略記法
-------------------------------------------------------
四つの文字 $1,2,3,4$ のうち、 $1$ と $3$ だけを入れ換える置換は $(1 \ 3)$ のように略記できます。意味は $\Big( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 4 \\ \end{array} \Big) $ と同じです。
また、置換を繰り返して一巡する場合、これを巡回置換と呼びます。図で見ると分かりやすいのですが、一巡するとは、次々に置換を繰り返した結果、また最初の文字にどこかで戻り、そこで置換の連鎖が閉じるような置換列のことです。
.. image:: Joh-cyclicmut.gif
:align: center
例えば、この図の例では『 $4 \rightarrow 1$ , $1 \rightarrow 3$ , $3 \rightarrow 2$ , $2 \rightarrow 4$ 』という具合に置換が巡回しています。これをきちんと二列に $\Big( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1\\ \end{array} \Big)$ のように書いても同じことです。
巡回置換は $(1 \ 3 \ 2 \ 4)$ のように略記することで出来ます。最初の文字から順番にずらして $1 \rightarrow 3 \rightarrow 2 \rightarrow 4$ のように読みます。最後の文字だけは最初に文字に戻すようにします。
当然のことながら、 $(1 \ 3 \ 2 \ 4)$ , $(3 \ 2 \ 4 \ 1)$ , $(2 \ 4 \ 1 \ 3)$ , $(4 \ 1 \ 3 \ 2)$ はどれも同じ巡回置換を表わしています。
.. [*] 互換も巡回置換の一つです。
.. [*] 一番単純な巡回置換 $\Big( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ \end{array} \Big) $ が $(2 \ 3 \ 4 \ 1)$ と書けることからか、たまに巡回置換の略記法を『二列に書いた置換の記号の下の列だけを書く』と勘違いしている人がいます。そのような勘違いに基づいて書かれたサイトもありますので注意してください。
置換の積
---------------------------------------------------------------
連続的に置換を重ねていくことを、置換の積といいます。例えば次のように書きます。
<tex>
\Big( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ \end{array} \Big) \Big( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ \end{array} \Big)
</tex>
ここで重要なのは、 **置換の操作が一般には非可換** だという点です。つまり、この置換を対象物に左から作用させるのか、右から作用させるのかで結果が変わってくることに注意しなければなりません。
もしも、この固まりを左から掛ける場合(通常は、左からの作用を考える場合が多いです)、上の例では $\Big( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ \end{array} \Big)$ が最初に作用しますので、まず $(1,2,3,4)$ が $(2,1,4,3)$ に変わります。その次に $\Big( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ \end{array} \Big)$ が作用するので、 $1$ は $2$ に、 $2$ は $3$ に、 $3$ は $4$ に、 $4$ は $1$ に移され、 $(2,1,4,3)$ は $(3,2,1,4)$ になります。よって次のように書けます。
<tex>
\Big( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ \end{array} \Big) \Big( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ \end{array} \Big) = \Big( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 4 \\ \end{array} \Big)
</tex>
もし、右からの作用を考える場合は $\Big( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ \end{array} \Big)$ が先に作用することになります。結果は次のようになることを、自分で確認してみてください。
<tex>
\Big( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ \end{array} \Big) \Big( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ \end{array} \Big) = \Big( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2 \\ \end{array} \Big)
</tex>
.. [*] 『左から』『右から』という言葉で混乱する人がいるかも知れないので補足しておきます。例えば行列の積 $BA$ がベクトル $\bm{x}$ に作用する場合、左から作用する( $BA\bm{x}$ )なら最初に $\bm{x}$ に作用するのは $A$ です。逆に右側から作用する( $\bm{x}BA$ )なら、最初に $\bm{x}$ に作用するのは $B$ です。 $BA$ の見かけの左右と作用する順番は逆ですので注意してください。群の元が作用する、という意味は 群が集合の上で働くということ_ で詳しく勉強します。
.. [*] 幾つもの置換の積を取る場合には、紙の上で上から下に向かうように縦に置換の記号を書いていき、上から順番に操作していくようにすると間違いが少なくて済みます。
単位置換、逆置換
-----------------------------------------------------------
単位置換(恒等置換とも言う)は $(1)$ のように書くこともあります。 $e$ を使っても構いません。
逆置換は、上下の二列を入れ換えれば得られます。例えば次のような具合です。
<tex>
\Big( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2 \\ \end{array} \Big)^{-1}=\Big( \begin{array}{cccc} 1 & 4 & 3 & 2 \\ 1 & 2 & 3 & 4 \\ \end{array} \Big)</tex>
互換は二乗すれば元に戻りますから、互換の逆元は自分自身だと言えます。
<tex>
(1 \ 2)^{-1} = (1 \ 2)
</tex>
互いに素な置換
------------------------------------------------------------
５文字の置換で、次のようなものを考えてみます。
<tex>
\Big( \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5\\ 4 & 1 & 5 & 2 & 3\\ \end{array} \Big)
</tex>
よくみると、この置換は $(1 \ 4 \ 2)$ と $(3 \ 5)$ という二つの巡回置換からなっており、それぞれの巡回置換は、お互いに関係のない文字の間だけで行われていることが分かります。
.. image:: Joh-CyclicMut2.gif
:align: center
二つの巡回置換が、こうした家庭内離婚のような状態にあることを『互いに素』と言います。互いに素な巡回置換の積は可換です。
.. _対称群: http://www12.plala.or.jp/ksp/algebra/SymmetricGroup/
.. _群が集合の上で働くということ: http://www12.plala.or.jp/ksp/algebra/GroupAction/
@@author:Joh@@
@@accept: 2006-04-23@@
@@category: 代数学@@
@@id: Permutation@@
記事ソース/置換の計算 の変更点
