MAT 3343, APPLIED ALGEBRA, FALL 2003

Problem Set 4, due November 4, 2003

Peter Selinger

Problem 1. Recall the definition of Euler’s φ-function: φ(n) is the number of invertible elements in ℤ_{n}. Prove that if p is prime, then φ(p^{k}) = (p − 1)p^{k−1}.

Problem 2. Recall that the Gaussian Integers are the set ℤ[i] of complex numbers of the form a + bi, where a, b ∈ ℤ and i = \sqrt{−1}. In any ring R, we can say that x divides y if there exists some k ∈ R such that kx = y. Find all the divisors of 3 + 4i in ℤ[i].

Problem 3. Let R be a ring with 2 or more elements, which satisfies the cancellation property, i.e., whenever ab = ac and a ≠ 0, then b = c. Prove that R is an integral domain (has no zero divisors).

Problem 4. Let f : ℂ → ℂ be the function on complex numbers defined by f(a + bi) = a − bi. Prove that f is a ring homomorphism.

Problem 5. (a) Find the inverse of the following matrix with respect to the base field ℤ_{5}.

( \begin{matrix}0 & 1 & 2 & 3 \\ 1 & 0 & 4 & 0 \\ 0 & 2 & 1 & 3 \\ 1 & 4 & 2 & 1 \end{matrix} )

(b) Solve the following system of equations in ℤ_{3}. What is the most general solution?

\begin{aligned}2x + 1y + 0z + 1w & = & 2 \\ 1x + 0y + 2z + 0w & = & 1 \\ 0x + 1y + 2z + 2w & = & 1 \\ 1x + 2y + 0z + 1w & = & 0 \end{aligned}

Problem 6. Consider the (7, 4)-Hamming code with the following generator matrix G and parity check matrix H:

G = ( \begin{matrix}1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{matrix} ) H = ( \begin{matrix}1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} )

(a) Encode the message 0101 1100 1001 0000 1110 using this code.

(b) Decode the message 1100110 1100011 1111000 0111110 1010101, correcting all single-bit errors. What is the syndrome of each codeword?

Problem 7. The (15, 11)-Hamming code has parity check matrix

H = ( \begin{matrix}1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix} )^{T} .

Find the generator matrix for this code. Encode the message 01010101010 11101110111. Find the syndrome of 1000100010001000 and decode.