Julia(AbstractAlgebra)で置換の積、位数、符号、置換行列を求める方法

どうも、木村(@kimu3_slime)です。

今回は、Julia(AbstractAlgebra)で置換の積、符号、置換行列を求める方法を紹介します。

前提知識:対称群の基礎:置換・互換の記法、符号、交代群を解説

 

準備

AbstractAlgebra, LinearAlgebraを使うので、持っていなければインストールしておきましょう。

準備として、以下のコードを実行しておきます。

 

置換の積

二行記法で表した置換は、

\[ \begin{aligned}f_1=\begin{pmatrix} 1 & 2 & 3\\ 3& 1& 2 \end{pmatrix}\end{aligned} \]

その2行目を指定して作ることができます。

 

行き先を確認してみると、\(f_1(1)=3\)、\(f_1(2)=1\)、\(f_1(3)=2\)となっていることがわかります。

「f1(1)」のように丸括弧では成分が参照できないので注意。

 

f1を定義したときに戻ってきた表示式「(1,3,2)」は、巡回置換(サイクル)を使った一行記法を表しています。

\[ \begin{aligned}\begin{pmatrix} 1 & 2 & 3\\ 3& 1& 2 \end{pmatrix} =\begin{pmatrix} 1 & 3 &2 \end{pmatrix}\end{aligned} \]

文字列として巡回置換を指定すると、そのまま定義できます。

 

恒等置換は、次のように表せます。

 

互換の積(写像の合成)は、「*」で計算できます。

恒等置換は、どちらからかけても変化が起こりません。

 

「inv(置換)」で逆置換を表します。自身との積を取ると、恒等置換になることを確かめてみましょう。

 

置換同士の積は、一般に可換であるとは限らず、順番によって結果が変わりえます。(対称群\(S_3\)は可換でない)

 

積「*」が、写像の合成とマッチしていることを具体的に確かめてみましょう。

「(f1* f2 )[i]」は「f2[ f1[i] ]」の意味で、左側の置換を先に作用させるものになっているので注意です(数学での慣習と逆)。

確かにすべての値が一致しています。

(この点では、Permutations.jlの方が数学の慣習に合っていて使いやすいです。しかし、そちらはサイクル記法が使いにくいので、AbstractAlgebraを使いました。)

 

要素の位数

置換を何回かかけると、それは必ず恒等置換になります。その回数を要素の位数(order)や、巡回置換の長さと呼びます。

例えば、\(f_1^3 =e\)を満たすので、それは位数3(長さ3)の巡回置換です。

「order(置換)」で位数が求められます。

 

すべての置換は、互換(1つの要素だけの入れ替え:長さ2の巡回置換)の積に分解することができます。例えば次のように。

 

互換の積の分解は、コクセター分解(Coxeter decompositon)と呼ばれるものです。別のパッケージPermutations.jlを使うと、「CoxeterDecomposition(置換)」で分解が求められます

 

符号

置換の符号(互換の積として表した時、その互換の個数が偶数個か奇数個か)は、「sign(置換)」によって求められます。

「1」のときが偶置換、「-1」のときが奇置換です。

 

置換の積と符号の積は両立していること(符号は対称群から\(\{1,-1\}\)への準同型写像)が、次のようにしてわかります。

 

置換行列

数字の置換を、単位ベクトルの入れ替えとしてみることによって、置換行列を考えることができます。

置換行列は「matrix_repr(置換)」によって求められます。

恒等置換は単位行列に対応していることがわかりますね。

 

置換の積と置換行列の積は両立している\(P_g P_f = P_{g\circ f}\)ことを確かめてみましょう。

 

また、置換の符号はその置換行列の行列式に等しい\(\det P_f = \mathrm{sgn}f\)ことも確かめられます。

 

以上、Julia(AbstractAlgebra)で置換の積、符号、置換行列を求める方法を紹介してきました。

SymPyでも置換は扱えるのですが、添字が0から始まる(Python流)のが気になってしまいます。その点、AbstractAlgebra.jlは添字が1から(Julia流)なので、数学での一般的な記法と一致して書きやすいですね。

木村すらいむ(@kimu3_slime)でした。ではでは。

 

1から始める Juliaプログラミング
進藤 裕之(著), 佐藤 建太(著)
コロナ社 (2020-03-26T00:00:01Z)
5つ星のうち4.5
¥7,353 (コレクター商品)

 

こちらもおすすめ

対称群の基礎:置換・互換の記法、符号、交代群を解説

置換行列とは?置換との関係、性質、転置・直交行列