任意の置換を互換の積で表すことについて

たとえば
　　 (1 2 3 4 5 6 7 8 9) = (1 2 5 7 9)
　　 (2 5 3 4 7 6 9 8 1)
という置換は

　　 (1 2 3 4 5 6 7 8 9)(1 2)→(1 2 3 4 5 6 7 8 9)(1 5)→(1 2 3 4 5 6 7 8 9)
　　 (1 2 3 4 5 6 7 8 9)　　　 (2 1 3 4 5 6 7 8 9)　　　 (2 5 3 4 1 6 7 8 9)

　 →(1 2 3 4 5 6 7 8 9)(1 7)→(1 2 3 4 5 6 7 8 9)(1 9)→(1 2 3 4 5 6 7 8 9)
　　 (2 5 3 4 1 6 7 8 9)　　　 (2 5 3 4 7 6 1 8 9)　　　 (2 5 3 4 7 6 9 8 1)

　　∴(1 2 3 4 5 6 7 8 9) = (1 9)(1 7)(1 5)(1 2)
　　　(2 5 3 4 7 6 9 8 1)

となるので確かに
　　(　1　　　2　　…　　n　)
　　( σ(1) 　σ(2)　…　σ(n) )
も互換の積で表わせそうなのですが、具体的にはどのように証明すればいいのでしょう。

No.1 ベストアンサー 回答者： endlessriver 回答日時： 2022/11/07 22:46

https://math-note.xyz/linear-algebra/basics-of-l …

この回答へのお礼

すばやい回答まことにありがとうございました。

お礼日時：2022/11/07 23:10

No.2 回答者： stomachman 回答日時： 2022/11/07 23:08

(1,2,....,n)から(σ(1),σ(2),…,σ(n))に至る互換の列は、逆順にやれば(σ(1),σ(2),…,σ(n))から(1,2,....,n)に至るわけです。

なので、互換の列を逆順に作ればOK。それには：

while (σ(1),σ(2),…,σ(n)のうちσ(k)≠kであるkが存在する）
　　σ(k)≠kであるkを（どれでもいいから）ひとつ選ぶ。
　　k=σ(j)となるj をみつける。（そういうj が必ず存在して、j≠k）
　　列(σ(1),σ(2),…,σ(n))に対して互換(k,j)をやる。
　　その結果を、改めて(σ(1),σ(2),…,σ(n))とする。（∴σ(k)=kになっている）
end while

ということをやる。互換を1回やるごとに、「σ(1),σ(2),…,σ(n)のうちσ(k)=kであるk」の個数が少なくとも1個増えるから、高々n回の反復でこのループは終わる。終わった時にはどのkについてもσ(k)=k。

この回答へのお礼

BAを選んでから今確認しました。まことにありがとうございました。

お礼日時：2022/11/07 23:11