4章A-置換を用いた行列式の導出

(3049d) 更新

線形代数I

行列式の定義

n 次の正方行列 A に対して、行列式 \det A あるいは |A| を次の3つの性質を持つとして定義する。

1. 交代性:

任意の2つの列ベクトルを交換すると、符号が反転する。

&|\bm{a}_1\ \bm{a}_2\ \hdots\ \bm{a}_i\ \hdots\ \bm{a}_j\ \hdots\ \bm{a}_n| = \\ -&|\bm{a}_1\ \bm{a}_2\ \hdots\ \bm{a}_j\ \hdots\ \bm{a}_i\ \hdots\ \bm{a}_n|

2. n 重線形性:

どの列ベクトルに対しても線形である。

&|\bm{a}_1\ \bm{a}_2\ \hdots\ \alpha\bm{a}_i + \beta \bm{b}_i\ \hdots\ \bm{a}_n|=\\ &\alpha |\bm{a}_1\ \bm{a}_2\ \hdots\ \bm{a}_i\ \hdots\ \bm{a}_n| + \beta |\bm{a}_1\ \bm{a}_2\ \hdots\ \bm{b}_i\ \hdots\ \bm{a}_n| \\

3. 単位行列の行列式:

単位行列の行列式は1である。

\left| \begin{array}{cccc} 1&0&\hdots&0 \\ 0&\ddots& &\vdots \\ \vdots& &\ddots&0 \\ 0&\hdots&0&1 \end{array} \right| = 1

行列式の具体的な形

上記3つの性質だけを使って行列式の具体的な形を以下のようにして導くことができる。

始めに

A=(a_{ij})=(\bm{a}_1\ \bm{a}_2\ \hdots\ \bm{a}_n)

と置こう。

標準基底 \bm{e}_i=\!^t\,(0\ \hdots\ 1\ \hdots\ 0) を使って \bm{a}_1 を展開すると、

\bm{a}_1=\sum_{i=1}^n a_{i1}\bm{e}_i

と書ける。 列ベクトル \bm{a}_1 i 成分が行列 A (i,1) 成分であることに注意せよ。

これを代入して A の行列式を展開すると

\det A &= \left| \bm{a}_1\ \bm{a}_2\ \hdots\ \bm{a}_n \right| \\ &= \left| \left( \sum_{i=1}^n a_{i1}\bm{e}_i \right) \ \bm{a}_2\ \hdots\ \bm{a}_n \right| \\ &= \sum_{i=1}^n a_{i1} \left| \bm{e}_i\ \bm{a}_2\ \hdots\ \bm{a}_n \right|

とできる。同様に \bm{a}_2 を展開すると

&= \sum_{i=1}^n a_{i1} \sum_{j=1}^n a_{j2} \left| \bm{e}_i\ \bm{e}_j\ \hdots\ \bm{a}_n \right|

となり、以下これを繰り返すことで

&= \sum_{i_1=1}^n a_{i_11} \sum_{i_2=1}^n a_{i_22} \dots \sum_{i_n=1}^n a_{i_nn} \left| \bm{e}_{i_1}\ \bm{e}_{i_2}\ \hdots\ \bm{e}_{i_n} \right|\\ &= \sum_{i_1=1}^n \sum_{i_2=1}^n \dots \sum_{i_n=1}^n a_{i_11}a_{i_22}\dots a_{i_nn} \left| \bm{e}_{i_1}\ \bm{e}_{i_2}\ \hdots\ \bm{e}_{i_n} \right|

とできる。

この式は各列からそれぞれ1つずつ行列要素を取り出して掛け算せたもの ( a_{i_11}a_{i_22}\dots a_{i_nn} の部分)に、 その取り出した位置のみに1を立てた行列の行列式 ( \left| \bm{e}_{i_1}\ \bm{e}_{i_2}\ \hdots\ \bm{e}_{i_n} \right| の部分)を かけて足し合わせた形になっている。 項数は n^n 個である。これは n とともに爆発的に大きな値となる。

具体例を見てみよう。

\left| \begin{array}{cc} a&b\\c&d \end{array} \right| &= ab \left|\begin{array}{cc} 1&1\\0&0 \end{array} \right| + ad \left|\begin{array}{cc} 1&0\\0&1 \end{array} \right|\\ &+ cb \left|\begin{array}{cc} 0&1\\1&0 \end{array} \right| + cd \left|\begin{array}{cc} 0&0\\1&1 \end{array} \right|

項数は4。

&\left| \begin{array}{ccc} a&b&c\\d&e&f\\g&h&i \end{array} \right|\\ &= abc \left|\begin{array}{ccc} 1&1&1\\0&0&0\\0&0&0 \end{array} \right| + abf \left|\begin{array}{ccc} 1&1&0\\0&0&1\\0&0&0 \end{array} \right| + abi \left|\begin{array}{ccc} 1&1&0\\0&0&0\\0&0&1 \end{array} \right|\\ &+ aec \left|\begin{array}{ccc} 1&0&1\\0&1&0\\0&0&0 \end{array} \right| + aef \left|\begin{array}{ccc} 1&0&0\\0&1&1\\0&0&0 \end{array} \right| + aei \left|\begin{array}{ccc} 1&0&0\\0&1&0\\0&0&1 \end{array} \right|\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \\ &+ ghc \left|\begin{array}{ccc} 0&0&1\\0&0&0\\1&1&0 \end{array} \right| + ghf \left|\begin{array}{ccc} 0&0&0\\0&0&1\\1&1&0 \end{array} \right| + ghi \left|\begin{array}{ccc} 0&0&0\\0&0&0\\1&1&1 \end{array} \right|\\

項数は27。

同様にして、4次では256個、5次では3125個の項からなる式が得られることになる。

以上より、各列に1つずつ1を含みその他の成分がゼロである行列式( \left| \bm{e}_{i_1}\ \bm{e}_{i_2}\ \hdots\ \bm{e}_{i_n} \right| の 部分)の値が求まれば(形式的には)行列式が求まることになる。 これらの行列式の値はいくつになるだろう?

行列式の性質の1より、複数の列ベクトルが同じ値を持てばその行列式はゼロである ことが分かる。なぜなら、それらの互いに等しい列を入れ替えたとしても行列の形は 変わらないため、行列式の値も変わらない。それにもかかわらず、性質1によれば その符号は逆転することになる。符号を逆転しても値が変わらない値はゼロのみで ある。

したがって n^n 個の項のうち、 \left|\begin{array}{cc} 1&1\\0&0 \end{array} \right| や、 \left|\begin{array}{ccc} 1&0&0\\0&1&1\\0&0&0 \end{array} \right| というような、複数の列ベクトルが同じ値を持つ項はすべてゼロになる。 言い換えれば、 i_1, i_2, i_3, \dots, i_n の中に同じ数字が2回以上 出てくればその項はゼロになる。

それではゼロにならない場合、すなわちの i_1, i_2, i_3, \dots, i_n がすべて 異なる値である場合はどうだろうか?

そもそも n 個の変数 i_1, i_2, i_3, \dots, i_n 1,2,\dots,n の範囲の 値しか取らないから、これらがすべて異なるというのは、 i_1, i_2, i_3, \dots, i_n 1,2,\dots,n を並べ替えたものであることを意味する。

この条件の下で i_1, i_2, i_3, \dots, i_n を動かし和を取るために教科書では

&= \sum_{(i_1, i_2, \dots, i_n)} a_{i_11}a_{i_22}\dots a_{i_nn} \left| \bm{e}_{i_1}\ \bm{e}_{i_2}\ \hdots\ \bm{e}_{i_n} \right|

なる書き方をしている。シグマの下の (i_1, i_2, \dots, i_n) という書き方が i_1, i_2, i_3, \dots, i_n 1,2,\dots,n のすべての順列を動くことを 表す。このときの項数は _nP_n=n! になる。

n! 個の \left| \bm{e}_{i_1}\ \bm{e}_{i_2}\ \hdots\ \bm{e}_{i_n} \right| の形の 行列式のうち、値がすぐに分かるのは、 (i_1, i_2, \dots, i_n)=(1,2,\dots,n) の場合、 すなわち i_k=k の場合である。このとき中の行列は単位行列になるため、この値は 行列式の性質3から明らかに1である。

次に分かるのは、 (i_1, i_2, i_3, \dots, i_n)=(2,1,3,\dots,n) のように、 (i_1, i_2, i_3, \dots, i_n) のどれか2つを入れ替えるだけで (1,2,\dots,n) の形にできる場合である。(この例であれば i_1 i_2 とを入れ替えればよい)このとき入れ替えた要素を m 番目と l 番目とすれば、 \left| \bm{e}_{i_1}\ \bm{e}_{i_2}\ \hdots\ \bm{e}_{i_n} \right| m 番目と l 番目とを入れ替えると単位行列になるはずである。行列式の 性質1と3とを組み合わせることで、この行列式は 1 の符号を反転した -1 であることが分かる。

同様にして、 (i_1, i_2, i_3, \dots, i_n) のどれか2つを入れ替える操作を m 回 繰り返すことで (1,2,\dots,n) の形にできるならば、同じようにして 行列 \left[ \bm{e}_{i_1}\ \bm{e}_{i_2}\ \hdots\ \bm{e}_{i_n} \right] のを m 回入れ替えることで単位行列とすることができ、元の行列式の値は (-1)^m で あることになる。

まとめると、行列式 \left| \bm{e}_{i_1}\ \bm{e}_{i_2}\ \hdots\ \bm{e}_{i_n} \right| の 値は -1, 0, 1 の3つの値を取る可能性があり、

1. n 個の数字 i_1, i_2, \dots, i_n が同じ値を複数回含んでいれば 0 である。

2. i_1, i_2, \dots, i_n に対して2つの値を入れ替える操作を偶数回施して 1,2,\dots,n の形にできれば 1 である。

3. i_1, i_2, \dots, i_n に対して2つの値を入れ替える操作を奇数回施して 1,2,\dots,n の形にできれば -1 である。

この条件を式で書くため

\text{sgn} \left( \begin{array}{cccc} 1&2&\dots&n \\ i_1&i_2&\dots&i_n \end{array} \right)

という表記法を使って上の式を書き直したのが教科書に出てくる

\det A= \sum_{(i_1, i_2, \dots, i_n)} \text{sgn} \left( \begin{array}{cccc} 1&2&\dots&n \\ i_1&i_2&\dots&i_n \end{array} \right) a_{i_11}a_{i_22}\dots a_{i_nn}

という式である。

置換について

上式の中に出てくる

\left( \begin{array}{cccc} 1&2&\dots&n \\ i_1&i_2&\dots&i_n \end{array} \right)

は「置換」を表す表記法である。置換について以下で詳しく見てみよう。

行列式の展開公式で置換を導入した経緯を振り返ると、 (1,2,\dots,n) を並べ替えた (i_1, i_2, i_3, \dots, i_n) という数字の列を、2つの要素の入れ替えを繰り返して 元の (1,2,\dots,n) に並べなおす。そのとき必要な入れ替え回数が偶数か奇数かを 考えたい、ということであった。

ここで重要となるのが、

  1. 数字を並べ替える操作を、複数の操作に分解する
  2. 単純な並べ替えを組み合わせて、目的の並べ替えを達成する

といった、「並べ替え操作の分解・合成」の概念である。

これを数学的に記述し、一般化したのが「置換」である。

n 文字の置換

n 文字の置換とは、

\left( \begin{array}{ccccc} 1&2&3&4&5 \\ 2&1&4&3&5 \end{array} \right) \left( \begin{array}{cccc} 1&3&4&2 \\ 4&3&1&2 \end{array} \right)

のように、 n 個ずつの数字を2行に並べ括弧でくくったものである。 それぞれの列は 1 から n までの数字がそれぞれ1つずつ、任意の 順序で並んだものになっている。

一般的な形で書けば、

\left( \begin{array}{ccccc} a_1&a_2&a_3&\dots&a_n \\ b_1&b_2&b_3&\dots&b_n \end{array} \right)

の形であり、 a_1,a_2,a_3,\dots,a_n および b_1,b_2,b_3,\dots,b_n はどちらも 1 から n までの数字を適当に並べ替えた数字の列である。

置換は a_k b_k に置き換える「操作」を表す。例えば上の例で

\left( \begin{array}{cccc} 1&3&4&2 \\ 4&3&1&2 \end{array} \right)

は、1 を 4 に、3 を 3 に、4 を 1 に、2 を 2 に置き換える。

この操作を 1, 2, 3, 4 という数の並びに適用すると、4, 2, 3, 1 という新しい 数の並びが得られる。同様に 1, 3, 2, 4 に適用すれば結果は 4, 3, 2, 1 になる。 上記置換の表す操作をより簡単な言葉で表せば 1 と 4 とを入れ替える操作であると言える。

置換の定義では n 対の (a_k, b_k) のペアが意味を持つのであって、 記述する際の順には意味が無いことに注意しよう。すなわち、

\left( \begin{array}{cccc} 1&2&3&4 \\ 4&2&3&1 \end{array} \right) \left( \begin{array}{cccc} 4&3&1&2 \\ 1&3&4&2 \end{array} \right)

などはやはり 1 と 4 とを入れ替える置換を表しており、上で示した表記と 同一視することができる。一般に n 字の置換を上記形式で書き表す方法は n! 通り存在する。

それでは異なる意味を持つ置換の数についてはどうであろうか。 n 文字の置換の 集合を S_n と書こう。 S_n の要素の数は 1, 2, \dots, n を 並び替えた順列の数に等しいため、 _nP_n = n! 個であることが分かる。

特殊な置換として、恒等置換と逆置換がある。

\left( \begin{array}{cccc} a_1&a_2&\dots&a_n \\ a_1&a_2&\dots&a_n \end{array} \right)

のように、上の行と下の行とがまったく同じ数列である場合、この置換はなんら 置き換えを行わないという「操作」に対応する。これを恒等置換と呼ぶ。

また、

\sigma=\left( \begin{array}{cccc} a_1&a_2&\dots&a_n \\ b_1&b_2&\dots&b_n \end{array} \right)

に対して、上下の行を入れ替えた

\sigma^{-1}=\left( \begin{array}{cccc} b_1&b_2&\dots&b_n \\ a_1&a_2&\dots&a_n \end{array} \right)

の形の置換を \sigma の逆置換と呼ぶ。これは、 \sigma により並び替えた数列を さらに \sigma^{-1} により並べ替えることで元の数列に戻るためである。 定義から明らかなように、任意の \sigma \in S_n に対して必ず1つだけ \sigma^{-1} \in S_n が存在することに注意しよう。

合成置換と対称群

複数の置換を順番に適用した結果として得られる並び替え操作を、合成置換と呼ぶ。 例えば、 1, 2, 3, 4 に置換

\alpha=\small{\left( \begin{array}{cccc} 1&2&3&4 \\ 4&2&3&1 \end{array} \right)}

を適用すると、 4, 2, 3, 1 が得られ、その結果にさらに

\beta=\small{\left( \begin{array}{cccc} 1&2&3&4 \\ 4&3&1&2 \end{array} \right)}

を適用すると、 2, 3, 1, 4 が得られる。この過程のはじめと終わりとを見比べると \alpha \beta とを連続して適用する演算は

\gamma=\small{\left( \begin{array}{cccc} 1&2&3&4 \\ 2&3&1&4 \end{array} \right)}

を一回適用する操作と同一視できる。

このことを、 \alpha \beta との合成変換は \gamma に等しいと言い、 \gamma=\beta \times \alpha と書く。このようにして、ごく自然に S_n に含まれる 要素の間に「積」の演算を定義することができ、その積について S_n が閉じていることが分かる。

この積の定義に対して、 S_n が以下の3つの性質を持っていることを示すことができる。

1. 結合法則:すべての \alpha, \beta, \gamma \in S_n に対して

(\alpha \times \beta) \times \gamma = \alpha \times (\beta \times \gamma)

2. 単位元の存在:ある e \in S_n が存在し、すべての \alpha \in S_n に対して

e \times \alpha = \alpha \times e = \alpha

(註: e は上で定義した恒等置換のことである)

3. 逆元の存在:すべての \alpha \in S_n に対して、ある \alpha^{-1} \in S_n が 存在して、

\alpha \times \alpha^{-1} = \alpha^{-1} \times \alpha = e

(註: \alpha^{-1} は上で定義した逆置換のことである)

ある演算に対してこれら3つの性質を持つ集合は「群」と呼ばれる。つまり、 n 文字の置換は 上で定義した積について群を為す言える。特に「置換」によって定義される群は対称群と呼ばれ、 様々な分野で役に立っている。

互換への分解

ここでもう一度振り返ると、置換を導入した目的は 1 から n までの数の並び i_1, i_2, \dots, i_n 1, 2, \dots, n に並べ替えるのに要する 「入れ替え操作」の回数を調べたいのであった。

そこでまず、互換という言葉を導入する。互換とは、 n 文字のうち特定の2文字を入れ替える 置換のことである。例えば上で見た

\alpha=\small{\left( \begin{array}{cccc} 1&2&3&4 \\ 4&2&3&1 \end{array} \right)}

は 1 と 4 とを入れ替える操作であるから互換である。 S_n に含まれる n! 個の置換の うち、 _nC_2=n(n-1)/2 個が互換である。(互換は n 個の数字のうちどれと どれを入れ替えるか、順序を気にせず2つを選ぶ組み合わせの数だけ存在する)

ここで証明すべき重要な定理が「任意の置換は互換の積として表すことができる」そして、 「ある与えられた置換 \alpha m 個の互換の積として表したとすると( \alpha=\beta_1 \times \beta_2 \times \dots \times \beta_m )、 m が 偶数であるか奇数であるかは \beta_k の選び方によらない \alpha に固有の 属性である」の2つである。

1つ目は説明は直感的に分かりやすく、成立することもほぼ自明であるが、2つ目については 補足が必要であろう。まず、ある置換を互換の積として表す方法は複数考えることができる。

例えば、

&\left( \begin{array}{cccc} 1&2&3&4 \\ 1&3&4&2 \end{array} \right)\\ = &\left( \begin{array}{cccc} 1&2&3&4 \\ 1&4&3&2 \end{array} \right) \times \left( \begin{array}{cccc} 1&2&3&4 \\ 1&3&2&4 \end{array} \right)\\ = &\left( \begin{array}{cccc} 1&2&3&4 \\ 1&3&2&4 \end{array} \right) \times \left( \begin{array}{cccc} 1&2&3&4 \\ 1&2&4&3 \end{array} \right)

であるし、そもそも恒等変換を

&\left( \begin{array}{cccc} 1&2&3&4 \\ 1&2&3&4 \end{array} \right)\\ = &\left( \begin{array}{cccc} 1&2&3&4 \\ 1&3&2&4 \end{array} \right) \times \left( \begin{array}{cccc} 1&2&3&4 \\ 1&3&2&4 \end{array} \right)\\

などと互換の積で表せるのだから、その書き表し方は無限に考えられることになる。

それにもかかわらず、もしある置換を偶数個の互換の積として表すことができるので あれば、どう書き直したとしても必ず偶数個の互換としてしか書くことができず、 逆に奇数個の場合であれば必ず奇数個となる。すなわち、偶数個になるか奇数個に なるかは書き表し方によって変わるものではなく、置換自身の持つ固有の属性で あるというのが上の定理の意味するところである。

実はこの証明は比較的難しく、短く解こうとすると技巧的にならざるを得ない。 そこで、ここでは証明の詳細に踏み込まず、後に置換の厳密な定義と共に参考資料と して掲載する。

ある置換を互換の積として表したとき、その個数が偶数になる置換を遇置換、奇数に なる置換を奇置換と呼ぶ。また、置換のシグネチャー(signature)は、遇置換に対して 1であり、奇置換に対して -1 であるとして定義される。置換 \alpha の シグネチャーを \text{sgn} \alpha と書く。

このようにして、 i_1, i_2, \dots, i_n 1, 2, \dots, n に 並べ替えるのに要する2つの数の入れ替え操作の回数は、回数自体は不定である にもかかわらず、その偶奇性は i_1, i_2, \dots, i_n により一意に 定まることが分かる。

そして、シグネチャーの定義を使うことで行列式を

\det A= \sum_{(i_1, i_2, \dots, i_n)} \text{sgn} \left( \begin{array}{cccc} i_1&i_2&\dots&i_n \\ 1&2&\dots&n \end{array} \right) a_{i_11}a_{i_22}\dots a_{i_nn}

というような短い表式で書けることになる。

逆置換のシグネチャー

さて、上の式に含まれる置換が教科書に現れるものの逆置換になっていることに 気づいただろうか?式を導く過程の考え方の違いで結果が異なったのであるが、 これは重要な違いではない。

なぜなら、置換 \alpha のシグネチャーとその逆置換 \alpha^{-1} のシグネチャーと とは等しいからである。これは、以下のようにして示される。

\alpha を互換の積として表した表式を

\alpha=\beta_1 \times \beta_2 \times \dots \times \beta_m

としよう。すると

\alpha^{-1}=\beta_m^{-1} \times \dots \times \beta_2^{-1} \times \beta_1^{-1}

と書くことができ、また、互換の逆置換はそれ自身であることから、

\alpha^{-1}=\beta_m \times \dots \times \beta_2 \times \beta_1

を得る。すなわち \alpha^{-1} \alpha と同じ数の互換で表せるのであるから 両者のシグネチャーは等しいのである。

したがって、上式は教科書の

\det A= \sum_{(i_1, i_2, \dots, i_n)} \text{sgn} \left( \begin{array}{cccc} 1&2&\dots&n \\ i_1&i_2&\dots&i_n \end{array} \right) a_{i_11}a_{i_22}\dots a_{i_nn}

と等しくなる。

コメント

何かあれば自由にコメントを付けてください。


Counter: 15768 (from 2010/06/03), today: 2, yesterday: 0