置换的奇偶性, 在数学中, 当x是一个至少有两个元素的有限集合时, x的置换, 即从x到x的双射, 可分为大小相同的两类, 奇置换与偶置换, 如果x固定了任何一个全序, x的一个置换σ, displaystyle, sigma, 的奇偶性可以定义为σ, displaystyle, sigma, 中反向对个数的奇偶性, 所谓反向对即x中二元组x, displaystyle, 使得x, displaystyle, 且σ, displaystyle, sigma, sigma, 这里σ, displaystyle, si. 在数学中 当X是一个至少有两个元素的有限集合时 X的置换 即从X到X的双射 可分为大小相同的两类 奇置换与偶置换 如果X固定了任何一个全序 X的一个置换s displaystyle sigma 的奇偶性可以定义为s displaystyle sigma 中反向对个数的奇偶性 所谓反向对即X中二元组x y displaystyle x y 使得x lt y displaystyle x lt y 且s x gt s y displaystyle sigma x gt sigma y 这里s x displaystyle sigma x 为置换s displaystyle sigma 中第x displaystyle x 位的元素 Permutations of 4 elementsOdd permutations have a green or orange background The numbers in the right column are the inversion numbers OEIS數列A034968 which have the same parity as the permutation 一个置换s displaystyle sigma 的符号 sign或signature 记作sgn s 如果s displaystyle sigma 是偶数则定义为 1 如果s displaystyle sigma 是奇数则定义为 1 符号定义了对称群Sn的交错特征 置换的符号另一个更一般的符号为列维 奇维塔符号 ϵ s displaystyle epsilon sigma 定义在X到X的所有映射上 而在非双射映射上取值为0 置换的符号可以清晰地表达为 sgn s 1 N s displaystyle operatorname sgn sigma 1 N sigma 这里N s displaystyle N sigma 是s displaystyle sigma 中反向对的个数 或者 置换s displaystyle sigma 的符号也可通过对换分解定义为 sgn s 1 m displaystyle operatorname sgn sigma 1 m 这里m是分解中对换的个数 尽管这样一个分解不是惟一的 所有分解中对换个数的奇偶性是相同的 蕴含着置换的符号是良定义的 目录 1 例子 2 性质 3 两个定义的等价性 3 1 证明一 3 2 证明二 3 3 证明三 4 相关条目例子 编辑考虑集合 1 2 3 4 5 的置换s 它将初始排列12345变为34521 可以通过三个对换得到 首先交换1和3的位置 然后交换2和4 最后交换1和5 这证明了给定的置换s是奇的 利用置换一文中的记号 我们可写成 s 1 2 3 4 5 3 4 5 2 1 1 3 5 2 4 1 5 2 4 1 3 displaystyle sigma begin pmatrix 1 amp 2 amp 3 amp 4 amp 5 3 amp 4 amp 5 amp 2 amp 1 end pmatrix begin pmatrix 1 amp 3 amp 5 end pmatrix begin pmatrix 2 amp 4 end pmatrix begin pmatrix 1 amp 5 end pmatrix begin pmatrix 2 amp 4 end pmatrix begin pmatrix 1 amp 3 end pmatrix nbsp 有无穷种方式将s写成换位的复合 例如 s 23 12 24 35 45 displaystyle sigma 23 12 24 35 45 nbsp 但是不可能将其写为偶数个换位的复合 性质 编辑恒同置换是偶置换 一个偶置换可以由恒同置换通过偶数次两个元素互换 称为对换 得到 而一个奇置换可由奇数次对换得到 由整数加法相应的法则马上得到下列性质 两个偶置换的复合是偶的 两个奇置换的复合是偶的 一个奇置换与偶置换的复合是奇的由此得到 任何偶置换的逆是偶的 任何奇置换的逆是奇的考虑集合 1 n 的所有置换之对称群Sn 我们可总结为映射 sgn S n 1 1 displaystyle operatorname sgn S n to 1 1 nbsp 将每个置换映为其符号是一个群同态 进一步 我们见到偶置换组成Sn的一个子群 这就是n个字母上的交错群 记作An 它是符号同态的核 奇置换不能组成一个子群 因为两个奇置换的复合是偶置换 但它们是An 在Sn中 的一个陪集 如果n gt 1 则Sn中偶置换与奇置换一样多 从而An包含n 2个置换 原因 如果s是偶的 则 12 s是奇的 如果s是奇的 则 12 s是偶的 这两个映射互逆 一个轮换是偶的当且仅当它的长度是奇的 这得自如下类似公式 a b c d e a e b e c e d e 特别地 为了确定给定的置换是偶的还是奇的 将它写成不交轮换的乘积 这个置换是奇的当且仅当这个分解包含奇数个偶长度的轮换 每个奇数阶置换必须是偶的 反之一般不成立 两个定义的等价性 编辑证明一 编辑 任意置换可以由一列对换产生 对第一个对换我们将置换的第一个元素放到它恰当的位置 第二个对换放第二个元素 等等 给定一个置换s 我们可用无数种方式将其写成对换之积 我们要证明所有这样一个分解 要么都有偶数个对换 要么有奇数个对换 假设我们有两个这样的分解 s T 1 T 2 T k s Q 1 Q 2 Q m 我们要证明k 与m 要么都是偶的 要么都是奇的 每个对换可以写成奇数个相邻元素的对换之乘积 例如 2 5 2 3 3 4 4 5 4 3 3 2 如果我们将上面的T 1 T k 与Q 1 Q m 中每个对换作这样的分解 我们得到一个新的分解 s T1 T2 Tk s Q1 Q2 Qm这里所有T1 Tk Q1 Qk是相邻对换 k k 是偶数 m m 是偶数 现在将T1的逆与s复合 T1是两个相邻数 i i 1 的对换 所以与s相比 新置换s i i 1 恰好少一个 若 i i 1 是s的反向对 或多一个反向对 若 i i 1 不是s的反向对 然后以相同的方法应用到T2 T3 Tk的逆 消解 了置换s 最后我们得到了恒同置换 它的N是零 这意味着首先的N s 减去k是偶数 对另一个置换Q1 Qm我们对同样的事情 从而首先的N s 减去m是偶数这样m k是偶数 这就是我们要证明的 现在我们可以定义置换s是偶的 如果N s 是偶数 是奇的 如果N s 是奇数 这与首先给出的定义相同 但现在清晰地看到每个置换不是偶的就是奇的 证明二 编辑 另一个证明利用多项式 P x 1 x n i lt j x i x j displaystyle P x 1 ldots x n prod i lt j x i x j nbsp 例如在n 3的情形 我们有 P x 1 x 2 x 3 x 1 x 2 x 2 x 3 x 1 x 3 displaystyle P x 1 x 2 x 3 x 1 x 2 x 2 x 3 x 1 x 3 nbsp 现在对 1 n 的一个给定置换s 我们定义 sgn s P x s 1 x s n P x 1 x n displaystyle operatorname sgn sigma frac P x sigma 1 ldots x sigma n P x 1 ldots x n nbsp 因为多项式P x s 1 x s n displaystyle P x sigma 1 dots x sigma n nbsp 与P x 1 x n displaystyle P x 1 dots x n nbsp 除了符号之外它们的因子相同 从而sgn s 不是 1就是 1 从而如果s与t是两个置换 我们有 sgn s t P x s t 1 x s t n P x 1 x n displaystyle operatorname sgn sigma tau frac P x sigma tau 1 ldots x sigma tau n P x 1 ldots x n nbsp P x s 1 x s n P x 1 x n P x s t 1 x s t n P x s 1 x s n displaystyle frac P x sigma 1 ldots x sigma n P x 1 ldots x n cdot frac P x sigma tau 1 ldots x sigma tau n P x sigma 1 ldots x sigma n nbsp dd dd dd sgn s sgn t displaystyle operatorname sgn sigma cdot operatorname sgn tau nbsp dd dd dd 有此定义之后 显然任何两个相邻元素的对换有符号 1 这样我们事实上重新得到了早先定义的符号 证明三 编辑 第三个证明利用群Sn一个呈示 使用生成元为t 1 t n 1 displaystyle tau 1 dots tau n 1 nbsp 关系为 t i 2 1 displaystyle tau i 2 1 nbsp 对所有i t i t i 1 t i t i 1 t i t i 1 displaystyle tau i tau i 1 tau i tau i 1 tau i tau i 1 nbsp 对所有i lt n 1 t i t j t j t i displaystyle tau i tau j tau j tau i nbsp 如果 i j 2 这里生成元t i displaystyle tau i nbsp 表示对换 i i 1 所有的关系将一个词的长度保持或改变2 从一个偶数长词开始使用这些关系后总得到偶数长词 对奇数长词也类似 从而可以毫无歧义地称Sn中由偶数长词表示的元素是偶的 由奇数长词表示的元素是奇的 相关条目 编辑魔方的每一步的转动都是偶置换 故盲拧有时会出现奇偶校验的情况 数字推盘游戏是一个经典应用 事实上它涉及一个群胚 佐洛塔列夫引理 Zolotarev s lemma 取自 https zh wikipedia org w index php title 置换的奇偶性 amp oldid 54252446, 维基百科,wiki,书籍,书籍,图书馆,