どうも、木村（@kimu3_slime）です。
今回は、Julia（AbstractAlgebra）で置換の積、符号、置換行列を求める方法を紹介します。
前提知識：対称群の基礎：置換・互換の記法、符号、交代群を解説
準備
AbstractAlgebra, LinearAlgebraを使うので、持っていなければインストールしておきましょう。
1 2 3 | using Pkg Pkg.add("AbstractAlgebra") Pkg.add("LinearAlgebra") |
準備として、以下のコードを実行しておきます。
1 | using AbstractAlgebra, LinearAlgebra |
置換の積
二行記法で表した置換は、
\[ \begin{aligned}f_1=\begin{pmatrix} 1 & 2 & 3\\ 3& 1& 2 \end{pmatrix}\end{aligned} \]
その2行目を指定して作ることができます。
1 | f1 = perm([3,1,2]) |
1 | (1,3,2) |
行き先を確認してみると、\(f_1(1)=3\)、\(f_1(2)=1\)、\(f_1(3)=2\)となっていることがわかります。
1 | f1[1],f1[2],f1[3] |
1 | (3, 1, 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} \]
文字列として巡回置換を指定すると、そのまま定義できます。
1 | f1 = perm"(1,3,2)" |
1 | (1,3,2) |
恒等置換は、次のように表せます。
1 2 | e = perm([1,2,3]) e = one(SymmetricGroup(3)) |
1 2 | () () |
互換の積（写像の合成）は、「*」で計算できます。
恒等置換は、どちらからかけても変化が起こりません。
1 2 | f1 *e e * f1 |
1 2 | (1,3,2) (1,3,2) |
「inv(置換)」で逆置換を表します。自身との積を取ると、恒等置換になることを確かめてみましょう。
1 2 | inv(f1) f1 * inv(f1) == e |
1 2 | (1,2,3) true |
置換同士の積は、一般に可換であるとは限らず、順番によって結果が変わりえます。（対称群\(S_3\)は可換でない）
1 2 3 4 | f2 = perm([2,1,3]) f1 * f2 f2 * f1 f1*f2 == f2*f1 |
1 2 3 4 | (1,2) (1,3) (2,3) false |
積「*」が、写像の合成とマッチしていることを具体的に確かめてみましょう。
「(f1* f2 )[i]」は「f2[ f1[i] ]」の意味で、左側の置換を先に作用させるものになっているので注意です（数学での慣習と逆）。
1 2 3 4 5 6 7 8 | for i in 1:3 if ((f1 * f2)[i]) == f2[f1[i]] #do nothing else return false end return true end |
1 | true |
確かにすべての値が一致しています。
（この点では、Permutations.jlの方が数学の慣習に合っていて使いやすいです。しかし、そちらはサイクル記法が使いにくいので、AbstractAlgebraを使いました。）
要素の位数
置換を何回かかけると、それは必ず恒等置換になります。その回数を要素の位数（order）や、巡回置換の長さと呼びます。
例えば、\(f_1^3 =e\)を満たすので、それは位数3（長さ3）の巡回置換です。
1 | f1^3 == e |
1 | true |
「order(置換)」で位数が求められます。
1 2 | order(f1) order(f2) |
1 2 | 3 2 |
すべての置換は、互換（1つの要素だけの入れ替え：長さ2の巡回置換）の積に分解することができます。例えば次のように。
1 2 3 | f3 = perm"(1,2)(3)" f4 = perm"(1)(2,3)" f1 == f3*f4 |
1 2 3 | (1,2) (2,3) true |
互換の積の分解は、コクセター分解（Coxeter decompositon）と呼ばれるものです。別のパッケージPermutations.jlを使うと、「CoxeterDecomposition(置換)」で分解が求められます。
符号
置換の符号（互換の積として表した時、その互換の個数が偶数個か奇数個か）は、「sign(置換)」によって求められます。
1 2 | sign(f1) sign(f2) |
1 2 | 1 -1 |
「1」のときが偶置換、「-1」のときが奇置換です。
置換の積と符号の積は両立していること（符号は対称群から\(\{1,-1\}\)への準同型写像）が、次のようにしてわかります。
1 | sign(f1) == sign(f4)*sign(f3) |
1 | true |
置換行列
数字の置換を、単位ベクトルの入れ替えとしてみることによって、置換行列を考えることができます。
置換行列は「matrix_repr(置換)」によって求められます。
1 2 | matrix_repr(f1) matrix_repr(e) |
1 2 3 4 5 6 7 8 9 | 3×3 SparseArrays.SparseMatrixCSC{Int64, Int64} with 3 stored entries: ⋅ ⋅ 1 1 ⋅ ⋅ ⋅ 1 ⋅ 3×3 SparseArrays.SparseMatrixCSC{Int64, Int64} with 3 stored entries: 1 ⋅ ⋅ ⋅ 1 ⋅ ⋅ ⋅ 1 |
恒等置換は単位行列に対応していることがわかりますね。
置換の積と置換行列の積は両立している\(P_g P_f = P_{g\circ f}\)ことを確かめてみましょう。
1 | matrix_repr(f2)*matrix_repr(f1) == matrix_repr(f2 *f1) |
1 | true |
また、置換の符号はその置換行列の行列式に等しい\(\det P_f = \mathrm{sgn}f\)ことも確かめられます。
1 2 | det(matrix_repr(f1)) == sign(f1) det(matrix_repr(f2)) == sign(f2) |
1 2 | true true |
以上、Julia（AbstractAlgebra）で置換の積、符号、置換行列を求める方法を紹介してきました。
SymPyでも置換は扱えるのですが、添字が0から始まる（Python流）のが気になってしまいます。その点、AbstractAlgebra.jlは添字が1から（Julia流）なので、数学での一般的な記法と一致して書きやすいですね。
木村すらいむ（@kimu3_slime）でした。ではでは。
コロナ社 (2020-03-26T00:00:01Z)
￥7,353 (コレクター商品)
