巡回置換・互換・置換の符号
行列式を計算する方法のひとつに置換を用いる方法がある。このとき必要になるのが置換の正負の符号である。この章では置換行列から巡回置換を求め、それを互換に分解し、符号を判定する手順について説明する。合わせて、分解した互換から元の置換を復元する手順も説明する。
手順は全て JavaScriptで実装している。
置換
５次の置換を例にとってみる。
置換から巡回置換を抽出する
置換は、一つ以上の巡回置換から、過不足なく構成される。
巡回置換を互換に分解する
互換とは、長さが２の巡回置換のことである。長さが３以上の巡回置換は互換に分解する。
互換に分解する最もシンプルな方法は、互換の左の要素は最左端の要素に固定し、右の要素は２番目の要素から順番に選んで互換を作り、全ての要素を使い切るまで繰り返す。この例では、巡回置換 (1, 3, 4) は二つの互換 (1, 3) (1, 4) に分解される。
置換の符号
置換の符号は、互換の個数で決まる。偶数の場合、正(＋)、偶数の場合、負(−)になる。この置換は、互換が３個なので符号は負(−)となる。
互換の積
行列式を計算するために必要な置換の符号を得る手順の説明は以上で終わりだが、互換の積という操作を行うと、互換から元の置換が得られるので、以下それを説明する。
要は、互換を求めるプロセスの逆を行っていて、元に戻るのは当たり前なのだが、互換を求める作業自体に間違いがなかったかの検証にはなる。
注意すべきは、一つの巡回置換が複数の互換で構成されるとき、互換の積の計算では、計算の方向が意味を持っていること、つまり交換法則が成り立たないことである。本稿では、計算は「左から右に進む」という定義にする。これはプログラムを追ってもらえば明らかなのだが、計算のアルゴリズムに基づいたものである。
数学の世界では、本稿と異なり「右から左に進む」方が多数派なようだが、要は決めの問題であり、プログラミング的にはこちらの方が何となく理解しやすいのでそうしてみた。
なお、巡回置換単位の入れ替えは可能である。
処理手順を示す。
まず、それぞれの互換を恒等置換に適用する。
置換行列の値を左から右にたどることによって元の置換を復元する。例えば１列目の値は、置換 Aの１列目の下段の値が３なので、置換 Bの３列目に移動する。置換 B３列目の下段の値は３なので、置換 Cの３列目に移動する。置換 Cの３列目の値は３で、これが最終的な置換の１列目の値になる。この操作を全列に対して同様に行う。
最終的に元の置換行列の下段の値と等しい [ ３、５、４、１、２ ]という値が得られる。
JavaScriptコード
このページを表示する HTMLと javaScriptの全コード。行列の計算式、キャンバスの描画などを含む。