next up previous
次: 4.3 多項式の文字の置換 上: 4 行列式 前: 4.1 行列式の導出

4.2 置換

定義 4.1 (文字の置換)   $ n$ 個の文字 $ \{1,2,\cdots,n\}$ から 自分自身 $ \{1,2,\cdots,n\}$ への $ 1$ 対 $ 1$ の写像を $ n$ 文字の置換（permutation）という． $ n$ 文字の置換 $ \sigma$ が写像

$\displaystyle 1\to k_{1}\,,\quad 2\to k_{2}\,,\quad \cdots n\to k_{n}\,$ (609)

のとき $ \sigma$ を

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & \cdots & n \\ k_{1} & k_{2} & \cdots & k_{n} \end{pmatrix}$ (610)

と表わす． 写像 $ j\to k_{j}$ を $ \sigma(j)=k_{j}$ と表わす．

例 4.2 (置換の具体例)  

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{pmatrix}\,,$ (611)
  $\displaystyle 1\to3\,,\quad 2\to1\,,\quad 4\to4\,,\quad 4\to2\,,$ (612)
  $\displaystyle \sigma(1)=3\,,\quad \sigma(2)=1\,,\quad \sigma(4)=4\,,\quad \sigma(4)=2\,.$ (613)

例 4.3 (置換の表記)  

$\displaystyle \begin{pmatrix}1 & 2 & 3 & 4 \\ 3 & 2 & 4 & 1 \end{pmatrix}= \beg... ...4 & 1 & 3 \end{pmatrix}= \begin{pmatrix}3 & 1 & 4 \\ 4 & 3 & 1 \end{pmatrix}\,.$ (614)

同じ数字に置換する場合は省略可能． 並べる順はどうでも良い．

定義 4.4 (置換の積)   二つの置換

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & \cdots & n \\ k_{1} & k_{2} & \cdots & k_{n} \end{pmatrix}\,,$ (615)
$\displaystyle \tau$ $\displaystyle = \begin{pmatrix}1 & 2 & \cdots & n \\ l_{1} & l_{2} & \cdots & l_{n} \end{pmatrix}$ (616)

の積 $ \sigma\tau$ を

$\displaystyle \sigma\tau$ $\displaystyle = \begin{pmatrix}1 & 2 & \cdots & n \\ k_{1} & k_{2} & \cdots & k... ...rix}1 & 2 & \cdots & n \\ k_{l_1} & k_{l_2} & \cdots & k_{l_n} \end{pmatrix}\,,$ (617)

または

$\displaystyle (\sigma\tau)(i)=\sigma(\tau(i))\,,\quad i=1,2,\cdots,n$ (618)

と定義する．

例 4.5 (置換の積の具体例)  

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{pmatrix}\,,\quad \tau= \begin{pmatrix}1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{pmatrix}\,,$ (619)
$\displaystyle \sigma\tau$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{pmatrix} \begin{pmatrix}1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{pmatrix}$ (620)
  $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ \sigma(\tau(1)) & \sigma(\tau(2... ...ix}1 & 2 & 3 & 4 \\ \sigma(2) & \sigma(3) & \sigma(4) & \sigma(1) \end{pmatrix}$ (621)
  $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{pmatrix}\,,$ (622)
$\displaystyle \tau\sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{pmatrix} \begin{pmatrix}1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{pmatrix}$ (623)
  $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ \tau(\sigma(1)) & \tau(\sigma(2... ...in{pmatrix}1 & 2 & 3 & 4 \\ \tau(4) & \tau(3) & \tau(1) & \tau(2) \end{pmatrix}$ (624)
  $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ 1 & 4 & 2 & 3 \end{pmatrix}\,.$ (625)

注意 4.6 (置換の積は非可換)   一般的に $ \sigma\tau=\tau\sigma$ は成立しない．

定義 4.7 (単位置換)   全ての文字を動かさない置換

$\displaystyle \epsilon$ $\displaystyle = \begin{pmatrix}1 & 2 & \cdots & n \\ 1 & 2 & \cdots & n \end{pmatrix}$ (626)

を単位置換と呼ぶ．

定義 4.8 (逆置換)   置換 $ \sigma$ に対して

$\displaystyle \sigma\tau=\tau\sigma=\epsilon$ (627)

を満たす置換 $ \tau$ を $ \sigma$ の逆置換と呼び， $ \tau=\sigma^{-1}$ と表わす．

定理 4.9 (逆置換)   置換

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & \cdots & n \\ k_{1} & k_{2} & \cdots & k_{n} \end{pmatrix}$ (628)

の逆置換は

$\displaystyle \sigma^{-1}$ $\displaystyle = \begin{pmatrix}k_{1} & k_{2} & \cdots & k_{n} \\ 1 & 2 & \cdots & n \end{pmatrix}$ (629)

で与えられる．

例 4.10 (逆置換の具体例)  

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 1 & 3 & 2 \end{pmatrix}\,,$ (630)
$\displaystyle \sigma^{-1}$ $\displaystyle = \begin{pmatrix}4 & 5 & 1 & 3 & 2 \\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}= \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{pmatrix}\,.$ (631)

定義 4.11 (巡回置換)   $ n$ 個の文字 $ \{1,2,\cdots,n\}$ のうち $ r$ 個の文字 $ \{k_{1},k_{2},\cdots,k_{r}\}$ のみを $ k_{1}\to k_{2},k_{2}\to k_{3},\cdots,k_{r}\to k_{1}$ と順にずらし， 残りの文字 $ \{k_{r+1},\cdots,k_{n}\}$ を $ k_{r+1}\to k_{r+1},\cdots,k_{n}\to k_{n}$ と動かさない 写像の置換を巡回置換という． 巡回置換は

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}k_{1} & k_{2} & \cdots & k_{r-1} & k_{r} & k_{r+... ...k_{2} & k_{3} & \cdots & k_{r} & k_{1} & k_{r+1} & \cdots & k_{n} \end{pmatrix}$ (632)
  $\displaystyle = \begin{pmatrix}k_{1} & k_{2} & \cdots & k_{r-1} & k_{r} \\ k_{2} & k_{3} & \cdots & k_{r} & k_{1} \end{pmatrix}$ (633)

と表わされ，省略するときは

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}k_{1} & k_{2} & \cdots & k_{r} \end{pmatrix}$ (634)

と書く．

例 4.12 (巡回置換の具体例)  

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 1 & 5 & 2 & 4 & 3 \end{pmat... ...\\ 5 & 2 & 3 \end{pmatrix}= \begin{pmatrix}2 & 5 & 3 \\ 5 & 3 & 2 \end{pmatrix}$ (635)
  $\displaystyle = \begin{pmatrix}2 & 5 & 3 \end{pmatrix}= \begin{pmatrix}5 & 3 & 2 \end{pmatrix}= \begin{pmatrix}3 & 2 & 5 \end{pmatrix}\,,$ (636)
$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 2 & 4 & 5 \end{pmat... ...\\ 3 & 1 & 2 \end{pmatrix}= \begin{pmatrix}1 & 3 & 2 \\ 3 & 2 & 1 \end{pmatrix}$ (637)
  $\displaystyle = \begin{pmatrix}1 & 3 & 2 \end{pmatrix}= \begin{pmatrix}3 & 2 & 1 \end{pmatrix}= \begin{pmatrix}2 & 1 & 3 \end{pmatrix}\,.$ (638)

定理 4.13 (置換を巡回置換の積で表わす)   任意の置換 $ \sigma$ は巡回置換 $ \sigma_{1},\sigma_{2},\cdots,\sigma_{n}$ の積で $ \sigma=\sigma_{1}\sigma_{2}\cdots\sigma_{n}$ と表わされる．

例 4.14 (置換を巡回置換の積で表わす計算例)  

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 1 & 6 & 2 & 7 &... ...in{pmatrix}1 & 4 & 2 & 3 & 6 & 5 & 7 \\ 4 & 2 & 1 & 6 & 5 & 7 & 3 \end{pmatrix}$ (639)
  $\displaystyle = \begin{pmatrix}1 & 4 & 2 & 3 & 6 & 5 & 7 \\ 4 & 2 & 1 & 3 & 6 &... ...2 & 1 \end{pmatrix} \begin{pmatrix}3 & 6 & 5 & 7 \\ 6 & 5 & 7 & 3 \end{pmatrix}$ (640)
  $\displaystyle = \begin{pmatrix}1 & 4 & 2 \end{pmatrix} \begin{pmatrix}3 & 6 & 5 & 7 \end{pmatrix}\,.$ (641)

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 5 & 3 & 7 & 1 & 4 &... ...in{pmatrix}1 & 5 & 4 & 2 & 3 & 7 & 6 \\ 5 & 4 & 1 & 3 & 7 & 6 & 2 \end{pmatrix}$ (642)
  $\displaystyle = \begin{pmatrix}1 & 5 & 4 & 2 & 3 & 7 & 6 \\ 5 & 4 & 1 & 2 & 3 &... ...4 & 1 \end{pmatrix} \begin{pmatrix}2 & 3 & 7 & 6 \\ 3 & 7 & 6 & 2 \end{pmatrix}$ (643)
  $\displaystyle = \begin{pmatrix}1 & 5 & 4 \end{pmatrix} \begin{pmatrix}2 & 3 & 7 & 6 \end{pmatrix}\,.$ (644)

定義 4.15 (互換)   $ 2$ 文字の巡回置換 $ (i\quad j)$ を 互換という．

定理 4.16 (巡回置換を互換の積で表わす)   任意の巡回置換は互換の積で表わされる． たとえば，その一つとして

$\displaystyle \begin{pmatrix}k_1 & k_2 & \cdots & k_r \end{pmatrix}= \begin{pma... ...s \begin{pmatrix}k_1 & k_3 \end{pmatrix} \begin{pmatrix}k_1 & k_2 \end{pmatrix}$ (645)

と表わされる．

例 4.17 (置換を互換の積で表わす)   たとえば

$\displaystyle \begin{pmatrix}1 & 2 & 3 & 4 \end{pmatrix}$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \\ 4 & 2 & 3 & 1 \end{pmatrix} \be... ...1 & 4 \end{pmatrix} \begin{pmatrix}1 & 2 & 3 & 4 \\ 2 & 1 & 3 & 4 \end{pmatrix}$ (646)
  $\displaystyle = \begin{pmatrix}1 & 4 \end{pmatrix} \begin{pmatrix}1 & 3 \end{pmatrix} \begin{pmatrix}1 & 2 \end{pmatrix}\,.$ (647)

たとえば

$\displaystyle \begin{pmatrix}1 & 2 & 3 & 4 \end{pmatrix}$ $\displaystyle = \begin{pmatrix}1 & 3 \end{pmatrix} \begin{pmatrix}1 & 4 \end{pm... ...atrix} \begin{pmatrix}2 & 3 \end{pmatrix} \begin{pmatrix}1 & 3 \end{pmatrix}\,.$ (648)

注意 4.18   互換の積で表わす方法は幾通りもある．

定義 4.19 (置換の符号)   置換 $ \sigma$ が $ m$ 個の互換の積で表わされるとき $ \sigma$ の符号（sign）を

$\displaystyle \mathrm{sgn}\,(\sigma)=(-1)^{m}$ (649)

と定義する．

例 4.20 (置換の符号の具体例)  

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \end{pmatrix}= \begin{pmatrix}1 & ... ...{pmatrix} \begin{pmatrix}1 & 3 \end{pmatrix} \begin{pmatrix}1 & 2 \end{pmatrix}$ (650)

より

$\displaystyle \mathrm{sgn}\,(\sigma)$ $\displaystyle = (-1)^{3}=-1$ (651)

となる．また

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 \end{pmatrix}= \begin{pmatrix}1 & ... ...{pmatrix} \begin{pmatrix}2 & 3 \end{pmatrix} \begin{pmatrix}1 & 3 \end{pmatrix}$ (652)

より

$\displaystyle \mathrm{sgn}\,(\sigma)$ $\displaystyle = (-1)^{5}=-1$ (653)

である．

定理 4.21 (置換の符号の一意性)   置換 $ \sigma$ の符号 $ \mathrm{sgn}\,(\sigma)$ は 互換の積の表わし方によらず一意に定まる．

定理 4.22 (置換の符号の性質)  

  $\displaystyle \mathrm{sgn}\,(\epsilon)=1$ (654)
  $\displaystyle \mathrm{sgn}\,(\sigma\tau)=\mathrm{sgn}\,(\sigma)\mathrm{sgn}\,(\tau)$ (655)
  $\displaystyle \mathrm{sgn}\,(\sigma^{-1})=\mathrm{sgn}\,(\sigma)$ (656)

定義 4.23 (偶置換，奇置換)   $ \mathrm{sgn}\,(\sigma)=1$ となる置換を 偶置換と呼び， $ \mathrm{sgn}\,(\sigma)=-1$ となる置換を 奇置換と呼ぶ．

例 4.24 (偶置換，奇置換の具体例)  

$\displaystyle \sigma$ $\displaystyle = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 7 & 6 & 8 &... ... & 9 & 5 & 2 & 6 & 4 & 3 & 3 \\ 7 & 9 & 5 & 1 & 6 & 4 & 2 & 8 & 2 \end{pmatrix}$ (657)
  $\displaystyle = \begin{pmatrix}1 & 7 & 9 & 5 \\ 7 & 9 & 5 & 1 \end{pmatrix} \be... ...trix} \begin{pmatrix}2 & 6 & 4 \end{pmatrix} \begin{pmatrix}3 & 8 \end{pmatrix}$ (658)
  $\displaystyle = \begin{pmatrix}1 & 5 \end{pmatrix} \begin{pmatrix}1 & 9 \end{pm... ...{pmatrix} \begin{pmatrix}2 & 6 \end{pmatrix} \begin{pmatrix}3 & 8 \end{pmatrix}$ (659)

より

$\displaystyle \mathrm{sgn}\,(\sigma)$ $\displaystyle =(-1)^6=1$ (660)

となる． $ \sigma$ は偶置換である．

定義 4.25 (置換全体の集合)   $ n$ 文字の置換 $ \sigma$ の全体の集合を $ S_{n}$ と書く．

注意 4.26 (置換全体の集合の要素の個数)   $ n$ 文字の置換は写像

$\displaystyle \{1,2,\cdots,n\}\quad\to\quad \{k_{1},k_{2},\cdots,k_{n}\}$ (661)

であるから， その個数は $ n$ 個の文字の順列組合わせに等しい． よって集合 $ S_{n}$ の個数は $ n!$ である．

例 4.27 (置換全体の集合の具体例)  

$\displaystyle S_{1}$ $\displaystyle =\left\{ \begin{pmatrix}1 \\ 1 \end{pmatrix} \right\}= \{\underset{\text{偶}}{\epsilon}\}$ (662)
$\displaystyle S_{2}$ $\displaystyle = \left\{ \begin{pmatrix}1 & 2 \\ 1 & 2 \end{pmatrix}, \begin{pma... ...�}}{\epsilon},\quad \underset{\text{奇}}{\begin{pmatrix}1 & 2 \end{pmatrix}} \}$ (663)
$\displaystyle S_{3}$ $\displaystyle = \left\{ \begin{pmatrix}1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}, \b... ...& 2 \end{pmatrix}, \begin{pmatrix}1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix} \right\}$ (664)
  $\displaystyle = \{ \underset{\text{偶}}{\epsilon},\quad \underset{\text{奇}}{\b... ...end{pmatrix}},\quad \underset{\text{奇}}{\begin{pmatrix}1 & 2 \end{pmatrix}} \}$ (665)

問 4.28 (置換全体の集合)   $ 4$ 次の置換全体の集合 $ S_4$ の要素全てを書き出せ． またその偶奇も述べよ．

問 4.29 (偶置換，奇置換の個数)   $ S_{n}$ $ (n\geq2)$ に含まれる偶置換と奇置換の個数は等しい． これを示せ．

next up previous
次: 4.3 多項式の文字の置換 上: 4 行列式 前: 4.1 行列式の導出

Kondo Koichi
平成17年9月15日