\documentclass{article} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{enumerate} \usepackage{ifthen} \usepackage{graphicx} \usepackage{color} \usepackage{tikz} % for \sout to strike through text \usepackage{ulem} \setlength{\unitlength}{0.1in} \setlength{\oddsidemargin}{-0.50in} \setlength{\evensidemargin}{-0.50in} \setlength{\topmargin}{-0.50in} \setlength{\headheight}{0.0in} \setlength{\headsep}{0.0in} \setlength{\topskip}{0.0in} \setlength{\textheight}{9.5in} \setlength{\textwidth}{7.5in} \newcommand{\comp}{ \,{\scriptstyle \stackrel{\circ}{}}\, } \newcommand{\nullset}{\mathrm{O}\!\!\!\!\big/\,} \newcommand{\divides}{\,\Big|\,} \newcommand{\myspace}{\mbox{\parbox[c][0.35in]{0.35in}{\hfill}}} \newcommand{\myspacea}{\mbox{\parbox[c][0.35in]{0.65in}{\hfill}}} \newcommand{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}} \newcommand{\force}{{$\mbox{\;}$}} \begin{document} %\pagestyle{empty} \noindent \parbox{2in}{\bf Math 3110} \hfill {\Large \bf Test \#1} \hfill \parbox{2in}{\bf \hfill February $11^{\mathrm{th}}$, 2015} \vspace{0.3in} \noindent {\large\bf Name:} \underline{\Large\sc\color{red} \quad Answer Key \quad} \hfill {\bf Be sure to show your work!} \vspace{0.2in} \noindent {\bf\large 1. (20 points)} Definition and Basics \begin{enumerate}[(a)] \item Suppose that $G$ is a non-empty set equipped with an operation. What 4 things do I need to check to see if $G$ is a group? Give details. %\vspace{-0.05in} \begin{enumerate}[1:] \item Closure: $\forall x,y \in G$, we have $xy \in G$ \item Associativity: $\forall x,y,z \in G$, we have $(xy)z = x(yz)$ \item Identity: $\exists e \in G$ such that $\forall x \in G$, $xe = x = ex$ \item Inverses: $\forall x \in G$, $\exists y \in G$ such that $xy = e = yx$ \vspace{0.1in} \force\hspace{-0.35in} What additional property needs to hold for $G$ to be an {\bf Abelian} group? \vspace{0.1in} \item Commutivity: $\forall x,y \in G$, $xy = yx$ \vspace{0.05in} \end{enumerate} \item Let $G = \mathbb{Z}_{\geq 0}$ be the set of non-negative integers. It can be shown that $x \star y = \mbox{max} \{ x,y \}$ (example: $3 \star 1 = \mbox{max} \{3,1\} = 3$) is an associative, commutative (closed) binary operation on $G$ with identity $0$. However, $G$ is not a group. Why? [Use a concrete counterexample.] \vspace{0.05in} The only thing that keeps $G$ from being a group is its lack of {\it inverses}. Notice that $2 \in \mathbb{Z}_{\geq 0}$ but $\mbox{max} \{ 2, x \} \ne 0$ for all $x \in \mathbb{Z}_{\geq 0}$ since $\mbox{max}\{2,x\}$ $\ne 0$. Thus $2$ has no inverse. In fact, the only element that {\it does} have an inverse is $0$ itself: $\mbox{max}\{0,0\}=0$. \vspace{0.05in} {\it Note:} A non-empty set equipped with a closed associative binary operation which also has an identity is called a {\it monoid}. Thus even though $G$ isn't a group, it is a {\it commutative monoid}. \vspace{0.1in} \item Let $G = \mathbb{R} - \mathbb{Q} = \{ x \in \mathbb{R} \;|\; x \mbox{ is irrational }\}$. Prove $G$ is {\bf not} a group under addition. \vspace{0.05in} There are several ways to see that $G$ is not a group. For example: $G$ is not closed under addition. Notice that $\pm\sqrt2 \in G$ but $\sqrt2 + (-\sqrt2) = 0 \notin G$. Alternatively, $G$ isn't a group since it has no identity. $0$ would be the identity, but $0$ is rational (not irrational). Since $0 \not\in G$, $G$ has no identity! \vspace{0.1in} \end{enumerate} \noindent {\bf\large 2. (20 points)} Some modular arithmetic. \begin{enumerate}[(a)] \item What is the inverse of $10$ in the group $\mathbb{Z}_{15}$? What operation makes $\mathbb{Z}_{15}$ a group? \vspace{0.05in} Addition makes this an abelian group. The inverse of 10 in $\mathbb{Z}_{15}$ is $-10=5$. \vspace{0.05in} \item Is $10$ an element of $U(15)$? If not, why not? If so, why so \& what is its inverse? \vspace{0.05in} No, $10\notin U(5)$ since $\mathrm{gcd}(10,15) = 5 \neq 1$. \vspace{0.05in} \item List all of the {\it distinct} cyclic subgroups, $\langle x \rangle$, of $\mathbb{Z}_{15}$. \vspace{0.05in} Notice that 1, 3, 5, 15 are the divisors of 15. We get a unique subgroup associated with each of these numbers: \begin{itemize} \item $\langle 0\rangle = \{0\}$ \item $\langle 5 \rangle = \{ 0,5,10\}$ \item $\langle 3 \rangle=\{0,3,6,9,12\}$ \item $\langle 1 \rangle = \{0,1,2,\dots,14\} = \mathbb{Z}_{15} $ \end{itemize} \item What is the order of $10$ in $\mathbb{Z}_{15}$? \vspace{0.05in} $(1)10 = 10$ , $(2)10 = 10+10=5$ , $(3)10 = 10+10+10=0$ and therefore $|10| = 3$ Alternatively, notice that $\langle 10 \rangle =\mbox\{0,5,10\}$ and so $|10| =|\langle 10 \rangle| = 3$ \vspace{0.05in} \item Draw the subgroup lattice of $\mathbb{Z}_{15}$. \vspace{-0.25in} \begin{center} \begin{minipage}{2in} \begin{tikzpicture}[node distance=1cm] % 15's divisibility lattice \node(grp){15}; \node(placeholder)[below of = grp]{ }; % blank space \node(sg5)[left of = placeholder]{3}; \node(sg3)[right of = placeholder]{5}; \node(trivial)[below of = placeholder]{1}; % Lines between 1st and 2nd rows \draw(grp)--(sg5); \draw(grp)--(sg3); % Lines between 2nd and 3rd rows \draw(sg5)--(trivial); \draw(sg3)--(trivial); \end{tikzpicture} \vspace{0.15in} \force \hspace{-0.15in} Divisibility Lattice \end{minipage} \begin{minipage}{3in} \begin{tikzpicture}[node distance=2cm] % Z_15's subgroup lattice \node(grp){$\mathbb{Z}_{15} = \langle 1 \rangle$}; \node(placeholder)[below of = grp]{ }; % blank space \node(sg5)[left of = placeholder]{$\langle 5 \rangle = \{ 0,5,10 \}$}; \node(sg3)[right of = placeholder]{$\langle 3 \rangle = \{0,3,6,9,12 \}$}; \node(trivial)[below of = placeholder]{$\langle 0 \rangle = \{ 0 \}$}; % Lines between 1st and 2nd rows \draw(grp)--(sg5); \draw(grp)--(sg3); % Lines between 2nd and 3rd rows \draw(sg5)--(trivial); \draw(sg3)--(trivial); \end{tikzpicture} \vspace{0.15in} \force \hspace{0.65in} Subgroup Lattice \end{minipage} \end{center} \vspace{-0.2in} \end{enumerate} \noindent {\bf\large 3. (25 points)} More Modular Arithmetic. \begin{enumerate}[(a)] \item Draw a Cayley table for $U(5)$. \vspace{0.05in} \force \hspace*{1in} \begin{minipage}{3in} \begin{tabular}{c||cccc} & 1 & 2 & 3 & 4 \\ \hline\hline 1 & 1 & 2 & 3 & 4 \\ 2 & 2 & 4 & 1 & 3 \\ 3 & 3 & 1 & 4 & 2 \\ 4 & 4 & 3 & 2 & 1 \end{tabular} \end{minipage} \vspace{0.05in} \item List the elements of $U(5)$. Then find their {\bf order}s and the list the elements in {\bf cyclic subgroup} generated by that element. [{\it Note:} There may be more spaces than you need.] \vspace{0.1in} \force %\hspace{-0.45in} \begin{tabular}{c||c|c|c|c|c|c|} $x=$ & 1 & 2 & 3 & 4 \\ \hline\hline $|x|=$ & 1 & 4 & 4 & 2 \large\strut \\ \hline $\langle x \rangle=$ & $\{ 1 \}$ & $\{1,2,3,4\}$ & $\{1,2,3,4\}$ & $\{1,4\}$ \large\strut \\ \hline \end{tabular} \vspace{0.05in} % \item Is $U(8)$ cyclic? \qquad {\bf\Large Yes \quad / \quad No} \qquad (Circle the correct answer.) %\vspace{0.15in} \item Find $\displaystyle \left\langle A \right\rangle = \left\langle \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix} \right\rangle$ in $\mathrm{GL}_2(\mathbb{Z}_6)$. What is the order of $A$? What is $A^{-1}$? \vspace{0.05in} $A^2=\begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1&2\\0&1\end{bmatrix}=\begin{bmatrix}1&4\\0&1\end{bmatrix}$ \quad $A^3=A^2A=\begin{bmatrix} 1&4\\0&1\end{bmatrix} \begin{bmatrix} 1&2\\0&1 \end{bmatrix}=\begin{bmatrix} 1&0\\0&1\end{bmatrix}$ \vspace{0.05in} Thus the cyclic subgroup generated by $A$ is $\langle A \rangle =\{I, A, A^2\}=\left\{\begin{bmatrix} 1&0\\0&1 \end{bmatrix}, \begin{bmatrix} 1&2\\0&1 \end{bmatrix},\begin{bmatrix} 1&4\\0&1 \end{bmatrix}\right\}$ and so $|A|=3$. To find $A^{-1}$, note that the order of A is 3, so $A^{-1}=A^2=\begin{bmatrix} 1&4\\0&1 \end{bmatrix}$ It can also be found directly: $A^{-1}=(\mathrm{det}(A))^{-1} \begin{bmatrix} 1&-2\\0&1 \end{bmatrix}=1^{-1} \begin{bmatrix} 1&-2\\0&1 \end{bmatrix}=\begin{bmatrix} 1&4\\0&1 \end{bmatrix}$ \vspace{0.05in} \item \sout{Find $99^{-1}$ mod 123 using} {\color{red}Run} the extended Euclidean algorithm {\color{red}on 99 and 123}. \vspace{0.05in} Note that 123 divided by 99 is 1 with a remainder of 24. Then 99 divided by 24 is 4 with a remainder of 3. Finally, 24 divided by 3 is 8 with no remainder. Thus the last non-zero remainder is 3 so that $\mathrm{gcd}(99,123)=3$. We have $123=(1)(99)+24$ and $99=(4)24+3$. Thus $3=(1)99+(-4)24$ and so $3=(1)99+(-4)[123+(-1)99]$. Therefore, \fbox{$3=(5)99+(-4)123$}. Of course, the original problem (computing $99^{-1}$ mod 123) is impossible since 99 and 123 aren't relatively prime. $99 \not\in U(123)$ so $99^{-1}$ (mod 123) does not exist! \end{enumerate} \newpage \noindent {\bf\large 4. (15 points)} Recall $D_n = \{1,x,\dots,x^{n-1},y,xy,\dots,x^{n-1}y \} = \langle x,y \;|\; x^n=1, y^2=1, (xy)^2=1 \rangle$. \begin{enumerate}[(a)] \item Use the relations for $D_{10}$ to simplify $x^{-3}y^2x^{15}yx^4y^{-22}$ \vspace{0.05in} Recall $y's$ exponents ``work mod 2'', $x's$ ``work mod 10''. Also, $yx=x^{-1}y$ and $xy=yx^{-1}$. Therefore, $$x^{-3}y^{2}x^{15}yx^{4}y^{-22}=x^{-3}x^{15}yx^{4}=x^{12}x^{-4}y=x^{8}y$$ \vspace{-0.1in} \item Fill in the Cayley table for $D_3$: \force \hspace{1in} \begin{minipage}{3in} \begin{tabular}{c||c|c|c|c|c|c|} & $1$ & $x$ & $x^2$ & $y$ & $xy$ & $x^2y$ \\ \hline \hline $1$ & $1$ & $x$ & $x^2$ & $y$ & $xy$ & $x^2y$ {\Large\strut} \\ \hline $x$ & $x$ & $x^2$ & $1$ & $xy$ & $x^2y$ & $y$ {\Large\strut} \\ \hline $x^2$ & $x^2$ & $1$ & $x$ & $x^2y$ & $y$ & $xy$ {\Large\strut} \\ \hline $y$ & $y$ & $x^2y$ & $xy$ & $1$ & $x^2$ & $x$ {\Large\strut} \\ \hline $xy$ & $xy$ & $y$ & $x^2y$ & $x$ & $1$ & $x^2$ {\Large\strut} \\ \hline $x^2y$ & $x^2y$ & $xy$ & $y$ & $x^2$ & $x$ & $1$ {\Large\strut} \\ \hline \end{tabular} \end{minipage} \vspace{0.1in} \item Do the {\bf reflections} form a subgroup of $D_3$? If so, why? If not, why not? \vspace{0.05in} No. The set of reflections are not closed under function composition. For example: $y^2=1$ but $1$ is not a reflection. In fact, the reflections {\it never} form a subgroup since a reflection composed with a reflection is a rotation (closure fails in an extreme way). Alternatively, we could see that the reflections don't form a subgroup since they lack an identity (1 is a rotation not a reflection). \end{enumerate} \vspace{0.05in} \noindent {\bf\large 5. (20 points)} Proofs! \begin{enumerate}[(a)] \item Choose one of the following: \begin{enumerate}[I.] \item Suppose that $(ab)^{-1}=a^{-1}b^{-1}$ for all $a,b \in G$. Prove that $G$ is abelian. \vspace{0.05in} Suppose $a,b \in G$ . Then $(ab)^{-1} = b^{-1} a^{-1}$. Therefore $b^{-1}a^{-1}=a^{-1}b^{-1}$ since we have assumed $(ab)^{-1}=a^{-1}b^{-1}$. Thus $ab(b^{-1} a^{-1})=ab(a^{-1}b^{-1})$. So that $e=aba^{-1}b^{-1}$. Therefore, $e(ba)=aba^{-1}b^{-1}(ba)$. Thus $ba=ab$ and so $G$ is abelian. Alternatively, we have $a^{-1}b^{-1}=(ab)^{-1}=b^{-1}a^{-1}$ so $(a^{-1})^{-1}(b^{-1})^{-1}=(a^{-1}b^{-1})^{-1}=(b^{-1})^{-1}(a^{-1})^{-1}$ thus $ab=ba$. \vspace{0.05in} \item Let $G$ be a group and $g \in G$. Prove that $\langle g \rangle = \langle g^{-1} \rangle$ \quad (i.e. $g$ and its inverse generate the same cyclic subgroup). $$\langle g \rangle = \mbox\{g^k \;|\; k\in \mathbb{Z}\} = \mbox\{g^{-k} \;|\; -k \in \mathbb{Z}\} = \mbox\{(g^{-1})^k \;|\; k \in \mathbb{Z} \} = \langle g^{-1} \rangle$$ \end{enumerate} \item Choose one of the following: \qquad (You {\bf must} use a subgroup test in your proof.) \begin{enumerate}[I.] \item Prove that $H = 6\mathbb{Z} = \{ m \in \mathbb{Z} \;|\; m \mbox{ is a multiple of 6 }\}$ is a subgroup of $\mathbb{Z}$. \vspace{0.05in} Note $0 \in H$ (it is a nonempty subset of $\mathbb{Z}$). Suppose $x,y \in H$. Then there is some $k, \ell \in \mathbb{Z}$ such that $x = 6k$ and $y = 6\ell$. So $x + y = 6k +6\ell = 6(k+\ell) \in H$ since $k+\ell \in \mathbb{Z}$ . Also, $-x=-6k=6(-k) \in H$ since $-k\in\mathbb{Z}$ Therefore, $H$ is closed under addition and inverses, and thus $H$ is a subgroup by the 2-step test. \vspace{0.05in} \item Prove that $K = \left\{ \begin{bmatrix} 1 & a \\ 0 & 1 \end{bmatrix} \;\Bigg|\; a \in \mathbb{R} \right\}$ is a subgroup of $\mathrm{SL}_2(\mathbb{R})$. \vspace{0.05in} Clearly $K$ is a non-empty subset of $\mathrm{GL}_2(\mathbb{R})$ (notice that elements of $K$ have determinant 1, so they are invertible matrices). Suppose $\displaystyle \begin{bmatrix} 1 & a \\ 0 & 1 \end{bmatrix}, \begin{bmatrix} 1 & b \\ 0 & 1 \end{bmatrix} \in K$. Then $\displaystyle \begin{bmatrix} 1 & a \\ 0 & 1 \end{bmatrix}\begin{bmatrix} 1 & b \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & a+b \\ 0 & 1 \end{bmatrix} \in K$. Also, $\begin{bmatrix} 1 & a \\ 0 & 1 \end{bmatrix}^{-1} = \begin{bmatrix} 1 & -a \\ 1 & 0 \end{bmatrix} \in K$. Thus $K$ is closed under matrix multiplication and inverses, so by the 2-step subgroup test, $K$ is a subgroup of $\mathrm{GL}_2(\mathbb{R})$. \end{enumerate} \end{enumerate} \end{document}