Algebra II MATH 251 Instructor: Dr. E. Goren.

Assignment 1

To be submitted by January 17, 12:00

In this assignment 𝔽 is a field and V is a vector space over 𝔽.

1. Subspace. Prove that a subspace W of V (namely, a non-empty subset W of V with the properties:

(i) w_{1}, w_{2} ∈ W implies w_{1} + w_{2} ∈ W, (ii) w ∈ W, α ∈ 𝔽 implies αw ∈ W) is a vector space under the operations induced from V.

2. Inclusion. Let W_{1} and W_{2} be subspaces of V. Prove that if W_{1} ∪ W_{2} is a subspace of V then W_{1} ⊂ W_{2} or W_{2} ⊂ W_{1}.

3. Intersection. Let W_{1} and W_{2} be subspaces of V. Prove that W_{1} ∩ W_{2} is a subspace of V.

4. Direct sum.^{1} Let V and W be vector spaces over 𝔽. Define the direct sum of V and W as

V ⊕ W = {(v, w) : v ∈ V, w ∈ W }.

Verify that V ⊕ W is a vector space over 𝔽 where we define:

(v, w) + (v′, w′) = (v + v′, w + w′), α(v, w) = (αv, αw).

5. Let V be a vector space over 𝔽 and let S ⊂ V be a non-empty set. Let v ∈ V. Prove that

Span(S ∪ {v}) = Span(S) ⟺ v ∈ Span(S).

6. Find which 2 of the following sets of vectors in ℝ^{3} have the same span:

(i) {(1, 0, 1), (2, 3, 2), (−1, −3, −1)};

(ii) {(3, −2, 3), (1, 1, 1)};

(iii) {(1, 0, 0), (0, 0, 1), (0, 1, 0)}.

7. Rudiments of Coding Theory I. In this exercise 𝔽 is a finite field having q elements, for example ℤ/pℤ that has p elements.^{2} Let V = 𝔽^{n}. Thus, an element of V is just an n-tuple (x_{1}, …, x_{n}) where each coordinate x_{i} is an element of 𝔽. Define a distance function d(x, y) on V as follows. If x and y are vectors

d(x, y) = the number of coordinates in which x and y differ.

For example: if n = 6, x = (1, 1, 0, 0, 1, 0) and y = (1, 1, 1, 0, 0, 0) then d(x, y) = 2. This distance is called the Hamming distance^{3}. Prove that:

(1) d(x, y) ≥ 0 with equality holding if and only if x = y;

(2) d(x, y) ≤ d(x, z) + d(z, y) for every x, y, z ∈ V (the Triangle Inequality). We also call d(x, 0), where 0 is the zero vector, the Hamming weight of x; it is equal to the number of non zero coordinates of x.

1If V and W happen to be both subspaces of some vector space U then there are two possible constructions V ⊕ W and V + W as defined in class. These are different constructions. Later on you’ll see that the relation between the two concepts is expressed by a surjective linear map V ⊕ W ⟶ V + W with kernel V ∩ W.

2We use the notation ℤ/nℤ for the ring of integers (mod n), which some denote by ℤ_{n}. A good case to keep in mind in this exercise is 𝔽 = ℤ/2ℤ = {0, 1}.

3After the scientist Richard W. Hamming.

Coding theory has nothing to do with concealing information. It is rather the science of transmitting information over noisy, or defective, channels. This could either your telephone line when you connect to the internet, or a rover transmitting to NASA from Mars. The purpose in each case is to find some means to ensure that the receiving side either receives the correct information or is able to reconstruct it from the information it does receive, if it is not too corrupted. Assume that the original message, that consists of “words” (or chunks of information) of some fixed length, is written as a string of zeros and ones. For example, suppose that 𝔽 = ℤ/2ℤ, we might be interested in sending the following information

01 11 01 10 00 …

(This might mean “all is well, tell mom I’ll be back for supper”). To do that we have a “code”. A code is like a dictionary that substitutes for each original word a longer word and it is that longer word that is being transmitted. The receiving side has the same code (or dictionary) and has no problem translating longer words to the original words. The logic is, in a sense, that longer words are more “robust” and can be recognized even if distorted.

For example, our code could be the subspace of 𝔽^{3} consisting of all vectors (x_{1}, x_{2}, x_{3}) such that x_{1} + x_{2} + x_{3} = 0. There are q^{2} such code words in this code. We translate each original word (i.e., 00, 01, 10, 11) to a code word by adding the unique third digit that makes the sum zero. Therefore, our original message is now written as

011 110 011 101 000 …

This code is called a parity check code. The receiver gets the message and checks if every word belongs to the code by checking in this example that the sum of digits is zero. Thus, if 111 is received, we know there is an error because the digits sum up to 1 in the field ℤ/2ℤ.

Definition 1. An (n, k) linear code C is a subspace of 𝔽^{n} having q^{k} elements.

Show that the minimal distance between two distinct elements of a code C is the minimal weight of a non-zero vector. Namely:

min{d(x, y) : x ≠ y, x ∈ C, y ∈ C} = min{d(x, 0) : x ∈ C}.

The procedure of coding continues as follows. The transmitting side is sending words that belong to an (n, k) code C that is known to the receiving side and sends only such words. The receiving side receives vectors of 𝔽^{n}. Each such vector may be in C (i.e., if no errors occurred, or if errors did occur but the erroneous vector happens to belong to C as well). In case it isn’t, the receiving side looks for the word in C that is closest to the vector that was received.

We say that a linear code corrects t errors if for every code word that is transmitted with t or less errors the original code word is the unique element of the code C which is the nearest to it. We say that a linear code detects t errors if every received word with at least one, but no more that t errors, is not a code word. Prove the following Theorem

Theorem 2. A linear code C corrects t errors if and only if the Hamming distance of every two elements of C is at least 2t + 1.

A linear code C detects t errors if and only if the Hamming distance between any two elements of C is at least t + 1.

For example, in the parity check code, the Hamming distance of every non zero vector is precisely 2. Thus, the code detects single errors and corrects none. This illustrate the fact that we can tell that 111 is an error, but cannot determine if the original word was 101 or 011.