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

Recap

Group

Closure: $\forall a,b\in G, a\cdot b\in G$ .
Associativity: $\forall a,b,c\in G, (a\cdot b)\cdot c=a\cdot (b\cdot c)$ .
Identity: $\exists e\in G, \forall a\in G, a\cdot e=e\cdot a=a$ .
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$ .

Example

$(\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.)

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

Example

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

Only need to check three:

non-empty
closure
finite

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$

Example

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

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\}

Example

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$

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.

Proof

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.

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

Example

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

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

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

Theorem field characteristic is prime

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

Proof

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.

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

Proof

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

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

Example

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.

Example

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

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.