知识卡片
仿射映射扩大置换族
GF(2)上满秩矩阵A使x↦Ax可逆且固定零点;加入c后,x↦Ax+c可移动零点,形成仿射置换。
- n=1、2时它覆盖全部2ⁿ个元素的置换;
- n≥3时才是所有置换的真子集,不能把题目中的计数目标逐n泛化。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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