2019-03-05
2. The Integers
Theorem 2.10
Let $a$ and $b$ be nonzero integers. Then there exist integers $r$ and $s$ such that
$$ \gcd(a,b)=ar+bs $$
Furthermore, the greatest common divisor of $a$ and $b$ is unique
3.Groups
Theorem 3.23
In a group, the usual laws of exponents hold; that is, for all $g, h\in G$
$g^mg^n=g^{m+n}$ for all $m, n\in\mathbb{Z}$
$(g^m)^n=g^{mn}$ for all $m, n\in\mathbb{Z}$
$(gh)^n=(g^{-1}h^{-1})^{-n}$ for all $n\in\mathbb{Z}$. Furthermore, if $G$ is abelian, then $(gh)^n=g^nh^n$
Proposition 3.30
A subset $H$ of $G$ is a subgroup if and only if it satisfies the following conditions
The identity $e$ of $G$ is in $H$
If $h_1, h_2\in H$, then $h_1h_2\in H$
If $h\in H$, then $h^{-1}\in H$
Proposition 3.31
Let $H$ be a subset of a group $G$. Then $H$ is a subgroup of $G$ if and only if $H\not=\emptyset$, and whenever $g, h\in H$ then $gh^{-1}$ is in $H$
4.Cyclic Groups
Remark 4.4
If we are using the “+” notations, as in the case of the integers under addition, we write $\langle a\rangle={na:a\in\mathbb{Z}}$
For $a\in G$, we call $\langle a\rangle$ the cyclic subgroup generated by $a$. If $G$ contains some element $a$ such that $G=\langle a\rangle$, then $G$ is a cyclic group. In this case $a$ is a generator of $G$.
If $a$ is an element of a group $G$, we define the order of $a$ to be the smallest positive integer $n$ such that $a^n=e$, and we write $|a|=n$. If there is no such integer $n$, we say that the order of $a$ is infinite and write $|a|=\infty$ to denote the order of $a$
Corollary 4.14
The generators of $\mathbb{Z}_n$ are the integers r subch that $1\le r<n$ and gcd$(r, n)=1$
$\text{cis}(x)=\cos(x)+$i$\sin(x)$
Proposition 4.20
Let $z=r\text{cis}\theta$ and $w=s\text{cis}\phi$ be two nozero compler numbers. Then $$zw=rs\text{cis}(\theta+\phi)$$
5. Permutation Groups
Proposition 5.8
Let $\sigma$ and $\tau$ be two disjoint cycles in $S_X$. Then $\sigma\tau=\tau\sigma$
Theorem 5.9
Every permutation in $S_n$ can be written as the product of disjpint cycles
Lemma 5.14
If the identity is written is written as the product of r transpositions $$id=\tau_1\tau_2…\tau_r$$ then $r$ is an even number
The Alternating Groups
One of the most important subgroups of $S_n$ is the set of all even permutations, $A_n$. The group $A_n$ is called the alternating group on n letters
Theorem 5.16
The set $A_n$ is a subgroup of $S_n$
Proposition 5.17
The number of even permutations in $S_n, n\ge2$, is equal to the number of odd permutations; hence, the order of $A_n$ is $\dfrac{n!}{2}$
Dihedral Groups
We define the nth dihedral group to be the group of rigid motions of a regular n-gon. $D_n$ consists of all finite products of $r$ and $s$
$$D_n={1, r, r^2…r^{n-1}, s, sr, sr^2…sr^{n-1}}$$
6.Cosets and Lagrange’s Theorem
Cosets
Let $G$ be a group and $H$ a subgroup of $G$. Define a left coset of $H$ with representative $g\in G$ to be the set $$gH={gh:h\in H}$$
Lemma 6.3
Let $H$ be a subgroup of a group $G$ and suppose that $g_1,g_2\in G$. The following conditions are equivalent
- $g_1H=g_2H$
- $Hg_1^{-1}=Hg_2^{-1}$
- $g_1H\subset g_2H$
- $g_2\in g_1 H$
- $g_1^{-1}g_2\in H$
Theorem 6.4
Let $H$ be a subgroup of a group $G$. Then the left cosets of $H$ in $G$ partition $G$. That is, the group $G$ is the disjoint union of the left cosets of $H$ in $G$
Remark 6.5
Let $G$ be a group and $H$ be a subgroup of $G$. Define the index of $H$ in $G$ to be the number of left cosets of $H$ in $G$. We will denote the index by $[G:H]$
Theorem 6.10 Lagrange
Let $G$ be a finite group and let $H$ be a subgroup of $G$. Then $G/H=[G:H]$ is the number of distinct left cosets of $H$ in $G$. In particular, the number of elements in $H$ must divide the number of elements in $G$
Corollary 6.11
Suppose that $G$ is a finite group and $g\in G$. Then the order of $g$ must divide the number of elements in $G$
Corollary 6.12
Let $|G|=p$ with $p$ a prime number. Then $G$ is cyclic and any $g\in G$ such that $g\not=e$ is a generator
Corollary 6.13
Let $H$ and $K$ be subgroups of a finite group $G$ such that $K\subset H\subset G$. Then $$[G:K]=[G:H][H:K]$$
Proposition 6.15
The group $A_4$ has no subgroup of order 6
Theorem 6.16
Two cycles $\tau$ and $\mu$ in $S_n$ have the same length if and only if there exists a $\sigma\in S_n$ such that $\mu=\sigma\tau\sigma^{-1}$
Euler $\phi$-function
The Euler $\phi$-function is the map $\phi:\mathbb{N}\to\mathbb{N}$ defined by $\phi(n)=1$ for $n=1$, and, for $n>1$, $\phi(n)$ is the number of positive integers $m$ with $1\le m < n$ and $\gcd(m,n)=1$
Theorem 6.18 Euler’s Theorem
Let $a$ and $n$ be integers such that $n>0$ and $\gcd(a,n)=1$. Then $a^{\phi(n)}\equiv1(\mod n)$
Theorem 6.19 Fermat’s Little Theorem
Let $p$ be any prime number and suppise that $p\not|a(p$ does not divide $a$). Then $$a^{p-1}\equiv1(\mod p)$$
Furthermore, for any integer $b, b^p\equiv b(\mod p)$
Algebraic Coding Theory
weight
The weight $w(x)$ of a binary code word $x$ is the number of 1s in $x$, $w(x)=d(x,0)$
Theorem 8.17
Let $x$ and $y$ be binary n-tuples. Then $w(x + y) = d(x, y)$
Theorem 8.18
Let $d_{\min}$ be the minimum distance for a group code $C$. Then $d_{\min}$ is the minimum of all the nonzero weights of the nonzero codewords in $C$. That is
$$d_{\min}=\min{w(x):x\not=0}$$
Theorem 8.21
Let $\mathbb{M}_{m\times n}$ denote the set fo all $m\times n$ matrices with entries in $\mathbb{Z}_2$. We do matrix operations as usual except that all our addition and multiplication operations occur in $\mathbb{Z}_2$. Define the null sppace of a matrix $H\in\mathbb{M}_{m\times n}(\mathbb{Z}_2)$ to be the set of all binary n-tuples $x$ such that $Hx=0$. We denote the null space of a matrix $H$ by Null$(H)$
Let $H$ be in $\mathbb{M}_{m\times n}(\mathbb{Z}_2)$. Then the null space of $H$ is a group code.
Theorem 8.25
If $H\in\mathbb{M}_{m\times n}(\mathbb{Z}_2)$ is a canonical parity-check matrix, then Null$(H)$ consists of all $x\in\mathbb{Z}_2^n$ whose first $n-m$ bits are arbitrary but whose last $m$ bits are determined by $Hx=0$. Each of the last $m$ bits serves as an even parity check bit for some of the first $n-m$ bits. Hence, $H$ gives rise to an $(n,n-m)$-block code
Theorem 8.26
Suppose that $G$ is an $n\times k$ standard generator matrix. Then $C={y:Gx=y for x\in\mathbb{Z}_2^k}$ is an $(n,k)$-block code. More specifically, $C$ is a group code
Lemma 8.27
Let $H=(A|I_m)$ be an $m\times n$ canonical parity-check matrix and $G=(\dfrac{I_{n-m}}{A})$ be the corresponding $n\times(n-m)$ standard generator matrix. Then $HG=0$
Theorem 8.28
Let $H=(A|I_m)$ be an $m\times n$ canonical parity-check matrix and let $G=(\dfrac{I_{n-m}}{A})$ be the $n\times(n-m)$ standard generator matrix associated with $H$. Let $C$ be the code generated by $G$. Then $y$ is in $C$ if and only if $Hy=0$. In particular, $C$ is a linear code with canonical parity-check matrix $H$
Proposition 8.30
Let $e_i$ be the binary n-tuple with a 1 in the ith coordinate and 0’s elsewhere and suppose that $H\in\mathbb{M}_{m\times n}(\mathbb{Z}_2)$. Then $He_i$ is the ith column of the matrix $H$
Theorem 8.31
Let $H$ be an $m\times n$ binary matrix. Then the null space of $H$ is a single error-detecting code if and only if no column of $H$ consists entirely of zeros
Theorem 8.34
Let $H$ be a binary matrix. The null space of $H$ is a single error-correcting code if and only if $H$ does not contain any zero columns and no two columns of $H$ are identical
Proposition 8.36
If $H$ is an $m\times n$ matrix and $x\in\mathbb{Z}_2^n$, then we say that the syndrome of $x$ is $Hx$
Let the $m\times n$ binary matrix $H$ determine a linear code and let $x$ be the received n-tuple. Write $x$ as $x=c+e$, where $c$ is the transmitted codeword and $e$ is the transmission error. The the syndrome $Hx$ of the received codeword $x$ is also the syndrome of the error $e$
Proposition 8.43
Let $C$ be an $(n,k)$-linear code given by the matrix $H$ and suppose that $x$ and $y$ are in $\mathbb{Z}_2^n$. Then $x$ and $y$ are in the same coset of $C$ if and only if $Hx=Hy$. That is, two n-tuples are in the same coset if and only if their syndromes are the same
Isomorphisms
Isomorphism
If $G$ is isomorphic to $H$, we write $G\cong H$. The map $\phi$ is called an isomorphism
Theorem 9.7
All cyclic groups of infinite order are isomorphic to $\mathbb{Z}$
Theorem 9.8
If $G$ is a cylic group of order $n$, then $G$ is isomorphic to $\mathbb{Z}$
Corollary 9.9
If $G$ is a group of order $p$, where $p$ is a prime number, then $G$ is isomorphic to $\mathbb{Z}_p$
Theorem 9.12
Every group is isomorphic to a group of permutations
Proposition 9.13
Let $G$ and $H$ be groups. The set $G\times H$ is a group under the operation $(g_1,h_1)(g_2,h_2)=(g_1g_1,h_1h_2)$ where $g_1,g_2\in G$ and $h_1,h_2\in H$
External Direct Product
The group $G\times H$ is called the external direct product of $G$ and $H$. Notice that there is nothing special about the fact that we have used only two groups to build a new group. The direct product $$\prod^n_{i=1}G_i=G_1\times G_2…G_n$$ of the groups $G_1,G_2…G_n$ is defined in exactly the same manner. If $G=G_1=G_2…G_n$, we often write $G^n$ instead of $G_1\times G_2…G_n$
9.17
Let $(g,h)\in G\times H$, If $g$ and $h$ have finite orders $r$ and $s$ respectively, then the order of $(g,h)$ in $G\times H$ is the least common multiple of $r$ and $s$
Corollary 9.18
Let $(g_1,…,g_n)\in\prod G_i$. If $g_i$ has finite order $r_i$ in $G_i$, then the order of $(g_1,…,g_n)$ in $\prod G_i$ is the least common multiple of $r_1,…,r_n$
Theorem 9.21
The group $\mathbb{Z}_m\times\mathbb{Z}_n$ is isomorphic to $\mathbb{Z}_{mn}$ if and only if $\gcd(m,n)=1$
Corollary 9.22
Let $n_1,…,n_k$ be positive integers. Then $$\prod^k_{i=1}\mathbb{Z}_{n_i}\cong\mathbb{Z}_{n_1…n_k}$$ if and only if $\gcd(n_i,n_j)=1$ for $i\not=j$
Corollary 9.23
If $$m=p_1^{e_1},…,p_k^{e_k}$$ where the $p_is$ are distinct primes, then
$$\mathbb{Z}_{m_{}}\cong\mathbb{Z}_{p_1^{e_1}}\times…\times\mathbb{Z}_{p_k^{e_k}}$$
Internal Direct Products
Internal Direct Product
Let $G$ be a group with subgroups $H$ and $K$ satisfying the following conditions
- $G=HK={hk:h\in H,k\in K}$
- $H\cap K={e}$
- $hk=kh$ for all $k\in K$ and $h\in H$
then $G$ is the internal direct product of $H$ and $K$
Theorem 9.27
Let $G$ be the internal direct product of subgroups $H$ and $K$. Then $G$ is isomorphic to $H\times K$
Theorem 9.28
The group $\mathbb{Z}_6$ is an internal direct product of subgroups $H_i$, where $i=1,2…n$. Then $G$ is isomorphic to $\prod_iH_i$
10 Normal Subgroups and Factor Groups
Normal Subgroups
A subgroup $H$ of a group G is normal in $G$ if $gH=Hg$ for all $g\in G$. That is,a normal subgroup of a group $G$ is one in which the right and left cosets are precisely the same
Theorem 10.3
Let $G$ be a group and $N$ be a subgroup of $G$. Then the following statements are equivalent
- The subgroup $N$ is normal in G
- Forall $g\in G, gNg^{-1}\subset N$
- For all $g\in G, gNg^{-1}=N$
Factor Groups
If $N$ is a normal subgroup of a group $G$, then the cosets of $N$ in $G$ form a group $G/N$ under the operation $(aN)(bN)=abN$. The group is called the factor or quotient group of $G$ and $N$
Theorem 10.4
Let $N$ be a normal subgroup of a group $G$. The cosets of $N$ in $G$ form a group $G/N$ of order $G/N$
Simple Groups
Groups with nontrivial normal subgroups are called simple groups
Lemma 10.8
The alternating group $A_n$ is generated by 3-cycles for $n\ge3$
Lemma 10.9
Let $N$ be a normal subgroup of $A_n$, where $n\ge3$. If $N$ contains a 3-cycle, then $N=A$
Lemma 10.10
For $n\ge5$, every nontrivial normal subgroup $N$ of $A_n$ contains a 3-cycle
Theorem 10.11
The alternating group $A_n$ is simple for $n\ge5$
11 Group Homomorphisms
Homomorphisms
A homomorphism between groups $(G,\cdot)$ and $(H,\circ)$ is a map $\phi:G\to H$ such that $$\phi(g_1\cdot g_2)=\phi(g_1)\circ\phi(g_2)$$ for $g_1,g_2\in G$. The range of $\phi$ in $H$ is called the homomorphic image of $\phi$
Proposition 11.4
Let $\phi:G_1\to G_2$ be a homomorphism of groups. Then
- If $e$ is the identity of $G_1$, then $\phi(e)$ is the identity of $G_2$
- For any element $g\in G_1, \phi(g^{-1})=[\phi(g)]^{-1}$
- If $H_1$ is a subgroup of $G_1$, then $\phi(H_1)$ is a subgroup of $G_2$
- If $H_2$ is a subgroup of $G_2$, then $\phi^{-1}(H_2)-{g\in G_1:\phi(g)\in H_2}$ is a subgroup of $G_1$. Furthermore, if $H_2$ is normal in $G_2$, then $\phi^{-1}(H_2)$ is normal in $G_1$
Kernel
Let $\phi:G\to H$ be a group homomorphism and suppose that $e$ is the identity of $H$. By Proposition 11.4, $\phi^{-1}({e})$ is a subgroup of $G$. This subgroup is called the kernel of $\phi$ and will be denoted by $\ker\phi$
Theorem 11.5
Let $\phi:G\to H$ be a group homomorphism. Then the kernel of $\phi$ is a normal subgroup of $G$
Canonical Homomorphism
Let $H$ be a normal subgroup of $G$. Define the natural or canonical homomorphism $$\phi:G\to G/H$$ by $$\phi(g)=gH$$ This is indeed a homomorphism since $$\phi(g_1g_2)=g_1g_2H=g_1Hg_2H=\phi(g_1)\phi(g_2)$$ The kernel of this homomorphism is $H$
Theorem 11.10 First Isomorphism Theorem
If $\phi:G\to H$ is a group homomorphism with $K=\ker\psi$, then $K$ is normal in $G$. Let $\phi:G\to G/K$ be the canonical homomorphism. Then there exists a unique isomorphism $\eta:G/K\to\psi(G)$ such that $\psi=\eta\phi$
Theorem 11.12 Second Isomorphism Theorem
Let $H$ be a subgroup of a group $G$ (not necessarily normal in $G$) and $N$ a normal subgroup of $G$. Then $HN$ is a subgroup of $G, H\cap N$ is a normal subgroup of $H$, and $$H/N\cap N\cong HN/N$$
Theorem 11.13 Correspondence Theorem
Let $N$ be a normal subgroup of a group $G$. Then $H\mapsto H/N$ is a one-to-one correspondence between the set of subgroups $H$ containing $N$ and the set of subgroups of $G/N$. Furthermore, the normal subgroups of $G$ containing $N$ correspond to normal subgroups of $G/N$
Third Isomorphism Theorem
Let $G$ be a group and $N$ and $H$ be normal subgroups of $G$ with $N\subset H$. Then $$G/H\cong\dfrac{G/N}{H/N}$$