フィボナッチ・フリーク

数学の小ネタ集。

あるサイズの巡回置換だけで任意の置換を作る

組み合わせ論

任意の置換は互換の積に表すことができます。では同じように、3元の巡回置換 $(i~j~k)$ （ $i,j,k$ は相異なる）だけを組み合わせて任意の置換を作ることはできるでしょうか？

答えはNoです。 $(i~j~k)=(i~k)(i~j)$ （置換は右から合成する）と書けるので、3元の巡回置換は偶置換です。偶置換の積は偶置換なので、この方法では偶置換しか作ることができません。

しかし、実は3元の巡回置換を使えば全ての偶置換を作ることができます。すなわち、 $S_n$ を $n$ 次の対称群、 $A_n$ を交代群とし、 $k$ 元の巡回置換で生成される $S_n$ の部分群を $T^{(k)}_n$ とすると、次が成り立ちます。

命題1. $~T^{(3)}_n=A_n.$

証明. 交わる2つの互換の積は3元の巡回置換に他ならず、交わらない2つの互換の積は $(i~j)(k~l)=(i~j~k)(j~k~l)$ なので、2つの互換の積は必ず $T^{(3)}_n$ に入る。 $A_n$ はこれらで生成されるから $A_n\subset T^{(3)}_n$ である。逆の包含は3元の巡回置換が偶置換であることから明らか。 $~~~\square$

実はより一般に次が成り立ちます。

命題2. $~k$ が奇数のとき $T^{(k)}_n=A_n.$

証明. 命題1より、任意の $k\geq 5$ について $(3~4~5)\in T^{(k)}_n$ を示せばよい（すると対称性から任意の3元の巡回置換を含む）。

$(k~(k-1)~\cdots~1)^2(1~2~4~3~5~6~~\cdots~k)^2=(1~2)(3~4)$

より $(1~2)(3~4)\in T^{(k)}_n$ であり、同様に $(1~2)(3~5)\in T^{(k)}_n$ なので $(3~4~5)=(1~2)(3~5)(1~2)(3~4)\in T^{(k)}_n$ となる。 $~~~\square$

では $k$ が偶数のときはどうなるでしょうか。

この場合、なんと任意の置換を作ることができます！以下の証明は箱(@o_ccah)さんから教えていただきました。

命題3. $~k$ が偶数のとき $T^{(k)}_n=S_n.$

証明. $k=2m$ とする。 $(1~2)\in T^{(k)}_n$ を示せばよい。

$\sigma = (2~4~6~\cdots~2m~1~3~5~\cdots~(2m-1))\\ \tau=(1~2~\cdots~2m)$

と置く。 $\tau^2\sigma^{-1}=(1~2)$ なので示された。 $~~~\square$

このように、あるタイプの置換で生成される置換の全体を求めることは、しばしば面白いパズルになります。皆さんも是非オリジナルの置換パズルを考えてみてください。