教材一覧
教材一覧
教材検索
DETERMINANT

順列の置換の符号

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

順列の置換

有限な自然数\(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*}をともに満たすことが明らかです。

最も典型的な順列は、集合\(\mathbb{N} _{n}\)の要素を小さい順に並べることで得られる順列\begin{equation*}\left( 1,2,\cdots ,n\right)
\end{equation*}ですが、このような順列は自然な順序(natural order)にある言います。

自然な順序にある順列\(\left( 1,2,\cdots ,n\right) \)の成分の順番を並べ替えて順列\(\left( p_{1},p_{2},\cdots ,p_{n}\right) \)を得る操作を、\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} _{2}=\left\{ 1,2\right\} \)の要素を成分とする順列に関して以下の2通りの置換\begin{equation*}\begin{pmatrix}
1 & 2 \\
1 & 2\end{pmatrix},\quad
\begin{pmatrix}
1 & 2 \\
2 & 1\end{pmatrix}\end{equation*}が存在します。

例(順列の置換)
集合\(\mathbb{N} _{3}=\left\{ 1,2,3\right\} \)の要素を成分とする順列に関して以下の6通りの置換\begin{eqnarray*}&&\begin{pmatrix}
1 & 2 & 3 \\
1 & 2 & 3\end{pmatrix},\quad
\begin{pmatrix}
1 & 2 & 3 \\
1 & 3 & 2\end{pmatrix},\quad
\begin{pmatrix}
1 & 2 & 3 \\
2 & 1 & 3\end{pmatrix}, \\
&&\begin{pmatrix}
1 & 2 & 3 \\
2 & 3 & 1\end{pmatrix},\quad
\begin{pmatrix}
1 & 2 & 3 \\
3 & 1 & 2\end{pmatrix},\quad
\begin{pmatrix}
1 & 2 & 3 \\
3 & 2 & 1\end{pmatrix}\end{eqnarray*}が存在します。

例(順列の置換)
\(\mathbb{N} _{n}=\left\{ 1,2,\cdots ,n\right\} \)の要素を成分とする順列に関して以下の置換\begin{equation*}\begin{pmatrix}
1 & 2 & \cdots & n \\
1 & 2 & \cdots & n\end{pmatrix}\end{equation*}に注目します。つまり、これは自然な順序にある順列\(\left( 1,2,\cdots ,n\right) \)から成分を入れ替えないケースの置換です。このような置換を恒等置換(identity permutation)と呼びます。

集合\(\mathbb{N} _{n}=\left\{ 1,2,\cdots ,n\right\} \)の要素を成分とする順列の置換をすべて集めてできる集合を、\begin{equation*}S_{n}
\end{equation*}で表記します。置換は\(n\)個の自然数\(1,2,\cdots ,n\)を配列し直したものであるため、全部で\(n!\)通りの置換が存在します。

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

 

全単射としての置換

繰り返しになりますが、集合\(\mathbb{N} _{n}=\left\{ 1,2,\cdots ,n\right\} \)の要素を成分とする順列の置換を、\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}=\left\{ 1,2\right\} \)の要素を成分とする順列に関して以下の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}=\left\{ 1,2,3\right\} \)の要素を成分とする順列に関して以下の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}\)についても同様に考えます。

 

置換の符号

置換\(\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*}です。順序対\(\left( \sigma \left(i\right) ,\sigma \left( j\right) \right) \in \mathbb{N} _{n}\times \mathbb{N} _{n}\)に対して以下の条件\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}\)において転倒している順序対の個数が偶数個である場合、その置換\(\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*}を満たすものとします。転倒している順序対は、\begin{equation*}
\left( 3,1\right) ,\quad \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*}を満たすものとします。転倒している順序対は、\begin{equation*}
\left( 3,2\right) ,\quad \left( 3,1\right) ,\quad \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*}を満たすものとします。転倒している順序対は、\begin{equation*}
\left( 3,1\right) ,\quad \left( 5,1\right) ,\quad \left( 3,2\right) ,\quad
\left( 5,2\right) ,\quad \left( 4,2\right) ,\quad \left( 5,4\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 \)の符号を特定してください。
解答を見る

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

Share on twitter
Twitterで共有
Share on email
メールで共有
DISCUSSION

質問とコメント

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

RELATED KNOWLEDGE

関連知識

置換の合成
置換の積(合成)の符号

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

置換の符号
逆置換の符号

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