离散数学ii（李占山）6.3置换群.ppt

6 3置换群 6 3 1置换的定义6 3 2置换的轮换表法6 3 3置换的顺向圈表示6 3 4置换的奇偶性 6 3 1置换的定义 定义 设M是一个非空的有限集合 M的一个一对一变换称为一个置换 设M a1 a2 an 则M的置换 可简记为 bi ai i 1 2 n结论 M的置换共有n 个 M上的置换称为n元置换 特别地 若 ai ai i 1 2 n 则 为n元恒等置换 Sn n 个置换作成的集合 置换的例 设M 1 2 3 则有3 6个3元置换 所有元素不动 1 一个元素不动 2 3 4 0个元素不动 5 6 故 S3 1 2 3 4 5 6 置换的乘法 对M中任意元素a及M的任意两个置换 规定 a a 例 设 则 满足结合律 Sn Sn中有单位元 n元恒等置换 设为 0 有 0 0 Sn每个n元置换在Sn中都有逆元素 置换的乘法的性质 n次对称群 n元置换的全体作成的集合Sn对置换的乘法作成一个群 称为n次对称群 n 1 M a S1 在置换的乘法作成1次对称群 为Abel群 n 2 M a b S2 在置换的乘法作成2次对称群 为Abel群 当n 3时 Sn不是交换群 轮换 设 是M的置换 若可取到M的元素a1 ar使 a1 a2 a2 a3 ar 1 ar ar a1 而 不变M的其余的元素 自己变换到本身 则 称为一个轮换 记为 a1a2 ar 6 3 2置换的轮换表法轮换的定义 例 134 341 413 M的两个轮换 a1 ar 和 b1 bs 说是不相杂或不相交 如果a1 ar和b1 bs都不相同 即 a1 ar b1 bs 不相杂轮换 不相杂轮换 结论 若 和 是M的两个不相杂的轮换 则 证明 设 a1 ar b1 bs 和 不相杂 命 为M的任意元若 a1 ar 设 ai 则 ai ai ai 1 ai ai 1 ai 1 i r时 ai 1应改为a1 故 不相杂轮换 同理可证 若 b1 bs 也有 设 a1 ar b1 bs 于是 综上 故 定理6 3 2任意置换 恰有一法写成不相杂的轮换乘积 即 任意置换 可以写成不相杂的轮换的乘积 可表性 如果不考虑乘积的顺序 则写法是唯一的 唯一性 不相杂轮换 证明 1 可表性 设 是M上置换 任取a1 M 若 a1 a1 则有轮换 a1 设 a1 a2 a2 a3 由于M有限 故到某一个元素ar ar 必然不能再是新的元素 即 ar a1 ar 由于 是一对一的 已有 ai ai 1 i 1 2 r 1 所以 ar 只能是a1 于是得到一个轮换 a1 ar 若M已经没有另外的元素 则 就等于这个轮换 否则设b1不在a1 ar之内 则同样作法又可得到一个轮换 b1 bs 因为a1 ar各自已有变到它的元素 所以b1 bs中不会有a1 ar出现 即这两个轮换不相杂 若M的元素已尽 则 就等于这两个轮换的乘积 否则如上又可得到一个轮换 如此类推 由于M有限 最后必得 a1 ar b1 bs c1 ct 1 即 表成了不相杂的轮换的乘积 证明 2 唯一性 设 又可表为不相杂的轮换的乘积如下 a 1 a r b 1 b s c 1 c t 2 考虑 1 式中任意轮换 a1 ar 不妨设a1 a 1 a r 且a1 a 于是 a2 a1 a 1 a 2 a3 a2 a 2 a 3 证明 证明可见 a1 ar 必和 a 1 a r 完全相同 这就是说 1 中的任意轮换必出现在 2 中 同样 2 中的任意轮换必出现在 1 中 因之 1 和 2 一样 最多排列的方法不同 但不相杂的轮换相乘适合交换律 所以排列的次序本来是可以任意颠倒的 例 设M 1 2 3 4 M的24个置换可写成 I 12 13 14 23 24 34 123 132 124 142 134 143 234 243 1234 1243 1324 1342 1423 1432 12 34 13 24 14 23 轮换的长度其中所含的元素个数 a1a2 ar 长度为r 对换长度为 的轮换 结论 任意轮换可以写成对换的乘积 a1a2 ar a1ar a1ar a1a3 a1a2 3 证明 对r进行归纳 当r 2时命题显然成立 假设r t时结论为真 考虑 a1a2 arat 1 的情况 令 1 a1at 1 2 a1a2 at 下面证明 1 2 对换 任取l S 若l a1 a2 at 1 不妨设l am 则 l am am 1 1 2 l 1 am 1 am 1 若l at 则 l at 1 1 a1 1 2 at 1 2 at 1 2 l 若l at 1 则 l at 1 a1 1 at 1 1 2 at 1 1 2 l 若l a1 a2 at 1 则 l l 1 l 1 2 l 1 2 l 即 1 2 a1at 1 2 由归纳假设 2 a1a2 at 可表为 a1at a1at 1 a1a2 所以 a1at 1 a1at a1at 1 a1a2 归纳法完成 有兴趣的同学可以采用直接证明的方法进行证明 推论 对任意置换 有一法 未必只有一法 可将其写成一些对换的乘积 12 13 13 23 13 23 先把置换表成不相杂轮换之乘积 然后用一组顺向圈来表示每个顺向圈的长度 即圈上所含的元素个数 就是该圈所表示的轮换的长度 一个n元置换对应一组顺向圈 这组圈的长度之总和为n 反之 一组顺向圈表示一置换 置换的元素个数就是组中各图长度之总和 6 3 3置换的顺向圈表示 1324 n元置换 对应图形表达式 图型 G 1z1 2z2 rzrzi表示长度为i的圈 而zi的系数 i表示如此的zi的个数 诸 为非负整数 0 1 n n 0或1 1 2 2 r r n 6 3 3置换的顺向圈表示 设 表为k个不相杂的轮换的乘积 包括长度为1的轮换在内 长度分别为r1 r2 rk 若 n k为奇数 偶数 则称 为奇置换 偶置换 例如 134 是偶置换是奇置换 6 3 4置换的奇偶性 因每个长度为r的轮换可写成r 1个对换的乘积 a1a2 ar a1ar a1ar a1a3 a1a2 于是 可写成 n k个对换的乘积 结论 奇置换可表为奇数个对换之积 偶置换可表为偶数个对换之积 定理6 3 3每个置换都能分解为对换的乘积 但偶置换只能分解为偶数个对换的乘积 奇置换只能分解为奇数个对换的乘积 证明 只需证明 只能分解 任取 Sn 设 等于k个轮换之积 这些轮换分别含r1 r2 rk个元素 于是 可以写成个对换之积 定义置换 的符号sgn 如下 sgn 显然 偶置换的符号为1 奇置换的符号为 1 首先证明sgn sgn sgn 4 设 等于k个不相杂轮换之积 等于h个不相杂轮换之积 且 写成对换乘积时最后一个对换为 ab 以 ab 乘 而看其变化 1 若a和b在 的两个不同的轮换之内 aa1 as bb1 bi 则 ab aa1 asbb1 bi 若 为h个不相杂轮换之积 则 ab 为 h 1 个不相杂轮换之积 故 sgn ab 1 n h 1 1 n h sgn 2 若a和b在 的同一个轮换之内 aa1 asbb1 bi 则 ab aa1 as bb1 bi 故 sgn ab 1 n h 1 1 n h sgn 补充证明 ab ab aa1 as bb1 bi 总之 以一个对换乘 则将sgn 变号 今 等于 n k 个对换之积 故以 乘 将sgn 变号 n k 次 即sgn 1 n ksgn sgn sgn 因此 和 的奇偶性与其乘积 的奇偶性之关系如下 偶 偶 偶 奇 奇 偶 奇 偶 奇 偶 奇 奇 因为对换是奇置换 所以只有奇数个对换之积是奇置换 偶数个对换之积是偶置换 定理6 3 4设M的元数为n 若n 1 则奇置换的个数和偶置换的个数相等 都等于 证明 命 1 2 m 5 为M的所有偶置换 由于n 1 故可取到一个对换 而作下列乘积 1 2 m 6 显然 i是奇置换 而且诸 i互不相同 即 6 中无重复元素 反证 若 i j 则以 1左乘得 i j 矛盾 这说明M的奇置换不少于偶置换 反之 若 为M的任意奇置换 则 1 为偶置换 故必等于某一个 i 1 i 因而 i 这说明M的任意奇置换必在 6 中 6 就是M的所有奇置换 M的奇置换不多于偶置换 于是奇置换的个数和偶置换的个数相等 各占置换总数n 的一半 定义 之奇偶性的整数 n k称为 的定性数 定理6 3 5设n元置换 有图型G 则 之定性数等于 证明 n 1 2 2 r r n nk 1 2 r nn k 2 r 1 r n 1 n 置换的定性数 例子 图1是一个2 2的方格图形 它可以围绕中心旋转 也可以围绕对称轴翻转 但要求经过这样的变动以后的图形要与原来的图形重合 方格中的数字可以改变 例如 当它绕中心逆时针旋转900以后 原来的数字1 2 3 4分别变为2 3 4和1 可以把这个变化看作是 1 2 3 4 上的图1一个置换 4321 下面给出所有可能的置换 1 1 绕中心顺时针转00 2 1234 绕中心顺时针转900 3 13 24 绕中心顺时针转1800 4 1432 绕中心顺时针转2700 5 12 34 绕垂直轴翻转1800 6 14 23 绕水平轴翻转1800 7 24 绕西北 东南轴翻转1800 8 13 绕西南 东北轴翻转1800 表1给出它们的运算表 令D4 1 2 8 易见D4关于置换的乘法是封闭的 1 1 是单位元 且 1 1 1 2 1 4 3 1 3 4 1 2 5 1 5 6 1 6 7 1 7 8 1 8 构成一个群 且是S4的子群 表1 例子 例设G a1 a2 an 为群 则G的运算表的每行每列