3 順列に関する用語と補題

この節では、本稿で必要となる順列の用語、それに関する補題などを紹介する。

まず、行列式の定義を紹介するが、 行列式の定義は、置換群を用いて紹介する流儀もある。 しかし、本稿では線形代数の教科書 [2] に 書かれている定義や用語にできるだけ従うため、 (置換と 1 対 1 に対応するのであるが) 順列 を用いて行列式の定義を行うことにする。

$n$ 次の正方行列 $A=[a_{i,j}]$ に対して、その行列式は、 次のように定義される:

$$\vert A\vert = \sum_{\sigma\in S_n}\mathop{\mathrm{sgn}}\nolimits (\sigma) a_{1,\sigma_1}a_{2,\sigma_2}\cdots a_{n,\sigma_n}$$ (3)

ここで、$S_n$ は $\{1,2,\ldots,n\}$ のすべての順列 $\sigma=(\sigma_1,\sigma_2,\ldots,\sigma_n)$ からなる集合 (要素数 $n!$ 個) で、 (3) はそのすべてにわたる和である。 $\mathop{\mathrm{sgn}}\nolimits (\sigma)$ は、順列 $\sigma$ から一意に決まる値で、 $+1$ か $-1$ の値を取る関数であり (順列 $\sigma$ の 符号 と呼ばれる)、 その定義は 5 節で行う。

これらにより、この (3) は、 $A$ の要素のうちすべてが異なる行、異なる列に入る $n$ 個の要素を取り出し、 その積

$$a_{1,\sigma_1}a_{2,\sigma_2}\cdots a_{n,\sigma_n}$$

を作り、それに適当に符号をつけたものを加え合わせることを意味している。

一方、良く知られているように

$$\vert A\vert=\vert{}^t\!A\vert$$ (4)

が成り立つので、よって (3) を $\vert{}^t\!A\vert$ について書けば

$$\vert A\vert = \vert{}^t\!A\vert = \sum_{\sigma\in S_n}\m... ...its (\sigma) a_{\sigma_1,1}a_{\sigma_2,2}\cdots a_{\sigma_n,n}$$ (5)

となる。

もちろん本来は、順列の 逆対応 $\sigma^{-1}=(\sigma^{-1}_1,\sigma^{-1}_2,\ldots,\sigma^{-1}_n)\in S_n$:

$$\sigma^{-1}_j=i \Leftrightarrow \sigma_i=j$$

によって $\sigma$ と $\sigma^{-1}$ が 1 対 1 に対応し、

$$a_{\sigma_1,1}a_{\sigma_2,2}\cdots a_{\sigma_n,n} =a_{1,\sigma^{-1}_1}a_{2,\sigma^{-1}_2} \cdots a_{n,\sigma^{-1}_n}$$

であり、また、

$$\mathop{\mathrm{sgn}}\nolimits (\sigma^{-1})=\mathop{\mathrm{sgn}}\nolimits (\sigma)$$ (6)

も成り立つので、そこから逆に $\vert A\vert= \vert{}^t\!A\vert$ が成り立つことが 示されるのであるが、ここでは逆に $\vert A\vert= \vert{}^t\!A\vert$ を利用して、 (5) を計算法の考察のために用いることにする。

この節では、まずこの行列式を生成するための順列について考察し、 2,3 の補題を示すことにする。

まず、順列のうち、 $(1,2,\ldots,n)$ とは異なる部分を挙げたものを

$$\sigma =(\sigma_1,\sigma_2,\ldots,\sigma_n) =[\sigma_{i_1},\sigma_{i_2},\ldots,\sigma_{i_m}]$$

のように書くことにする。ここで、 $k\not\in\{i_1,i_2,\ldots,i_m\}$ ならば $\sigma_k=k$ であるとする。 例えば、

$$(1,3,4,2)=[3,4,2]$$

と書くのであるが、この記法は $(1,2,\ldots,n)$ とは 違うもののみを挙げなければいけないわけではないので、 一意的に決まる記法ではないことに注意する。 例えば、$n=6$ のときに $\sigma=[5,2,4,1]$ と書けば、これは、 $\{1,2,4,5\}$ 以外の 3, 6 は少なくとも元の位置からは動かず、 残りの部分がこの順に並ぶので、

$$\sigma=(5,2,3,4,1,6)$$

を意味することになる。しかし、これは実際には 2, 4 も動いていないので、

$$\sigma = [5,1] = [5,2,1] = [5,2,3,1]$$

などのように書くこともできる。

また、順列を一つずつ順送りにしたものを 巡回順列 と呼ぶ。 例えば、以下の順列は $(1,2,3,4)$ の巡回順列である。

$$(2,3,4,1), (3,4,1,2), (4,1,2,3)$$

このような順列全体が巡回するものばかりではなく、 そのうち一部分のみを巡回したものも巡回順列と呼ぶ。例えば、

$$[3,5,2], [5,2,3]$$

は、 $[2,3,5]=(1,2,3,4,5)$ の巡回順列である。一般に、 $[\mu_1,\mu_2,\ldots,\mu_m]$ ( $\mu_1<\mu_2<\cdots<\mu_m$) の巡回順列

$$[\mu_{k+1},\mu_{k+2},\ldots,\mu_m,\mu_1,\mu_2,\ldots,\mu_k]$$ (7)

の $k$ を 位数 と呼び、

$$[\mu_{k+1},\mu_{k+2},\ldots,\mu_m,\mu_1,\mu_2,\ldots,\mu_k] = [\mu_1,\mu_2,\ldots,\mu_m]^{(k)}$$

と書くことにする。 この位数は、$k=m$ の場合は元に戻るので周期 $m$ を持つと考え、 $m$ より大きい整数、あるいは 0 以下の整数 $k$ に対しても、 $k\equiv j\pmod{m}$, $0\leq j<m$ となる $j$ を取って、

$$\begin{eqnarray*}\lefteqn{[\mu_1,\mu_2,\ldots,\mu_m]^{(k)}} \ &=& \left\{\beg... ...>0),\ {} [\mu_1,\mu_2,\ldots,\mu_m] & (j=0) \end{array}\right.\end{eqnarray*}$$

と書くことにする。例えば、

$$(1,2,3,4)^{(3)}=(4,1,2,3), [2,3,5]^{(-7)}=[2,3,5]^{(2)}=[5,2,3]$$

のようになる。

順列 $\sigma$, $\mu$ に対して、その合成による順列

$$p=(\mu_{\sigma_1},\mu_{\sigma_2},\ldots,\mu_{\sigma_n})$$

を $\sigma$, $\mu$ の 積 と呼び、 $\sigma\circ\mu=p$ と書く。 例えば、

$$\sigma=(\sigma_1,\sigma_2,\sigma_3,\sigma_4)=(2,1,3,4),\hspace{1zw} \mu=(\mu_1,\mu_2,\mu_3,\mu_4)=(1,3,2,4)$$

の場合は、

$$\mu_{\sigma_1}=\mu_2=3,\ \mu_{\sigma_2}=\mu_1=1,\ \mu_{\sigma_3}=\mu_3=2,\ \mu_{\sigma_4}=\mu_4=4$$

なので $\sigma\circ\mu=(3,1,2,4)$、

$$\sigma_{\mu_1}=\sigma_1=2,\ \sigma_{\mu_2}=\sigma_3=3,\ \sigma_{\mu_3}=\sigma_2=1,\ \sigma_{\mu_4}=\sigma_4=4$$

なので $\mu\circ\sigma=(2,3,1,4)$ となる。

この積は、置換の考え方で理解することもできる¹。 この例の $\sigma$, $\mu$ は $\sigma=[2,1]$, $\mu=[3,2]$ であり、 $\sigma\circ\mu$ は、$(1,2,3,4)$ をまず $\mu=[3,2]$ に従って 2 番目と 3 番目を入れかえて $(1,3,2,4)$ とし、 次に $\sigma=[2,1]$ に従ってその順列の 1 番目と 2 番目を入れかえて $(3,1,2,4)$ としたものに等しい。

この順列の積について、容易に次が示される。

補題 1

1. $\sigma$ とその逆対応 $\sigma^{-1}$ に対して、次が成り立つ。

   $$\sigma^{-1}\circ\sigma=\sigma\circ\sigma^{-1}=(1,2,\ldots,n)$$ (8)

   
   
2. 結合法則が成り立つ。

   $$(\sigma\circ\mu)\circ\tau = \sigma\circ(\mu\circ\tau)$$ (9)

   
   
3. 巡回順列に対して、次が成り立つ。

   $$[\mu_1,\mu_2,\ldots,\mu_m]^{(j)}\circ[\mu_1,\mu_2,\ldots,\mu_m]^{(k)} =[\mu_1,\mu_2,\ldots,\mu_m]^{(j+k)}$$ (10)

   
   

証明

1. $\sigma_j=k$ とすると $\sigma^{-1}_k=j$ であるから、

   $$\begin{eqnarray*}&& (\sigma^{-1}\circ\sigma)_k=\sigma_{\sigma^{-1}_k}=\sigma_j=k... ...sigma\circ\sigma^{-1})_j=\sigma^{-1}_{\sigma_j}=\sigma^{-1}_k=j \end{eqnarray*}$$

   
   
   
   がすべての $j$ に対して成り立つので (8) が成立する。

2. 両辺の $j$ 番目の成分を見れば、

   $$\begin{eqnarray*}((\sigma\circ\mu)\circ\tau)_j &=& \tau_{(\sigma\circ\mu)_j}... ..._j &=& (\mu\circ\tau)_{\sigma_j} = \tau_{\mu_{\sigma_j}} \end{eqnarray*}$$

   
   
   
   となるので、 (9) が成り立つ。

3. この積では、 $\{\mu_1,\mu_2,\ldots,\mu_m\}$ 以外の要素は いずれの項でも場所は動かないので、 $\{\mu_1,\mu_2,\ldots,\mu_m\}$ のみを考えればよいことにまず注意する。

   $k=1$ の場合を考えれば、

   $$\begin{eqnarray*}\lefteqn{% [\mu_1,\mu_2,\ldots,\mu_m]^{(j)}\circ[\mu_1,\mu_2,\... ...,\mu_2,\ldots,\mu_{j+1}] = [\mu_1,\mu_2,\ldots,\mu_m]^{(j+1)} \end{eqnarray*}$$

   
   
   
   となることが容易に示される。後はこれと 2. を組み合わせれば、 (10) は容易に示される。

補題 2

$S_n$ のすべての順列は、巡回順列の $(n-1)$ 個の積

$$[1,2,\ldots,n]^{(j_n)}\circ[2,3,\ldots,n]^{(j_{n-1})}\circ\cdots \circ[n-1,n]^{(j_2)} \hspace{1zw}(0\leq j_k < k)$$ (11)

で一意に表現できる。

証明

以後、(11) の積の式を $p(j_2,j_3,\ldots,j_n)$ と書くことにする。 この $p(j_2,j_3,\ldots,j_n)$ は、$j_2$ が 0,1 の 2 通り、 $j_3$ が 0,1,2 の 3 通り、そして最後に $j_n$ が $n$ 通りなので、 結局 (11) は $2\cdot 3\cdots n=n!$ 通りあるから、 異なる $(j_2,j_3,\ldots,j_n)$ に対しては 異なる順列 $p(j_2,j_3,\ldots,j_n)$ が得られるのであれば、 これですべての $S_n$ の元が一意に得られることになる。

よって、 $p(j_2,j_3,\ldots,j_n)=p(k_2,k_3,\ldots,k_n)$ ならば $(j_2,j_3,\ldots,j_n)=(k_2,k_3,\ldots,k_n)$ であることを示せばよい。

前に見たように、 $p(j_2,j_3,\ldots,j_n)$ は $(1,2,\ldots,n)$ を $[n-1,n]^{(j_2)}$ に従って最後の 2 つの数字を巡回し、 次にそれを $[n-2,n-1,n]^{(j_3)}$ に従って最後の 3 つの数字を巡回し、 という形で並び変えていき、 最後に $[1,2,\ldots,n]^{(j_n)}$ に従って $n$ 個全部を巡回したもの、 となっている。 よって、1 は最後の $[1,2,\ldots,n]^{(j_n)}$ によってのみ場所が移動するので、 その 1 の場所を見れば $j_n$ ($0\leq j_n<n$) が一意に決定することになる。 よって結果の順列が

$$p(j_2,j_3,\ldots,j_n)=p(k_2,k_3,\ldots,k_n)$$

のように等しければ、1 の位置ももちろん等しいので $j_n=k_n$ が成り立つことになる。 次にこの最後の順列による巡回 $[1,2,\ldots,n]^{(j_n)}$ ( $=[1,2,\ldots,n]^{(k_n)}$) の前の状態、 すなわち $p(j_2,j_3,\ldots,j_{n-1},0)$ と $p(k_2,k_3,\ldots,k_{n-1},0)$ に戻れば (左から $[1,2,\ldots,n]^{(n-j_n)}$ をかけると考えてもよい)、

$$p(j_2,j_3,\ldots,j_{n-1},0)=p(k_2,k_3,\ldots,k_{n-1},0)$$

であることになるが、この式では最後の巡回 $[2,3,\ldots,n]^{(j_{n-1})}$ で 2 が初めて移動するので、 その 2 の位置によって $j_{n-1}$ が一意に決定する。 よって $j_{n-1}=k_{n-1}$ が言え、

$$p(j_2,j_3,\ldots,j_{n-2},0,0)=p(k_2,k_3,\ldots,k_{n-2},0,0)$$

が成り立つ。

この論法を繰り返せば、結局 $(j_2,j_3,\ldots,j_n)=(k_2,k_3,\ldots,k_n)$ が言える。

例えば $n=4$ のとき、

$$\begin{eqnarray*}&& p(k,j,i) = [1,2,3,4]^{(i)}\circ[2,3,4]^{(j)}\circ[3,4]^{(k)}... ...S_4 = \{p(k,j,i); \hspace{1zw}0\leq i<4, 0\leq j<3, 0\leq k<2\}\end{eqnarray*}$$

が成り立つことになるが、これをすべて書いてみる。

$$\begin{eqnarray*}p(0,0,0) &=& (1,2,3,4),\\ p(1,0,0) &=& (1,2,4,3),\\ p(0,1,0... ... (3,1,4,2),\\ p(1,2,3) &=& (4,1,2,3)\circ (1,3,2,4) = (4,1,3,2)\end{eqnarray*}$$

のようになり、確かにこれですべての順列が現われていることがわかる。

順列 $\sigma=(\sigma_1,\sigma_2,\ldots,\sigma_n)$ に対して、 それを逆順にしたもの

$$(\sigma_n,\sigma_{n-1},\ldots,\sigma_1)$$

を $\sigma$ の反転 と呼び、$\bar{\sigma}$ と書く ( $\bar{\sigma}_j = \sigma_{n-j+1}$)。 一般の反転 $\bar{\sigma}$ は、 次のように $(1,2,\ldots,n)$ の反転と $\sigma$ との積で表すこともできる。

$$\bar{\sigma} = (\sigma_n,\sigma_{n-1},\ldots,\sigma_1) = (n,n-1,\ldots,1)\circ \sigma$$

反転と巡回の積に対して、次が成り立つ。

補題 3

$${[n,n-1,\ldots,j]\circ [j,j+1,\ldots,n]^{(k)}}$$

$$= [j,j+1,\ldots,n]^{(n-j+1-k)}\circ [n,n-1,\ldots,j]$$

$$= [j,j+1,\ldots,n]^{(n-j+2-k)}\circ [j,n,n-1,\ldots,j+1]$$ (12)

証明

$$\begin{eqnarray*}\lefteqn{[j,j+1,\ldots,n]^{(1)}\circ [j,n,n-1,\ldots,j+1]} \ ... ...1,j+2,\ldots,n,j]\circ [j,n,n-1,\ldots,j+1] = [n,n-1,\ldots,j] \end{eqnarray*}$$

であるから、(12) の後半は 結合法則から得られることになるので、最初の等式のみ示せばよい。

$k=1$ の場合を考えると、

$$\begin{eqnarray*}\lefteqn{[n,n-1,\ldots,j]\circ [j,j+1,\ldots,n]^{(1)}} \ &=& ... ...dots,j] \ &=& [j,j+1,\ldots,n]^{(n-j)}\circ [n,n-1,\ldots,j] \end{eqnarray*}$$

となって、この場合には (12) の前半は成り立つ。

これを繰り返せば、補題 1 により、

$$\begin{eqnarray*}\lefteqn{[n,n-1,\ldots,j]\circ [j,j+1,\ldots,n]^{(k)}} \ &=& ... ...& \cdots = [j,j+1,\ldots,n]^{(k(n-j))}\circ [n,n-1,\ldots,j] \end{eqnarray*}$$

となるが、

$$k(n-j) = k(n-j+1)-k \equiv -k \equiv n-j+1-k \pmod{n-j+1}$$

なので、

$$[j,j+1,\ldots,n]^{(k(n-j))} = [j,j+1,\ldots,n]^{(n-j+1-k)}$$

となって (12) が示される。

この補題を使うと、次のことが示される。

補題 4

$0\leq j_k<k$ に対して、$m_k=k+1-j_k$ とすると次が成り立つ。

$$\overline{p(j_2,j_3,\ldots,j_n)} =p(m_2,m_3,\ldots,m_n)$$ (13)

証明

まず、反転を

$$\overline{p(j_2,j_3,\ldots,j_n)} = (n,n-1,\ldots,1)\circ p(j_2,j_3,\ldots,j_n)$$

と積の形に書けば、補題 3 を使って、 次々に $(n,n-1,\ldots,1)$ を $p(j_2,j_3,\ldots,j_n)$ の各巡回順列の項と交換して前に出していくことができる。

$$\begin{eqnarray*}\lefteqn{(n,n-1,\ldots,1)\circ p(j_2,j_3,\ldots,j_n)} \ &=& ... ...(m_n)}\circ [n,n-1,\ldots,2] \circ p(j_2,j_3,\ldots,j_{n-1},0) \end{eqnarray*}$$

のようにしてまず $n$ 個の巡回と入れかえ、

$$\begin{eqnarray*}\lefteqn{[n,n-1,\ldots,2] \circ p(j_2,j_3,\ldots,j_{n-1},0)} \... ...1})}\circ [n,n-1,\ldots,3] \circ p(j_2,j_3,\ldots,j_{n-2},0,0) \end{eqnarray*}$$

のようにして $(n-1)$ 個の巡回と入れかえられる。 これを繰り返すと、最後は

$$\begin{eqnarray*}\lefteqn{[n,n-1]\circ [n-1,n]^{(j_2)}} \ &=& [n-1,n]^{(2-j_2)}\circ [n,n-1] = [n-1,n]^{(3-j_2)} = [n-1,n]^{(m_2)} \end{eqnarray*}$$

となる。よってこれらを合わせれば、 (13) が成り立つ。

$S_n$ は、$n!$ 個の要素を持つが、これは次の $B_n$ で 2 つに分けられる:

$$B_n = \{p(0,j_3,j_4,\ldots,j_n);\hspace{1zw}0\leq j_k<k\}$$ (14)

この $B_n$ は (11) のうち、 $[n,n-1]$ の 2 つの巡回が含まれないものの集まり、 つまり 3 つ以上の巡回から作られる順列で、 この要素数は、$n!/2$ 個になる。 逆に $j_2=1$ の項は $B_n$ には含まれない。

そして補題 4 を使うと、 この $B_n$ は順列とその反転の対を持たないことが示される。

補題 5

$\sigma$ が $B_n$ の元ならば、 その反転 $\bar{\sigma}$ は $B_n$ には含まれない。

証明

$\sigma=p(j_2,j_3,\ldots,j_n)$ とすると、$\sigma\in B_n$ ならば $j_2=0$ である。よって補題 4 より、 $\bar{\sigma}=p(m_2,m_3,\ldots,m_n)$ ($m_k=k+1-j_k$) となるが、 よって、 $m_2=3-j_2=3\equiv 1\pmod{2}$ より

$$\bar{\sigma}=p(1,m_3,\ldots,m_n)\not\in B_n$$

となる。