Mengzelev's Blog

问求学习笔记-置换群与拉格朗日定理

Word count: 1,124 / Reading time: 6 min
2019/03/09 Share

置换群(Permutation Group)

定理5.1:The symmetric group on $n$ letters, $S_n$, is a group with $n!$ elements, where
the binary operation is the composition of maps.

置换群(permutation group):所有排列的集合$S_n$的一个子集

Cycle Notation

A permutation $\sigma\in S_X$ is a cycle of length $k$ if there exist elements $a_1,a_2,…a_k\in X$ such that
$$\sigma(a_1) = a_2$$
$$\sigma(a_2) = a_3$$
$$…$$
$$\sigma(a_k) = a_1$$
and $\sigma(x)=x$ for all other elements $x\in X$.

We write $(a_1,a_2,…a_k)$ to denote the cycle $\sigma$.

Cycles are the building blocks of all permutations.循环是所有排列的基石。

Two cycles in $S_X$, $\sigma=(a_1,a_2,…a_k)$, $\tau=(b_1,b_2,…b_l)$, are disjoint if $a_i\neq b_j$ for all $i$ and $j$

命题5.8: Let $\sigma$ and $\tau$ be 2 disjoint cycles in $S_X$. Then $\sigma\tau=\tau\sigma$.

定理5.9: $S_n$中的所有排列都可以被写成不相交循环的乘积的形式。

Transpositions: a cycle of length 2 (任意两个数交换位置)

命题5.12: 任意至少含有两个元素的有限集的排列都可以写成transposition乘积的形式
e.g. (253)=(23)(25)

引理5.14: identity(恒等变换)只能写成偶数个transposition的乘积的形式

定理5.15: 如果一个排列能被写成偶数个置换乘积的形式,那么另一个与之等价的排列也一定拥有偶数项置换乘积。奇数同理。
据此定理可以将排列分为奇偶两类

交替组(The Alternating Groups)

交替组$A_n$是所有偶排列的集合

定理5.16: 集合$A_n$是$S_n$的子群

命题5.17: $S_n$中奇排列和欧排列的数目相等,都为$n!/2$

反组(Dihedral Groups)

the nth dihedral group($D_n$): the group of rigid motions of a regular n-gon(正多边形的刚性运动=转动+反射)

定理5.20: $D_n$ is a subgroup of $S_n$ of order $2n$

定理5.23: The group $D_n$, $n\ge 3$, consists of all products of the two elements $r$ and $s$, satisfying the relations
$$r^n=1$$
$$s^2=1$$
$$srs=r^{-1}$$
($r,s$分别为转动和反射)

$$D_n={1,r,r^2,..,r^{n-1},s,sr,sr^2,…,sr^{n-1}}$$

立方体的运动

命题5.27: The group of rigid motions of a cube contains 24 elements.

命题5.28: The group of rigid motions of a cube is $S_4$.(看体对角线)

陪集(Coset)

$G$为群,$H$为$G$的子群,定义
左陪集(left coset): $gH={gh:~h\in H}$
右陪集(left coset): $Hg={hg:~h\in H}$ (这真的不是汞吗)
其中$g\in G$称为代表元(representative)

在交换群中,左陪集与右陪集是相同的。

引理6.3: $g_1,g_2\in G$,以下条件等价:
$1. g_1H=g_2H$;
$2. Hg_1^{-1}=Hg_2^{-1}$;
$3. g_1H\subset g_2H$;
$4. g_2\in g_1H$;
$5. g_1^{-1}g_2\in H$;

定理6.4: $H$为$G$的子群。$H$的左陪集分割(partition)了$G$,即$G$是$H$的左陪集的disjoint union. (右陪集同理)

index of $H$: the number of left cosets of $H$ in $G$. 表示为$[G:H]$

定理6.8: $H$在$G$中的左陪集与右陪集的个数相等。

拉格朗日定理

命题6.9: 定义映射$H\to gH$ by $\phi(h)=gh$. 该映射是双射,$H$中元素的个数等于$gH$中元素的个数。

定理6.10(拉格朗日定理): Let $G$ be a finite group and let $H$ be a subgroup of $G$. Then $|G|/|H|=[G:H]$ is the number of distinct left cosets of $H$ in $G$. In particular, the number of elements in $H$ must divide the number of elements in $G$.
$$|G|=[G:H]|H|$$

推论6.11: Suppose that $G$ is a finite group and $g\in G$. Then the order of $g$ must divide the number of elements in $G$.

推论6.12: Let $|G|=p$ with $p$ a prime number. Then $G$ is cyclic and any $g\in G$ such that $g\neq e$ is a generator. 含有质数个元素的群为循环群且任何非单位元的元素都是生成元。

推论6.13: Let $H$ and $K$ be subgroups of a finite group $G$ such that $G\supset H\supset K$. Then $[G:K]=[G:H][H:K]$.

拉格朗日定理的逆命题是不成立的

命题6.15: The group $A_4$ has no subgroup of order 6.

定理6.16: Two cycles $\tau$ and $\mu$ in $S_n$ have the same length if and only if there exists a $\sigma\in S_n$ such that $\mu=\sigma\tau\sigma^{-1}$.

费马与欧拉定理

欧拉函数$\phi(n)$表示$n$以内与$n$互质的数的个数
对任意质数$p$, $\phi(p)=p-1$

定理6.17: Let $U(n)$ be the group of units in $\mathbb{Z}_n$. Then $|U(n)|=\phi(n)$

怎么又是欧拉
定理6.18(欧拉定理): Let $a$ and $n$ be integers such that $n>0$ and $gcd(a,n)=1$. Then $a^{\phi(n)}\equiv 1\pmod n$

定理6.19(费马小定理): Let $p$ be any prime number and suppose that $p\nmid a$($p$ does not divide $a$). Then $a^{p-1}\equiv 1\pmod p$.
Furthermore, for any integer $b$, $b^p\equiv b\pmod p$.

CATALOG
  1. 1. 置换群(Permutation Group)
    1. 1.1. Cycle Notation
      1. 1.1.1. 交替组(The Alternating Groups)
  2. 2. 反组(Dihedral Groups)
    1. 2.1. 立方体的运动
  3. 3. 陪集(Coset)
  4. 4. 拉格朗日定理
  5. 5. 费马与欧拉定理