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