2016年6月28日

日記

昨日の置換の実装の話の続き。

話を具体的にするために、次の2つの置換を定義しておく:

  { \displaystyle\begin{align*}
  \sigma &= \begin{pmatrix} 0 & 1 & 2 & 3 \\ 1 & 3 & 2 & 0 \end{pmatrix} &
  \tau &= \begin{pmatrix} 0 & 1 & 2 & 3 \\ 0 & 2 & 1 & 3 \end{pmatrix}
\end{align*}}

これらは整数を整数に写す写像と見なせて、 { \sigma(0) = 1,\,\sigma(1) = 3 } などができるとする。 2つの置換の合成  { \upsilon = \tau\sigma } は、整数を整数に写す写像とみなした関数合成ができるとして

  { \displaystyle\begin{align*}
  \upsilon
    &= \tau\sigma \\
    &= \begin{pmatrix} 0 & 1 & 2 & 3 \\ 0 & 2 & 1 & 3 \end{pmatrix}
      \begin{pmatrix} 0 & 1 & 2 & 3 \\ 1 & 3 & 2 & 0 \end{pmatrix}  \\
    &= \begin{pmatrix} 1 & 3 & 2 & 0 \\ 2 & 3 & 1 & 0 \end{pmatrix}
      \begin{pmatrix} 0 & 1 & 2 & 3 \\ 1 & 3 & 2 & 0 \end{pmatrix}  \\
    &= \begin{pmatrix} 0 & 1 & 2 & 3 \\ 2 & 3 & 1 & 0 \end{pmatrix}
\end{align*}}

さて、順序付きの列  { \textbf{x} = (x_0, x_1, x_2, x_3) } に対して、置換  { \sigma } の作用を

  { \displaystyle\begin{align*}
  \sigma \textbf{x} &= (x_{\sigma(0)}, x_{\sigma(1)}, x_{\sigma(2)}, x_{\sigma(3)}) \\
    &= (x_1, x_3, x_2, x_0)
\end{align*}}

となるように定める。 このとき、置換の合成がうまく定義できるためには

  { \displaystyle\begin{align*}
  (\tau\sigma)\textbf{x} = \tau(\sigma(\textbf{x}))
\end{align*}}

が成り立ってないといけない。 両辺をそれぞれ計算してみると

  { \displaystyle\begin{align*}
  (l.h.s)
    &= \upsilon \textbf{x} \\
    &= (x_{\upsilon(0)}, x_{\upsilon(1)}, x_{\upsilon(2)}, x_{\upsilon(3)}) \\
    &= (x_2, x_3, x_1, x_0) \\[2mm]
  (r.h.s)
    &= \tau (\sigma \textbf(x)) \\
    &= \tau  (x_1, x_3, x_2, x_0) \\
    &= (x_{\tau(1)}, x_{\tau(3)}, x_{\tau(2)}, x_{\tau(0)}) \\
    &= (x_2, x_3, x_1, x_0)
\end{align*}}

となって、問題なく両辺が等しくなる気がする。 ただ、ちょっと微妙なのは右辺の計算の2行目から3行目への変形

  { \displaystyle\begin{align*}
 \tau  (x_1, x_3, x_2, x_0) 
    &= (x_{\tau(1)}, x_{\tau(3)}, x_{\tau(2)}, x_{\tau(0)})
\end{align*}}

の箇所で、これは当然ながら

  { \displaystyle\begin{align*}
 \tau  (x_0, x_1, x_2, x_3) 
    &= (x_{\tau(0)}, x_{\tau(1)}, x_{\tau(2)}, x_{\tau(3)}) \\
    &= (x_0, x_2, x_1, x_3) \\
\end{align*}}

とは結果が異なる。 つまり、置換の合成が上手く定義できるためには、並べられている要素がどんな順序で並べられているかを知っていないといけない、もしくは自然な順序が定義されていないといけないことになる。 なので、例えば

  { \displaystyle\begin{align*}
  (\clubsuit, \diamondsuit, \heartsuit, \spadesuit)
\end{align*}}

 { \tau } を作用させようとしても、  { (\heartsuit, \spadesuit, \diamondsuit, \clubsuit) } になるのか  { (\clubsuit, \heartsuit, \diamondsuit, \spadesuit) } になるのか、もっと他のものになるのか分からないのでうまく定義できない。

ところで、置換の解釈を少し変えて、 { \sigma(0) = 1 } を「0の位置にあるものを1の位置に移動する」、 { \sigma(1) = 3 } を「1の位置にあるものを3の位置に移動する」とみなすと、上記の合成が特に問題なく定義できる。 実際にやってみると

  { \displaystyle\begin{align*}
  \sigma (\clubsuit, \diamondsuit, \heartsuit, \spadesuit)
    &= (\spadesuit, \clubsuit, \heartsuit, \diamondsuit) \\
  \tau (\spadesuit, \clubsuit, \heartsuit, \diamondsuit)
    &= (\spadesuit, \heartsuit, \clubsuit, \diamondsuit) \\[2mm]
  (\tau\sigma) (\clubsuit, \diamondsuit, \heartsuit, \spadesuit)
    &= (\spadesuit, \heartsuit, \clubsuit, \diamondsuit)
\end{align*}}

となって結果が一致する。 ただ、問題は

  { \displaystyle\begin{align*}
  \sigma = \begin{pmatrix} 0 & 1 & 2 & 3 \\ 1 & 3 & 2 & 0 \end{pmatrix}
\end{align*}}

 { (0, 1, 2, 3) } に作用させても、2行目の数字の並び  { (1, 3, 2, 0) } にならず  { (3, 0, 2, 1) } になるところ。 これは、2行表現の置換で2行目を順番に並べた

  { \displaystyle\begin{align*}
  \sigma = \begin{pmatrix} 3 & 0 & 2 & 1 \\ 0 & 1 & 2 & 3 \end{pmatrix}
\end{align*}}

で1行目の数字の並び。 つまりは逆置換に当たるもの。 なので対応が真逆になるのね。

ツイート (ツイート数 22)