Scisys-Math
La

置換の分解（2）

任意の置換は互換の積として表すことができます。

導出方法は主に 22 つあり、前項とこの項では 11 つ目の方法（置換を巡回置換の積で表し、更に巡回置換を互換の積に分解する方法）について示します。

巡回置換の互換への分解

前項では、任意の置換が巡回置換の積として表せることを示しました（定理 3.1（置換と巡回置換））。

ここでは、任意の巡回置換が互換の積として表せることを示します。これらを合わせて、任意の置換が互換の積として表せることが示されるというわけです。

定理 3.2（巡回置換と互換）

任意の巡回置換は互換の積として表せる。


証明

巡回置換 σ=( i1  i2  ⋯  im )\sigma = (\, i_1 \; i_2 \; \cdots \; i_m \,) に対して、τ1=( i1  i2 ),  τ2=( i1  i3 ),  ⋯ ,  τm−1=( i1  im )\tau_{1} = (\, i_1 \; i_2 \,), \;\tau_{2} = (\, i_1 \; i_3 \,), \; \cdots, \; \tau_{m-1} = (\, i_1 \; i_m \,) のような互換を考える。これらの互換の積 τm−1 ⋯ τ1\tau_{m-1} \, \cdots \, \tau_{1} により、i1, i2, ⋯ , imi_1, \, i_2, \, \cdots, \, i_m はそれぞれ次のように移される。

τm−1  ⋯  τ1(i1)=τm−1  ⋯  τ2(i2)=i2τm−1  ⋯  τ1(i2)=τm−1  ⋯  τ2(i1)=τm−1  ⋯  τ3(i3)=i3    ⋮τm−1  ⋯  τ1(im−1)=τm−1  τm−2(im−1)=τm−1(i1)=imτm−1  ⋯  τ1(im)=τm−1(im)=i1 \begin{split} \tau_{m-1} \; \cdots \; \tau_{1} (i_1) &= \tau_{m-1} \; \cdots \; \tau_{2} (i_2) \\ &= i_2 \\ \tau_{m-1} \; \cdots \; \tau_{1} (i_2) &= \tau_{m-1} \; \cdots \; \tau_{2} (i_1) \\ &= \tau_{m-1} \; \cdots \; \tau_{3} (i_3) \\ &= i_3 \\ & \; \; \vdots \\ \tau_{m-1} \; \cdots \; \tau_{1} (i_{m-1}) &= \tau_{m-1} \; \tau_{m-2} (i_{m-1}) \\ &= \tau_{m-1} (i_{1}) \\ &= i_m \\ \tau_{m-1} \; \cdots \; \tau_{1} (i_{m}) &= \tau_{m-1} (i_{m}) \\ &= i_1 \\ \end{split}

すなわち、任意の i∈{i1, ⋯ , im}i \in \{ i_1, \, \cdots, \, i_m \} について σ(i)=τm−1 ⋯ τ1(i)\sigma(i) = \tau_{m-1} \, \cdots \, \tau_{1} (i) が成り立つ。このとき、巡回置換 σ\sigma は次のように互換の積として表すことができる。

( i1  i2  ⋯  im )=( i1  im ) ( i1  im−1 )  ⋯  ( i1  i3 ) ( i1  i2 ) \begin{equation} \tag{⋆\star} (\, i_1 \; i_2 \; \cdots \; i_m \,) = (\, i_1 \; i_m \,) \, (\, i_1 \; i_{m-1} \,) \; \cdots \; (\, i_1 \; i_3 \,) \, (\, i_1 \; i_2 \,) \end{equation}

したがって、任意の巡回置換は互換の積として表せる。□\quad \square

証明の考え方

巡回置換が（⋆\star）式のような具体的な互換の積の形で表せることを示します。

m=3m = 3 の場合など、長さの小さい巡回置換を互換の積として表す方法を考えて、これを一般化します。

巡回置換の分解（m=3m = 3 の場合）

  • 巡回置換 σ=( i1  i2  ⋯  im )\sigma = (\, i_1 \; i_2 \; \cdots \; i_m \,) は、i1→i2→i3→⋯→im→i1i_1 \rightarrow i_2 \rightarrow i_3 \rightarrow \cdots \rightarrow i_m \rightarrow i_1 のように、{ i1,i2,⋯ ,im }\{\, i_1, i_2, \cdots, i_m \,\} の元をそれぞれ 11 つ隣の元に移します。

  • いま、巡回置換が mm 個の元を持つとすると、mm 個の元を順次 11 つずつ隣に移していくためには、22 つの元を入替える操作を少なくとも (m−1)(m-1) 回繰り返す必要があると考えられます。

  • このことは、m=3m = 3 の場合などの小さい巡回置換について考えるとよくわかります。

    • m=3m = 3 として、巡回置換 σ=( i1  i2  i3 )\sigma = (\, i_1 \; i_2 \; i_3 \,) について考えると、σ\sigma により i1i_1 は i2i_2 に、i2i_2 は i3i_3 に、i3i_3 は i1i_1 に移ります。言い換えると、σ\sigma は次のように置換と同じです（巡回置換の定義）。

      ( i1  i2  i3 )=(i1i2i3i2i3i1) \begin{align*} (\, i_1 \; i_2 \; i_3 \,) = \begin{pmatrix} i_1 & i_2 & i_3 \\ i_2 & i_3 & i_1 \end{pmatrix} \end{align*}

    • この置換は、次のような 22 つの互換 τ1,τ2\tau_{1}, \tau_{2} の積により代替できます。すなわち、まず互換 τ1=( i1  i2 )\tau_{1} = (\, i_1 \; i_2 \,) により i1i_1 と i2i_2 を入れ替え、次に互換 τ2=( i1  i3 )\tau_{2} = (\, i_1 \; i_3 \,) により i1i_1 と i3i_3 を入れ替えます。この 22 つの操作により i1i_1 は i2i_2 に、i2i_2 は（まず i1i_1 に移った後）i3i_3 に、i3i_3 は i1i_1 に移ることが確かめられます。

      τ2  τ1(i1)=τ2(i2)=i2    ⋯    i1→i2τ2  τ1(i2)=τ2(i1)=i3    ⋯    i2→i1→i3τ2  τ1(i3)=τ2(i3)=i1    ⋯    i3→i1 \begin{align*} \tau_{2} \; \tau_{1} (i_1) = \tau_{2} (i_2) = i_2 & \; \; \cdots \; \; i_1 \to i_2 \\ \tau_{2} \; \tau_{1} (i_2) = \tau_{2} (i_1) = i_3 & \; \; \cdots \; \; i_2 \to i_1 \to i_3 \\ \tau_{2} \; \tau_{1} (i_3) = \tau_{2} (i_3) = i_1 & \; \; \cdots \; \; i_3 \to i_1 \\ \end{align*}

    • したがって、巡回置換 ( i1  i2  i3 )(\, i_1 \; i_2 \; i_3 \,) と 22 つの互換の積 ( i1  i3 )( i1  i2 )(\, i_1 \; i_3 \,) (\, i_1 \; i_2 \,) は同じであることがわかります。

      ( i1  i2  i3 )=( i1  i3 )( i1  i2 ) (\, i_1 \; i_2 \; i_3 \,) = (\, i_1 \; i_3 \,) (\, i_1 \; i_2 \,)

  • 以上から、mm 個の要素の巡回置換は (m−1)(m-1) 個の互換の積として表すことができると考えられます。

巡回置換の分解（一般の場合）

  • 上記の考察から、長さ mm の巡回置換 σ=( i1  i2  ⋯  im )\sigma = (\, i_1 \; i_2 \; \cdots \; i_m \,) に相当する互換の積として ( i1  im ) ( i1  im−1 )  ⋯  ( i1  i3 ) ( i1  i2 )(\, i_1 \; i_m \,) \, (\, i_1 \; i_{m-1} \,) \; \cdots \; (\, i_1 \; i_3 \,) \, (\, i_1 \; i_2 \,) が考えられます。この互換の積による各要素の行き先が、巡回置換による行き先と一致していることを確かめます。
  • (m−1)(m-1) 個の互換を τ1=( i1  i2 ),  τ2=( i1  i3 ),  ⋯ ,  τm−1=( i1  im )\tau_{1} = (\, i_1 \; i_2 \,), \;\tau_{2} = (\, i_1 \; i_3 \,), \; \cdots, \; \tau_{m-1} = (\, i_1 \; i_m \,) として、互換の積による i1,  i2,  ⋯ ,  imi_1, \; i_2, \; \cdots, \; i_m の像（行き先）をみていきます。
互換の積による i1i_1 の像

  • 互換の積による像 τm−1  ⋯  τ1(i1)\tau_{m-1} \; \cdots \; \tau_{1} (i_1) を考えます。

    τm−1  ⋯  τ1(i1)=τm−1  ⋯  τ2(i2)=i2 \begin{split} \tau_{m-1} \; \cdots \; \tau_{1} (i_1) &= \tau_{m-1} \; \cdots \; \tau_{2} (i_2) \\ &= i_2 \\ \end{split}

    • まず、τ1\tau_{1} により i1i_1 は i2i_2 に移ります。
    • 次に、τm−1  ⋯  τ2(i2)\tau_{m-1} \; \cdots \; \tau_{2} (i_2) を考えますが、τm−1  ⋯  τ2\tau_{m-1} \; \cdots \; \tau_{2} に i2i_2 は登場しませんので、これらの互換により、i2i_2 はどこにも移りません。

  • よって、τm−1  ⋯  τ1(i1)=i2\tau_{m-1} \; \cdots \; \tau_{1} (i_1) = i_2 となります。これは σ(i1)=i2\sigma(i_1) = i_2 と一致します。

互換の積による i2i_2 の像

  • 同様に τm−1  ⋯  τ1(i2)\tau_{m-1} \; \cdots \; \tau_{1} (i_2) を考えます。

    τm−1  ⋯  τ1(i2)=τm−1  ⋯  τ2(i1)=τm−1  ⋯  τ3(i3)=i3 \begin{split} \tau_{m-1} \; \cdots \; \tau_{1} (i_2) &= \tau_{m-1} \; \cdots \; \tau_{2} (i_1) \\ &= \tau_{m-1} \; \cdots \; \tau_{3} (i_3) \\ &= i_3 \\ \end{split}

    • まず、τ1\tau_{1} により i2i_2 は i1i_1 に移ります。
    • 次に、τ2\tau_{2} により i1i_1 は i3i_3 に移ります。
    • さらに、τm−1  ⋯  τ3(i3)\tau_{m-1} \; \cdots \; \tau_{3} (i_3) を考えますが、τm−1  ⋯  τ3\tau_{m-1} \; \cdots \; \tau_{3} により i3i_3 はどこにも移りません。

  • よって、τm−1  ⋯  τ1(i2)=i3\tau_{m-1} \; \cdots \; \tau_{1} (i_2) = i_3 となります。これは σ(i2)=i3\sigma(i_2) = i_3 と一致します。

互換の積による i3∼im−2i_3 \sim i_{m-2} の像
  • i3,  i4,  ⋯i_3, \; i_4, \; \cdots についても、同様になると考えられます。
  • 最後に、im−1,  imi_{m-1}, \; i_{m} の場合について見てみます。
互換の積による im−1i_{m-1} の像

  • τm−1  ⋯  τ1(im−1)\tau_{m-1} \; \cdots \; \tau_{1} (i_{m-1}) を考えます。

    τm−1  ⋯  τ1(im−1)=τm−1  τm−2(im−1)=τm−1(i1)=im \begin{split} \tau_{m-1} \; \cdots \; \tau_{1} (i_{m-1}) &= \tau_{m-1} \; \tau_{m-2} (i_{m-1}) \\ &= \tau_{m-1} (i_{1}) \\ &= i_m \\ \end{split}

    • まず、τm−3  ⋯  τ1\tau_{m-3} \; \cdots \; \tau_{1} により im−1i_{m-1} はどこにも移りません。よって、τm−1  ⋯  τ1(im−1)=τm−1  τm−2(im−1)\tau_{m-1} \; \cdots \; \tau_{1} (i_{m-1}) = \tau_{m-1} \; \tau_{m-2} (i_{m-1}) となります。
    • 次に、τm−2\tau_{m-2} により im−1i_{m-1} は i1i_1 に移ります。さらに、τm−1\tau_{m-1} により i1i_1 は imi_m に移ります。

  • よって、τm−1  ⋯  τ1(im−1)=im\tau_{m-1} \; \cdots \; \tau_{1} (i_{m-1}) = i_m となります。これは σ(im−1)=im\sigma(i_{m-1}) = i_m と一致します。

互換の積による imi_{m} の像

  • τm−1  ⋯  τ1(im)\tau_{m-1} \; \cdots \; \tau_{1} (i_{m}) を考えます。

    τm−1  ⋯  τ1(im)=τm−1(im)=i1 \begin{split} \tau_{m-1} \; \cdots \; \tau_{1} (i_{m}) &= \tau_{m-1} (i_{m}) \\ &= i_1 \\ \end{split}

    • まず、τm−2  ⋯  τ1\tau_{m-2} \; \cdots \; \tau_{1} により imi_{m} はどこにも移りません。よって、τm−1  ⋯  τ1(im)=τm−1(im)\tau_{m-1} \; \cdots \; \tau_{1} (i_{m}) = \tau_{m-1} (i_{m}) となります。
    • 次に、τm−1\tau_{m-1} により imi_{m} は i1i_1 に移ります。

  • よって、τm−1  ⋯  τ1(im)=i1\tau_{m-1} \; \cdots \; \tau_{1} (i_{m}) = i_1 となります。これは σ(im)=i1\sigma(i_{m}) = i_1 と一致します。

互換の積による像（まとめ）

  • 以上から、任意の i∈{i1,  i2,  ⋯ ,  im}i \in \{ i_1, \; i_2, \; \cdots, \; i_m \} について σ(i)=τm−1  ⋯  τ1(i)\sigma(i) = \tau_{m-1} \; \cdots \; \tau_{1} (i) が成り立つことが確かめられました。
  • 巡回置換による行き先と（⋆\star）式の互換の積による行き先が一致していますので、巡回置換が互換の積として表せることが示されたといえます。

互換の積への分解は一意的ではない

実は、巡回置換 ( i1  i2  ⋯  im )(\, i_1 \; i_2 \; \cdots \; i_m \,) を互換の積として分解した形は、上記の証明に示した、次のような形だけではありません。

( i1  im ) ( i1  im−1 )  ⋯  ( i1  i3 ) ( i1  i2 ) (\, i_1 \; i_m \,) \, (\, i_1 \; i_{m-1} \,) \; \cdots \; (\, i_1 \; i_3 \,) \, (\, i_1 \; i_2 \,)

例えば、次のような互換の積も、上記の巡回置換 ( i1  i2  ⋯  im )(\, i_1 \; i_2 \; \cdots \; i_m \,) と同じ行き先を持ちます。（上記の証明と同様に計算により確かめられます。）

( im−1  im ) ( im−2  im )  ⋯  ( i2  im ) ( i1  im ) (\, i_{m-1} \; i_m \,) \, (\, i_{m-2} \; i_m \,) \; \cdots \; (\, i_2 \; i_m \,) \, (\, i_1 \; i_m \,)

また、ここで挙げた 22 つの互換の積は必要最小限である (m−1)(m-1) 個の互換の積ですが、もっと冗長な積の形は際限なく考えられます。

すなわち、任意の巡回置換は互換の積で表せるが、その表し方は一意的ではないといえます。

置換の分解の一意性

前項で示した通り、任意の置換が巡回置換の積として表すことができ、かつ、任意の巡回置換が互換の積として表せることが示されました。これらのことから、任意の置換が互換の積として表せることが示されたことになります。

また、任意の置換を巡回置換の積として表す方法は、積の順序を除いて一意的でしたが、巡回置換を互換の積として表す方法は一意的ではありません。結果として、任意の置換は互換の積で表せるが、その表し方は一意的ではないことが分かります。


まとめ

  • 任意の巡回置換は互換の積として表せる。
  • 巡回置換を互換の積として表す表し方は一意的ではない。

参考文献

[1] 齋藤正彦. 線型代数入門. 東京大学出版会. 1966.
[2] 永田雅宣 他. 理系のための線型代数の基礎. 紀伊國屋書店. 1986.
[3] 川久保勝夫. 線形代数学 [新装版]. 日本評論社. 2010.
[4] 松坂和夫. 線型代数入門 [新装版]. 岩波書店. 2018.
[5] 三宅敏恒. 線形代数学 初歩からジョルダン標準形へ. 培風館. 2008.
[6] S. Lang. Linear Algebra Third Edition. Springer. 1987.
[7] T. Miyake. Linear Algebra From the Beginnings to the Jordan Normal. Springer. 2022.
[8] 雪江明彦. 代数学 11 群論入門. 日本評論社. 2010.
[9] 雪江明彦. 代数学 22 環と体とガロア理論. 日本評論社. 2010.
[10] 桂利行. 代数学 I\text{I} 群と環. 東京大学出版会. 2004.
[11] 松坂和夫. 代数系入門. 岩波書店. 1976.
[12] 高木貞治. 代数学講義 [改訂新版]. 共立出版. 1965.
[13] S. Lang. Algebra Revised Third Edition. Springer. 2002.
[14] M. Artin. Algebra Second Edition. Pearson Education Limited. 2014.
[15] 青本和彦 他. 数学入門辞典. 岩波書店. 2005.


初版：2022-11-13   |   改訂：2024-10-29
Prev
置換の分解（1）
Next
置換の分解（3）