4 行の入れ換えによる順列の生成

この節では、3 節の考察に基づき、 行列式に現れるすべての順列に対応した積を作り出すための 行の入れ換えについて考察する。 まずは、そのために 2 節の $n=4$ の場合を振り返って 考えてみることにする。

式 (5) の方で見た場合、 (1) の和 $I_4(A)$ に現れる各項は、 次の順列に対応していることがわかる:

(1,2,3,4), (2,3,4,1), (3,4,1,2), (4,1,2,3) (左上から右下の方向の積),
(4,3,2,1), (1,4,3,2), (2,1,4,3), (3,2,1,4) (右上から左下の方向の積)

例えば 6 項目の $a_{2,4}a_{3,3}a_{4,2}a_{1,1}$ は、

$$a_{2,4}a_{3,3}a_{4,2}a_{1,1} =a_{1,1}a_{4,2}a_{3,3}a_{2,4} =a_{\sigma_1,1}a_{\sigma_2,2} a_{\sigma_3,3}a_{\sigma_2,4}$$

と書けば、(5) の和の $\sigma=(1,4,3,2)$ の項に 対応していることがわかる。

さて上の 8 つの順列は、(1,2,3,4) の巡回順列とその反転からできている ことが容易にわかる:

$$(1,2,3,4)^{(j)}, \overline{(1,2,3,4)^{(j)}}(=(4,3,2,1)\circ(1,2,3,4)^{(j)}) (0\leq j<3)$$ (15)

$A'$ は、$A$ の行を入れかえているが、それは順列 $p'=(1,3,4,2)$ に従って、 $A$ の $i$ 行目を $p'_i$ 行目にした、と見ることができる。 よって、今 $A'=[a'_{i,j}]$ とすると、

$$a'_{i,j}=a_{p'_i,j}$$

となる。よって、例えばこの $A'$ に対する順列 $\sigma$ に対する積の項は、

$$a'_{\sigma_1,1}a'_{\sigma_2,2} a'_{\sigma_3,3}a'_{\sigma_4,4... ...},1}a_{p'_{\sigma_2},2} a_{p'_{\sigma_3},3}a_{p'_{\sigma_2},4}$$

となるので、これは元の $A$ で言えば、

$$(p'_{\sigma_1},p'_{\sigma_2},p'_{\sigma_3},p'_{\sigma_4})=\sigma\circ p'$$

という順列の積に対応する。よって $I_4(A')$ の項は、 (5) の和の

$$(1,2,3,4)^{(j)}\circ p', \overline{(1,2,3,4)^{(j)}\circ p'} (0\leq j<3)$$ (16)

の 8 つの順列に対応することになる。

同様に、$A''$ は $p''=(1,4,2,3)$ によって行を並べ変えたものであるから、 $I_4(A'')$ の項は、(5) の和の

$$(1,2,3,4)^{(j)}\circ p'', \overline{(1,2,3,4)^{(j)}\circ p''} (0\leq j<3)$$ (17)

の 8 つの順列に対応する。

この (15), (16), (17) の 24 個の順列がちゃんと $S_4$ を構成していることを確認してみる。

$$p'=(1,3,4,2)=[3,4,2]=[2,3,4]^{(1)}, p''=(1,4,2,3)=[4,2,3]=[2,3,4]^{(2)}$$

であるので、 (15), (16), (17) の 反転でない方全体は、

$$[1,2,3,4]^{(j)}\circ [2,3,4]^{(k)} (0\leq j<3, 0\leq k<2)$$

と書くことができ、これはまさに (14) の $B_4$ を 構成している。 よって、補題 5 により、この $B_4$ の元の反転である (15), (16), (17) の 後半部分は $B_4$ には入らず、 しかも明らかにすべて異なるから、よって、 (15), (16), (17) によって $S_4$ 全体が構成されることがわかる。

これと同様に考て一般の $n$ に拡張できる。 まず、4 次と同様の斜めの積によって、 巡回順列とその反転

$$(1,2,\ldots,n)^{(j)}, \overline{(1,2,\ldots,n)^{(j)}} (0\leq j<n)$$

に対応する (5) の項が得られる ($2n$ 個)。

そして、行の入れ替えは、

$$C_n=\{p(0,j_3,j_4,\ldots,j_{n-1},0); 0\leq j_k<k\}$$ (18)

の元 $p$ を取って、その $p$ に対して $i$ 行目を $p_i$ 行目に変える、 ということを行う。 $C_n$ の元 $p$ は、$j_n=0$ であるから 1 は動かず、 よって $p_1=1$ となるので 1 行目は動かさない。

この $p$ それぞれに対して斜めの積を作れば、それにより順列

$$\begin{eqnarray*}\{(1,2,\ldots,n)^{(j)}\circ p; 0\leq j<n, p\in C_n\} &=& \{p(0,j_3,j_4,\ldots,j_n); 0\leq j_k<k\} \ &=&B_n\end{eqnarray*}$$

とその反転がすべて作られるので、 これで $S_n$ の順列に対応する (5) の項が すべての得られることになる。

つまり、行の入れ換えは $C_n$ (要素数 $(n-1)!/2$ 個) の順列に従って 行えば良いことがわかるが、 この $C_n$ は巡回による構成的な表現で与えられているので、 行の入れ替えの作業には便利な形にもなっている。

例えば、$n=5$ の場合、

$$C_5=\{p(0,i,j,0)=[2,3,4,5]^{(j)}\circ [3,4,5]^{(i)}; 0\leq i<3, 0\leq j<4\}$$

であるので、この場合行の入れ換えは、 3,4,5 行目の下 3 行の巡回 ($[3,4,5]^{(i)}$) を行い (3 通り)、 その後に行う 2,3,4,5 行目の下 4 行の巡回 ( $[2,3,4,5]^{(j)}$) を 行うことになる (4 通り)。 この計 12 通りの面に対し、それぞれで斜めの積による 10 項を作ればよい ( $12\times 10=120=5!$ 項)。

同様に $n=6$ の場合は、下 3 行の巡回 (3 通り)、 それに続く下 4 行の巡回 (4 通り)、そしてそれに続く下 5 行の巡回 (5 通り) による $3\times 4\times 5=60$ 面を作り、 そのそれぞれで斜めの積による 12 項を作ればすべての順列に対応する項 $60\times 12=720=6!$ 項ができ上がる。

実際にこれを実行するのはかなり大変であるが、 原理的にはこれですべての順列に対応する項を生成できることになる。