【行列式編】置換と巡回置換
大学1年生もバッチリ分かる線形代数入門

【行列式編】置換と巡回置換

こんにちは、おぐえもん(@oguemon_com)です。

今回は行列式の定義に使用する「置換」という概念について説明します。今回の記事で「置換」を学んで、次の記事で「互換」と「置換の符号」を学ぶことで、行列式の定義を理解することができるようになります！

互換や、置換の符号は以下の記事で解説しています！

【行列式編】互換の求め方と置換の符号
【行列式編】互換の求め方と置換の符号
おぐえもん.com

それでは頑張っていきましょう！！

置換とは

置換とは、ある数列のアナグラムのことを言います。

例えば、「1,2,3,4,5」という数列を、「4,3,2,5,1」と並び替え、両者の数字をそれぞれ左から順に「1 と 4」「2 と 3」「3 と 2」「4 と 5」「5 と 1」と対応づけると、この対応を5 文字の置換と呼ぶわけです。

「1 と 4」みたいな対応関係を「σ(1)=4\sigma(1)=4」と表し、さらには、この対応を

σ=(1234543251)\sigma=\left( \begin{array}{ccccc} 1&2&3&4&5 \\ 4&3&2&5&1 \end{array} \right)

とまとめます。上の段が先ほどの「1,2,3,4,5」で、下の段がその並び替えの「4,3,2,5,1」であることが分かりますよね？

ある列の上下の数字をペアとして捉えることがこの表記を扱う上の基本です。例えば、3列目は「σ(3)=2\sigma(3)=2」を表します。そして、上下の数字の組み合わせさえ合っているならば、列を好きに入れ替えても問題ありません。

ちなみに、行列っぽい見た目ですが、行列とは別物です！！

置換について抽象的にまとめると以下のようになります。

置換

nn個の要素1,2,⋯ ,n1,2,\cdots,nを適当な順番に並べたp1,p2,⋯ ,pnp_1,p_2,\cdots,p_nについて、iiとpip_iの対応づけをσ(i)=pi (i=1,2,⋯ ,n)\sigma(i)=p_i \ (i=1,2,\cdots,n)と表し、これらをまとめて

σ=(12⋯np1p2⋯pn)\sigma=\left( \begin{array}{cccc} 1&2&\cdots&n \\ p_1&p_2&\cdots&p_n \end{array} \right)

と表す。

nn文字の置換は全部でn!n!パターンあることは、高校生以上の方なら分かるはずですよね！？（だって置換の総数は、並び替えの総パターン数ですから）

また、ある列に同じ数字が並ぶこと（同じ数字が上下に対応すること）がありますが、そのような列は基本的に省略して記します。

【例】1,2,3,4→2,4,3,11,2,3,4 \rightarrow 2,4,3,1のとき

σ=(123‾4243‾1)=(124241)\sigma=\left( \begin{array}{cccc} 1&2&\underline{3}&4 \\ 2&4&\underline{3}&1 \end{array} \right) = \left( \begin{array}{ccc} 1&2&4 \\ 2&4&1 \end{array} \right)

置換の積

置換の積とは

nn文字の 2 つの置換σ,τ\sigma,\tauが手元にあるとします。このとき、置換σ\sigmaにおけるσ(i)\sigma(i)の値を置換τ\tauにそのまま与えることで、「iiとτ(σ(i))\tau(\sigma(i))」の対応を考えることができます。

簡単に言えば、2 つの置換の対応関係（「A→B」と「B→C」）を 3 段論法的な感じで 1 つにギュッとまとめる(「A→C」)感じですね。

さて、「iiとτ(σ(i))\tau(\sigma(i))」の対応をまとめたものを、置換σ\sigmaと置換τ\tauの積と言います。記号ではτσ\tau\sigmaと書きます。

置換の積

iiとτ(σ(i))\tau(\sigma(i))の対応づけを置換σ\sigmaと置換τ\tauの積と言い、両者の積をτσ\tau\sigmaと表す。

τσ=(12⋯nτ(1)τ(2)⋯τ(n))(12⋯nσ(1)σ(2)⋯σ(n))=(12⋯nτ(σ(1))τ(σ(2))⋯τ(σ(n)))\begin{aligned} \tau\sigma&=\left( \begin{array}{cccc} 1&2&\cdots&n \\ \tau(1)&\tau(2)&\cdots&\tau(n) \end{array} \right) \left( \begin{array}{cccc} 1&2&\cdots&n \\ \sigma(1)&\sigma(2)&\cdots&\sigma(n) \end{array} \right)\\ &=\left( \begin{array}{cccc} 1&2&\cdots&n \\ \tau(\sigma(1))&\tau(\sigma(2))&\cdots&\tau(\sigma(n)) \end{array} \right) \end{aligned}

置換の積の例

以下の 2 つの置換

τ=(123231),σ=(123321)\tau=\left( \begin{array}{ccc} 1&2&3 \\ 2&3&1 \end{array} \right),\sigma=\left( \begin{array}{ccc} 1&2&3 \\ 3&2&1 \end{array} \right)

の積τσ\tau\sigmaを考えます。

まず、σ\sigmaでは、1が3に対応しています（σ(1)=3\sigma(1)=3）。そして、τ\tauでは3が1に対応している（τ(3)=1\tau(3)=1）ので、積τσ\tau\sigmaでは1がτ(σ(1))=τ(3)=1\tau(\sigma(1))=\tau(3)=1と対応することになります。

同様にすると、

2→τ(σ(2))=τ(2)=33→τ(σ(3))=τ(1)=2\begin{aligned} 2 \rightarrow \tau(\sigma(2))=\tau(2)=3 \\ 3 \rightarrow \tau(\sigma(3))=\tau(1)=2 \end{aligned}

となるので、

τσ=(123231)(123321)=(123132)=(2332)\begin{aligned} \tau\sigma&=\left( \begin{array}{ccc} 1&2&3 \\ 2&3&1 \end{array} \right) \left( \begin{array}{ccc} 1&2&3 \\ 3&2&1 \end{array} \right)\\ &=\left( \begin{array}{ccc} 1&2&3 \\ 1&3&2 \end{array} \right)\\ &=\left( \begin{array}{cc} 2&3 \\ 3&2 \end{array} \right) \end{aligned}

となります。簡単に言えば、右の置換の上段から数字を辿って、最終的に行き着く左の置換の下段の数字が、積における対応になります。

置換の積の注意点

置換の積では、行列と同じく、掛け合わせる順序を逆にすれば基本的に答えが変わります。

一般に

τσ≠στ\tau\sigma \neq \sigma\tau

が成立する。（ただし、組み合わせ次第ではτσ=στ\tau\sigma = \sigma\tauのときもある）

先ほどの例で、τ\tauとσ\sigmaの順序を逆にしてみます。

στ=(123321)(123231)=(123213)=(1221)\begin{aligned} \sigma\tau&= \left( \begin{array}{ccc} 1&2&3 \\ 3&2&1 \end{array} \right) \left( \begin{array}{ccc} 1&2&3 \\ 2&3&1 \end{array} \right)\\ &=\left( \begin{array}{ccc} 1&2&3 \\ 2&1&3 \end{array} \right)\\ &=\left( \begin{array}{cc} 1&2 \\ 2&1 \end{array} \right) \end{aligned}

先ほどと答えが異なることがわかります。

単位置換と逆置換

まず、同じ数字同士の対応付けしかない置換を単位置換と言います。

単位置換

以下のような置換を単位置換と言う。

ϵ=(12⋯n12⋯n)\epsilon=\left( \begin{array}{cccc} 1&2&\cdots&n \\ 1&2&\cdots&n \end{array} \right)

単位行列は、他の置換と掛けても、積に変化を及ぼしません。

ϵσ=σϵ=σ\epsilon\sigma = \sigma\epsilon = \sigma

次に、ある置換の上段と下段を入れ替えた置換を逆置換と言います。

逆置換

以下のような置換を逆置換と言い、σ−1\sigma^{-1}で表す。

σ−1=(σ(1)σ(2)⋯σ(n)12⋯n)\sigma^{-1}=\left( \begin{array}{cccc} \sigma(1)&\sigma(2)&\cdots&\sigma(n) \\ 1&2&\cdots&n \end{array} \right)

逆置換σ−1\sigma^{-1}は、σ\sigmaと掛け合わせることで単位置換になります。σ−1σ=σσ−1=ϵ\sigma^{-1}\sigma = \sigma\sigma^{-1} = \epsilon

巡回置換

ある1つの置換について考えたとき、対応する数字を追っていくと最終的に元の数字にたどり着くことがあります。

例えば、以下の置換

(123456356124)\left( \begin{array}{cccccc} 1&2&3&4&5&6\\ 3&5&6&1&2&4 \end{array} \right)

について、

「1と3」「3と6」「6と4」「4と1」という4つの対応関係から「1→3→6→4→11 \rightarrow 3 \rightarrow 6 \rightarrow 4 \rightarrow 1」という輪っかが生まれます。

同様にして「2→5→22 \rightarrow 5 \rightarrow 2」という輪っかも見つけられると思います。

このように、同じ置換で対応関係を追うことでii文字を一巡する置換を、長さiiの巡回置換と言います。

巡回置換

ある置換σ\sigmaについて、

σ(i1)=i2, σ(i2)=i3 ⋯ σ(pm)=i1\sigma(i_1)=i_2, \ \sigma(i_2)=i_3 \ \cdots \ \sigma(p_m)=i_1

という風に対応関係が一巡する置換を長さiiの巡回置換と言い、

(i1 i2 ⋯ im)(i_1 \ i_2 \ \cdots \ i_m)

で表す。

先ほどの例で言えば、(1 3 6 4)(1 \ 3 \ 6 \ 4)と(2 5)(2 \ 5)の2つの巡回置換が置換の中に含まれていたことになります。

またまた新しい記法が登場しちゃいましたが、これは先ほどの記法を1行にしたものと同じです。

(1 3 6 4)=(13643641)(1 \ 3 \ 6 \ 4) = \left( \begin{array}{cccccc} 1&3&6&4 \\ 3&6&4&1 \end{array} \right)

1 つの置換が複数の巡回置換で構成されているなら、その置換は巡回置換の積で表せられます。

(123456356124)=(1 3 6 4)(2 5)\left( \begin{array}{cccccc} 1&2&3&4&5&6\\ 3&5&6&1&2&4 \end{array} \right)=(1 \ 3 \ 6 \ 4)(2 \ 5)

このとき、積として与えられている 2 つの巡回置換は、構成されている要素が全く異なるので、掛け合わせる順番を逆にしても同じ結果が導かれます。

(2 5)(1 3 6 4)=(1 3 6 4)(2 5)(2 \ 5)(1 \ 3 \ 6 \ 4)=(1 \ 3 \ 6 \ 4)(2 \ 5)

ちなみに、どんな置換も、巡回置換の積を用いて表現できることが知られています。

おわりに

今回は、置換の概念について説明し、その中でも重要な「巡回置換」というものを紹介しました。

次の記事では、これに加え「互換」と「置換の符号」というものを説明し、行列式の定義に必要な知識をコンプリートします！！

互換の求め方と置換の符号＞＞

▲ トップへ戻る