\documentclass[12pt]{amsart}
\usepackage{amsfonts}
\usepackage{tikz-cd}
\setlength{\topmargin}{0in}
\setlength{\textheight}{10in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\parskip0.4em
\thispagestyle{empty}
\def\R{\mathbb{R}}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\def\C{\mathbb{C}}
\renewcommand{\phi}{\varphi}

\begin{document}
\begin{center}
{\bf Math 113 Homework 3, due 2/12/2019}
\end{center}
\medskip

{\bf 1.} Book exercises 3.2, 3.3, 3.4.

{\bf \noindent\large Make sure you are using the 7th edition of Abstract algebra by Fraleigh -- if you do the wrong problems, you won't get points!}

\

{\bf 2.} Book exercises 4.1-4.7

\

{\bf 3.} {\bf (a)} Show that ``two-sided cancellation'' holds in groups. I.e., if $a, b, \tilde{b}, c$ are elements of a group $G$  with operation $\cdot$, and $a\cdot b\cdot c = a \cdot \tilde{b}\cdot c$ then $b = \tilde{b}$.

\noindent {\bf (b)} If $G$ is a group and $g\in G$ is a fixed element, show that the function $i_g$ with $i_g(x) = g\cdot x \cdot g^{-1}$ is an isomorphism of $G$ with itself.

\

{\bf Quiz prep questions. Your \% score on the following problems will be added to your quiz score percentage on Quiz 2, up to 100\%.}

{\bf i.} Let $U_4: = (\{1,i, -1, -i\}, \cdot)$ be the binary structure with four elements, and with operation multiplication (as we shall see in class, this is a group). Let $\equiv_4$ be the ``mod $4$'' equivalence relation on $\Z$ with $a \equiv_4 b$ if and only if $4\mid b-a$. Remember the notation $\Z/\equiv_4$ for the quotient set: this is the set of classes $[a]$ like $[-1],$ $[0]$ or $[5]$, where $[a]$ and $[b]$ are identified iff $a \equiv_4 b$ (so $[1] = [5]$ but $[1]\ne [3]$). Suppose $[a]\in \Z/\equiv_4$ (here $[a]$ is the class corresponding to some integer $a\in \Z$). Now define $f([a]) : = i^a$ (here $i$ is the square root of $-1$). Show that this determines a \emph{well-defined} function $$f:\Z/\equiv_4\to U_4,$$ i.e.\ if $a \equiv_4 b$ then $f(a) = f(b).$

\

{\bf ii.} Let $(\C^*, \cdot)$ be the group of complex numbers with multiplication. Let $U\subset \C^*$ be the subgroup of all elements which have absolute value equal to $1$.

Define an equivalence relation $\sim$ on $\C^*$ by $z\sim z'$ if and only if $z/z' \in U$, i.e. if the quotient has absolute value $1$. 

(a) Check that $\C^*$ is closed under multiplication (so the operation makes sense). 

(b) Check that $z \sim z'$ if and only if $|z| = |z'|.$

(c) Check that $\sim$ is in fact an equivalence relation (i.e. it satisfies r, s, t).

(d) Check that multiplication on $\C^*/\sim$ is well-defined, i.e. if $a \sim a'$ and $b\sim b'$ then $ab \sim a'b'$.

(e) Is addition well-defined? Prove this or give a counterexample.

(f) Let $(\R_{>0}, \cdot)$ be the group of (strictly) positive real numbers under multiplication. Construct an isomorphism $\phi:\R_{>0}\to \C^*/\sim.$ Hint: try $\phi(r) = [r]$ for $r\in \R_{>0}.$ Now check that multiplication goes to multiplication and that the map is a bijection.
\newpage

{\bf iii} A (simple) \emph{graph} $\Gamma$ is a finite set of vertices $V = \{v_1, v_2, v_3, \dots, v_n\}$ together with a set of \emph{edges} $E = \{e_1,e_2,\dots, e_k\}$ where each edge is an un-ordered pair $\{v_i, v_j\}$ of two distinct vertices. Here is an example of a graph:

Vertices: $v_1, v_2, v_3, v_4$.

Edges: $e_1 = \{v_1, v_2\}, e_2 = \{v_3, v_4\}, e_3 = \{v_2, v_4\}$:
\begin{equation}
\begin{tikzcd}
{\quad}\quad\bullet \quad v_1 \arrow[d, "e_1" description, no head] & {\quad}\quad\bullet\quad v_4 \arrow[d, "e_2" description, no head] \\
{\quad}\quad\bullet\quad v_2 \arrow[ru, "e_3" description, no head] & {\quad}\quad\bullet \quad v_3
\end{tikzcd}
\end{equation}
(graphs are drawn by drawing the vertices as points and the edges as lines between pairs of points). Now define a relation {\large $\quad\sim_\Gamma\quad$} on the set of points: $v_i$ is related to $v_j$ if one of the following conditions hold:
$$v_i\sim_\Gamma v_j\text{ if }\quad
\begin{cases}
  \text{The vertices are the same, i.e. }v_i = v_j\\
  \text{There is an edge }\{v_i, v_j\}\in E.
\end{cases}
$$

\

(a) Show that $\sim_\Gamma$ for $\Gamma$ as above is not an equivalence relation.

\

(b) Show that the following two graphs do define equivalence relations:

\begin{equation}
\begin{tikzcd}
{\quad}\quad\bullet \quad v_1 \arrow[d, "e_1" description, no head] & {\quad}\quad\bullet\quad v_4 \arrow[d, "e_2" description, no head] \\
{\quad}\quad\bullet\quad v_2  & {\quad}\quad\bullet \quad v_3
\end{tikzcd}
\end{equation}
and
\begin{equation}
  \begin{tikzcd}
{\quad}\quad\bullet \quad v_1 \arrow[rd, no head] \arrow[r, no head] \arrow[d, no head] & {\quad}\quad\bullet\quad v_4 \arrow[d, no head] \\
{\quad}\quad\bullet\quad v_2 \arrow[ru, no head] \arrow[r, no head] & {\quad}\quad\bullet \quad v_3
\end{tikzcd}
\end{equation}
(for (3) it doesn't matter how we label the edges: in this graph every pair of vertices is connected).

Show that in graph (2), there are two equivalence classes and in graph (3) there is one equivalence class.

\

(c) Can you explain (not necessarily rigorously) what it means for the graph $\Gamma$ that it defines an equivalence relation? Draw a graph on the vertices $v_1,\dots, v_4$ which has two equivalence classes, one of which is just $\{v_1\}$ and the other is $\{v_2, v_3, v_4\}.$ (No proofs necessary for this part.)

%
%{\bf 4.} {\bf (a)} We can write a bijection $\sigma:\{1, 2, 3\}\to \{1, 2, 3\}$ as a permutation: i.e., as a table recording the three values $\begin{pmatrix}1,&2,&3\\ \sigma(1),& \sigma(2), &\sigma(3)\end{pmatrix}$ (since $\sigma$ is a bijection, the values in the second row must not repeat, hence form a permutation of $\{1, 2, 3\}$), for example, $\begin{pmatrix}1,&2,&3\\2,&3,&1\end{pmatrix}$ means the function $\sigma$ with $\sigma(1) = 2, \sigma(2) = 3, \sigma(3) = 1$. If there is no ambiguity, you can also write $[2,3,1]$ for the same permutation (note the square brackets above: round brackets mean something else for permutations).

% Write down all elements of the group of bijections $\{1, 2, 3\}\to \{1, 2, 3\}$ to itself as permutations. These form a group under the composition operation, $\circ$: this group is called the ``symmetric group on three elements'', or $S_3$. Write down a multiplication table for $S_3$ under composition (there should be $3! = 6$ permutations, and $36$ entries in the multiplication table).

%  As an example, say $\sigma = \begin{pmatrix}1,&2,&3\\2,&3,&1\end{pmatrix}$ and $\tau = \begin{pmatrix}1,&2,&3\\2,&1,&3\end{pmatrix}.$ Then \[\sigma\circ \tau (1) = \sigma(\tau(1)) = \sigma(2) = 3,\] \[\sigma\circ \tau (2) = \sigma(1) = 2,\] \[\sigma\circ \tau(3) = \sigma(3) = 1,\] so $\sigma\circ \tau = \begin{pmatrix}1,&2,&3\\3,&2,&1\end{pmatrix} = [3,2,1].$

%  Write down the inverse $\sigma^{-1}$ for the six permutations $\sigma\in S_3$. (Use the multiplication table!)

%  Convince yourself (without proof) that the multiplication table you constructed is associative: check using the table that $(\sigma_1\circ \sigma_2)\circ\sigma_3 = \sigma_1\circ(\sigma_2\circ\sigma_3)$ for a couple of examples.

%  \noindent {\bf (b)} Let $\tau = \begin{pmatrix}1,&2,&3\\2,&1,&3\end{pmatrix},$ the permutation that flips $1$ and $2$ and leaves $3$ the same. Note that $\tau^{-1} = \tau$. Recall from Problem {\bf 2 (b)} the function $i_\tau:S_3\to S_3$ given by $i_\tau(\sigma) = \tau\cdot \sigma \cdot \tau^{-1}$. Write down $i_\tau(\sigma)$ for the six permutations $\sigma$ in the previous problem. Can you briefly describe what $i_\tau$ does in words?

% \noindent {\bf (c)} For $\sigma = \begin{pmatrix} 1,& 2,& 3\\ 2,& 3,& 1\end{pmatrix},$ write down the cyclic subgroup $H_\sigma$ generated by $\sigma$ (i.e., all powers $\sigma^0, \sigma^1, \sigma^2, \dots, $ until they start repeating). Check this is indeed closed under composition.

%  {\bf As an alternative to doing parts a-c, you can instead write down a list of all subgroups of $S_3$, and give a proof of why there are no more. Then explain how $i_\tau$ in part (b) permutes these subgroups.}

\end{document}