Chapter 02 Groups and Vector Spaces

2.1

A group can be constructed by using the rotations and reflections of a regular pentagon into itself. The group operator is “followed by” (e.g., a reflection $𝜌$ “followed by” a rotation $r$). This is a permutation group, as in Example 2.14.

(a) How many elements are in this group?

There are $5$ different rotations and $5$ different reflections along each vertex of the pentagon. So there are 10 elements in this group.

$\square$

(b) Construct the group (i.e., show the “multiplication table” for the group).

$*$	$e$	$r_1$	$r_2$	$r_3$	$r_4$	$s_0$	$s_1$	$s_2$	$s_3$	$s_4$
$e$	$e$	$r_1$	$r_2$	$r_3$	$r_4$	$s_0$	$s_1$	$s_2$	$s_3$	$s_4$
$r_1$	$r_1$	$r_2$	$r_3$	$r_4$	$e$	$s_1$	$s_2$	$s_3$	$s_4$	$s_0$
$r_2$	$r_2$	$r_3$	$r_4$	$e$	$r_1$	$s_2$	$s_3$	$s_4$	$s_0$	$s_1$
$r_3$	$r_3$	$r_4$	$e$	$r_1$	$r_2$	$s_3$	$s_4$	$s_0$	$s_1$	$s_2$
$r_4$	$r_4$	$e$	$r_1$	$r_2$	$r_3$	$s_4$	$s_0$	$s_1$	$s_2$	$s_3$
$s_0$	$s_0$	$s_4$	$s_3$	$s_2$	$s_1$	$e$	$r_4$	$r_3$	$r_2$	$r_1$
$s_1$	$s_1$	$s_0$	$s_4$	$s_3$	$s_2$	$r_1$	$e$	$r_4$	$r_3$	$r_2$
$s_2$	$s_2$	$s_1$	$s_0$	$s_4$	$s_3$	$r_2$	$r_1$	$e$	$r_4$	$r_3$
$s_3$	$s_3$	$s_2$	$s_1$	$s_0$	$s_4$	$r_3$	$r_2$	$r_1$	$e$	$r_4$
$s_4$	$s_4$	$s_3$	$s_2$	$s_1$	$s_0$	$r_4$	$r_3$	$r_2$	$r_1$	$e$

skip

(c) Is it an Abelian group?

Solution: No.

$r_1 s_0 = s_1$ and $s_0 r_1 = s_4$.

$\{0,1,2,3,4\} \rightarrow \{4,0,1,2,3\} \rightarrow \{4,3,2,1,0\}$

(d) Find a subgroup with five elements and a subgroup with two elements.

Solution: The rotations forms five elements. One of the reflections and $0$ forms two elements.

$\square$

2.10

An automorphism of a group $G$ is an isomorphism of the group with itself, $\phi: G \to G$. Using Exercise 2.9, how many automorphisms are there of $\mathbb{Z}_2$? of $\mathbb{Z}_6$? of $\mathbb{Z}_8$? of $\mathbb{Z}_{17}$?

Solution:

Because all these groups are cyclic group, so we just need to consider $\phi(1)$.

For $\mathbb{Z}_2$, there is only one case for automorphism, i.e. $\phi(1) = 1$.

For $\mathbb{Z}_6$, there are 2 cases for automorphism, i.e. $\phi(1) = 1, 5$.

For $\mathbb{Z}_8$, there are 4 cases for automorphism, i.e. $\phi(1) = 1,3,5,7$.

For $\mathbb{Z}_17$, there are 16 cases for automorphism, i.e. $\phi(1) = 1,\cdots,16$.

$\square$

2.11 [144]

Let $G$ be a finite Abelian group of order $n$, and let $r$ be a positive integer relatively prime to $n$ (i.e., they have no factors in common except $1$). Show that the map $\phi_r ∶ G → G$ defined by $\phi_r(a) = a^r$ is an isomorphism of $G$ onto itself (an automorphism). Deduce that the equation $x^r = a$ always has a unique solution in a finite Abelian group $G$ if $r$ is relatively prime to the order of $G$.

Proof:

First, we will show that we cannot find $a \in G$ and $a \neq e$ such that $a^r = e$.

Consider the following $n+1$ elements

$$a^0 = e, a, a^2, \cdots, a^n$$

Since $|G|=n$, there must be 2 elements satisfy $a^i = a^j$, with $i < j$. As a result $a^{j-i}=e$.

Let $m$ be the order of $a$, then we know $m \leq j-i \leq n$.

Since $a^0, a, \cdots, a^{m-1}$ forms a subgroup, then from the Lagrange’s Theorem, we know $m \mid n$.

Since $(r,n) = 1$, then we have $(r,m) = 1$. So $m \nmid r$.

Let $r' \equiv r (\text{mod } m)$, then $0 < r' < m$. So $a^r = a^{r'} \neq e$.

Then assume $a^r = b^r$, since $G$ is Abelian, we have $(a b^{-1})^r = e$. From the discussion above, $a b^{-1} = e$, so $a = b$.

This means $\phi_r$ is injective. Since $G$ is a finite group, it means $\phi_r$ is also surjective.

Then $\phi_r$ is one-to-one.

Furthermore, since $G$ is Abelian

$$\begin{align*} \phi_r(ab) &= (ab)^r \\ &= a^r b^r \\ &= \phi_r(a) \phi_r(b) \end{align*}$$

So $\phi_r$ is an isomorphism.

Since $\phi_r$ is one-to-one, given any $x \in G$, we can find unique $a$ such that $\phi_r(a) = x$, i.e. $a^r = x$.

A proof from AI:

Since $\gcd(r, n) = 1$, there exist integers $s$ and $t$ such that: $rs + nt = 1$

Now, suppose $\phi_r(a) = \phi_r(b)$, which means $a^r = b^r$. Raise both sides to the power of $s$: $(a^r)^s = (b^r)^s \implies a^{rs} = b^{rs}$

Using Bezout's identity, we can substitute $rs = 1 - nt$: $a^{1 - nt} = b^{1 - nt}$ $a \cdot (a^n)^{-t} = b \cdot (b^n)^{-t}$

By Lagrange's Theorem (or a corollary of it), the order of any element divides the order of the group, so $a^n = e$ and $b^n = e$ for all elements in $G$. $a \cdot (e)^{-t} = b \cdot (e)^{-t}$ $a = b$

This directly proves injectivity without needing to explicitly define the order $m$ of the element or use modulo arithmetic.

$\square$

2.18

Consider the set $S = \{0,1,2,3\}$ with the operations

$+$	$0$	$1$	$2$	$3$
$0$	$0$	$1$	$2$	$3$
$1$	$1$	$2$	$3$	$0$
$2$	$2$	$3$	$0$	$1$
$3$	$3$	$0$	$1$	$2$

$\cdot$	$0$	$1$	$2$	$3$
$0$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$2$	$3$
$2$	$0$	$2$	$3$	$1$
$3$	$0$	$3$	$1$	$2$

Is this a field? If not, why not?

Solution:

Consider the F11 Multiplication distributes over addition: $a \cdot (b +c) = a \cdot b +a \cdot c$

Let $a = 2, b = 2, c = 3$

$$2 \cdot (2 + 3) = 2 \cdot 1 = 2$$

And

$$a \cdot b +a \cdot c = 2 \cdot 2 + 2 \cdot 3 = 3 + 1 = 0$$

So it violates the F11, then it's not a field.

$\square$

2.20

Use the representation of $GF(4)$ in (2.4) to solve the following pair of equations:

$$2x + y = 3 \\ x + 2y = 3 \\ $$

Solution

We first add them together and get

$$3(x+y) = 3+3 = 0$$

So $x+y = 0$. Also $2(x+y)=0$.

We add it to the first equation and get $(2+2)x + (1+2)y = 0x + 3y = 3y = 3$. So $y = 1$, similarly, $x = 1$.

$\square$

2.24

Let $V$ be a vector space, and let $W \subset V$ be a subspace. The dual space $W^\perp$ of $W$ is the set of vectors in $V$ which are orthogonal to every vector in $W$. Show that the dual space $W^\perp$ is a subspace of $V$.

Proof:

Assume $u,v \in W^\perp$, $w \in W$, then

First $⟨0,w⟩ = 0$. So $0 \in W^\perp$.

Also

$$⟨u+v,w⟩ = ⟨u,w⟩+⟨v,w⟩ = 0 + 0 = 0$$

Also

$$⟨ku,w⟩ = k ⟨u,w⟩ = k0 = 0$$

So $W^\perp$ is a subspace of $V$.

$\square$

2.25

Show that the set of binary polynomials (i.e., polynomials with binary coefficients, with operations in $GF(2)$) with degree less than $r$ forms a vector space over $GF(2)$ with dimension $r$.

Solution:

Let $𝒫_{r-1}(GF(2))$ be the set.

Since the constant $0$ has degree $-\infty$ which is less than $r$, so $0 \in 𝒫_{r-1}(GF(2))$.

Next, if

$$p_1(z) = a_0 + a_1 z + \cdots + a_{r-1} z^{r-1} \\ p_2(z) = b_0 + b_1 z + \cdots + b_{r-1} z^{r-1} \\ $$

Then

$$p_1(z) + p_2(z) = \\ (a_0+b_0) + (a_1+b_1) z + \cdots + (a_{r-1}+b_{r-1}) z^{r-1}$$

Its degree is still less than $r$.

Also

$$k p_1(z) = ka_0 + ka_1 z + \cdots + ka_{r-1} z^{r-1}$$

Its degree is still less than $r$.

So $𝒫_{r-1}(GF(2))$ is a vector space.

Now we need to prove it's dimension is $r$.

Consider the following $r$ polynomials

$$1, z, \cdots, z^{r-1}$$

First, if

$$a_0 + a_1 z + \cdots + a_{r-1} z^{r-1} = 0$$

Then $a_0 = a_1 = \cdots = a_{r-1} = 0$.

So they are linear independent.

Also for any binary polynomial with degree less than $r$, it can be represented as the linear combination of $1, z, \cdots, z^{r-1}$.

So it's a basis of $𝒫_{r-1}(GF(2))$.

So $\dim 𝒫_{r-1}(GF(2)) = r$.

$\square$

2.26

What is the dimension of the vector space spanned by the vectors

$$\{(1,1,0,1,0,1),(0,1,0,1,1,1),(1,1,0,0,1,1),(0,1,1,1,0,1),(1,0,0,0,0,0)\}$$

over $GF(2)$?

Solution:

Assume

$$\begin{align*} v_1 = (1,1,0,1,0,1) \\ v_2 = (0,1,0,1,1,1) \\ v_3 = (1,1,0,0,1,1) \\ v_4 = (0,1,1,1,0,1) \\ v_5 = (1,0,0,0,0,0) \\ \end{align*}$$

We will prove they are independent.

Assume $a_1 v_1 + \cdots + a_5 v_5 = 0$

We have

$$\begin{align*} a_1 + a_3 + a_5 &= 0 & (1)\\ a_1 + a_2 + a_3 + a_4 &= 0 & (2)\\ a_4 &= 0 & (3)\\ a_1 + a_2 + a_4 &= 0 & (4)\\ a_2 + a_3 &= 0 & (5)\\ \end{align*}$$

From $(2)(3)(5)$, we have $a_1 = a_4 = 0$. Then from (4), we have $a_2 = 0$, then from (5), $a_3 = 0$. Then from $(1)$, we have $a_5 = 0$.

$\square$

2.27

Find a basis for the dual space to the vector space spanned by

$$\{(1,1,1,0,0),(0,1,1,1,0),(0,0,1,1,1)\}$$

Solution:

First note, these 3 vectors are linear independent. That means the dimension of the dual space is $2$.

Assume $(a_1, \cdots, a_5)$ is orthogonal to these 3 vectors.

Then we have

$$\begin{align*} a_1 + a_2 + a_3 &= 0 \\ a_2 + a_3 + a_4 &= 0 \\ a_3 + a_4 + a_5 &= 0 \\ \end{align*}$$

we have

$$\begin{align*} a_1 &= a_4 \\ a_2 &= a_5 \\ \end{align*}$$

Consider the following 2 vectors.

$$(1,0,-1,1,0), (0,1,-1,0,1)$$

Note they are independent, then they are a basis of the dual space.

$\square$

2.29

Is it true that if 𝐱,𝐲 and 𝐳 are linearly independent vectors over $GF(q)$ then so also are 𝐱 +𝐲, 𝐲 +𝐳 and 𝐳 +𝐱?

Proof: We will give an counterexample for $GF(2)^3$.

Assume

$$x = (1,0,0) \\ y = (0,1,0) \\ z = (0,0,1) \\ $$

Then

$$\begin{align*} x+y &= (1,1,0) \\ y+z &= (0,1,1) \\ z+x &= (1,0,1) \\ \end{align*}$$

Then $(x+y) + (y+z) + (z+x) = (0,0,0)$, so they are linear dependent.

$\square$

2.33

In this exercise, let $𝐱⋅ 𝐲$ denote the inner product over the real numbers. Let $𝐱$ and $𝐲$ be vectors of length $n$ with elements from the set $\{−1,1\}$. Show that

$$d_H (𝐱,𝐲) = \frac{n−𝐱⋅𝐲}{2}.$$

Proof:

Let

$$𝐱 = (x_1, \cdots, x_n) \\ 𝐲 = (y_1, \cdots, y_n) \\ $$

$$\begin{align*} d_H(𝐱,𝐲) &= \frac{1}{4} (\sum_{i = 1}^{n} (x_i - y_i)^2) \\ &= \frac{1}{4} (\sum_{i = 1}^{n} x_i^2 + \sum_{i = 1}^{n} y_i^2 - 2 \sum_{i = 1}^{n} x_i y_i ) \\ &= \frac{1}{4} ( 2n - 2 𝐱⋅𝐲 ) \\ &= \frac{n - 𝐱⋅𝐲}{2} \end{align*}$$

$\square$