Algebra II 189-251B Instructor: Dr. E. Goren.

Assignment 3

To be submitted by February 2, 12:00 In this assignment V and W are vector spaces over a field 𝔽.

1. Let B = {s_{1}, …, s_{n}} be a basis for V and let C = {t_{1}, …, t_{n}} be any subset of W. Show that there is a unique linear map T : V ⟶ W such that

T (s_{i}) = t_{i}, i = 1, …, n.

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. 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_{4} + x_{3} = 0\} .

For each pair of subspaces among U_{1}, U_{2}, U_{3} determine whether ℝ^{3} is their direct sum or not. (c) Find a 3 × 3 real matrix A such that the transformation T : ℝ^{3} ⟶ ℝ^{3}, defined by

T v = Av,

is a projection on U_{1} along the z-axis (i.e., the kernel is the z-axis).

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).

6. Rudiments of coding theory II. How do we construct codes?

Fix a pair of positive integers (n, k). Let 𝔽 = ℤ/2ℤ be the field of two elements. 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}} ) .

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

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 k × n 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 α = 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. Prove that the linear code we obtain is precisely the

set of vectors in 𝔽^{k+1} with even number of 1’s. Hence, we may check if a word is a code word or not by checking whether it has an even number of 1’s or not. Find how many errors this code detects and how many errors it corrects.

(iii) 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?