{%hackmd @RintarouTW/About %}

# Algebraic Structure

$$
[V;*_1, *_2,\ldots, *_n]\cases{
V : \text{a set called domain of elements}\\
*_n : operations
}
$$

## Operations

:::info
Binary Opeartion
$$
S\times S\rightarrow S
$$
Unary Operation
$$
S\rightarrow S
$$
:::

### Properties of Opeartions

:::info
Communtative Property : $\forall a,b \in S, a\cdot b=b\cdot a$
Associative Property : $\forall a,b,c\in S, a(bc)=(ab)c$
Identity Property : $\forall a,e\in S, ae=ea=a$
Idempotent Property : $\forall a\in S, a\cdot a=a$
Left Distributive Property : $a\cdot(b+c)\iff \cdot$ is left distributive over $+$
Right Distributive Property : $(b+c)\cdot a\iff \cdot$ is right distributive over $+$
Distributive Property : $a\cdot(b+c) \land (b+c)\cdot a$
Involution Property : $\forall -(-a)=a\iff$ $-$ has the involution property.
Closure Property : $\forall a,b\in S, a\cdot b\in S$
:::

## Monoid

:::info
$M$ is the set
- associative : $\forall a,b,c\in M, a(bc)=(ab)c$
- identity : $\forall a\in M, ae=ea=a$
:::

## Group

:::info
$G$ is the set
- associative : $\forall a,b,c\in G, a(bc)=(ab)c$
- identity : $\forall a\in G, ae=ea=a$
- inverse : $\forall a\in G, \exists b\in G, ab=ba=e\implies b=\cases{a^{-1}\\-a}$

Abelian Group
- communitive : $\forall a,b\in G, ab=ba$
:::

Examples:

- $[Z;+]$ is a group
- $[Z;\cdot]$ is not a group since inverse(fraction) is not integer.
- $[\mathcal{P}(U);\oplus] \cases{\oplus:exclusive\ or\\U\text{ is any set}}$ is a group
- $[M_{m\times n}(\mathbb{R});+]$ is a group

Rook Matrix ($R_n$)
- $n\times n$ matrix
- each row and column has exactly one 1.

[More about Rook Matrix]()

$R_3$ : 3x3 rook matrices

$$
\pmatrix{1&0&0\\0&1&0\\0&0&1}
\pmatrix{0&1&0\\0&0&1\\1&0&0}
\pmatrix{0&0&1\\1&0&0\\0&1&0}
\\
\pmatrix{0&0&1\\0&1&0\\1&0&0}
\pmatrix{1&0&0\\0&0&1\\0&1&0}
\pmatrix{0&1&0\\1&0&0\\0&0&1}
$$

### Properties of Groups

#### Identities are Unique

:::info
Rephrased
Identities are unique $\iff$ if $e$ is the identity, no other element of $G$ is an identity of $G$.

Proof:
$$
G=[G;\cdot]\\
\forall a,e\in G, ae=ea=a\\
assume\ e_2\in G, e_2\neq e, ae_2=e_2a=a,\\
ae=a=ae_2\implies e=e_2\\
\therefore contradiction\ to\ e\neq e_2
$$
:::

#### Inverses are Unique

#### Inverse of Inverse

:::info
$$
\forall a\in G, (a^{-1})^{-1} = a
$$

Proof :
$$
Assume\ (a^{-1} = b)\land (b^{-1} = c)\land (a\ne c)\\
(ab = e)\land (cb=e)\\
ab = cb\implies a=c\\
\therefore contraditcion.
$$
:::

#### Inverse of a Product

:::info
$$
(ab)^{-1} = b^{-1}a^{-1}
$$
:::

#### Cancellation Law

:::info
$$
\forall a,b,c\in G,\\
left\ cancellation : ab=ac\implies b=c\\
right\ cancellation : ba=ca\implies b=c
$$
:::

#### Linear Equations in a Group

:::info
$$
\forall a,b\in G, ax=b\implies x=a^{-1}b\\
\forall a,b\in G, xa=b\implies x=ba^{-1}
$$
:::

#### Exponents

:::info
$$
\forall a\in G, n\geq 0, a^0 = e,\\
a^n = a^{n-1}a\\
if\ n>0, a^{-n} = (a^n)^{-1}\\
proved\ by\ induction\cases{
a^{n+1}=aa^{n}\\
a^{-n}=(a^{-1})^n, (a^n)^{-1}=(a^{-1})^n\\
a^{n+m}=a^na^m\\
(a^n)^m=a^{nm}
}
$$
:::

#### $a^m=e, 1\le m\le |G|$

:::info
G is a finite group, $|G|=n$
$$
\forall a\in G, \exists m\leq n, a^m = e\\
$$

Proof :
$$
list\ \{a, a^2, \ldots, a^{n+1}\}\ has\ n+1\ elements \implies exist\ duplication \because pigeonhole\\
let\ a^p\ and\ a^q\ are\ two\ of\ the\ duplicated\ elements. \implies a^p = a^q, p\neq q\\
let\ m = q-p\implies
\begin{array}l
a^m &= a^{q-p}\\
&= a^q a^{-p}\\
&= a^q (a^p)^{-1}\\
&= a^q (a^q)^{-1} \because a^p = a^q\\
&= e
\end{array}
$$
:::

## Greatest Common Divisors

:::info
$$
\forall a,b\in \mathbb{Z}, a,b, \text{not both 0},\\
gcd(a,b) = g \iff g\mid a\land g\mid b\\
and\\
(if\ exist\ c\mid a\land c\mid b\implies c\mid g\therefore \text{$g$ is the greatest of all common divisors})
$$
:::

### Relative Prime (Coprime)

:::info
$$
a,b\in \mathbb{Z}, gcd(a,b) = 1 \iff a,b\text{ are relatively prime}\\
p\text{ is a prime}\implies \forall a\in \mathbb{Z}, a\neq p, gcd(a,p) = 1
$$
:::

### Euclidean Algorithm

:::info
$$
\forall a\in \mathbb{Z}, a\neq 0, gcd(a,0) = a\\
\forall a,b\in \mathbb{Z}, b\neq 0, a=qb+r, gcd(a,b) = gcd(b,r) \mid 0\leq r\leq |b|, q\in \mathbb{Z}
$$
:::

### Modular Arithmetic

$$
\mathbb{Z_n} \overset{def}{=} \{0,1,2,\ldots,n-1\}
$$

:::info
Congruence Modulo $n$
Let $n \in \mathbb{Z}, n\geq 2$,
$$a\equiv_n b \iff n\mid (a-b)$$ or $$a\equiv b \pmod{n}$$

Modular Addition

$$
a+_n b\iff (a+b) \pmod{n}
$$

Modular Multiplication

$$
a\times_n b\iff ab \pmod{n}
$$
:::

#### Additive Inverse in $\mathbb{Z_n}$

:::info
$\forall a\in \mathbb{Z_n}, a\neq 0, (n-a)$ is the additive inverse of $a$. (complement-like)
:::

#### The Additive Group of Integers Modulo $n = [\mathbb{Z_n}, +_n]$
- 0 is the identity
- $\forall a\in \mathbb{Z}, a+_n 0 = 0+_n a = a$
- $\forall a\in \mathbb{Z},\exists b\in\mathbb{Z_n}, a+_n b = b+_n a = 0\mid b=-a$

#### The Multiplicative Group of Integers Modulo $n = [\mathbb{U_n}, \times_n]$
$$
\mathbb{U_n}=\{k\mid k\in\mathbb{Z},1\leq k\leq n-1,gcd(n,k)=1\}
$$
- 1 is the identity
- $\forall a\in \mathbb{U_n}, a\times_n 1 = 1\times_n a = a$
- $\forall a\in \mathbb{U_n}, \exists b\in \mathbb{U_n}, a\times_n b=b\times_n a=1$

## Subsystems

:::info
$$
[V;\cdot_1,\cdot_2,\ldots,\cdot_n]\land W\subseteq V, [W;\cdot_1,\cdot_2,\ldots,\cdot_n]
\iff W\text{ is the subsystem of V}\iff W\leq V
$$
:::

ex:
- subgroup : $[G;\cdot]$ is a group, $H\subset G$ and $[H;\cdot]$ is still a group, then $H$ is a subgroup of $G$.
- submonoid : If $M$ is a monoid and $P$ is a subset of $M$, then $P$ is a submonoid of $M$ if $P$ is a monoid.

### Subgroups

:::info
$[G;\cdot]\land H\subset G$
- closed in $H\iff \forall a,b\in H, a\cdot b\in H$
- identity $\in H$
- inverse $\in H\iff \forall a\in H, a^{-1}\in H$

implies $H\leq G$
:::

#### Subgroup of a finite group

:::info
$$
[G;\cdot]\land H\subset G,\\
H\text{ is closed}\iff H\leq G
$$
when $H$ is closed,
$$
\forall a\in H, a^m = e (m\leq |H|)\\
\therefore \cases{e\in H\\a(a^{m-1})=e\implies a^{-1} = a^{m-1}\in H}
$$
so when $H$ is closed in the finite group, it's the sufficient condition for a subgroup.
:::

#### Generator

:::info
$$
\langle a\rangle=\cases{
\{a^n\mid n\in\mathbb{Z}\}\ for\ multiplicative\ operation\\
\{(n)a\mid n\in\mathbb{Z}\} \ for\ additive\ operation
}
$$
:::

#### Cyclic Subgroup

:::info
$$
G\in Group,H\leq G,\exists a\in H, \langle a\rangle=H\iff H\text{ is a Cyclic Subgroup}\\
G\in Group,\exists a\in G, \langle a\rangle = G\iff G\text{ is a Cyclic Group}\\
ord(a)=|\langle a\rangle|\iff\text{The Order of }a\\
\langle a\rangle=\langle a^{-1}\rangle
$$
$a$ is referred as a generator of the subgroup($H$)/group($G$)
:::

## Direct Products

:::info
$$
\cases{
[V_i;\cdot_i,\Diamond_i,\ldots]\\
V=V_1\times V_2\times\cdots V_n\\
a=(a_1,a_2,\ldots,a_n)\mid a_i\in V_i, a\in V\\
b=(b_1,b_2,\ldots,b_n)\mid b_i\in V_i, b\in V
}\\
a\cdot b=(a_1\cdot_1 b_1, a_2\cdot_2 b_2,\ldots, a_n\cdot_n b_n)\\
a\Diamond b=(a_1\Diamond_1 b_1, a_2\Diamond_2 b_2,\ldots, a_n\Diamond_n b_n)\\
$$
:::

### The direct product of monoids is a monoid
### The direct product of groups is a group

$$
\cases{
[G_1;\cdot_1],[G_2;\cdot_2]\\
V=G_1\times G_2
}\\
$$

### Associativity of a direct product
$$
\forall a=(a_1,a_2),b=(b_1,b_2),c=(c_1,c_2)\in V,\\
\begin{array}l
a\cdot (b\cdot c)&=(a_1\cdot_1 (b_1\cdot c_1), a_2\cdot_2 (b_2\cdot_2 c_2))\\
&=(a_1\cdot_1 b_1\cdot_1 c_1, a_2\cdot_2 b_2\cdot_2 c_2)\\
&=((a_1\cdot_1 b_1)\cdot c_1, (a_2\cdot_2 b_2)\cdot_2 c_2)\\
&=(a\cdot b)\cdot c
\end{array}\\
$$

### Identity of a direct product
$$
\forall a=(a_1,a_2)\in V,\\
\begin{array}l
a\cdot e&=(a_1\cdot_1 e_1,a_2\cdot_2 e_2)\\
&=(a_1,a_2)\\
&=a
\end{array}\\
\therefore e=(e_1,e_2)
$$

### Inverse of a direct product
$$
\forall a=(a_1,a_2)\in V,\\
\begin{array}l
a\cdot a^{-1}&=(a_1\cdot_1 (a_1)^{-1},a_2\cdot_2 (a_2)^{-1})\\
&=(e_1,e_2)\\
&=e
\end{array}\\
$$

## Group Isomorphisms

:::info
$$
\cases{
[G_1;\cdot_1],[G_2;\cdot_2]\\
\exists f:G_1\rightarrow G_2, f\text{ is a bijection}\\
\forall a,b\in G1,f(a\cdot_1 b)=f(a)\cdot_2 f(b)\\
}
\iff G_1\ is\ isomorphic\ to\ G_2
$$
:::

### Properties of Group Isomorphism
:::info
$$
\cases{
[G;\cdot_1], [H;\cdot_2]\\
f:G\rightarrow H\\
e\in G, e'\in H
}\implies
\cases{
f(e)=e'\\
\forall a\in G,f(a)^{-1}=f(a^{-1})\\
K\ is\ a\ subgroup\ of\ G\implies \cases{
f(K)=\{f(a)|a\in K\}\ is\ a\ subgroup\ of\ H\\
f(K)\ is\ isomorphic\ to\ K.
}
}
$$
:::

###### tags: `math` `algebra`