1. Left-Right Cancellation Implies Commutativity.
Let \(G\) be a group with the property that for any \(x,y,z \in G\text{,}\) \(xy=zx\) implies \(y=z\text{.}\) Prove that \(G\) is Abelian.
Print preview
Worksheet Problem Set 1
Instructions: You may type up or handwrite your work, but it must be neat, professional, and organized and it must be saved as a PDF file and uploaded to the appropriate Gradescope assignment. Use a scanner or scanning app to convert handwritten work on paper to PDF. I encourage you to type your work using the provided template.
All tasks below must have a complete solution that represents a good-faith attempt at being right to receive engagement credits. If your submission is complete and turned in on time, you will receive full engagement credits for the assignment. All other submissions will receive zero engagement credit. Read the guidelines at Grading Specifications carefully.
To abide by the class’ academic honesty policy, your work should represent your own understanding in your own words. If you work with other students, you must clearly indicate who you worked with in your submission. The same is true for using tools like generative AI although I strongly discourage you from using such tools since you need to build your own understanding here to do well on exams.
Problems Doable After Week 1.
Problem Specs/Notes: This problem needs careful choice of group elements to apply the assumption to for a Success.
2. One-Step Subgroup Test.
Prove the One-Step Subgroup Test: Let \(G\) be a group and \(H\) a nonempty subset of \(G\text{.}\) If \(ab^{-1}\) is in \(H\) whenever \(a\) and \(b\) are in \(H\text{,}\) then \(H\leq G\text{.}\)
You may use the Two-Step Subgroup Test in your proof.
Solution.
By the Two-Step Subgroup Test, it suffices to show that \(H\) is closed under products and closed under inverses, since \(H\) is nonempty. First, we can see that \(e\in H\text{,}\) taking \(a=b\) in the hypothesis of the One-Step Subgroup Test: then \(aa^{-1}=e\in H\text{.}\) Now for any \(b\in H\) we have \(b^{-1}=eb^{-1}\in H\text{,}\) so \(H\) is closed under inverses. Finally, since \(H\) is closed under inverses, if \(x,y\in H\) we have \(y^{-1}\in H\) and then taking \(a=x,b=y^{-1}\) in the hypothesis we have \(xy=ab^{-1}\in H\text{,}\) so \(H\) is closed under products. Hence \(H\) is a subgroup of \(G\text{.}\)
3. Playing with Group Elements.
Choose one of the problems below to complete for this Problem Set.
(a)
Solution.
(b)
If \(a\) and \(b\) are distinct group elements, prove that either \(a^{2}\neq b^{2}\) or \(a^{3}\neq b^{3}\text{.}\)
Solution.
We will prove the contrapositive: if \(a^{2}=b^{2}\) and \(a^{3}=b^{3}\text{,}\) then \(a=b\text{.}\) So let \(a,b \in G\) and suppose \(a^{2}=b^{2}\) and \(a^{3}=b^{3}\text{.}\) Then we have
\begin{equation*}
b(b^{2})=b^{3}=a^{3}=a(a^{2})=a(b^{2})
\end{equation*}
But then right-cancellation implies \(a=b\text{.}\)
Problem Specs/Notes: This problem needs careful choice of proof method for a Success.
Problems Doable After Week 2.
4. Order is Preserved Under Conjugation.
Solution.
First, note that \((aba^{-1})^{k}=ab^{k}a^{-1}\) for any integer \(k\geq 1\) by induction on \(k\text{.}\) Therefore
\begin{align*}
(aba^{-1})^k =e \amp \Leftrightarrow ab^ka^{-1}=e \amp \Leftrightarrow b^k=e \text{.}
\end{align*}
Now the order of \(aba^{-1}\) is the smallest positive integer \(k\) such that \((aba^{-1})^k=e\text{,}\) and the order of \(b\) is the smallest positive integer \(k\) such that \(b^k=e\text{,}\) if these exist. Since these two conditions are equivalent, we have \(|aba^{-1}|=|b|\text{.}\)
Problem Specs/Notes: For a Success you need to handle:
-
The finite order case, which may require a two-sided proof.
-
The infinite order case.
5. Cyclic Subgroups.
Prove that \(H=\left\{ \begin{bmatrix}1 \amp n \\ 0 \amp 1\end{bmatrix}\mid n \in \Z \right\}\) is a cyclic subgroup of \(\GL(2,\R)\text{.}\)
Solution.
It suffices to show that \(H=\subgroup{A}\) where \(A\) is the matrix
\begin{equation*}
A=\begin{bmatrix}1 \amp 1 \\ 0 \amp 1\end{bmatrix}\text{.}
\end{equation*}
Certainly \(A^{0}=I_{2}\) and \(A^{1}=\begin{bmatrix}1 \amp 1 \\ 0 \amp 1\end{bmatrix}\text{.}\) So suppose \(A^{k}=\begin{bmatrix}1 \amp k \\ 0 \amp 1\end{bmatrix}\) for some \(k\geq 0\text{.}\) Then
\begin{equation*}
A^{k+1}= A^{k}A=\begin{bmatrix}1 \amp k \\ 0 \amp 1\end{bmatrix} \begin{bmatrix}1 \amp 1 \\ 0 \amp 1\end{bmatrix}=\begin{bmatrix}1 \amp k+1 \\ 0 \amp 1\end{bmatrix}.
\end{equation*}
Hence by induction on \(n\) we have \(A^{n}=\begin{bmatrix}1 \amp n \\ 0 \amp 1\end{bmatrix}\) for all \(n\geq 0\text{.}\) For \(n<0\text{,}\) we use this to see that
\begin{equation*}
\begin{bmatrix}1 \amp n \\ 0 \amp 1\end{bmatrix}=\begin{bmatrix}1 \amp -n \\ 0 \amp 1\end{bmatrix}^{-1}=(A^{-n})^{-1}=A^{n}.
\end{equation*}
Thus every element of \(H\) is a power
Problem Specs/Notes: This problem needs justification of both the fact that the given set is a subgroup and that it is cyclic for a Success. Depending on your argument structure, it may be possible to do both at once.
6. Well-Foundedness of Even and Odd Permutations.
Prove using induction that a permutation in \(S_n\) cannot be expressed both as the product of both an even number of transpositions and an odd number of transpositions. In other words, that our definitions of even and odd permutations are well-founded.
Hint.
Solution.
First, let \(\alpha \in S_n\) be written as a product of transpositions in two ways:
\begin{equation*}
\tau_1 \tau_2 \dots \tau_s = \alpha = \mu_1 \mu_2 \dots \mu_t\text{.}
\end{equation*}
Then we have
\begin{equation*}
e = \alpha\alpha^{-1}=\tau_1 \tau_2 \dots \tau_s \mu_t \mu_{t-1}\dots \mu_1\text{,}
\end{equation*}
so \(e\) can be written as a product of \(s+t\) transpositions. So it suffices to show that \(s+t\) must be even; then \(s\) and \(t\) must have the same parity.
Let us now induct on the number of transpositions in a decomposition of the identity. First, the identity can be written as a product of zero transpositions (or if you like it is clear that no single transposition is the identity and we can write the identity as a product \(e=(ab)(ab)\)) so our base case is done. Now suppose that any decomposition of the identity into \(n\) transpositions has \(n\) even. Let
\begin{equation}
e=\tau_1\tau_2\dots\tau_s\tag{1}
\end{equation}
for some \(s\gt n\text{.}\) We want to show that we can reduce the number of transpositions to apply our inductive hypothesis.
To do this, write \(\tau_1=(a\;b)\text{.}\) We must have an \(a\) in some later \(\tau_i\text{,}\) or else the RHS of (1) sends \(a\) to \(b\) (as this is the final swap in the product) which is not the identity. Since also \((a_i\; b_i)=(b_i\; a_i)\text{,}\) we have \(\tau_i=(a\; c)\) for some smallest \(i\gt 1\text{.}\) Now we want to pull this transposition to the left in the product. We can freely commute it with any transposition not involving \(a\) or \(c\text{.}\) When we do reach such a transposition, we have to be more careful. Otherwise, we can use the relation (for three distinct numbers \(a,c,d\))
\begin{equation*}
(c\;d)(a\;c)=(a\;d\;c)=(a\;d)(c\;d)
\end{equation*}
to rewrite any product of transpositions where the right one moves \(a\) and the left one does not as a product with the same number of transpositions but with the left one moving \(a\) and the right one not. By applying these two cases, we can get to the form
\begin{equation*}
e=(a\; b)(a\;b')\tau_3 \dots \tau_s
\end{equation*}
(note that our two rules for moving \((a\; c)\) show that the other permutations \(\tau_j\) do not change when we do this).
At this point, there are two possibilities. If \(b=b'\text{,}\) then we have the product \((ab)(ab)\) starting our RHS and so we may cancel these factors and by the inductive hypothesis the remaining product of \(s-2\) transpositions has an even number of transpositions and so \(s\) is even. Otherwise, we can use the similar relation for distinct numbers \(a,b,b'\)
\begin{equation*}
(a\;b)(a\;b')=(a\;b'\;b)=(a\;b')(b\;b')
\end{equation*}
to write
\begin{equation*}
e=(a\;b)(b\; b')\tau_3\dots \tau_s\text{.}
\end{equation*}
This new decomposition has one fewer transposition involving \(a\) than previous. So we can repeat the same argument and at each step either we reduce the number of transpositions by two and can apply our inductive step or we can reduce the number of transpositions involving \(a\text{.}\) Because there are at most \(s\) transpositions involving \(a\text{,}\) this must eventually terminate with reducing the number of transpositions by two. So by induction the identity can only be written as a product of an even number of transpositions. See this nice YouTube video for a visual explanation of this argument.
Problem Specs/Notes: This problem must be done with induction, giving clear base case and inductive step, for a Success.
