问题求解4-3 置换群与拉格朗日定理

分类:Problem Solving, 发布于:2019-03-09 15:13:00, 更新于:2019-04-19 00:09:40。 评论

5.1 定义和记号

In general, the permutations of a set $X$ form a group $S_X$. If $X$ is a finite set, we can assume $X = \{1, 2, \dots, n\}$. In this case we write $S_n$ instead of $S_X$. The following theorem says that $S_n$ is a group. We call this group the symmetric group on $n$ letters.

Theorem 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.

A subgroup of $S_n$ is called a permutation group.

A permutation $\sigma \in S_X$ is a cycle of length $k$ if there exist elements $a_1, a_2, \dots, a_k \in X$ such that $$ \sigma(a_1)=a_2, \sigma(a_2)=a_3, \dots, \sigma(a_k)=a_1$$ and $\sigma(x) = x$ for all other elements $x \in X$. We will write $(a_1, a_2, \dots, 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, \dots, a_k)$ and $\tau = (b_1, b_2, \dots, b_l)$ are disjoint if $a_i \neq b_j$ for all $i$ and $j$.

Proposition 5.8. Let $\sigma$and $\tau$ be two disjoint cycles in $S_X$. Then $\sigma\tau = \tau\sigma$.

Theorem 5.9. Every permutation in $S_n$ can be written as the product of disjoint cycles.

The simplest permutation is a cycle of length 2. Such cycles are called transpositions.

Proposition 5.12. Any permutation of a finite set containing at least two elements can be written as the product of transpositions.

Lemma 5.14. If the identity is written as the product of $r$ transpositions, $$id = \tau_1 \tau_2 \dots \tau_r,$$ then $r$ is an even number.

Theorem 5.15. If a permutation $\sigma$ can be expressed as the product of an even number of transpositions, then any other product of transpositions equaling $\sigma$ must also contain an even number of transpositions. Similarly, if $\sigma$ can be expressed as the product of an odd number of transpositions, then any other product of transpositions equaling $\sigma$ must also contain an odd number of transpositions.

One of the most important subgroups of $S_n$ is the set of all even permutations, $A_n$. The group $A_n$ is called the alternating group on $n$ letters.

Theorem 5.16. The set $A_n$ is a subgroup of $S_n$.

Proposition 5.17. The number of even permutations in $S_n$, $n \geqslant 2$, is equal to the number of odd permutations; hence, the order of $A_n$ is $n!/2$.

5.2 二面体群

For $n = 3, 4, \dots$, we define the $n$th dihedral group to be the group of rigid motions of a regular $n$-gon. We will denote this group by $D_n$.

Theorem 5.20. The dihedral group, $D_n$, is a subgroup of $S_n$ of order $2n$.

Theorem 5.23. The group $D_n$, $n \geqslant 3$, consists of all products of the two elements $r$ and $s$, satisfying the relations $$r^n=1, s^2=1, srs=r^{-1}.$$

Proposition 5.27. The group of rigid motions of a cube contains $24$ elements.

Theorem 5.28. The group of rigid motions of a cube is $S_4$.

6.1 陪集

Let $G$ be a group and $H$ a subgroup of $G$. Define a left coset of $H$ with representative $g \in G$ to be the set $$gH = \{gh : h \in H\}$$ Right cosets can be defined similarly by $$Hg = \{hg : h \in H\}$$

Lemma 6.3. Let $H$ be a subgroup of a group $G$ and suppose that $g_1, g_2 \in G$. The following conditions are equivalent.

  1. $g_1H = g_2H$;
  2. $Hg_1^{-1} = Hg_2^{-1}$;
  3. $g_1H \subset g_2H$;
  4. $g2 \in g1H$;
  5. $g_1^{-1}g_2 \in H$.

Theorem 6.4. Let $H$ be a subgroup of a group $G$. Then the left cosets of $H$ in $G$ partition $G$. That is, the group $G$ is the disjoint union of the left cosets of $H$ in $G$.

Let $G$ be a group and $H$ be a subgroup of $G$. Define the index of $H$ in $G$ to be the number of left cosets of $H$ in $G$. We will denote the index by $[G : H]$.

Theorem 6.8. Let $H$ be a subgroup of a group $G$. The number of left cosets of $H$ in $G$ is the same as the number of right cosets of $H$ in $G$.

6.2 拉格朗日定理

Proposition 6.9. Let $H$ be a subgroup of $G$ with $g \in G$ and define a map $\phi: H \rightarrow gH$ by $\phi(h) = gh$. The map $\phi$ is bijective; hence, the number of elements in $H$ is the same as the number of elements in $gH$.

Theorem 6.10 Lagrange. 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$.

The converse of Lagrange’s Theorem is false.

Corollary 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$.

Corollary 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.

Corollary 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].$$

Proposition 6.15. The group $A_4$ has no subgroup of order $6$.

Theorem 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}$.

6.3 费马与欧拉定理

The Euler $\phi$-function is the map $\phi : \mathbb{N} \rightarrow \mathbb{N}$ defined by $\phi(n) = 1$ for $n = 1$, and, for $n > 1$, $\phi(n)$ is the number of positive integers $m$ with $1 \leqslant m < n$ and $\gcd(m,n) = 1$.

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

Theorem 6.18 Euler’s Theorem. Let $a$ and $n$ be integers such that $n > 0$ and $\gcd(a,n) = 1$. Then $a^{\phi(n)} \equiv 1 \mod n$.

Theorem 6.19 Fermat’s Little Theorem. Let $p$ be any prime number and suppose that $p \nmid a$ ($p$ does not divide $a$). Then $$a^{p-1} \equiv 1 \mod p.$$ Furthermore, for any integer $b$, $b^p \equiv b \mod p$.

评论