線形代数　第９回　置換

※横に長い数式をスマホ画面で見る際に，途中で切れているものがあることがあります．このときは，画面を横向きにして（ページを更新し直す）か，数式を横にスクロールさせることで，全貌を見ることができます．

　

連立方程式については一通り解説が終わり，ここから話題が切り替わり，行列式についての話になります．今回はそのための準備で，行列に関係ない話をします．突然行列と全く関係ない話になるのでびっくりすると思いますが，この話は後々必要になるのでしているわけです．

という表記をする．この表示の仕方をサイクル表示と呼ぶこととする．正式な呼び方ではない◆

全単射とはなんだったかというと，全射かつ単射であることでした．
写像$f:X\longrightarrow Y$が全射であるとは，$\forall\;y\in Y,\; \exists\;x\in X\; y=f(x)$が成り立つことです．
写像$f:X\longrightarrow Y$が単射であるとは，$\forall x_1,x_2\in X,\;f(x_1)=f(x_2)\Longrightarrow x_1=x_2$が成り立つことです．

全単射であることは「一対一対応」といいました．つまり，今回の場合，置換というのは，$\{1,2,…,n\}$の元から$\{1,2,…,n\}$の元への一対一対応の仕方と言い換えることができます．それは$\{1,2,…,n\}$の「並べ替え」という同じです．

例１　$n=6$のとき\[\sigma(1)=2,\sigma(2)=1,\sigma(3)=5,\sigma(4)=3,\sigma(5)=4,\sigma(6)=6\]という並べ替えを考えてみましょう．これは\[\displaystyle\sigma=\left(\begin{array}{cccccc}
1 & 2 & 3 & 4 & 5 & 6\\
2 & 1 & 5 & 3 & 4 & 6
\end{array}\right)\]と書けます．$(1,2,3,4,5,6)$を$(2,1,5,3,4,6)$に並べ替えているわけですね．
あるいはサイクル表示をすると\[(1\; 2)(3\; 5 \; 4)\]と書けます．1は2に行き2は1に行きます．3は5に，5は4に，4は3に行くのでそこでループを描いているわけですね．それを表現しているのが上のような書き方です．6は動かないので，6は書かなくていいです．

に対して，真逆に変換する置換（つまり逆写像）：\[\left(\begin{array}{ccccc}
a_1 & a_2 & a_3 & … & a_n\\
1 & 2 & 3 & … & n
\end{array}\right)\]を逆置換といい，$\sigma^{-1}$と表す．つまり「$1$を$a_1$に，$2$を$a_2$に…」する変換に対して，「$a_1$を$1$に，$a_2$を$2$に…」する変換のことを逆変換と言います．

(3) 2つの置換$\sigma,\tau\in\mathfrak{S}_n$に対して，合成（積ともいう）$\sigma\circ\tau\in\mathfrak{S}_n$も置換である．これを$\sigma\tau$と書く．◆

これは大事な注意ですが，$\sigma\tau$と書いたら，まず$\tau$の変換をしてから$\sigma$の変換をするのであって，$\sigma$の変換をしてから$\tau$の変換をするのではないです．写像の合成$\sigma\circ\tau$と同じルールです．

例２　$\sigma,\tau\in\mathfrak{S}_4$は\[\sigma=\left(\begin{array}{ccccc}
1 & 2 & 3 & 4\\
2 & 4 & 3 & 1
\end{array}\right),\;\;\;\tau=\left(\begin{array}{ccccc}
1 & 2 & 3 & 4\\
4 & 3 & 2 & 1
\end{array}\right)\]で定義される．$\sigma\tau$を考えてみよう．
$1$は$\tau$によって$4$に行き，$4$は$\sigma$によって$1$に行く．従って，$1$は$\sigma\tau$によって$1$に行く．これを$2,3,4$についても考えると\[\sigma\tau=\left(\begin{array}{ccccc}
1 & 2 & 3 & 4\\
1 & 3& 4 & 2
\end{array}\right)=(2\;3\;4)\] ◆

（群という言葉を知っている人向け）この定義によって，$\mathfrak{S}_n$は群になります．
置換が全単射写像であることを考えれば，証明はどれも明らかです．

例３\[\sigma=\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5 & 6 & 7\\
2 & 3 & 5 & 6 & 1& 4 & 7
\end{array}\right)\]を考えよう．これは$(1\;2\;3\;5)(4\;6)$と表されている．$(1\;2\;3\;5)$の方をさらに互換の積で書きたい．\[\left(\begin{array}{ccccc}
1 & 2 & 3 & 5 \\
2 & 3 & 5 & 1
\end{array}\right)\]$(1,2,3,5)$を$(2,3,5,1)$に2つの数字の交換のみで並べ替えたいので\[
(1,2,3,5)\overset{(1\; 2)}{\longmapsto}(2,1,3,5)\overset{(1\; 3)}{\longmapsto}(2,3,1,5)\overset{(1\; 5)}{\longmapsto}(2,3,5,1)\]とできます．矢印の上に書いた$(1\; 2)$などは互換を表します．つまり$(1\; 2)$と書いてあるところは$1,2$を入れ替える操作をした，ということです．よって\[(2\;3\;5\;1)=(1\;5)(1\;3)(1\; 2)\]以上から\[\sigma=(1\;5)(1\;3)(1\; 2)(4\;6)\]と書けます．${\rm sgn}\:\sigma=(-1)^4=1$です．

つまり偶数個の互換の積で表される置換は符号を$+1$，気数個の互換の積で表される置換は符号を$-1$とするんですね．ここで大事なことが一つあります．それは「置換を互換の積で表したときに，偶数個の互換の積と奇数個の互換の積の2通りで表せてしまうことがあるのではないか？」ということです．そのような場合，その置換は符号をうまく定められません．
しかし，実際にはそのようなことは起きないことが知られています．

この定理の証明は省略します．
例えば，$(1\;2\;3)$は$(1\;3)(1\;2)$と表されるわけですが，これを$(1\;3)(1\;2)(2\;3)(2\;3)$と表すこともできます．$(2\;3)(2\;3)={\rm id}$ですから，$(1\;3)(1\;2)$と等しいわけです．このときに用いている互換の個数はどちらも偶数で変わってないですよね．これは簡単な例ですが，そういうことが起きているわけです．

この置換の符号，という概念は行列式を定義するうえでとても大事なものです．

演習問題

9.1　次の置換の積を計算せよ．そしてそれをサイクル表示せよ．さらに，それを互換の積のみで表せ．
\[(1)\;\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5 \\
3 & 1 & 5 &2 & 4
\end{array}\right)\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5 \\
1 & 4 & 2 &5 & 3
\end{array}\right)\]\[(2)\;\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5 \\
5 & 3 & 2 & 1 & 4
\end{array}\right)\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5 \\
4 & 3 & 2 &5 & 1
\end{array}\right)\left(\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5 \\
1 & 4 & 2 & 5 & 3
\end{array}\right)\]\[(3)\; (1\; 3)(2\; 3)(5\; 4)(6\; 2)\in\mathfrak{S}_6\]

9.2 $2$以上の自然数$n$に対して，$(1\;2\;…\;n)=(1\;2)(2\;3)\cdots(n-1\;n)$を示せ．

9.3 (1) $f:\mathfrak{S}_n \longrightarrow \mathfrak{S}_n$を$f(\sigma)=\sigma^{-1}$で定義する．このとき，$f$が全単射であることを示せ．
(2) $g:\mathfrak{S}_n \longrightarrow \mathfrak{S}_n$を$g(\sigma)=\tau\sigma$で定義する．このとき，$g$が全単射であることを示せ．$g'(\sigma)=\sigma\tau$としても$g’$は全単射です．
この結果は後々使います．