用户: Kokic/置换分解的构造证明

1置换分解的构造证明

命题 1.1. 所有的置换都可被 $2$-置换生成.

我们在这里给出一个借用了冒泡排序算法实现的证明 (因此这是构造性的). 固定列表 $X$, 对任意 $X$ 的置换 $\sigma$ 和置换后的列表 $Y$, 我们将说明 $\sigma$ 可以写成一系列 $2$-置换 [1.2] 之积.

证明. (1) 对 $X$ 做冒泡排序得到 $Z$, 记录排序中的交换过程 ${\sigma }_{X_i}$. (2) 对 $Y$ 做冒泡排序得到 $Z$, 记录排序中的交换过程 ${\sigma }_{Y_j}$. (3) 那么现在就有 $X⟶Z⟵Y$, 将后一个箭头反向, 这样 ${\prod }_j{\sigma }_{Y_j}^{-1}{\prod }_i{\sigma }_{X_i}$ 就给出 $X⟶Y$, 即 $\sigma$.

$\square$

注 1.2. 即对换.

我们还可以写得更 " 显而易见 " 一些, 尽管这会损失一些构造上的直观.

证明. 冒泡排序使用若干次对换将 $X$, $Y$ 打到 $Z$, 把这两个映射记为 ${\sigma }_X,{\sigma }_Y$. 换言之, ${\sigma }_{\square }$ 实际上是以对换为元素的列表, 反转列表即可构造出 ${\sigma }_{\square }^{-1}$. 现在写下 ${\sigma }_Y^{-1}{\sigma }_X$, 这当然就是 $\sigma$.

亦或以下图概之

$\square$