NoteNextra-origin/content/CSE5313/CSE5313_L5.md

# CSE5313 Coding and information theory for data science (Lecture 5)

## Recap

### Group

1. Closure: $\forall a,b\in G, a\cdot b\in G$.
2. Associativity: $\forall a,b,c\in G, (a\cdot b)\cdot c=a\cdot (b\cdot c)$.
3. Identity: $\exists e\in G, \forall a\in G, a\cdot e=e\cdot a=a$.
4. Inverses: $\forall a\in G, \exists a^{-1}\in G, a\cdot a^{-1}=a^{-1}\cdot a=e$.

May not be commutative (group of invertible matrices).

### Order of element in group

$a\in G$ is of order $k$ if $a^k=e$ and $k$ is the smallest positive integer such that $a^k=e$.

If $a^n=e$, then $O(a)\mid n$.

### Generator of group

$a\in G$ is a generator of $G$ if $\mathcal{O}(a)=|G|$. (for finite groups)

For infinite groups, $\langle a\rangle=G$.

<details>
<summary>Example</summary>

$(\mathbb{Z}_n,+)$ has generator $1$.

$(\mathbb{Z}_8^*,\cdot)$ has generator $3$. (Recall $\mathbb{Z}_8^*=\{x\in\mathbb{Z}_8:gcd(x,8)=1\}$. for multiplicative inverse.)

</details>

## New content

### Subgroups

A subgroup $H$ of $G$ is a nonempty subset of $G$ that is itself a group under the operation of $G$.

Denoted as $H\leq G$.

<details>
<summary>Example</summary>

$(\mathbb{Z}_6,+)$ has subgroups $H=(\{0,2,4\},+)$.

Only need to check three:

- non-empty
- closure
- finite

</details>

#### Theorem for finite subgroups

If $H$ is finite, non-empty, and closed under the operation of $G$, then $H$ is a subgroup of $G$.

### Equivalence relations

An equivalence relation $\sim$ on a set $X$ is a relation that is

- reflexive: $\forall x\in X, x\sim x$
- symmetric: $\forall x,y\in X, x\sim y\implies y\sim x$
- transitive: $\forall x,y,z\in X, x\sim y\text{ and } y\sim z\implies x\sim z$

<details>
<summary>Example</summary>

Let $S$ be points on land, and $a\sim b$ if $a$ and $b$ are connected by land.

</details>

#### Equivalence classes

An equivalence relation on $S$ partitions $S$ into equivalence classes.

Equivalence classes are:

- Disjoint
- Cover $S$

### Cosets

Let $G$ be a group and $H$ its subgroup.

The coset of $H$ in $G$ is the equivalence class under congruence modulo $H$.

Alternatively, (more convenient)

$$
\{h+a|h\in H,a\in G\}
$$

<details>
<summary>Example</summary>

Let $G=(\mathbb{Z}_6,+)$ and $H=(\{0,2,4\},+)$.

Define the equivalence relation on $G$ as:

$a\sim b$ if $a+b^{-1}\in H$ (congruence modulo $H$)

To find the equivalence classes of this relation for $G=(\mathbb{Z}_6,+)$ and $H=(\{0,2,4\},+)$, we have:

- $0\sim 0, 0\sim 2, 0\sim 4$
- $1\sim 1, 1\sim 3, 1\sim 5$

</details>

### Lagrange's theorem

For every finite group $G$, the order of every subgroup $H$ of $G$ divides the order of $G$.

#### Corollary of Lagrange's theorem

If $|G|$ is prime, then $G$ is cyclic.

<details>
<summary>Proof</summary>

Let $A=\{a^0=e,a,a^2,\cdots,a^{|G|-1}\}$.

$A$ is a cyclic subgroup of $G$. of order at least two.

Then $|A|||G|$.

So $|A|=|G|$.

So $A=G$.

So $G$ is cyclic.

</details>

### Additive group of a field

Any finite field has two types groups:

- Additive group: $(\mathbb{F},+)$
- Multiplicative group: $(\mathbb{F}^*,\cdot)$

The "integer" of $F$ is:

$$
\{a\in F|1^k=a,k\in\mathbb{N}\}
$$

The "characteristic" of $F$ is:

- The order of $1$ in additive group
- Number of times that $1$ is added to itself to get $0$
- Denoted by $\operatorname{c}(F)$.

<details>
<summary>Example</summary>

$\operatorname{c}(\mathbb{Z}_7)=7$.

$\operatorname{c}(\mathbb{R})=0$.

$\operatorname{c}(\mathbb{Z}_2[x] \mod x^2+x+1)=2$.

</details>

#### Theorem field characteristic is prime

If $\operatorname{c}(F)>0$, then $\operatorname{c}(F)$ is prime.

<details>
<summary>Proof</summary>

Suppose $\operatorname{c}(F)=mn$, then $0=\sum_{i=0}^{m-1}1\cdot\sum_{j=0}^{n-1}1=0$.

So $m$ or $n$ must be $0$.

So $\operatorname{c}(F)$ is prime.

</details>

#### Theorem of linear power over additive group with prime characteristic

Let $F$ be a field with characteristic $p>0$, then operation $^p$ is linear.

That is, $(a+b)^p=a^p+b^p$.

<details>
<summary>Proof</summary>

$$
(a+b)^p=\sum_{i=0}^p \binom{p}{i} a^i b^{p-i}
$$

$$
\begin{aligned}
\binom{p}{i}&=\frac{p!}{i!(p-i)!}\\
&=\frac{p(p-1)\cdots(p-i+1)}{i(i-1)\cdots 1}
\end{aligned}
$$

> Informally, $p$ divides the numerator but not the denominator. So the whole fraction is an integer.

Since $\binom{p}{i}$ is an integer of $F$ except for $i=0$ and $i=p$, we have $\binom{p}{i}=0$ for $i=1,\cdots,p-1$.

So $(a+b)^p=a^p+b^p$.

</details>

### Multiplicative group of a field

Every element in a multiplicative group of a field is cyclic.

Corollary:

- Every finite field has a generator, called a primitive element.
- This is an element $\gamma$ such that $\mathbb{F}^*=\langle \gamma\rangle$.
- Every element of $\mathbb{F}^*$ is a power of $\gamma$.

<details>
<summary>Example</summary>

Build $F_{16}=\mathbb{Z}_2[\zeta] \mod \zeta^4+\zeta+1$.

The elements are:

| Power of $\zeta$ | Element | As vector in $\mathbb{Z}_2^4$ |
|---|---|---|
| 0 | 0 | (0,0,0,0) |
| 1 | 1 | (1,0,0,0) |
| 2 | $\zeta$ | (0,1,0,0) |
| 3 | $\zeta^2$ | (0,0,1,0) |
| 4 | $\zeta^3$ | (0,0,0,1) |
| 5 | $\zeta+1$ | (1,1,0,0) |
| 6 | $\zeta^2+\zeta$ | (0,1,1,0) |
| 7 | $\zeta^3+\zeta^2$ | (0,0,1,1) |
| 8 | $\zeta^3+\zeta^2+1$ | (1,1,1,0) |

The primitive element is $\zeta$.

### Vector spaces and subspaces over finite fields

$\mathbb{F}^n$ is a vector space over $\mathbb{F}$.

With point-wise vector addition and scalar multiplication.

<details>
<summary>Example</summary>

$\mathbb{F}_2^4$ is a vector space over $\mathbb{F}_2$.

Let $v=\begin{pmatrix}
1 & 1 & 1 & 1
\end{pmatrix}$

Then $v$ is a vector in $\mathbb{F}_2^4$ that's "orthogonal" to itself.

$v\cdot v=1+1+1+1=4=0$ in $\mathbb{F}_2$.

In general field, the dual space and space may intersect non-trivially.

</details>

Let $V$ be a subspace of $\mathbb{F}^n$.

$V$ is a subgroup of $\mathbb{F}^n$ under vector addition.

- Apply the theorem: If $H$ is finite, non-empty, and closed under the operation of $G$, then $H$ is a subgroup of $G$.

> Is every subgroup of $\mathbb{F}^n$ a subspace?

Cosets in this definition are called Affine subspaces.