［行列式１．転移数と互換数］

［行列式１．転移数と互換数］

 

　ネコ先生に多大な御迷惑をおかけした「線形代数って何さ？」の中では、行列式も連立一次方程式の整備も全く無視して話を進めましたので、いつかは行列式と連立一次方程式の話をやるべきだとは思っていました。

　今回ネコ先生に「ベクトル3重積（外積編）」と「ベクトル3重積（内積・外積編）」をアップした頂きましたので、良い機会かな？と思って、行列式の話を書く事にしました。目標はラプラス展開とクラーメルの公式あたりです。

 

　ここでは行列Ａに対して（正方行列に限る）、その行列式をdet(Ａ)や|Ａ|と表記します。

 

１．行列式の出自

 

　そもそもなんで行列式なんてものが考えられたんでしょう？。それは、多元連立一次方程式を解くために、です。ここで多元連立一次方程式とは説明するまでもないと思うんですが、記号を説明するためにします(^^;)。

　(1)のx₁，x₂，・・・，x_nは未知数で、b₁，b₂，・・・，b_nは既知数です。未知数x_jの前の係数a_ijは、「n元連立一次方程式の係数」と言われます。もちろんx_j，b_i，a_ij(i，j＝1～n)です。(1)は行列形式で、

 

(2)

などと書かれます。Ａ＝(a_ij)，x＝(x_j)，b＝(b_i)です。ここでクラーメルの公式を出しちゃいます。(2)の解は、

の形で与えられます。(3)の分母は(1)の係数行列Ａの行列式です。一方分子は、行列Ａのk列目をa_kで表しＡ＝(a₁，a₂，･･･，a_n)と書いたとき、Ａのj列目を既知ベクトルbに置き換えた行列、

 

 

 

 

の行列式です（← 長ぇ～な、おい(^^;)）。

　要するに多元連立一次方程式の解法は行列式の計算に帰着する、と言いたい訳です。(3)分母のdet(Ａ)の計算法がわかれば、当然分子の計算もできます。そこで昔の人達（1000年以上前から開始される）は、det(Ａ)の計算法を調べました。コンピューターも電卓もなかった時代、地道ぃ～に地道ぃ～に筆算したのです(^^;)。

　一般にn×n行列の（n次の）行列式の項数はn！になります。2×2行列なら2！＝2項となり、おなじみのad－bcです。3×3行列の3次のサラスの公式ってのは、もしかするとご存知かもしれませんね。調べた限りではサラスの公式のようなものは、少なくとも6次まではあるようです。これらの項数を調べてみると、昔の人達の苦労が身に沁みます。

 

　　1次：1！＝1

　　2次：2！＝1×2＝2

　　3次：3！＝2×3＝6

　　4次：4！＝6×4＝24

　　5次：5！＝24×5＝120

　　6次：6！＝120×6＝720

 

　普通の人なら4次くらいでギブアップのはずです。個人的には5次までならと思いますが、6次は絶対無理です(^^;)。このように果てしない苦労の末に、ついに行列式の計算法則は発見されます！(^^)。

 

　　※ 任意の順列j₁j₂･･･j_nについて和を取る．

 

　なんの事やらわかりませんよね？。なので説明します(^^;)。

　例えばa_1j1は、行列Ａ＝(a_ij)の1行目のj₁列成分です。本当は、

 

 

 

 

 

と書きたかったところなんですが（i行目のj_i列成分）、2重下付き添え字iが見えなくなるので（最近老眼だし・・・）、

 

 

 

 

 

と(4)では書いてます。(4)のΣ記号から明らかなように、ここでの変数は各行iに対応した列番号j_iです。つまり(4)は、Ａの各行から成分を1個取り出し、積a_1j1a_2j2･･･a_njnの和を取れと言ってます。さらに直下の但し書き（※）から、列番号j₁，j₂，･･･，j_nは重複してはいけない事もわかります。

　つまり並び：1 2 ･･･ n を任意に並べ替えた順列：j₁ j₂ ･･･ j_n について積a_1j1a_2j2･･･a_njnをつくり和をとる訳です。その際には係数σ(j₁j₂･･･j_n)が付きます。σはSign（符号）と呼ばれる関数で、その名の通り±1の値をとりますが、その符号は順列(j₁j₂･･･j_n)の並びによって決まる、という次第です。

 

　以上で(4)の意味はわかって頂けたと思います（← 本当か？(^^;)）。この行列式の定義に疑いをさしはさんではいけません！。(4)は、果てしなき苦労の果てに先人が残してくれた遺産なのです。じっさいに使えるし役に立つからこうなりました。そのまま受け入れるのが無難です。

 

 

２．転移数と互換数

 

　大学初年級の線形代数講義の冒頭近くで、行列式の定義(4)がドッカ～ンッ！と登場し学生は撃沈です。何故ならまず、高校でこんなに長ったらしい定義は扱った事がないからです。なんとか意味を理解したとしても、いや意味を理解すればするほど不安が募ります。行列式の定義(4)は、あらゆる数式パターンにのりそうにないからです。通常の数式計算が不可能な事態というのも、新入生には経験外です。

　じつは定義(4)を用いずに、ある意味でもっとわかりやすい行列式の定式化があります。それは行列式の公理的扱いです（後述）。それが余り用いられないのは、公理的扱いをすると行列式に関する数々の性質の証明がかなり間接的になり、学生がなれてないだろうという心遣い（教育的配慮？）からかも知れませんが、本音は違うと思うんですよね。公理的扱いをすると、行列式が本質的にテンソルである事がモロバレだからです。

　大学初年級の線形代数では、テンソルとして出して良いのは行列までという暗黙の不文律がある気がします。それで先生たちは行列式がテンソルであると正面切って言えず、愛想もへったくれもない定義(4)でごり押ししてる気がします。行列式は線形代数における必須の計算ツールなので、やらない訳にもいかず・・・。

　でも定義(4)を使おうと公理的扱いをしようと、次に述べる置換に関する基本定理は証明する必要に迫られます。そして基本定理の価値は、公理的扱いでよりはっきりします。という訳で公理的扱いは「後述」なので、ちょっと我慢して基本定理の証明に付き合って下さいな(^^;)。

 

　最初にちゃんと喋れるようになるために、またも計算に載らない用語を定義します。

 

［定義1］

　1～nの数字並び(1 2 ･･･ n)に対する任意の順列(j₁j₂･･･j_n)の事を、並び(1 2 ･･･ n)の置換と呼ぶ。置換の並びにおいてj_kとj_Lの数字を入れかえる操作を互換と呼び、t(k，L)で表す。

 

　　t(k，L)：(j₁j₂･･･j_k･･･j_L･･･j_n) → (j₁j₂･･･j_L･･･j_k･･･j_n)

 

　適当な互換を繰り返せば(1 2 ･･･ n)から任意の置換（順列）(j₁j₂･･･j_n)が得られるのは明らかです。

 

［定義2］

　並び(1 2 ･･･ n)から置換(j₁j₂･･･j_n)にいたる互換数が偶数の時、(j₁j₂･･･j_n)を偶置換と呼ぶ。奇数の時は奇置換と呼ぶ。

 

　一つの置換を得るための互換のやり方が一通りでないのは明らかです。例えば並び(1 2 3 4)から置換(2 4 1 3)を得るためには、

 

　　t(2，3)・t(3，4)・t(1，2)：

　　　(1 2 3 4) → (2 1 3 4) → (2 1 4 3) → (2 4 1 3)

 

というやり方もありますが（t(i，j)は右から順番に実行する）、

 

　　t(1，4)・t(3，4)・t(1，4)・t(2，3)・t(3，4)：

　　　(1 2 3 4) → (1 2 4 3) → (1 4 2 3) → (3 4 2 1) → (3 4 1 2) → (2 4 1 3)

 

とやっても可能です。最初の互換数は3、後の互換数は5です。今は3と5で最初と後の互換数の偶奇は一致しましたが、別のやり方をしたら8で偶数かも知れません。

　つまり［定義2］が実効的意味を持つためには、ある置換に達する互換数の偶奇は、どんなやり方をしても変わらない事が必要です。よって［定義2］は、そういう事態をあらかじめ想定した定義なのです。そして、そういう事態を証明するのが、置換に関する基本定理です。

 

［定理1］

　並び(1 2 ･･･ n)から置換(j₁j₂･･･j_n)にいたる互換数の偶奇は一定。

 

　［定理1］もまた、なんか数式にのりにくそうな性質です。そこで転移数という補助ツールを導入します。

 

［定義3］

　並び(j₁j₂･･･j_n)の任意の位置k＜L（1≦k，L≦n）について、j_L＜j_kとなるペア(j_k，j_L)の数を、並び(j₁j₂･･･j_n)の転移数と呼ぶ。

 

　ちょっと考えればわかるように転移数を勘定するには、k＜LのLを固定してkを1≦k＜Lの範囲で動かし、j_L＜j_kとなるペア(j_k，j_L)が何個になるかを調べれば十分です。その数を位置Lでの転移数と呼び、Ｔ(k＜L)で表す事にすれば、並び(j₁j₂･･･j_n)の転移数Ｔ(j₁j₂･･･j_n)は、

で計算できます。

 

［補題1］

　並び(j₁j₂･･･j_n)で互換t(k，L)，k＜Lを行ったとき、転移数は奇数個増減する。

［証明］

　転移数の計算式(5)より、位置k～Lでの転移数Ｔ_k，Ｔ_k+1，･･･，Ｔ_Lの変化を調べれば十分。

 

1) p＜kについてj_L＜j_pとなるj_pがn_L個，j_k＜j_pとなるj_pがＴ_k個あったとする。

2) 互換前にk+1＜p＜L-1についてj_L＜j_pとなるj_pがm_L個，j_k＜j_pとなるj_pがm_k個あったとする。

3) 1)より互換前のＴ_kは互換後Ｔ_k'＝n_Lに変化する。

4-1) 互換前j_k＜j_Lなら1)，2)より、互換前のＴ_L＝n_L＋m_Lは互換後Ｔ_L'＝Ｔ_k＋m_k＋1に変化する。

4-2) 互換前j_L＜j_kなら1)，2)より、互換前のＴ_L＝n_L＋m_L＋1は互換後Ｔ_L'＝Ｔ_k＋m_kに変化する。

 

　k～Lの間には(L－k－1)個の位置がある。m＝L－k－1とする。

 

5) k+1＜p＜L-1について互換前にj_L＜j_pだったm_L個のＴ_pは、j_Lの移動によって変化しない。

6) k+1＜p＜L-1について互換前にj_p＜j_Lだった(m－m_L)個のＴ_pは、j_Lの移動によって＋1変化する。

7) k+1＜p＜L-1について互換前にj_k＜j_pだったm_k個のＴ_pは、j_kの移動によって変化しない。

8) k+1＜p＜L-1について互換前にj_p＜j_kだった(m－m_k)個のＴ_pは、j_kの移動によって－1変化する。

 

　3)～8)を集計すれば、

　　Ｔ_kの変化 ：n_L－Ｔ_k

　　Ｔ_Lの変化 ：Ｔ_k＋m_k－n_L－m_L±1（±はj_k＜j_Lまたはj_L＜j_kによる）

　　5)～8)による変化：－m_L＋m_k

なので全体の転移数は、

　　(n_L－Ｔ_k)＋(Ｔ_k＋m_k－n_L－m_L±1)＋(－m_L＋m_k)＝2(m_k－m_L)±1

だけ変化します。

　2(m_k－m_L)±1は奇数なので、1回の互換について転移数は奇数個増減する。

［証明終］

 

　鬱陶しい証明でした。そして転移数というツールとその性質に最初に気づいた人は、やっぱり「すごい！」と思います。そうではありますが上記証明で、1)，2)は状況設定です。3)～8)はその状況設定に基づいて［定義3］に従い、ひたすら地を這うように地道ぃ～に地道ぃ～に状況変化を追跡しただけです。やりゃ～必ず出来ます(^^)。720項もの行列式を筆算で計算した昔の人達は、必ず気づけたんですよ。これも先人達の遺産です。

 

　初期並び(1 2 ･･･ n)は行われた互換数0（偶数）とみなせて、もちろん転移数0（偶数）です。そこから互換を0 → 1 → 2 → 3 → ・・・（回）と繰り返せば互換数は、偶 → 奇 → 偶 → 奇 → ・・・と変化します。1回の互換で転移数は奇数個増減し、奇数を偶数回足せば偶数，奇数回足せば奇数である事から、転移数も0 → 1 → 2 → 3 → ・・・に従って、偶 → 奇 → 偶 → 奇 → ・・・と変化します。よって、

 

［定理2］

　(j₁j₂･･･j_n)への互換数とその転移数Ｔ(j₁j₂･･･j_n)の偶奇は一致する。

［証明］

　［補題1］より明らか。

［証明終］

 

　ところで転移数Ｔ(j₁j₂･･･j_n)は、置換の並び(j₁j₂･･･j_n)だけで決定されます。よって並び(j₁j₂･･･j_n)への達し方がn回の互換とm回の互換であった場合、

 

［系1］

　並び(1 2 ･･･ n)から置換(j₁j₂･･･j_n)にいたるn回の互換とm回の互換において、nとmの偶奇は一致する。したがって［定理1］が成り立つ。

［証明］

　［定理2］よりnとmの偶奇は、Ｔ(j₁j₂･･･j_n)の偶奇に一致するから。この内容は［定理1］と同じ。

［証明終］

 

　こうして［定義2］が意味を持つようになり、符号関数σ(j₁j₂･･･j_n)の計算法を形式的に与える事が可能になります。

 

［定義3］

　(j₁j₂･･･j_n)が偶置換なら、σ(j₁j₂･･･j_n)＝＋1。

　(j₁j₂･･･j_n)が奇置換なら、σ(j₁j₂･･･j_n)＝－1。

　または、

　(1 2 ･･･ n)から(j₁j₂･･･j_n)にいたる互換数がkである時、σ(j₁j₂･･･j_n)＝(－1)^k。

 

　［定義3］は、σ(j₁j₂･･･j_n)の具体的な計算法も与えます。つまり「出来ちゃった」戦法です。例えばσ(2 4 1 3)の値が欲しいなら、

　　(1 2 3 4) → (2 1 3 4) → (2 1 4 3) → (2 4 1 3)

と(2 4 1 3)にいたる互換の系列を一つでも見つければ勝ちです。互換は3回だったのでσ(2 4 1 3)＝(－1)³＝－1。

　じつは互換の系列は系統的に構成できます。

　(1 2 ･･･ n) → (j₁j₂･･･j_n)にしたいとします。Lを並び(j₁j₂･･･j_n)の位置とし、次に定義するCounterという整数を勘定します。

 

1) L＝1のとき1＝j₁なら互換しない。1≠j₁なら位置2≦p≦nを検索し、k＝j₁となる位置kのkと、位置1の1を互換する。互換しないならCounter＝0。そうでないならCounter＝1。

2) L＝mのとき、位置1≦p≦m-1までは(j₁j₂･･･j_m-1 t_mt_m+1･･･t_n)になったと仮定する。t_m＝j_mなら互換しない。t_m≠j_mなら位置m+1≦p≦nを検索し、t_k＝j_mとなる位置kのj_mと、位置mのt_mを互換する。互換しないならCounterはそのまま。そうでないならCounterに1加算。

3) L＝m+1として2)に戻る。

 

　帰納法により(1 2 ･･･ n)は必ず(j₁j₂･･･j_n)に並べ替えられます。1)～3)の繰り返し過程で行われた互換の合計数Counterから、σ(j₁j₂･･･j_n)＝(－1)^Counterです。

　1)～3)の過程は線形ソートと本質的に同じで最も効率の悪いものですが、とにかく互換の系列がみつかりゃ良いのです(^^)。

 

例：(1 2 3 4) → (2 4 1 3)

　　(1 2 3 4) → (2 1 3 4) → (2 4 3 1) → (2 4 1 3)：Counter＝3

 

 

　次回は行列式を公理的に扱います。

 

（執筆：ddt³さん）