My note when previewing Copying the Textbook of abstract algebra.

Chapter 5: Permutation Groups

Definitions and Notation

Symmetric Group

  • Symmetric Group on n letters 对称群

    $S_X=S_n$ is the permutation of a set $X=\{1,2,\cdots,n\}$

  • 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.
    It is not necessarily commutative

    Proof:

    1. Identity: $\forall x\in X, x\to x$
    2. Associative: map composition is associative
    3. Inverse: $f^{-1}$ exists since $f$ is one-to-one and onto
    4. Size: number of permutations is $n!$
  • Permutation Group

    A subgroup of $S_n$

Cycle Notation

  • Cycle of Length $k$ 轮换

    A permutation $\sigma\in S_X$
    There exists elements $a_1$, $a_2$, $\cdots$, $a_k\in X$ such that
    $\sigma(a_1)=a_2$, $\sigma(a_2)=a_3$, $\cdots$, $\sigma(a_k)=a_1$
    $\{a_1,a_2,\cdots,a_k\}$ denotes the cycle $\sigma$
    Not every permutation is a cycle.

  • Disjoint Cycle

    $\forall i,j,\ a_i\ne b_j$

  • Proposition 5.8

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

    Proof:

    1. $x$ is neither in $\{a_1,a_2,\cdots,a_k\}$ nor $\{b_1,b_2,\cdots,b_l\}$
      $\sigma(x)=\tau(x)=x\Rightarrow\sigma\tau(x)=\tau\sigma(x)=x$
    2. $x$ in $\{a_1,a_2,\cdots,a_k\}$
      Then $x$ is not in $\{b_1,b_2,\cdots,b_l\}$
      Because they are disjoint, $\sigma(x)\notin\{b_1,b_2,\cdots,b_l\}$
      Then $\sigma\tau(x) = \sigma(x)$, and $\tau\sigma(x) = \tau(\sigma(x))=\sigma(x)$
    3. $\sigma\tau=\tau\sigma$

  • Theorem 5.9

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

    Proof: 咕咕咕

Transpositions

  • Transpositions 对换

    Permutation which is a cycle of length 2

  • 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\cdots \tau_r$ then r is an even number.

    Proof: 咕咕咕

  • Theorem 5.15

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

    Proof:
    $\sigma=\sigma_1\sigma_2\cdots\sigma_m=\tau_1\tau_2\cdots\tau_n$
    $id=\sigma\sigma^{-1}=\sigma_1\sigma_2\cdots\sigma_m(\tau_1\tau_2\cdots\tau_n)^{-1}=\sigma_1\sigma_2\cdots\sigma_m\tau_1\tau_2\cdots\tau_n$
    Then $m+n$ must be even.
    So even+even or odd+odd

The Alternating Groups

  • The Alternation Group on $n$ Letters 交代群

    The set of all even permutations $A_n$

  • Theorem 5.16

    The set $A_n$ is a subgroup of $S_n$

    Proof

    1. The product of 2 even permutations is even
    2. The identity is even
    3. The inverse is even

  • Proposition 5.17

    The number of even permutations in $S_n$, $n\geq2$, is equal to the number of odd permutations.
    Hence, the order of $A_n$ is $n!/2$.

    Proof:
    Prove a bijection $\lambda_\sigma(\tau)=\sigma\tau$

Dihedral Groups

  • The n-th Dihedral Group 二面体群

    The group of rigid motions of a regular $n-gon$

  • 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\geq 3$, consists of all products of the two elements $r$ and $s$, satisfying the relations
    $$r^n=1$$
    $$s^2=1$$
    $$srs = r^{-1}$$

    Proof:
    $r$ is the rotation $r^k=k\frac{360\degree}{n}$, $1,r,r^2\cdots r^{n-1}$
    $s_i$ is the mirror. If $n$ is even, then there are $n/2$ $s_i$ for each pair of across vertices, and $n/2$ $s_i$ for each pair of across edges. If $n$ is odd, then there are $n$ $s_i$ for each vertex.

The Motion Group of a Cube

  • The across vertices of the cube is labeled the same number.
  • Proposition 5.24

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

Chapter 6: Cosets and Lagrange’s Theorem

Cosets

  • Left Coset of $H$ with Representative $g\in G$ 陪集

    $gH=\{gh:h\in H\}$

  • Right Coset of $H$

    $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. $g_2\in g_1H$
    5. $g_1^{-1}g_2\in H$

  • Theorem 6.4

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

    Proof:
    $g_1H\cap g_2H\ne\emptyset\Rightarrow\exists a=g_1h_1=g_2h_2\Rightarrow g_1=g_2h_2h_1^{-1}\Rightarrow g_1\subset g_2H$
    By Lemma 6.3, $g_1H=g_2H$

  • The Index of $H$ in $G$

    $[G:H]$ the number of left cosets of $H$ in $G$

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

    Proof:
    Find a bijective map $\phi:\mathcal {L}_H\to\mathcal {R}_H$, $\phi(gH)=Hg^{-1}$
    $Hg_1^{-1}=\phi(g_1H)=\phi(g_2H)=Hg_2^{-1}$
    By Lemma 6.3

Lagrange’s Theorem

  • Proposition 6.9

    Let $H$ be a subgroup of $G$ with $g \in G$ and define a map $\phi :H \to 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$.

    Proof: 咕咕咕

  • 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 is false.

    Proof:
    The group $G$ is partitioned into $[G : H]$ distinct left cosets. Each left coset has $|H|$ elements; therefore, $|G| = [G : H]|H|$.

  • 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 \ne e$ is a generator.

    Proof: 咕咕咕

  • 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]$$

    Proof:
    $$[G:K]=\frac{|G|}{|K|}=\frac{|G|}{|H|}\frac{|H|}{|K|}=[G:H][H:K]$$

  • Proposition 6.15

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

    Proof: 咕咕咕

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

    Proof: 咕咕咕

Fermat’s and Euler’s Theorems

  • The Euler $\phi$-Function

    the map $\phi: \mathbb{N}\to\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 ≤ m < n$ and $gcd(m,n) = 1$.
    $$\phi(n)=n\prod_{p|n\textrm{ and }p\textrm{ is prime}}(1-\frac{1}{p})$$
    一个因子一次，例如$8$只需计算一次$p=2$

  • 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)$.

    Proof:
    $|U(n)|=\phi(n)$ by Theorem 6.17
    $\forall a\in U(n), a^{\phi(n)}=1$
    $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)$$
    For any integer $b$, $b^p\equiv b(mod\ p)$