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

Assignment 3

To be submitted by January 31, 12:00 In this assignment V and W are vector spaces over a field 𝔽. The space 𝔽[x]_{n} is the vector space over 𝔽 of polynomials of degree less than n.

1. Which of the following functions is a linear map? (provide proof):

(1) T : ℝ^{2} ⟶ ℝ^{2}, T (x, y) = (3x − 2y, x + y).

(2) T : ℝ^{2} ⟶ ℝ^{2}, T (x, y) = (x^{2} − y, x + y + 1).

(3) T : ℝ[x]_{3} ⟶ ℝ^{2}, T (f(x)) = (f(1), f′(1)).

(4) T : ℝ[x]_{3} ⟶ ℝ[x]_{4}, T (f(x)) = xf(x) + f(1). In each case where T is a linear map, find its kernel.

2. Let T : V ⟶ W be a surjective linear map. Prove that if dim(V) = dim(W) then T is an isomorphism.

3. Nilpotent operators. Let T : V ⟶ V be a nilpotent linear operator.^{1} Prove that if n = dim(V) then T^{n} ≡ 0. Show that for every n ≥ 2 there exists a vector space V of dimension n and a nilpotent linear operator T : V ⟶ V such that T^{n−1} ≢ 0.

4. Direct sum. (a) Let U and W be subspaces of a vector space V. Recall that we say that V is an (internal) direct sum of U and W, and denote it by V = U ⊕ W, if V = U + W and U ∩ W = {0}. Show that V = U ⊕ W (internal direct sum) iff every vector v ∈ V may be written uniquely in the form

v = u + w, u ∈ U, w ∈ W.

(b) Take V = ℝ^{3}. Let

U_{1} = Span \{( \begin{matrix}1 \\ 2 \\ 5 \end{matrix} ) , ( \begin{matrix}4 \\ 1 \\ 0 \end{matrix} )\} , U_{2} = Span \{( \begin{matrix}1 \\ 4 \\ 3 \end{matrix} )\} , U_{3} = \{( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \end{matrix} ) : x_{1} − x_{2} + x_{3} = 0\} .

For each pair of subspaces among U_{1}, U_{2}, U_{3} determine whether ℝ^{3} is their direct sum or not.

5. (a) Find a linear map T : ℝ^{3} ⟶ ℝ^{3} whose image is generated by (1, 2, 3) and (3, 2, 1). Here ‘find’ means represent by a matrix with respect to the standard basis.

(b) Find a linear map T : ℝ^{4} ⟶ ℝ^{3} whose kernel is generated by (1, 2, 3, 4), (0, 1, 0, 1).

1One often calls a linear transformation from a vector space to itself a ‘linear operator’.

6. Coding theory. How do we construct codes?

Fix a pair of positive integers (n, k) such that n ≥ k. Let 𝔽 a finite field. Consider the vector space 𝔽^{n} as column vectors of length n. Consider an n × k matrix A with entries in 𝔽. Then A defines a linear transformation

T : 𝔽^{k} ⟶ 𝔽^{n}, T ( ⋮_{a_{k}}^{a_{1}} ) = A ( ⋮_{a_{k}}^{a_{1}} ) .

Assume now that the first k rows of A just consist of the k standard basis vectors of 𝔽^{k}. For example for n = 4 and k = 3, the matrix A could be taken to be

(\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ ∗ & ∗ & ∗ \end{matrix})

(where the ∗ are any elements of 𝔽). We call such matrix a standard n × k generator matrix.

(i) Show that the image of T is a linear (n, k) code (called a systematic (n, k) code) and explain how to decode a message.

(ii) Consider a particular case where n = k +1. Let A be a standard (k +1, k) generator matrix whose last row consists of −1’s. For example, for (4, 3) we get the matrix

(\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ −1 & −1 & −1 \end{matrix}) .

The code we obtain is called a parity check code. Indeed, prove that the code word assigned to a vector

( ⋮_{a_{k}}^{a_{1}} ) is of the form ( a_{1} ; ⋮ ; a_{k} ; α ) where α = −(a_{1} + ⋯ + a_{k}) (so if 𝔽 = ℤ/2ℤ then α = 0 if the vector

( ⋮_{a_{k}}^{a_{1}} ) has an even number of 1’s, and α = 1 if the vector ( ⋮_{a_{k}}^{a_{1}} ) has an odd number of ones. Hence

the name). Prove that the linear code we obtain is precisely the set of vectors (a_{1}, …, a_{k+1})in 𝔽^{k+1} with the property that the sum of their coordinates is zero. Hence, we may check easily if a word is a code word or not by adding its coordinates. This, code, simple as it is, is one of the most widely used, e.g., in transferring files using modems. Find how many errors this code detects and how many errors it corrects.

(iii) (Bonus question = 15%) The most naive way to try and transmit a message clearly is by repeating everything twice. The most naive way to try and transmit a message clearly is by repeating everything twice. Namely, we are using the standard (2k, k) generator matrix ( \begin{matrix}I_{k} \\ I_{k} \end{matrix} ). How many errors does this detect? correct? Is there a (2k, k) standard code that does better?