{%hackmd @RintarouTW/About %}

# Group Theory

digraph {
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [fontcolor="#AAAAAA";fontsize="9";color="#888800"];
"Magama"->"Quasigroup" [xlabel="divisibility"];
"Magama"->"Unital magma" [xlabel="identity"];
"Magama"->"Semigroup"[xlabel="associativity"];
"Quasigroup"->"Loop"[xlabel="identity"];
"Quasigroup"->"Inverse semigroup"[xlabel="associativity"];
"Unital magma"->"Loop"[xlabel="inversibility"];
"Unital magma"->"Monoid"[xlabel="associativity"];
"Semigroup"->"Inverse semigroup"[xlabel="divisibility"];
"Semigroup"->"Monoid"[xlabel="identity"];
"Loop"->Group[xlabel="associativity"];
"Inverse semigroup"->Group[xlabel="identity"];
"Monoid"->Group[xlabel="inversibility"];
}

:::info
$$
\cases{
Magama: Closed\iff \forall x,y\in Magama,xy\in Magama\\
Semigroup: Associative\iff \forall x,y,z\in Semigroup, x(yz)=(xy)z\\
Monoid: Identity\iff\forall x\in Monoid, \exists! e\in Monoid,xe=ex=x\\
Group: Inversibility\iff\forall x\in Group,\exists! x^{-1}\in Group, xx^{-1}=x^{-1}x=e\\
}
$$
:::

- [Group](/@RintarouTW/Algebraic_Structure#Group)
- [Subgroup](/@RintarouTW/Algebraic_Structure#Subgroups)
- [Generator](/@RintarouTW/Algebraic_Structure#Generator)

## Cyclic Group

:::info
$$
G\ is\ cyclic\iff\exists a\in G, \langle a\rangle=\{na\mid n\in \mathbb{Z}\}=G
$$
:::

ex:

$$
\begin{array}l
[\mathbb{Z};+]\in cyclic&\iff \mathbb{Z}=\langle 1\rangle=\{n\cdot 1\mid n\in\mathbb{Z}\}\\
&\iff\mathbb{Z}=\{0\}\cup\{\overbrace{1+1+\cdots+1}^{n\ terms}\mid n\in\mathbb{P}\}\cup\{\overbrace{(-1)+(-1)+\cdots+(-1)}^{n\ terms}\mid n\in\mathbb{P}\}
\end{array}
$$

### Multipicative group of integers modulo $n$

:::info
$$
[\mathbb{U}_n;\times_n]\in cyclic
$$

Proof:
$$
\cases{
\mathbb{U}_n = \{k\in\mathbb{Z}\mid gcd(n,k)=1, 1\le k\le (n-1)\}\\
|\mathbb{U}_n|=m\\
[\mathbb{U}_n;\times_n]\in Group
}\\
\Downarrow\\
\cases{
a\in\mathbb{U}_n, a\ne 1\\
1\le i,j\le m, i\ne j, a^i\ne a^j \ (need\ better\ proof)\\
\forall x,y\in\mathbb{U}_n, x\times_n y\in\mathbb{U}_n\implies a^1,a^2,\ldots,a^m\in\mathbb{U}_n
}\\
\Downarrow\\
\cases{
a^1\ne a^2\ne\cdots\ne a^m\\
a^1,a^2,\ldots,a^m\in\mathbb{U}_n\\
|\mathbb{U}_n|=m
}\\
\Downarrow\\
\mathbb{U}_n=\{a^1,a^2,\ldots,a^m\}\iff\mathbb{U}_n=\langle a\rangle\\
\therefore a\ is\ a\ generator\ of\ \mathbb{U}_n\implies [\mathbb{U}_n;\times_n]\in cyclic
$$
:::

### Cyclic Implies Abelian

:::info
$$
[G;\cdot]\ is\ cyclic\iff G=\langle a\rangle=\{a^n\mid a\in G,n\in\mathbb{Z}\}\\
\forall x,y\in G\cases{
x=a^m, m\in\mathbb{Z}\\
y=a^n, n\in\mathbb{Z}
}\\
\begin{array}l
x\cdot y&=a^m\cdot a^n\\
&=a^{m+n}\\
&=a^{n+m}\\
&=a^n\cdot a^m\\
&=y\cdot x
\end{array}\\
\therefore G\ is\ abelian
$$
:::

### Possible Cyclic Group Structures

:::info
$$
G\ is\ cyclic\implies G\ is\ isomorphic\ to\cases{
[\mathbb{Z}_n;+_n]\ if\ G\ is\ finite\\
[\mathbb{Z};+]\ if\ G\ is\ infinite\\
}
$$

(TODO: proof)
:::

### Subgroups of Cyclic Groups

:::info
Every subgroup of a cyclic group is cyclic.

(TODO: proof)
:::

### The order of elements of a finite cyclic group

:::info
$$
\cases{
G\in cyclic\\
|G|=n\\
G=\langle a\rangle=\{ka\mid k\in\mathbb{Z}\}\\
S\le G
}\implies
|S|=n/d, d=gcd(n,k)
$$
(TODO: proof)
:::

### Chinese Remainder Theorem (CRT)

## Cosets and Factor Groups

:::info
Coset of $H$
$$
\cases{
[G;*]\in Group\\
H\le G,a\in G\\
}\\
left\ coset\ a*H=\{a*h\mid h\in H\}\\
right\ coset\ H*a=\{h*a\mid h\in H\}
$$

- $H$ is in both the left and right cosets ($e*H=H*e=H$)
- $G\in Abelian\implies a*H=H*a\implies$ left-coset = right-coset
:::

### Coset Representative

:::info
Any element of a coset is called a representative of that coset.
:::

:::info
Theorem:

$$
H\le G, a,b\in G\cases{
b\in a*H\implies b*H=a*H\\
b\in H*a\implies H*b=H*a
}
$$

Proof:
$$
b\in a*H\implies \exists h_1\in H, b=a*h_1\implies a=b*h_1^{-1}\\
\forall x\in a*H, \exists h\in H,x=a*h=b*h_1^{-1}*h\\
\because h_1^{-1},h\in H, h_1^{-1}*h\in H\\
\therefore x=b*(h_1^{-1}*h)\in b*H\implies a*H\subseteq b*H\\
\forall h\in H, b*h=a*h_1*h=a*(h_1*h)\\
\because h_1,h\in H, h_1*h\in H\\
\therefore b*h=a*(h_1*h)\in a*H\implies b*H\subseteq a*H\\
(a*H\subseteq b*H)\land(b*H\subseteq a*h)\implies b*H=a*H
$$
:::

### Cosets Partition a Group

:::info
- If $[G;∗]$ is a group and $H\le G$, the set of left cosets of $H$ is a partition of $G$.
- All of the left cosets of $H$ have the same cardinality.
- The same is true for right cosets.

Proof:

$$
\because\forall a\in G, e\in H, a=a*e\in a*H\\
\therefore \text{all elements of $G$ belongs to a left coset of $H$}
$$
:::

### A Coset Counting Formula

:::info
$$
|G|\lt\infty\land H\le G\\
\text{the number of distinct cosets of } H=\dfrac{|G|}{|H|}\\
G/H=\text{the set of left cosets of } H\ in\ G
$$
:::

### Distinguished Representatives

:::info

$4\mathbb{Z}$ is the subgroup of $[\mathbb{Z};+]$

$$
\mathbb{Z}/4\mathbb{Z} = \cases{
\{0+4k\mid k\in\mathbb{Z}\}=4\mathbb{Z}\\
\{1+4k\mid k\in\mathbb{Z}\}=1+\mathbb{Z}\\
\{2+4k\mid k\in\mathbb{Z}\}=2+\mathbb{Z}\\
\{3+4k\mid k\in\mathbb{Z}\}=3+\mathbb{Z}\\
}
$$
:::

### Lagrange’s Theorem

:::info
The order of a subgroup of a finite group must divide the order of the group.
$$
H\le G\implies |H|\ divides\ |G|\\
\Downarrow\\
\mathbb{Z}_p, p\in prime\implies \mathbb{Z}_p\text{ has no proper subgroup.}
$$
:::

### Operation on Cosets

:::info
Let $C$ and $D$ be left cosets of $H$, a subgroup of $G$ with representatives $c$ and $d$, respectively. Then
$$
C\oplus D = (c*H)\oplus (d*H) = (c*d)*H
$$
The operation $\oplus$ is called **the operation induced on left cosets by ∗**.

When the result we get for $C\oplus D$ is always independent of our choice of representatives, we say that **“$\oplus$ is well defined”**.
:::

Example:

Cosets of $4\mathbb{Z}\cases{
0+4\mathbb{Z}=\bar{0}\\
1+4\mathbb{Z}=\bar{1}\\
2+4\mathbb{Z}=\bar{2}\\
3+4\mathbb{Z}=\bar{3}\\
}$

$$
\begin{array}{c|c|c|c}
\oplus & \bar{0} & \bar{1} & \bar{2} & \bar{3}\\\hline
\bar{0} & \bar{0} & \bar{1} & \bar{2} & \bar{3}\\\hline
\bar{1} & \bar{1} & \bar{2} & \bar{3} & \bar{0}\\\hline
\bar{2} & \bar{2} & \bar{3} & \bar{0} & \bar{1}\\\hline
\bar{3} & \bar{3} & \bar{0} & \bar{1} & \bar{2}\\\hline
\end{array}
$$

### Coset operation is well-defined (Abelian Case)

:::info
$$
G\in Abelian, H\le G, \cases{a,a'\in C, C=a*H\\b, b'\in D, D=b*H}\\
\begin{array}l
a'*b'&=(a*h_1)*(b*h_2)\ where\ h1,h2\in H\\
&=a*b*h_1*h_2\ (\because G\in Abelian)\\
&=(a*b)*(h_1*h2)\in (a*b)*H\ (\because h_1,h_2\in H, h_1*h_2\in H)
\end{array}\\
\therefore a'*b'\in (a*b)*H\\
a*b,a'*b'\text{ got the same coset independently.}\implies *\text{ is well defined.}
$$
:::

### Well-defined operation implies left cosets a group

:::info
Let $G$ be a group and $H\le G$. If the operation induced on left cosets of $H$ by the operation of G is **well defined**, then **the set of left cosets forms a group under that operation**.
Proof
$$
\cases{
[G;*]\in group\\
H\le G\\
L=\text{left cosets of } H
}\\
\forall C_1=c_1*H,C_2=c_2*H,C_3=c_3*H\in L,\\
C_1*(C_2*C_3)=c_1*(c_2*c_3)=(c_1*c_2)*c_3=(C_1*C_2)*C_3\implies *\ is\ associative.\\
H=e*H\implies identity\ coset\\
\forall C=a*H, a\in G,\exists a^{-1}\in G, C^{-1}=a^{-1}*H,\\ C*C^{-1}=(a*a^{-1})*H=e*H\implies inverse\ coset
$$
:::

### Quotient/Factor Group

:::info
Let $G$ be a group and $H\le G$. If the set of left cosets of $H$ forms a group, then that group is called **the factor group of “G modulo H.”** It is denoted **$G/H$**.

If $G$ is abelian, then every subgroup of $G$ yields a factor group.

Integers modulo $n$ = $\mathbb{Z}/n\mathbb{Z}$
:::

## Permutation Groups

Elements of $S_3$

$$
A=\{1,2,3\}\\
i=\pmatrix{1&2&3\\1&2&3}, r_1=\pmatrix{1&2&3\\2&3&1},r_2=\pmatrix{1&2&3\\3&1&2}\\
f_1=\pmatrix{1&2&3\\1&3&2},f_2=\pmatrix{1&2&3\\3&2&1},f_3=\pmatrix{1&2&3\\2&1&3}\\
\begin{array}{ccccccc}
\circ & i & r_1 & r_2 & f_1 & f_2 & f_3\\\hline
i & i & r_1 & r_2 & f_1 & f_2 & f_3\\\hline
r_1 & r_1 & r_2 & i & f_3 & f_1 & f_2\\\hline
r_2 & r_2 & i & r_1 & f_2 & f_3 & f_1\\\hline
f_1 & f_1 & f_2 & f_3 & i & r_1 & r_2\\\hline
f_2 & f_2 & f_3 & f_1 & r_2 & i & r_1\\\hline
f_3 & f_3 & f_1 & f_2 & r_1 & r_2 & i\\\hline
\end{array}
$$

### Symmetric Groups

:::info
Let $A$ be a nonempty set. The set of all permutations on $A$ with the operation of function composition($\circ$) is called **the symmetric group on $A$**, denoted $S_A$.

$|A|=n, S_A=S_n, |S_n|=n!$

$n\ge 3, [S_n;\circ]\notin Abelian$

:::

### Cycle Notation

#### Disjoint Cycles

:::info
We say that two cycles are disjoint if no number appears in both cycles.
Disjoint cycles can be written in any order.
:::

#### Transposition

:::info
A transposition is a cycle of length 2.
:::

#### Decomposition into Cycles

:::info
Every cycle of length greater than 2 can be expressed as a product of transpositions.

$$
(a_1,a_2,\ldots,a_n)=(a_1,a_n)(a_1,a_{n-1})\cdots(a_1,a_2)
$$
:::

### Parity of Permutation

Every permutation on a finite set can be expressed as the product of an **even number of transpositions** or an **odd number of transpositions**, but not both.

#### The Alternating Group

:::info
Let $n\ge 2$. The set of even permutations in $S_n$ is a proper subgroup of $S_n$ called the alternating group on $\{1,2,...,n\}$, denoted $A_n$.
:::

### Dihedral Groups

:::info
$$
[\mathbb{Z}_2;+_2]\cong[\{-1,1\};\cdot]\cong[S_2;\circ]\\
\begin{array}{c|cc}
[\mathbb{Z}_2;+_2] & 0 & 1\\\hline
0 & 0 & 1\\\hline
1 & 1 & 0
\end{array}\cong
\begin{array}{c|cc}
[\{-1,1\};\cdot] & -1 & 1\\\hline
-1 & 1 & -1\\\hline
1 & -1 & 1
\end{array}\cong
\begin{array}{c|cc}
[S_2;\circ] & i & t\\\hline
i & i & t\\\hline
t & t & i
\end{array}
\cases{
i=\pmatrix{1&2\\1&2}\\
t=\pmatrix{1&2\\2&1}
}
$$
:::

:::info
$$
D_4=\langle r_1,f_1\rangle=\{i, r_1, {r_1}^2, {r_1}^3, f_1, r_1\circ f_1, {r_1}^2\circ f_1, {r_1}^3\circ f_1\}\\
\begin{array}{l}
i&=\pmatrix{1&2&3&4\\1&2&3&4}&
r_1&=\pmatrix{1&2&3&4\\2&3&4&1}&
{r_1}^2&=\pmatrix{1&2&3&4\\3&4&1&2}&
{r_1}^3&=\pmatrix{1&2&3&4\\4&1&2&3}\\
f_1&=\pmatrix{1&2&3&4\\4&3&2&1}&
r_1\circ f_1&=\pmatrix{1&2&3&4\\1&4&3&2}&
{r_1}^2\circ f_1&=\pmatrix{1&2&3&4\\2&1&4&3}&
{r_1}^3\circ f_1&=\pmatrix{1&2&3&4\\3&2&1&4}
\end{array}\\
\cases{
r_1=(1,2,3,4)=(1,4)(1,3)(1,2)\\
f_1=(1,4)(2,3)
}\\
odd=\{r_1,{r_1}^3,r_1\circ f_1,{r_1}^3\circ f_1\}\\
even=\{i,{r_1}^2,f_1,{r_1}^2\circ f_1\}
$$
:::

:::info
Dihedral Groups
$$
k\ge 3\cases{
r=(1,2,\ldots,k)\\
f=(1,k)(2,k-1)(3,k-2)\ldots
}\\
D_k=\langle r,f\rangle=\{i,r,r^2,\ldots,r^{k-1},f,r\circ f,r^2\circ f,\ldots,r^{k-1}\circ f\}\\
|D_k|=2k
$$
:::

## Normal Subgroups and Group Homomorphisms

$$
A_3\le S_3\\
A_3 = \{i, r_1, r_2\}\\
B_3 = \{f_1, f_2, f_3\} \in coset\ of\ A_3\\
S_3 = A_3 + B_3\\
S_3/A_3 = \{A_3, B_3\}\\
\begin{array}{l|ll}
\circ & A_3 & B_3\\\hline
A_3 & A_3 & B_3\\
B_3 & B_3 & A_3
\end{array}
$$

### Normal Subgroup

:::info

If $G$ is a group, $H\le G$, then $H$ is a normal subgroup of $G$, denoted $H \lhd G$, if and only if **every left coset of $H$ is a right coset of $H$**.

$$
H\lhd G\iff \cases{
H\le G\\
\forall a\in G, a*H=H*a
}
$$

:::

#### Conditions for a coset operation is well-defined

if $H\le G$, then the operation induced on left cosets of $H$ by **the operation of $G$ is well defined** if and only if any one of the following conditions is true.

- $H$ is a normal subgroup of $G$
- $h\in H, a\in G, \exists h\in H, h*a=a*h$
- $h\in H, a\in G, a^{-1}*h*a\in H$

If $H\le G$, then the operation induced on left cosets of $H$ by the operation of $G$ is well defined if either of the following two conditions is true.
- G is abelian
- $|H|= \dfrac{|G|}{2}$

### Homomorphisms

Homomorphisms is NOT required to be **one-to-one (bijection)** like isomorphism. So, the mappting function($\theta$) is possibly **many-to-one**.

$$
\theta(x\cdot y)=\theta(x)\diamond \theta(y)
$$

:::info
$$
\cases{
[G;\cdot],[G';\diamond]\in Group\\
\theta:G\to G'\\
}\\
\theta\ is\ homomporphism\iff \forall x,y\in G, \theta(x\cdot y)=\theta(x)\diamond\theta(y)
$$
:::

### Group Homomorphism Properties

:::info
If $\theta:G\to G'$ is a homomorphism, then:
- $e\in G, e'\in G', \theta(e)=e'$
- $\forall a\in G, \theta(a^{-1})=(\theta(a))^{-1}$
- $H\le G, \theta(H)=\{\theta(h)\mid h\in H\}\le G'$
:::

#### Natural Homomorphism

:::info
If $H\lhd G$, then the function π : G → G/H defined by π(a) = aH is called **the natural homomorphism**.
$$
H\lhd G\implies \pi: G\to G/H, \pi(a)=aH
$$
:::

#### Kernel of a homomorphism

:::info
Let $\theta : G\to G'$ be a homomorphism, and let $e$ and $e'$ be the identities of $G$ and $G'$, respectively.
The kernel of $\theta$ is the set $ker\theta = \{a\in G \mid \theta(a) = e'\}$

Let $\theta:G\to G'$ be a homomorphism.
The kernel of $\theta(ker\theta)$ is a normal subgroup of $G$.
:::

#### Fundamental Theorem of Group Homomorphisms

:::info
Let θ : G → G′ be a homomorphism. Then θ(G) is isomorphic to G/ ker θ.
:::

## Coding Theory, Group Codes

(TODO)

###### tags: `math`