Mathematics 243, section 3 – Algebraic Structures Solutions for Problem Set 3 due: September 21, 2012

‘A’ Section

1. Let A = {a, b, c}. In class we discussed the set S(A) of permutations of A, and we wrote

S(A) = {I_{A}, R_{a}, R_{b}, R_{c}, C_{1}, C_{2}}  (1)

where the R’s were mappings that fixed one element and swapped the other two, and the C’s were the cyclic permutations. For instance R_{a}(a) = a, R_{a}(b) = c, and R_{a}(c) = b and C_{1}(a) = b, C_{1}(b) = c and C_{1}(c) = a. We know that ∘ defines a binary operation on S(A) by results from class on September 14 and 17. Make the operation table for ∘ on this set, showing the results of composing all pairs of elements of S(A), listing the labels for the rows and columns in the order given in Eq. (1) above.

Solution: For example, R_{a} ∘ C_{1} is the mapping given by

(R_{a} ∘ C_{1})(a) = R_{a}(C_{1}(a)) = R_{a}(b) = c
(R_{a} ∘ C_{1})(b) = R_{a}(C_{1}(b)) = R_{a}(c) = b
(R_{a} ∘ C_{1})(c) = R_{a}(C_{1}(c)) = R_{a}(a) = a.

This says R_{a} ∘ C_{1} = R_{b}. The rest of the table fills in like this:

\begin{matrix}∘ & I & R_{a} & R_{b} & R_{c} & C_{1} & C_{2} \\ I & I & R_{a} & R_{b} & R_{c} & C_{1} & C_{2} \\ R_{a} & R_{a} & I & C_{1} & C_{2} & R_{b} & R_{c} \\ R_{b} & R_{b} & C_{2} & I & C_{1} & R_{c} & R_{a} \\ R_{c} & R_{c} & C_{1} & C_{2} & I & R_{a} & R_{b} \\ C_{1} & C_{1} & R_{c} & R_{a} & R_{b} & C_{2} & I \\ C_{2} & C_{2} & R_{b} & R_{c} & R_{a} & I & C_{1} \end{matrix}

2. Let

A = (\begin{matrix}1 & 1 & −1 \\ −2 & 3 & 0 \end{matrix}) , B = (\begin{matrix}1 \\ 7 \\ 3 \end{matrix}) , C = (\begin{matrix}3 & −3 & −4 \\ 1 & −8 & 2 \\ 0 & 1 & 4 \end{matrix}) , D = (\begin{matrix}4 & 3 & 3 \\ 5 & 0 & −2 \end{matrix}) .

Perform the indicated matrix operations, if possible. If the operation is not possible, say why not.

(a) A + D Solution: This sum is defined because A and D are both 2 × 3 matrices:

A + D = (\begin{matrix}5 & 4 & 2 \\ 3 & 3 & −2 \end{matrix})

(b) AC Solution: This product is defined since the number of rows in C is 3, which is the same as the number of columns in A. The product is the 2 × 3 matrix

AC = (\begin{matrix}4 & −12 & −6 \\ −3 & −18 & 14 \end{matrix})

(c) AD + A Solution: The product AD does not exist since the number of rows in D is 2 but the number of columns in A is 3. This means that AD + A is not defined either.

(d) CB + AB Solution: The product CB is 3 × 1, but the product AB is 2 × 1. This means that CB cannot be added to AB.

3. Let S be the following set of matrices in M_{3×3}(ℝ):

S = {I_{3}, F_{x}, F_{y}, F_{z}, G_{1}, G_{2}},  (2)

where I_{3} is the 3 × 3 identity matrix,

F_{x} = (\begin{matrix}1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}) , F_{y} = (\begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}) , F_{z} = (\begin{matrix}0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}) ,

and

G_{1} = (\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) , G_{2} = (\begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix}) .

Show that matrix multiplication defines a binary operation on this set S by constructing an operation table showing the results of doing all possible products of pairs of elements in S. Label the rows and columns in the order given in Eq. (2) above. Do you notice something about this table and the one in question 1?

\begin{matrix}· & I & F_{x} & F_{y} & F_{z} & G_{1} & G_{2} \\ I & I & F_{x} & F_{y} & F_{z} & G_{1} & G_{2} \\ F_{x} & F_{x} & I & G_{1} & G_{2} & F_{y} & F_{z} \\ F_{y} & F_{y} & G_{2} & I & G_{1} & F_{z} & F_{x} \\ F_{z} & F_{z} & G_{1} & G_{2} & I & F_{x} & F_{y} \\ G_{1} & G_{1} & F_{z} & F_{x} & F_{y} & G_{2} & I \\ G_{2} & G_{2} & F_{y} & F_{z} & F_{x} & I & G_{1} \end{matrix}

In the table from problem 1, if you replace R_{a} ↦ F_{x}, R_{b} ↦ F_{y}, R_{c} ↦ F_{z}, C_{1} ↦ G_{1}, and C_{2} ↦ G_{2}, you get the table here. This says that the two sets and binary operations have the “same structure,” even though they are different and the operations are defined differently. We will return to this idea later in the course.

‘B’ Section

1. Let A be a set and f, g ∈ S(A) be permutations.

(a) Show that (f^{−1})^{−1} = f as mappings on A.

Solution: By the definition of the inverse mapping, we have

f ∘ f^{−1} = I_{A} = f^{−1} ∘ f.

By theorems we proved in class we know that every element of S(A) has an inverse for the ∘ operation. Moreover by problem B 2 from Problem Set 2, we know that inverses are unique. The equation above says that the inverse of f^{−1} must be f, or in other words, (f^{−1})^{−1} = f.

(b) Show that (f ∘ g)^{−1} = g^{−1} ∘ f^{−1} as mappings on A.

Solution: By associativity of composition and the fact that I_{A} is an identity for composition, we have

(f ∘ g) ∘ (g^{−1} ∘ f^{−1}) = f ∘ (g ∘ g^{−1}) ∘ f^{−1}
= f ∘ I_{A} ∘ f^{−1}
= (f ∘ I_{A}) ∘ f^{−1}
= f ∘ f^{−1}
= I_{A}.

Similarly,

(g^{−1} ∘ f^{−1}) ∘ (f ∘ g) = g^{−1} ∘ (f^{−1} ∘ g) ∘ g
= g^{−1} ∘ I_{A} ∘ g
= (g^{−1} ∘ I_{A}) ∘ g
= g^{−1} ∘ g
= I_{A}.

By uniqueness of inverses, we conclude (f ∘ g)^{−1} = g^{−1} ∘ f^{−1}.

2. Suppose that A is a finite set. Show:

(a) A mapping f : A → A is a permutation of A if and only if f is one-to-one.

Solution: If f is a permutation, then it is one-to-one by definition. So there is nothing to prove. Conversely, let f be a one-to-one mapping from the finite set A to itself. If A = {a_{1}, …, a_{m}} for instance, this means that the f(a_{1}), …, f(a_{m}) are m distinct elements of A. But A has only m distinct elements, so every element of A is in the range of f. This shows that f is onto in addition to one-to-one. Therefore f is a permutation of A.

(b) A mapping f : A → A is a permutation of A if and only if f is onto.

Solution: If f is a permutation, then it is onto by definition. So there is nothing to prove. Conversely, let f be an onto mapping from the finite set A to itself. If A = {a_{1}, …, a_{m}} for instance, this means that for each i, a_{i} = f(a_{j}) for some j. Since there are only m distinct elements of A, this says that no two different elements of A can map to the same element of A. This shows that f is one-to-one in addition to onto. Therefore f is a permutation of A.

Hint for both parts: The idea here is to show that each of the defining properties of a permutation implies the other in this special situation. The ideas used in the proof of Exercise B 2 on Problem Set 1 may be helpful.

3. Show that matrix addition and matrix multiplication both define binary operations on the

set of matrices

M = \{(\begin{matrix}a & −b \\ b & a \end{matrix}) | a, b ∈ ℝ\} .

(That is, show that if A, B are two general matrices in M, then A + B ∈ M and A · B ∈ M.)

Solution: Write

A = (\begin{matrix}a & −b \\ b & a \end{matrix}) andB = (\begin{matrix}c & −d \\ d & c \end{matrix})

for some a, b, c, d ∈ ℝ. (Note that by using different names for the matrix elements here, we are allowing for corresponding elements of the two matrices to be the same or different.) By the definition of matrix addition,

A + B = (\begin{matrix}a + c & −(b + d) \\ b + d & a + c \end{matrix}) .

This has the correct form to be an element of M, since the diagonal elements are the same a + c, and the off-diagonal elements are negatives of one another. Similarly,

AB = (\begin{matrix}ac − bd & −(ad + bc) \\ ad + bc & ac − bd \end{matrix}) .

This also has the correct form to be an element of M, since the diagonal elements are the same ac − bd, and the off-diagonal elements are negatives of one another.

4. Let

A = (\begin{matrix}a & b \\ c & d \end{matrix})

be any matrix in M_{2×2}(ℝ) such that Δ = ad − bc ≠ 0. What happens if you multiply AB and BA for the matrix

B = (\begin{matrix}\frac{d}{Δ} & −\frac{b}{Δ} \\ −\frac{c}{Δ} & \frac{a}{Δ} \end{matrix})

What does this say about B?

Solution: The product AB is

AB = (\begin{matrix}\frac{ad−bc}{ad−bc} & \frac{−ab+ab}{ad−bc} \\ \frac{cd−cd}{ad−bc} & \frac{ad−bc}{ad−bc} \end{matrix} ) = (\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}) .

Similarly

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

This says B is the inverse for A under matrix multiplication.