第33話  置換

この記事を読む助けになる数学の記事
・数値計算：1話、 5話、 15話

　\( 1,2, \ldots , n \) を並べ替える操作を置換と呼びます。 順列の総数の公式より、\( n \) 文字の置換は全部で \( n! \) 個あることがわかります。 置換は次にあげる方法で表記されます。

　\( n \) 文字の置換の特別な例として、恒等置換または単位置換と呼ばれるものがあります。 これは \( 1_n \) と表され、 \[ \begin{align} 1_n = \left( \begin{array}{cccc} 1 & 2 & \ldots & n \\ 1 & 2 & \ldots & n \\ \end{array} \right) \end{align}\] となります。

　\( n \) 文字の置換 \( \sigma \) の逆操作を \( \sigma \) の逆置換と呼び、\( \sigma ^{-1}\) で表します。 すなわち、 \[ \begin{align} \sigma = \left( \begin{array}{cccc} 1 & 2 & \ldots & n \\ i_1 & i_2 & \ldots & i_n \\ \end{array} \right) \end{align}\] ならば、 \[ \begin{align} \sigma ^{-1} = \left( \begin{array}{cccc} i_1 & i_2 & \ldots & i_n \\ 1 & 2 & \ldots & n \\ \end{array} \right) \end{align}\] となります。

　置換には次に示す積と呼ばれる演算が定義されます。

　\( \sigma \) 、\( \tau \) 、\( \rho \) を \( n \) 文字の置換とすると、置換の積の定義から、次の 3 つの性質が成り立ちます。 \[ \begin{align} \left( \sigma \tau \right) \rho &= \sigma \left( \tau \rho \right) \\\\ 1_n \sigma &= \sigma 1_n \\\\ \sigma \sigma ^{-1} &= \sigma ^{-1} \sigma = 1_n \end{align}\] 　\( n \) 文字の置換全体の集合を \( S_n \) で表すと、これについて次の定理が成り立ちます。

i については、 \[ \begin{align} \sigma _1 \neq \sigma _2 \rm \ \ \ ならば \ \ \ \it \sigma \rm _1 ^{-1} \neq \it \sigma \rm _2 ^{-1} \end{align}\] であることから、\( \sigma ^{-1} \) が重複しないために成り立ちます。 ii についても同様に、 \[ \begin{align} \sigma _1 \neq \sigma _2 \rm \ \ \ ならば \ \ \ \it \sigma \rm _1 \it \tau \rm \neq \it \sigma \rm _2 \it \tau \end{align}\] \[ \begin{align} \sigma _1 \neq \sigma _2 \rm \ \ \ ならば \ \ \ \it \tau \sigma \rm _1 \rm \neq \it \tau \sigma \rm _2 \end{align}\] であることから、\( \sigma \tau \) および \( \tau \sigma \) が重複しないために成り立ちます。

　\( n \) 文字の置換で、2 つの文字のみを並べ替えるものを互換と呼びます。 任意の置換は互換の積で表すことができますが、その表し方は 1 通りではありません。 ですが、これについて次の定理が成り立ちます。

　上の定理を証明するにあたり、\( n \) 変数の差積と呼ばれる \( n \) 個の変数 \( x_1 , x_2 , \ldots , x_n \) からなる次の多項式 \( \Delta \left( x_1 , x_2 , \ldots , x_n \right) \) を考えます。 \[ \begin{align} \Delta \left( x_1 , x_2 , \ldots , x_n \right) &= \prod _{i \lt j} \left( x_j - x_i \right) \\\\ &= \prod _{j=2} ^n \left\{ \prod _{i=1} ^{j-1} \left( x_j - x_i \right) \right\} \\\\ &= \left( x_n - x_{n-1} \right) \left( x_n - x_{n-2} \right) \cdots \left( x_n - x_{2} \right) \left( x_n - x_{1} \right) \times \\\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left( x_{n-1} - x_{n-2} \right) \cdots \left( x_{n-1} - x_{2} \right) \left( x_{n-1} - x_{1} \right) \times \\\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \cdots \cdots \\\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left( x_{3} - x_{2} \right) \left( x_{3} - x_{1} \right) \times \\\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left( x_{2} - x_{1} \right) \end{align}\] なお、ここで \[ \begin{align} \prod _{i \lt j} \left( x_j - x_i \right) \end{align}\] は \( i \lt j \) を満たすあらゆる添え字の組 \( i,j \) にわたる \( \left( x_j - x_i \right) \) の積を表します。また、一般に数列 \( \left\{ a_k \right\} \) について \[ \begin{align} \prod _{k=n} ^{m} a_k = a_n a_{n+1} \cdots a_{m} \end{align}\] と表します。

　 \( n \) 文字の置換 \( \sigma \) について、差積の定義より、 \[ \begin{align} \Delta \left( x_{\sigma \left( 1 \right)} , x_{\sigma \left( 2 \right)} , \ldots , x_{\sigma \left( n \right)} \right) = \pm \Delta \left( x_1 , x_2 , \ldots , x_n \right) \end{align}\] となることがわかります。もし、\( \tau \) が互換なら、 \[ \begin{align} \Delta \left( x_{\tau \left( 1 \right)} , x_{\tau \left( 2 \right)} , \ldots , x_{\tau \left( n \right)} \right) = - \Delta \left( x_1 , x_2 , \ldots , x_n \right) \end{align}\] となります。これについては、次のように考えます。

　では、ここで置換 \( \sigma \) が互換の積として 2 通りに表されているとします。 \[ \begin{align} \sigma = \mu _1 \mu _2 \cdots \mu _k = \nu _1 \nu _2 \cdots \nu _l \end{align}\] すると、差積と互換の性質より、次式が成り立ちます。 \[ \begin{align} \Delta \left( x_{\sigma \left( 1 \right)} , x_{\sigma \left( 2 \right)} , \ldots , x_{\sigma \left( n \right)} \right) &= \left( -1 \right) ^k \Delta \left( x_1 , x_2 , \ldots , x_n \right) \\\\ &= \left( -1 \right) ^l \Delta \left( x_1 , x_2 , \ldots , x_n \right) \end{align}\] 従って、\( \left( -1 \right) ^l = \left( -1 \right) ^k \) が成り立つため、\( k \) と \( l \) の偶奇性は一致することがわかります。

　置換 \( \sigma \) が偶数個の互換の積であるとき偶置換、奇数個の互換の積であるとき奇置換と呼びます。 また、記号 \( \rm sgn \ \it \sigma \) を置換 \( \sigma \) の符号と呼び、\( \sigma \) が偶置換のときは \( \rm sgn \ \it \sigma \rm = 1 \) 、奇置換のときは \( \rm sgn \ \it \sigma \rm = -1 \) とします。 置換の符号について、次の性質が成り立ちます。 \[ \begin{align} \rm sgn \ 1 \it _n \rm &= 1 \\\\ \rm sgn \ \it \sigma \rm ^{-1} &= \rm sgn \ \it \sigma \\\\ \rm sgn \ \it \sigma \tau &= \rm sgn \ \it \sigma \cdot \rm sgn \ \it \tau \end{align}\]