Problem Solving IV 01

My note when previewing Copying the Textbook of abstract algebra.

Chapter 3：Groups

Integer Equivalence Classes and Symmetries

The Integers mod n

• 模n和: addition modulo n: $(a+b)\%n$

• 模n积: multiplication modulo n: $(ab)\%n$

• Proposition 3.4
  Let $\mathbb{Z}_n$ be the set of equivalence classes of the integers mod $n$ and $a$, $b$, $c$ $\in$ $\mathbb{Z}_n$.

  1. communicative 交换律

     $a+b \equiv b+a\quad(mod\ n)$
     $a\times b \equiv b\times a\quad(mod\ n)$

  2. associative 结合律

     $(a+b)+c \equiv a+(b+c)\quad(mod\ n)$
     $(a\times b)\times c \equiv a\times (b\times c)\quad(mod\ n)$

  3. identities 特征值（0元素，数1

     $a+0 \equiv a\quad(mod\ n)$
     $a\times1\equiv a\quad(mod\ n)$

  4. distribution 分配律

     $a\times(b+c)\equiv ab+ac\quad(mod\ n)$

  5. inverse 相反数（负元素

     $a+(-a)\equiv0\quad(mod\ n)$

  6. multiplicative inverse 倒数

     $a\ne 0$ required.
     $gcd(a,n)=1\Leftrightarrow \exists b$, $a\times b \equiv 1\quad (mod\ n)$

Symmetries

• Permutation of a set:

• a one-to-one and onto map $\pi:S\to S$

• Symmetry of a geometric figure:

  a rearrangement of the figure preserving the arrangement of its sides and vertices as well as its distances and angles.
  边布局、点布局、长度和角度均不变， [布局] Arrangement 不考虑顶点标号的 [排列] Permutation

• Rigid Motion of an object：

  a map from the plane to itself preserving the symmetry.
  不造成形变，到自身的映射，相当于重新分配点的标号
  $A\to B, B\to C, A\to A$ is denoted as:
  $$\begin{pmatrix}A & B & C \\ B & C & A\end{pmatrix}$$

• Composing motion

  similar to composing functions/maps

Definitions and Examples

Definitions

• Binary operations or Law of Composition on a set $G$:

  $f:G\times G\to G$
  every $(a,b)\in G\times G$ is mapped to a unique element denoted as $a\circ b$ or $ab$
  双射

• Composition of 2 elements:

  $a\circ b$ or $ab$

• Group $(G,\circ)$

  a set $G$ together with a law of composition $(a,b)\mapsto a\circ b$ that satisfies the following 3 axioms:

  1. Associative
     $\forall a,b,c\in G$, $(a\circ b)\circ c=a\circ(b\circ c)$
  2. Identity Element
     $\forall a\in G$, $\exists e\in G$, $e\circ a=a\circ e=a$
  3. Inverse Element
     $\forall a\in G$, $\exists a^{-1}$ that $a\circ a^{-1}=a^{-1}\circ a=e$

• Abelian Group or Commutative Group

  a group $(G,\circ )$ that $\forall a,b\in G$, $a\circ b=b\circ a$

• Cayley Table

  describe a group in terms of an addition or multiplication table
  类似乘法表的形式，将每对元素映射的结果记录在表中

• Order of a group

  A group is finite, or has finite order, if it contains a finite number of elements.
  The order is $|G|=n$
  Otherwise, the group is said to be infinite or to have infinite order.
  The order is $|G|=\infty$

Examples

• Group of Units of $\mathbb{Z}_n$

  The set of all elements in $\mathbb{Z}_n$ that is relatively prime to $n$

• Symmetries of an equilateral triangle form a nonabelian group.

  Described in Section 3.1

• General Linear Group

  The set of invertible matrices forms a group
  只有可逆阵满足，群定义 [公理3] Inverse Element

• Quaternion Group

  $Q_8=\{\pm 1,\pm I,\pm J,\pm K\}$
  $1=\begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}$, $I=\begin{pmatrix}0 & 1 \\ -1 & 0\end{pmatrix}$, $J=\begin{pmatrix}0 & i \\ i & 0\end{pmatrix}$, $K=\begin{pmatrix}i & 0 \\ 0 & -i\end{pmatrix}$
  $I^2=J^2=K^2=-1$
  $IJ=K$, $JK=I$, $KI=J$, $JI=-K$, $KJ=-I$, $IK=-J$

• Nonzero Complex Number

  $$z^{-1}=\frac{a-bi}{a^2+b^2}$$

Basic Properties of Groups

• Proposition 3.17 特征元素唯一
  The identity element in a group G is unique.

  Proof:
  $e=e’e=e’$

• Proposition 3.18 逆元素唯一
  The inverse of an element in a group G is unique.

  Proof:
  $(g^{-1})=e(g^{-1})=(g^{-1})’g(g^{-1})=(g^{-1})’e=(g^{-1})’$

• Proposition 3.19 取逆分配
  Let $G$ be a group. If $a,b\in G$, then $(ab)^{-1}=b^{-1}a^{-1}$.

  Proof:
  $abb^{-1}a^{-1}=aea^{-1}=aa^{-1}=e$
  $b^{-1}a^{-1}ab=b^{-1}eb=b^{-1}b=e$
  Inverse is unique

• Proposition 3.20 两次取逆
  Let $G$ be a group. For any $a\in G$, $(a^{-1})^{-1}=a$.

  Proof:
  $(a^{-1})^{-1}=e(a^{-1})^{-1}=aa^{-1}(a^{-1})^{-1}=ae=a$

• Proposition 3.21 方程唯一解
  Let $G$ be a group and $a,b\in G$. Then the equations $ax = b$ and $xa = b$ have unique solutions in $G$. The right and left cancellation laws are true in groups.

  Proof:
  $x_1=a^{-1}ax_1=a^{-1}ax_2=x_2$
  $x_1=x_1aa^{-1}=x_2aa^{-1}=x_2$

• Proposition 3.22 消去律
  If $G$ is a group and $a,b,c\in G$, then $ba=ca\Rightarrow b=c$ and $ab=ac\Rightarrow b=c$.

  Proof:
  $ba=ca\Rightarrow baa^{-1}=caa^{-1}\Rightarrow b=c$
  $ab=ac\Rightarrow a^{-1}ab=a^{-1}ac\Rightarrow b=c$

• Exponential Notation for $g\in G$ and $n\in\mathbb{N}$ 幂

  $g^0=e$
  $g^n=g\cdot g\cdots g$(n times)
  $g^{-n}=g^{-1}\cdot g^{-1}\cdots g^{-1}$(n times)

• Theorem 3.23

  1. $g^mg^n=g^{m+n}$, $\forall m,n\in\mathbb{Z}$
  2. $(g^m)^n=g^{mn}$, $\forall m,n\in\mathbb{Z}$
  3. $(gh)^n=(h^{-1}g^{-1})^{-n}$, $\forall n\in\mathbb{Z}$
  4. Only for abelian groups, $(gh)^n=g^nh^n$, $\forall n\in\mathbb{Z}$

Subgroups

Definitions

• Subgroup $H$ of a group $G$ 子群

  A subset H of G such that when the group operation of G is restricted to H, H is a group in its own right.
  元素为子集，二元操作不变，仍满足群公理

• Trivial Subgroup

  $H=\{e\}$

• Proper Subgroup 真子群

  $H\ne G$

Examples

• $\mathbb{Q}^*$ is a subgroup of $\mathbb{R}^*$

  Proof:

  1. 1 is the identity element
  2. $(p/q)^{-1}=q/p$
  3. Multiplication is associative in both $\mathbb{Q}^$ and $\mathbb{R}^$

• $\{1,-1,i,-i\}$ is a subgroup of $\mathbb{C}^*$

• $SL_2(\mathbb{R})$ is a subgroup of $GL_2(\mathbb{R})$

  $GL_2(\mathbb{R})$: general linear group.
  $SL_2(\mathbb{R})$: special linear group, matrices of determinant 1.

  Proof:

  1. $I_2$ is the identity element.
  2. $A=\begin{pmatrix}a & b \\ c & d\end{pmatrix}$, $A^{-1}=\begin{pmatrix}d & -b \\ -c & a\end{pmatrix}$
  3. Multiplication is associative.
  4. The product also has determinant 1, by $|AB|=|A||B|$.

• A subset $H$ of a group $G$ can be a group without being a subgroup of $G$.

  $(\mathbb{M}{2\times 2},+)$ is a subset of but not a subgroup of $GL{2}$.
  此处二元操作不同，因而不是子群

• One way of telling whether or not two groups are the same is by examining their subgroups.

  判断群是否同构，可判断子群的数量及各自的大小是否相同

Some Subgroup Theorems

• Proposition 3.30 子群充要条件1

  A subset H of G is a subgroup if and only if it satisfies the following conditions:

  1. The identity $e$ of $G$ is in $H$.
  2. If $h_1$, $h_2\in H$, then $h_1h_2\in H$.
  3. If $h\in H$, then $h^{-1}\in H$.

  Proof:
  $\Rightarrow$:

  1. $ee_H=e_H=e_He_H\Rightarrow e=e_H$
  2. $H$ is a group
  3. $H$ is a group, then $h(h^{-1})’=e$, $(h^{-1})’\in H$, also (h^{-1})’\in G$. By uniqueness of inverse, $(h^{-1})’=h^{-1}$.

  $\Leftarrow$:
  These conditions plus the associativity of the binary operation will prove that $H$ is a group.

• Proposition 3.31 子群充要条件2

  Let $H$ be a subset of a group $G$. Then $H$ is a subgroup of $G$ if and only if $H\ne \emptyset$, and whenever $g$, $h\in H$ then $gh^{−1}$ is in $H$.

  Proof:
  $\Rightarrow$:
  $h\in H\Rightarrow h^{-1}\in H\Rightarrow gh^{-1}\in H$

  $\Leftarrow$:

  1. Let $g=h$, we have $e\in H$
  2. Let $g=h_1$, $h=h_2^{-1}$, we have $gh^{-1}=h_1(h_2^{-1})^{-1}=h_1h_2\in H$
  3. Let $g=e$, we have $h^{-1}\in H$
  4. By Proposition 3.30

Chapter 4: Cyclic Groups

Cyclic Subgroups

Definitions

• Cyclic Subgroup of a group $G$ generated by $a$: 循环子群

  $\langle a\rangle=\{a^k:k\in\mathbb{Z}\}$, $a\in G$

• Theorem 4.3

  $\langle a\rangle$ is a subgroup of $G$.
  $\langle a\rangle$ is the smallest subgroup of $G$ that contains a.

  Proof:

  1. $e=a^0\in \langle a\rangle$
  2. $g=a^m\in \langle a\rangle$，$h=a^n\in \langle a\rangle$, then $gh=a^{m+n}\in \langle a\rangle$
  3. $g=a^n\in \langle a\rangle$，then $g^{-1}=a^{-n}\in \langle a\rangle$
  4. Any subgroup $H$ containing $a$ must contain all powers of $a$, then $\langle a\rangle\subset H$, $\langle a\rangle$ is the smallest

• Cyclic Group $G$ 循环群

  $\exists a\in G$, $G=\langle a\rangle$

• Generator of a cyclic group 生成元

  $a$ in $\langle a\rangle$

• Order of a cyclic group $G$: 阶

  $a\in G$, the smallest positive integer $n$ that $a^n=e$
  $|a|=n$
  If there is no such $n$, $|a|=\infty$

• Theorem 4.9

  Every cyclic group is abelian.

  Proof:
  $g=a^r\in \langle a\rangle$，$h=a^s\in \langle a\rangle$, $gh=a^ra^s=a^{r+s}=a^{s+r}=a^sa^r=hg$

Subgroups of Cyclic Groups

• Theorem 4.10

  Every subgroup of a cyclic group is cyclic.

  Proof: (Brief Version)
  Let $m$ be the smallest natural number such that $a^m\in H$. Such an $m$ exists by the Principle of Well-Ordering.
  $h=a^m\in H$, we must show that every $h’\in H$ can be written as a power of $h$
  $h’=a^k=a^{mq+r}=(a^m)^qa^r=h^qa^r\in H$, where $0\leq r<m$
  $a^r=a^kh^{-q}$, then $a^r\in H$
  $r=0$, because $m$ is the smallest positive integer that $a^m\in H$
  $h’=h^q$
  $H=\langle h\rangle$ is a cyclic group

• Corollary 4.11

  The The subgroups of $\mathbb{Z}$ are exactly $n\mathbb{Z}$ for $n=1,2,\cdots$.

• Proposition 4.12

  Let $G$ be a cyclic group of order $n$ and suppose that $a$ is a generator for $G$. Then $a^k = e$ if and only if $n$ divides $k$.

  Proof:
  $\Rightarrow$:
  $e=a^k=a^{nq+r}=a^{nq}a^r=ea^r=a^r$
  $r=0$, $n$ divides $k$

  $\Leftarrow$:
  $a^k=a^{ns}=(a^n)^s=e^s=e$

• Theorem 4.13

  Let G be a cyclic group of order n and suppose that $a\in G$ is a generator of the group. If $b=a^k$, then the order of $b$ is $n/d$, where $d = gcd(k,n)$.

  Proof:
  Suppose $e=b^m=a^{km}$
  The order $m$ is the smallest integer $n$ that $n$ divides $km$
  The smallest $km$ is $lcm(k,m)$, which is $kn/d$
  Then $m=n/d$

• Corollary 4.14

  The generators of $\mathbb{Z}_n$ are the integers r such that $1\leq r<n$ and $gcd(r,n) = 1$.
  See the Group of Units of $\mathbb{Z}_n$

Multiplicative Group of Complex Numbers

Definitions

• Complex Numbers 复数

  $\mathbb{C}=\{a+bi:a,b\in\mathbb{R}\}$
  $a$ is Real Part 实部
  $b$ is Imaginary Part 虚部

• Rectangular or Cartesian

  $z=a+bi$

• Complex Conjugate 共轭复数

  $z^*=a-bi$

• Absolute Value or Modulus

  $|z|=\sqrt{a^2+b^2}$

• Polar Coordinates

  $z=r(\cos\theta+i\sin\theta)=r\textrm{cis}(\theta)$
  $r=|z|$

Theorems

• Proposition 4.20

  $z=r\textrm{cis}\theta$, $w=s\textrm{cis}\phi$
  $zw=rs\textrm{cis}(\theta+\phi)$

• Theorem 4.22 DeMoivre

  $[r\textrm{cis}\theta]^n=r^n\textrm{cis}(n\theta)$

  Proof:
  Induction on n.

The Circle Group and the Roots of Unity

• Circle Group

  $\mathbb{T}=\{z\in\mathbb{C}:|z|=1\}$

• Proposition 4.24

  The circle group is a subgroup of $\mathbb{C}$

• $n$-th Roots of Unity

  The $z$ satisfying $z^n=1$

• Theorem 4.25

  The $n$-th roots of unity is $z=\textrm{cis}(\frac{2k\pi}{n})$

  Proof:
  $z^n=\textrm{cis}(2k\pi)=1$

• Primitive $n$-th Root of Unity

  A generator for the group of the nth roots of unity.

The Method of Repeated Squares

• Calculate $x^a(\textrm{mod }b)$
• First: $a=\sum{2^{a_i}}$
• Calculate: $x^{2^{a_i}}(\textrm{mod }b)$ (This is quick)
• Add up.