\documentclass[11pt]{article}
\usepackage{latexsym,amsmath,amssymb}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.0in}
\begin{document}
\centerline{Mathematics 243, section 3 -- Algebraic Structures}
\centerline{Solutions for Problem Set 3}
\centerline{{\bf due:} September 21, 2012}
\vskip 10pt
\noindent
{\it `A' Section}
\bigskip
\begin{enumerate}
\item[1.]  Let $\mathcal{A} = \{a,b,c\}$.  In class we discussed the 
set $\mathcal{S}(\mathcal{A})$ of permutations of $\mathcal{A}$, and we wrote 
\begin{equation}
\label{perm}
\mathcal{S}(\mathcal{A}) = \{I_{\mathcal{A}}, R_a,R_b,R_c,C_1,C_2\}
\end{equation}
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 $\circ$ defines
a binary operation on $\mathcal{S}(\mathcal{A})$ by results from class on 
September 14 and 17.  Make the operation table for $\circ$ on this set, showing
the results of composing all pairs of elements of $\mathcal{S}(\mathcal{A})$, listing
the labels for the rows and columns in the order given in Eq.~\eqref{perm} above.
\item[] {\it Solution:}  For example, $R_a \circ C_1$ is the mapping given by 
\begin{align*}
(R_a \circ C_1)(a) &= R_a(C_1(a)) = R_a(b) = c\\
(R_a \circ C_1)(b) &= R_a(C_1(b)) = R_a(c) = b\\
(R_a \circ C_1)(c) &= R_a(C_1(c)) = R_a(a) = a.\\
\end{align*}  
This says $R_a \circ C_1 = R_b$.  The rest of the table fills in like this:
\[
\begin{array}{rrrrrrrr}
          \circ & \vline & I & R_a & R_b & R_c & C_1 & C_2 \\ \hline
              I & \vline & I & R_a & R_b & R_c & C_1 & C_2  \\
            R_a & \vline & R_a & I & C_1 & C_2 & R_b & R_c \\
            R_b & \vline & R_b & C_2 & I & C_1 & R_c & R_a \\
            R_c & \vline & R_c & C_1 & C_2 & I & R_a & R_b \\
            C_1 & \vline & C_1 & R_c & R_a & R_b & C_2 & I \\
            C_2 & \vline & C_2 & R_b & R_c & R_a & I & C_1
\end{array}
\]
\item[2.] Let 
$$A =  \begin{pmatrix} 1 & 1 & -1\\
                      -2 & 3 & 0\end{pmatrix},\  
B = \begin{pmatrix} 1 \\ 7 \\ 3 \end{pmatrix},\ 
C = \begin{pmatrix} 3 & -3 & -4\\
                    1 & -8 & 2\\
                    0 & 1 & 4 \end{pmatrix},\  
D = \begin{pmatrix} 4 & 3 & 3\\
                    5 & 0 & -2\end{pmatrix}.
$$
Perform the indicated matrix operations, if possible.  If the operation
is not possible, say why not.
\begin{enumerate}
\item[(a)]  $A + D$
\item[] {\it Solution:}  This sum is defined because $A$ and $D$ are both
$2 \times 3$ matrices:
$$A + D = \begin{pmatrix} 5 & 4 & 2 \\ 3 &3 &-2\end{pmatrix}$$
\item[(b)]  $AC$
\item[]  {\it 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 \times 3$ matrix 
$$AC = \begin{pmatrix} 4 & -12 & -6\\ -3 & -18 & 14\end{pmatrix}$$
\item[(c)]  $AD + A$
\item[] {\it 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.
\item[(d)]  $CB + AB$
\item[] {\it Solution:}  The product $CB$ is $3 \times 1$, but the product $AB$ is 
$2\times 1$.  This means that $CB$ cannot be added to $AB$. 
\end{enumerate}
\item[3.]  Let $S$ be the following set of matrices in $M_{3\times 3}(\mathbb{R})$:
\begin{equation}
\label{mats}
S = \{I_3,F_x,F_y,F_z,G_1,G_2\},
\end{equation}
where $I_3$ is the $3\times 3$ identity matrix, 
$$F_x = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1\\ 0 & 1 & 0 \end{pmatrix},\  
F_y = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0\\ 1 & 0 & 0 \end{pmatrix},\  
F_z = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0\\ 0 & 0 & 1 \end{pmatrix},\  
$$
and 
$$G_1 = \begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0\\ 0 & 1 & 0 \end{pmatrix},\  
G_2 = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}.$$
Show that \emph{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.~\eqref{mats} above.  Do you notice something about this table
and the one in question 1?
\[
\begin{array}{rrrrrrrr}
          \cdot & \vline & I & F_x & F_y & F_z & G_1 & G_2 \\ \hline
              I & \vline & I & F_x & F_y & F_z & G_1 & G_2  \\
            F_x & \vline & F_x & I & G_1 & G_2 & F_y & F_z \\
            F_y & \vline & F_y & G_2 & I & G_1 & F_z & F_x \\
            F_z & \vline & F_z & G_1 & G_2 & I & F_x & F_y \\
            G_1 & \vline & G_1 & F_z & F_x & F_y & G_2 & I \\
            G_2 & \vline & G_2 & F_y & F_z & F_x & I & G_1
\end{array}
\]
In the table from problem 1, if you replace $R_a \mapsto F_x$, $R_b \mapsto F_y$, $R_c \mapsto F_z$,
$C_1 \mapsto G_1$, and $C_2 \mapsto 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.  
\end{enumerate}
\vskip 10pt
\noindent
{\it `B' Section}
\vskip 10pt
\begin{enumerate}
\item[1.]  Let $\mathcal{A}$ be a set and $f,g \in S(\mathcal{A})$ be 
permutations.  
\begin{enumerate}
\item[(a)]  Show that $(f^{-1})^{-1} = f$ as mappings on $\mathcal{A}$.
\item[] {\it Solution:}  By the definition of the inverse mapping, we have
$$f \circ f^{-1} = I_{\mathcal{A}} = f^{-1} \circ f.$$  
By theorems we proved
in class we know that every element of $S(\mathcal{A})$ has an inverse for the 
$\circ$ 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$.  
\item[(b)]  Show that $(f \circ g)^{-1} = g^{-1} \circ f^{-1}$ as mappings on $\mathcal{A}$.  
\item[] {\it Solution:}  By associativity of composition and the fact that
$I_{\mathcal{A}}$ is an identity for composition,  we have
\begin{align*}
(f \circ g) \circ (g^{-1} \circ f^{-1}) & = f \circ (g \circ g^{-1}) \circ f^{-1}\\
&= f \circ I_{\mathcal{A}} \circ f^{-1}\\
&= (f \circ I_{\mathcal{A}}) \circ f^{-1}\\
&= f \circ f^{-1}\\
&= I_{\mathcal{A}}.
\end{align*}
Similarly, 
\begin{align*}
(g^{-1} \circ f^{-1}) \circ (f \circ g) & = g^{-1} \circ (f^{-1} \circ g) \circ g\\
&= g^{-1} \circ I_{\mathcal{A}} \circ g\\
&= (g^{-1} \circ I_{\mathcal{A}}) \circ g\\
&= g^{-1} \circ g\\
&= I_{\mathcal{A}}.
\end{align*}
By uniqueness of inverses, we conclude $(f \circ g)^{-1} = g^{-1} \circ f^{-1}$.  
\end{enumerate}
\item[2.]  Suppose that $\mathcal{A}$ is a \emph{finite} set.  Show:
\begin{enumerate}
\item[(a)]  A mapping $f : \mathcal{A} \to \mathcal{A}$ is a permutation
of $\mathcal{A}$ if and only if $f$ is one-to-one.
\item[] {\it 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 $\mathcal{A}$ to itself.  If $\mathcal{A} = \{a_1,\ldots,a_m\}$
for instance, this means that the $f(a_1), \ldots,  f(a_m)$ are $m$ distinct
elements of $\mathcal{A}$.  But $\mathcal{A}$ has only $m$ distinct
elements, so every element of $\mathcal{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 $\mathcal{A}$.  
\item[(b)]  A mapping $f : \mathcal{A} \to \mathcal{A}$ is a permutation
of $\mathcal{A}$ if and only if $f$ is onto.
\item[] {\it 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 $\mathcal{A}$ to itself.  If $\mathcal{A} = \{a_1,\ldots,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 $\mathcal{A}$, this says that no two different elements of 
${\mathcal A}$ can map to the same element of $\mathcal{A}$. 
This shows that $f$ is one-to-one in addition to onto.  Therefore $f$ is a permutation
of $\mathcal{A}$.  
\item[] Hint for both parts:  The idea here is to show that each of the 
defining properties of a permutation \emph{implies the other} in 
this special situation.  The ideas used in the proof of Exercise B 2 on 
Problem Set 1 may be helpful.  
\end{enumerate}
\item[3.]  Show that matrix addition and matrix multiplication both
define binary operations on the set of matrices 
$$M = \left\{\begin{pmatrix} a & -b \\ b & a\end{pmatrix} \mid a,b \in \mathbb{R}\right\}.$$
(That is, show that if $A, B$ are two general matrices in $M$, 
then $A + B \in M$ and $A\cdot B \in M$.)  
\item[] {\it Solution:}  Write
$$A = \begin{pmatrix} a & -b \\ b & a\end{pmatrix}\quad \text{and} 
B = \begin{pmatrix} c & -d \\ d & c\end{pmatrix}$$
for some $a,b,c,d \in \mathbb{R}$.  (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{pmatrix} a+c & -(b+d) \\ b+d & a+c\end{pmatrix}.$$
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, 
$$A B = \begin{pmatrix} ac - bd & -(ad + bc) \\ ad + bc  & ac - bd\end{pmatrix}.$$
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.
\item[4.]  Let 
$$A = \begin{pmatrix} a & b \\ c & d\end{pmatrix}$$ 
be any matrix
in $M_{2\times 2}(\mathbb{R})$ such that $\Delta = ad - bc \ne 0$.  What happens
if you multiply $AB$ and $BA$ for the matrix
$$B = \begin{pmatrix} \frac{d}{\Delta} & -\frac{b}{\Delta} \\ -\frac{c}{\Delta} & \frac{a}{\Delta}
\end{pmatrix}$$
What does this say about $B$?  
\item[] {\it Solution:}  The product $AB$ is 
$$AB = \begin{pmatrix} \frac{ad - bc}{ad - bc} & & \frac{-ab + ab}{ad - bc} \\ & &\\ \frac{cd - cd}{ad-bc} & & \frac{ad - bc}{ad - bc}\end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix}.$$
Similarly 
$$BA = \begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix}.$$
This says $B$ is the inverse for $A$ under matrix multiplication.
\end{enumerate}


\end{document}
