CMSC 442/653 Section 0101, Fall 2007

SOLUTIONS TO HOMEWORK 3

Dr. Lomonaco

TA: Don Dimitroff

1U) Consider the following degree 4 irreducible polynomial p(x) given in Peterson’s Table of Irreducible Polynomials over GF(2): DEGREE 4 … 3 37D …

a) Write down p(x):

3  0117  111Hence:

b) Since p(x) is irreducible and of degree 3, it follows that:GF(24) = GF(2)[x] mod p(x)

List all of the elements of GF(24) in the above representation, i.e., in terms of ξ = x mod p(x)

ξ+1

ξ2

ξ2+1

ξ2+ ξ

ξ2+ ξ+1

ξ3

ξ3+1

ξ3+ξ

ξ3+ξ+1

ξ3+ξ2

ξ3+ξ2+1

ξ3+ξ2+ξ

ξ3+ξ2+ξ+1

c) Let ξ = x mod p(x). Why is {ξ2} not a complete list of all the non-zero elements of GF(24)?

Let ξ = x mod x4 + x3 + x2 + x + 1

That is: x4 + x3 + x2 + x + 1 ≠ 0

Or:ξ4 + ξ3 + ξ2 + ξ + 1 = 0

Hence:ξ4 = ξ3 + ξ2 + ξ + 1GF(2) = {0, 1}

ξ-∞ = 0

ξ0 = 1

ξ1 = ξ

ξ2 = ξ2

ξ3 = ξ3

ξ4 = ξ3 + ξ2 + ξ + 1

ξ5 = ξ (ξ3 + ξ2 + ξ + 1) = ξ4 + ξ3 + ξ2 + ξ = 2ξ3 + 2ξ2 + 2ξ + 1 = 1

The calculations in part (b) above demonstrate that ξ is not a primitive element. Hence p(x) must not be a primitive polynomial. Only primitive polynomials would generate the complete list.

2U) Consider the following matrix over GF(2)

0 1 1 0 1

M = 1 0 0 11

0 0 1 1 1

1 1 0 0 1

a) Prove that the rows of M are linearly dependent:

First put the matrix into row-echelon form (detail steps no shown)

1 0 0 11

M = 1 1 0 0 1

0 1 1 0 1

0 0 1 1 1

Next combine rows: row1 + row2  row2

1 0 0 11

M = 0 1 0 1 0

0 1 1 0 1

0 0 1 1 1

Finally combine rows: row2 + row3  row3

1 0 0 11

M = 0 1 0 1 0

0 0 1 1 1

Since rows 3 and 4 are identical, the matrix M had rows that are linearly dependent.

1 0 0 11

M = 0 1 0 1 0

0 0 1 1 1

b) Prove that the first three rows of M form a basis for the row space of M.

Using the last matrix from part (a) above, combine row3 + row4  row4

1 0 0 11

M = 0 1 0 1 0

0 0 1 1 1

0 0 0 0 0

Eliminate the last row since it is all zeros. Call this matrix M’

1 0 0 11

M’ = 0 1 0 1 0

0 0 1 1 1

The above matrix, M’, can be produced by using just the first three of M. Also, the rows of M’ are linearly independent, because the only combination of them: a1(10011)+a2(01010)+a3(00111) that will produce the zero vector is the trivial combination where all of coefficients are zero. Finally, the row space of M is the same as that of M’ (details not shown). Both M and M’ have the same span.

c) What is the dimension of the row space of M? Explain your answer.

Since the basis of M is M’ and M’ has three rows, then the dimension of M is 3.

3U) Consider the following matrix over GF(3)

0 0 22 0 2

S = 22 0 2 1 2

1120 2 2

1 1 0 12 1

a) Put the matrix into echelon canonical form.

Combine: row2 + row4  row2

0 0 2 2 0 2

S = 0 0 0 0 0 0

1 1 2 0 2 2

1 1 0 1 2 1

Compute:½ * row1  row1

0 0 11 0 1

S = 0 0 0 0 0 0

1 1 2 0 2 2

1 1 0 1 2 1

Compute:row1 + row3  row3

0 0 11 0 1

S = 0 0 0 0 0 0

1 1 01 2 0

1 1 0 1 2 1

Eliminate zero rows and rearrange rows (individual steps not shown).

1 1 01 2 0

S = 0 0 11 0 1

00 0 00 1

b) Use the resulting echelon canonical form to find a basis for the row space of S. Explain your answer.

As it turns out, the echelon canonical form from part (a) above is the basis.

1 1 01 2 0

S’ = 0 0 11 0 1

00 0 001

Both the original matrix S and the echelon form matrix S’ have the same span.

c) What is the dimension of the row space of S? Explain how you found your answer.

The dimension of the row space of S is 3, because the dimension of the vector space is equivalent to the cardinality of the basis.