WIIS

行列式

順列の置換とその符号

目次

前のページ:
Twitter
Mailで保存

順列の置換

自然数\(n\in \mathbb{N} \)を任意に選んだ上で、\(1\)から\(n\)までのすべての自然数からなる集合を、\begin{equation*}\mathbb{N} _{n}=\left\{ 1,2,\cdots ,n\right\} \end{equation*}で表記します。この集合\(\mathbb{N} _{n}\)の要素を何らかの順番にしたがって並べることで得られる列を順列(permutation)と呼び、これを、\begin{equation*}\left( p_{1},p_{2},\cdots ,p_{n}\right)
\end{equation*}で表記します。定義より、任意の順列は、\begin{eqnarray*}
&&\left( a\right) \ \forall j\in \mathbb{N} _{n},\ \exists i\in \mathbb{N} _{n}:p_{i}=j \\
&&\left( b\right) \ \forall i,j\in \mathbb{N} _{n}:\left( i\not=j\Rightarrow p_{i}\not=p_{j}\right)
\end{eqnarray*}をともに満たすことが明らかです。つまり、順列\(\left( p_{1},p_{2},\cdots ,p_{n}\right) \)とは\(1\)から\(n\)までの自然数を重複がない形で並べたものであるということです。

最も典型的な順列は、集合\(\mathbb{N} _{n}\)の要素を小さい順に並べることで得られる順列\begin{equation*}\left( 1,2,\cdots ,n\right)
\end{equation*}ですが、このような順列は自然な順序(natural order)にある言います。その上で、自然な順序にある順列の成分の順番を並べ替えて順列\begin{equation*}
\left( p_{1},p_{2},\cdots ,p_{n}\right)
\end{equation*}を得る操作を、\begin{equation*}
\begin{pmatrix}
1 & 2 & \cdots & n \\
p_{1} & p_{2} & \cdots & p_{n}\end{pmatrix}\end{equation*}もしくは、\begin{equation*}
\left( p_{1},p_{2},\cdots ,p_{n}\right)
\end{equation*}などで表記し、これを置換(permutation)と呼びます。また、集合\(\mathbb{N} _{n}\)の要素を成分とする順列の置換をすべて集めてできる集合を、\begin{equation*}S_{n}
\end{equation*}で表記します。

例(順列の置換)
集合\(\mathbb{N} _{2}\)に関しては、\begin{equation*}S_{2}=\left\{
\begin{pmatrix}
1 & 2 \\
1 & 2\end{pmatrix},\begin{pmatrix}
1 & 2 \\
2 & 1\end{pmatrix}\right\}
\end{equation*}となります。

例(順列の置換)
集合\(\mathbb{N} _{3}\)に関しては、\begin{equation*}S_{3}=\begin{array}{c}
\left\{
\begin{pmatrix}
1 & 2 & 3 \\
1 & 2 & 3\end{pmatrix},\begin{pmatrix}
1 & 2 & 3 \\
1 & 3 & 2\end{pmatrix},\begin{pmatrix}
1 & 2 & 3 \\
2 & 1 & 3\end{pmatrix},\right. \\
\left.
\begin{pmatrix}
1 & 2 & 3 \\
2 & 3 & 1\end{pmatrix},\begin{pmatrix}
1 & 2 & 3 \\
3 & 1 & 2\end{pmatrix},\begin{pmatrix}
1 & 2 & 3 \\
3 & 2 & 1\end{pmatrix}\right\}
\end{array}\end{equation*}となります。

例(恒等置換)
集合\(\mathbb{N} _{n}\)の要素を成分とする順列に関する以下の置換\begin{equation*}\begin{pmatrix}
1 & 2 & \cdots & n \\
1 & 2 & \cdots & n\end{pmatrix}\end{equation*}を恒等置換(identity permutation)と呼びます。これは、自然な順序にある順列\(\left( 1,2,\cdots ,n\right) \)の成分を入れ替えない場合の置換です。

集合\(\mathbb{N} _{n}\)の要素を成分とする順列の置換は\(n\)個の自然数\(1,2,\cdots ,n\)を配列し直したものであるため、置換は全部で\(n!\)通り存在します。

命題(置換の個数)
集合\(\mathbb{N} _{n}\)の要素を成分とする順列の置換に関して、\begin{equation*}\left\vert S_{n}\right\vert =n!
\end{equation*}が成り立つ。ただし、\(\left\vert S_{n}\right\vert \)は集合\(S_{n}\)の要素の個数を表す記号である。

 

全単射としての置換

集合\(\mathbb{N} _{n}\)の要素を成分とする順列の置換\begin{equation*}\begin{pmatrix}
1 & 2 & \cdots & n \\
p_{1} & p_{2} & \cdots & p_{n}\end{pmatrix}\end{equation*}が与えられたとき、それぞれの\(i\in \mathbb{N} _{n}\)に対して、\begin{equation*}\sigma \left( i\right) =p_{i}
\end{equation*}を像として定める写像\(\sigma :\mathbb{N} _{n}\rightarrow \mathbb{N} _{n}\)が定義可能です。置換の定義より、この写像\(\sigma \)は以下の2つの条件\begin{eqnarray*}&&\left( a\right) \ \forall j\in \mathbb{N} _{n},\ \exists i\in \mathbb{N} _{n}:\sigma \left( i\right) =j \\
&&\left( b\right) \ \forall i,j\in \mathbb{N} _{n}:\left[ i\not=j\Rightarrow \sigma \left( i\right) \not=\sigma \left(
j\right) \right] \end{eqnarray*}を満たしますが、これは\(\sigma \)が全単射であることを意味します。逆に、全単射\(\sigma :\mathbb{N} _{n}\rightarrow \mathbb{N} _{n}\)が与えられたとき、そこから以下のような置換\begin{equation*}\begin{pmatrix}
1 & 2 & \cdots & n \\
\sigma \left( 1\right) & \sigma \left( 2\right) & \cdots & \sigma \left(
n\right)
\end{pmatrix}\end{equation*}を構成できます。以上の議論より、置換と全単射は1対1で対応していることが明らかになりました。したがって、両者を同一視しても一般性は失われません。

例(全単射としての置換)
集合\(\mathbb{N} _{2}\)に関して以下の2個の置換\begin{equation*}\sigma _{1}=\begin{pmatrix}
1 & 2 \\
1 & 2\end{pmatrix},\quad \sigma _{2}=\begin{pmatrix}
1 & 2 \\
2 & 1\end{pmatrix}\end{equation*}が存在します。置換\(\sigma _{1}\)は、\begin{eqnarray*}\sigma _{1}\left( 1\right) &=&1 \\
\sigma _{1}\left( 2\right) &=&2
\end{eqnarray*}を満たす全単射\(\sigma _{1}:\mathbb{N} _{2}\rightarrow \mathbb{N} _{2}\)に相当し、置換\(\sigma _{2}\)は、\begin{eqnarray*}\sigma _{2}\left( 1\right) &=&2 \\
\sigma _{2}\left( 2\right) &=&1
\end{eqnarray*}を満たす全単射\(\sigma _{2}:\mathbb{N} _{2}\rightarrow \mathbb{N} _{2}\)に相当します。
例(全単射としての置換)
集合\(\mathbb{N} _{3}\)に関して以下の6個の置換\begin{eqnarray*}&&\sigma _{1}=\begin{pmatrix}
1 & 2 & 3 \\
1 & 2 & 3\end{pmatrix},\quad \sigma _{2}=\begin{pmatrix}
1 & 2 & 3 \\
1 & 3 & 2\end{pmatrix},\quad \sigma _{3}=\begin{pmatrix}
1 & 2 & 3 \\
2 & 1 & 3\end{pmatrix}, \\
&&\sigma _{4}=\begin{pmatrix}
1 & 2 & 3 \\
2 & 3 & 1\end{pmatrix},\quad \sigma _{5}=\begin{pmatrix}
1 & 2 & 3 \\
3 & 1 & 2\end{pmatrix},\quad \sigma _{6}=\begin{pmatrix}
1 & 2 & 3 \\
3 & 2 & 1\end{pmatrix}\end{eqnarray*}が存在します。置換\(\sigma _{1}\)は、\begin{eqnarray*}\sigma _{1}\left( 1\right) &=&1 \\
\sigma _{1}\left( 2\right) &=&2 \\
\sigma _{1}\left( 3\right) &=&3
\end{eqnarray*}を満たす全単射\(\sigma _{1}:\mathbb{N} _{3}\rightarrow \mathbb{N} _{3}\)に相当し、置換\(\sigma _{2}\)は、\begin{eqnarray*}\sigma _{2}\left( 1\right) &=&1 \\
\sigma _{2}\left( 2\right) &=&3 \\
\sigma _{2}\left( 3\right) &=&2
\end{eqnarray*}を満たす全単射\(\sigma _{2}:\mathbb{N} _{3}\rightarrow \mathbb{N} _{3}\)に相当します。残りの置換\(\sigma _{3},\sigma _{4},\sigma _{5},\sigma _{6}\)についても同様に考えます。

 

置換の符号

集合\(\mathbb{N} _{n}\)に関する置換\(\sigma \in S_{n}\)を任意に選びます。すなわち、\begin{equation*}\sigma =\begin{pmatrix}
1 & 2 & \cdots & n \\
\sigma \left( 1\right) & \sigma \left( 2\right) & \cdots & \sigma \left(
n\right)
\end{pmatrix}\end{equation*}です。この置換\(\sigma \)の2つの成分からなる順序対\(\left( \sigma \left( i\right) ,\sigma \left( j\right)\right) \in \mathbb{N} _{n}\times \mathbb{N} _{n}\)を任意に選んだとき、それが以下の2つの条件\begin{eqnarray*}&&\left( a\right) \ i<j \\
&&\left( b\right) \ \sigma \left( i\right) >\sigma \left( j\right)
\end{eqnarray*}がともに満たす場合には、つまり、置換\(\sigma \)において左側にある自然数\(\sigma \left( i\right) \)が右側にある自然数\(\sigma \left(j\right) \)よりも大きい場合には、この順序対\(\left(\sigma \left( i\right) ,\sigma \left( j\right) \right) \)は転倒(inversion)していると言います。

置換\(\sigma \in S_{n}\)からは\(\binom{n}{2}=\frac{n\left( n-1\right) }{2}\)個の順列対を取り出すことができますが、その中でも転倒している順序対の個数が偶数である場合、その置換\(\sigma \)を偶置換(even permutation)と呼びます。一方、置換\(\sigma \)において転倒している順序対の個数が奇数である場合、その置換\(\sigma \)を奇置換(odd permutation)と呼びます。

以上を踏まえた上で、置換\(\sigma \in S_{n}\)の符号(sign)または偶奇性(parity)を、\begin{equation*}\mathrm{sgn}\left( \sigma \right) =\left\{
\begin{array}{cc}
1 & \left( if\ \sigma \text{が偶置換}\right) \\
-1 & \left( if\ \sigma \text{が奇置換}\right)\end{array}\right.
\end{equation*}と定義します。つまり、偶置換の符号は\(1\)として、奇置換の符号は\(-1\)としてそれぞれ定義されます。

例(置換の符号)
置換\(\sigma _{1}\in S_{3}\)が、\begin{equation*}\sigma _{1}=\begin{pmatrix}
1 & 2 & 3 \\
3 & 1 & 2\end{pmatrix}\end{equation*}であるとき、\(\sigma _{1}\)の成分からなる順序対として以下の3つ\begin{equation*}\left( 3,1\right) ,\ \left( 3,2\right) ,\ \left( 1,2\right)
\end{equation*}が存在しますが、この中で転倒している順序対は、\begin{equation*}
\left( 3,1\right) ,\ \left( 3,2\right)
\end{equation*}の2個であるため\(\sigma _{1}\)は偶置換です。したがって、その符号は、\begin{equation*}\mathrm{sgn}\left( \sigma _{1}\right) =1
\end{equation*}となります。また、置換\(\sigma _{2}\in S_{3}\)が、\begin{equation*}\sigma _{2}=\begin{pmatrix}
1 & 2 & 3 \\
3 & 2 & 1\end{pmatrix}\end{equation*}であるとき、\(\sigma _{2}\)の成分からなる順序対として以下の3つ\begin{equation*}\left( 3,2\right) ,\ \left( 3,1\right) ,\ \left( 2,1\right)
\end{equation*}が存在しますが、この中で転倒している順序対は、\begin{equation*}
\left( 3,2\right) ,\ \left( 3,1\right) ,\ \left( 2,1\right)
\end{equation*}の3個であるため\(\sigma _{2}\)は奇置換です。したがって、その符号は、\begin{equation*}\mathrm{sgn}\left( \sigma _{2}\right) =-1
\end{equation*}です。

例(置換の符号)
置換\(\sigma \in S_{5}\)が、\begin{equation*}\sigma =\begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\
3 & 5 & 1 & 4 & 2\end{pmatrix}\end{equation*}であるとき、\(\sigma \)の成分からなる順序対として以下の10個\begin{equation*}\left( 3,5\right) ,\ \left( 3,1\right) ,\ \left( 3,4\right) ,\ \left(
3,2\right) ,\ \left( 5,1\right) ,\ \left( 5,4\right) ,\ \left( 5,2\right) ,\
\left( 1,4\right) ,\ \left( 1,2\right) ,\ \left( 4,2\right)
\end{equation*}が存在しますが、この中で転倒している順序対は、\begin{equation*}
\left( 3,1\right) ,\ \left( 3,2\right) ,\ \left( 5,1\right) ,\ \left(
5,4\right) ,\ \left( 5,2\right) ,\ \left( 4,2\right)
\end{equation*}の6個であるため\(\sigma \)は偶置換です。したがって、その符号は、\begin{equation*}\mathrm{sgn}\left( \sigma \right) =1
\end{equation*}です。

例(置換の符号)
置換\(\sigma \in S_{n}\)が恒等置換であるものとします。つまり、\begin{equation*}\sigma =\begin{pmatrix}
1 & 2 & \cdots & n \\
1 & 2 & \cdots & n\end{pmatrix}\end{equation*}です。転倒している順序対は存在しないため、すなわち転倒している順序対の個数は\(0\)であるため\(\sigma \)は偶置換です。したがって、恒等置換\(\sigma \)の符号は、\begin{equation*}\mathrm{sgn}\left( \sigma \right) =1
\end{equation*}です。

 

演習問題

問題(順列の置換)
置換\(\sigma \in S_{4}\)が、\begin{equation*}\sigma =\begin{pmatrix}
1 & 2 & 3 & 4 \\
4 & 2 & 3 & 1\end{pmatrix}\end{equation*}であるものとします。この置換の符号を特定してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(順列の置換)
置換\(\sigma \in S_{6}\)が、\begin{equation*}\sigma =\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 \\
5 & 4 & 2 & 1 & 6 & 3\end{pmatrix}\end{equation*}であるものとします。この置換の符号を特定してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(順列の置換)
置換\(\sigma \in S_{n}\)が、\begin{equation*}\sigma =\begin{pmatrix}
1 & 2 & \cdots & n \\
n & n-1 & \cdots & 1\end{pmatrix}\end{equation*}で与えられているものとします。つまり、\(\sigma \)は自然数\(1,2,\cdots ,n\)を大きい順に並べ替える置換です。この置換\(\sigma \)の符号を特定してください。
解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

前のページ:
Twitter
Mailで保存

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録

関連知識

順列の置換の積(合成)とその符号

順列の置換は全単射と同一視できるため、複数の置換の合成写像を定義できます。これを置換の積と呼びます。置換の積の符号は、置換の符号どうしの積と一致します。

順列の置換の逆置換とその符号

順列の置換は全単射と同一視できるため、その逆写像に相当する全単射が存在し、それを逆置換と呼びます。置換と逆置換の符号は一致します。