知识卡片

普通读书笔记卡 · 3729.c.3.a

仿射映射扩大置换族

理解等级:高级

GF(2)上满秩矩阵A使x↦Ax可逆且固定零点;加入c后,x↦Ax+c可移动零点,形成仿射置换。

  • n=1、2时它覆盖全部2ⁿ个元素的置换;
  • n≥3时才是所有置换的真子集,不能把题目中的计数目标逐n泛化。
这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 附录D 矩阵 · 查看原书依据

      We call any permutation that maps x ∈ Sn to Ax + c, for some n × n 0-1 matrix A with full rank and some n-bit vector c, a linear permutation. d. Use a counting argument to show that

    参考来源

    - 位置:《算法导论(第4版)》附录D《矩阵》(OEBPS/appendix004.xhtml,文本字符[15000,18442))。 - 结论依据:附录D问题D-2(c–e)给出仿射置换定义与计数任务。由满秩矩阵计数,n=1有2个、n=2有24个仿射置换,分别等于2!、4!;n≥3有不保仿射结构的置换,故为真子集。 - 原始内容:We call any permutation that maps x ∈ S n to Ax + c , for some n × n 0-1 matrix A with full rank and some n -bit vector c , a linear permutation . d. Use a counting argument to show that