
%% ================================================================
\section{Disclaimer}

There are many wonderful algebra texts.  My personal favorite is Dummit and
Foote \cite{bib:df}.  See also Grove \cite{bib:grove}, Hungerford
\cite{bib:hung}, or Lang \cite{bib:lang}.  Friedberg et al.  \cite{bib:fis} is
a nice reference for linear algebra.  In this note, unlike my other qual-prep
notes, I make no attempt to be comprehensive.  Rather, I take the opportunity
to present some problem solutions, preceded by some useful items.  For example,
I gather together in one handy reference all the criteria for diagonalizability
of which I am aware.


%% ================================================================
\section{Linear algebra}

One might think this section should be contained in the discussion of
\plainidx{modules} --- after all, a \plainidx{vector space} is nothing more
than a module over a field.  However, each of the three UA quals contains an
undergraduate component: for the algebra qual, this portion is over linear
algebra.  So, solutions to the linear-algebra problems need not require the use
of graduate-level material.

Criteria for \bfidx{diagonalizability}:  an $n \times n$ matrix $A$
is diagonalizable \ldots

\begin{itemize}
\item \ldots iff its minimal polynomial splits with distinct factors.
\item \ldots if  its characteristic polynomial splits with distinct factors.
	(This is sufficient, but not necessary:  consider the identity matrix.)
\item \ldots iff it is similar to a diagonal matrix, i.e. there exists
	an invertible $n \times n$ matrix $Q$ and a diagonal matrix $D$
	such that $A = Q D Q^{-1}$.
\item \ldots iff the sum of the dimensions of its eigenspaces is equal to $n$.
\end{itemize}

Criteria for \bfidx{non-diagonalizability}:
\begin{itemize}
\item The minimal polynomial doesn't split over the base field.
\item The minimal polynomial has a double root.
\item There is an eigenvalue $\lambda$ such that $\ker(A-\lambda I)^2$
	properly contains $\ker(A-\lambda I)$.
\end{itemize}

\beginex
To construct a matrix which is non-diagonalizable over $\R$, take a polynomial
which doesn't split over $\R$:  say, $\lambda^2+1$.  Then write the
\bfidx{companion matrix} for that polynomial.  In general, if $P(\lambda) =
\lambda^n + a_{n-1} \lambda^{n-1} + \ldots + a_1 \lambda + a_0$ is a monic
polynomial, a companion matrix for $P(\lambda)$ is
$$
\begin{bmatrix}
-a_{n-1} & -a_{n-2} & \cdots & a_1 & a_0 \\
1        & 0        &        &     &   0 \\
         & 1        & \ddots &     &     \\
         &          & \ddots &     &     \\
0        &          &        &   1 &   0 \\
\end{bmatrix}.
$$
That is, write the negated coefficients across the top, 1's on the subdiagonal,
and 0's elsewhere.  (One may find other conventions for the companion matrix.
You can write various matrices, e.g. the transpose of the above, whose
characteristic polynomial is what you desire.)
For $P(\lambda)=\lambda^2+1$, we get
$$
	A = \begin{bmatrix}
		0 & -1 \\
		1 &  0 \\
	\end{bmatrix}.
$$
\mendex

\beginex
To construct a matrix which is non-diagonalizable over $\C$, we can't use the
non-splitting property, since $\C$ is algebraically closed.  We have to find an
example where the minimal polynomial has a double root --- say, a matrix which
is non-zero but whose square is zero:
$$
	A = \begin{bmatrix}
		0 &  0 \\
		1 &  0 \\
	\end{bmatrix}
$$
The characteristic polynomial of $A$ is $\lambda^2$, which you can compute by
taking $\det(A-\lambda I)$.  The minimal polynomial has to divide the
characteristic polynomial, and cannot be $\lambda$ since $A$ itself isn't zero.
Thus, $\lambda=0$ is a double root of the minimal polynomial.
\mendex

%% ================================================================
\section{Useful classes of matrices}

Many qualifier problems are of the form \emph{Give an example of \ldots}, or
\emph{Prove or disprove \ldots}.  To be successful in providing examples and
counterexamples, we need to have a \bfidx{toolkit} of standard examples of
things.  One large class of examples has to do with matrices: we have rings of
matrices and groups of invertible matrices; given a commutative ring $R$, we
can obtain a non-commutative ring by, say, considering $2 \times 2$ matrices
over $R$; and so on.

[xxx type me up]

Permutation matrices\index{permutation matrix}.

Rotation matrices\index{rotation matrix}: emphasize no real eigenvalues.

Projection matrices\index{projection matrix}.

Shift matrices\index{shift matrix}.  Use as counterexample for $T:V \to V$ and
$V = \ker(T) \oplus \im(T)$.

Elementary matrices\index{elementary matrix} $E_{ij}$: use to sketch pfs of
simplicity of $M_n(K)$ and $Z(M_n(K))$.

%% ================================================================
\section{Groups}

Here are two criteria for solvability.  One of them may be taken to be the
definition, and the other may be proved equivalent.  In \cite{bib:grove}, the
first is taken to be the definition.  First, some preliminary definitions.

\begin{defn}
Let $G$ be a group, and let $x,y \in G$.  The \bfidx{commutator} of $x$ and
$y$, written $[x,y]$, is $xyx^{-1}y^{-1}$.
\end{defn}

\begin{defn}
Let $G$ be a group.  The \bfidx{derived subgroup} of $G$, written $G'$, is
generated by all the commutators $[x,y]$ where $x$ and $y$ range over all
elements of $G$.
\end{defn}

\begin{defn}
It is clear that $G' \le G$.  So, we can compute the derived subgroup of $G'$.
The $k$th derived subgroup of $G$ is written $G^{(k)}$.
\end{defn}

How to show a subgroup is \bfidx{normal}:
\begin{itemize}
\item By definition of normalcy: $H \lhd G$ iff for all $g \in G$,
	$g H g^{-1} \subseteq H$.
\item Similarly:  $H \lhd G$ iff for all $g \in G$ and all $h \in H$,
	$ghg^{-1} \in H$.
\item $H \lhd G$ iff $H = \ker\phi$ for some homomorphism from $G$ to
	some other group.  (Kernels are normal.)
\item If $H \subseteq G'$ then $H \lhd G$.
\end{itemize}

\begin{defn}
Let $G$ be a group.  A nested sequence of subgroups $G_i$
$$
	G=G_0 \ge G_1 \ge G_2 \ldots
$$
is called a \bfidx{series}.
\end{defn}

\begin{defn}
A series is called \bfidxaux{normal}{normal series} if
$$
	G \unrhd G_i
$$
for all $i$.
\end{defn}

\begin{defn}
A series is called \bfidxaux{subnormal}{subnormal series} if
$$
	G=G_0 \unrhd G_1 \unrhd G_2 \ldots .
$$
\end{defn}

\begin{mnem}
In a \emph{sub}normal series, each $G_i$ is normal in the \emph{sub}group above
it.
\end{mnem}

\begin{defn}
A subnormal series is called a \bfidx{composition series} if it descends to 1,
and if the $G_i/G_{i+1}$ are all simple (i.e. $G_{i+1}$ is a maximal normal
subgroup of $G_i$) for all $i$.
\end{defn}

\begin{defn}[Definition of solvability]
Let $G$ be a group.  Then $G$ is said to be \bfidx{solvable} if
$G^{(k)} = 1$ for some integer $k$.
\end{defn}


\begin{prop}[Alternate criterion for solvability]
A group $G$ is \bfidx{solvable} iff there exists a subnormal series, descending
to 1 (i.e. $G_k = 1$ for some $k$), with abelian factors $G_{i+1}/G_i$.
\end{prop}

\begin{rem}
Usually we use the derived series for this purpose.
\end{rem}

\begin{defn}
A group is said to be \bfidx{nilpotent} if it satisfies an awkward
ascending-series condition which I can never remember and, fortunately,
which I don't think I ever \emph{need} to remember.
\end{defn}

There are two alternative characterizations which are often useful:

\begin{prop}[Alternate criterion for nilpotency]
For $H < G$, let $[G,H]$ be the subgroup of $G$ generated by all commutators
$[g,h]$ for $g \in G$ and $h \in H$.  Define $G_0=G$, $G_1 = [G,G_0]$, and in
general $G_{i+1} = [G,G_i]$.  Then $G$ is nilpotent iff the series descends to
the trivial group, i.e. if there is an $n$ such that $G_n = 1$.
\end{prop}

\begin{prop}[Alternate criterion for nilpotency: \cite{bib:grove}, theorem
I.7.8.]
$G$ is nilpotent iff it is the direct product of its Sylow subgroups.  In
particular, if $G$ is nilpotent, each Sylow subgroup is normal, and hence is
unique.
\end{prop}

\begin{prop}[Sufficient condition for nilpotency]
Finite $p$-groups are nilpotent.
\end{prop}

\begin{mnem}
If $G$ is trivial, then $G_0=1$; if $G$ is abelian, then $G_1=1$.  Thus
nilpotent groups are almost abelian in the sense that they descend to 1, just
perhaps a bit slower than abelian groups do.
\end{mnem}

\begin{mnem}
\label{mnem:cansa}
Remember \bfidx{CANSA}: cyclic groups $\subsetneq$ abelian groups
$\subsetneq$ nilpotent groups $\subsetneq$ solvable groups
$\subsetneq$ all groups.  (See \cite{bib:df}, section 6.1.)
\end{mnem}

(This is nice, but doesn't come up nearly as often as FEPUI for rings (mnemonic
\ref{mnem:fepui}).) All these inclusions are proper.
Examples:

\begin{itemize}
\item $\Z_2 \oplus \Z_2$ is abelian but not cyclic.
\item The quaternion unit group is nilpotent but not abelian.
\item $\mcS_4$ is solvable but not nilpotent.  (Use Grove's I.7.8:
	there are 3 conjugate $\mcD_4$'s in $\mcS_4$, which are Sylow-2
	subgroups of $\mcS_4$.)
\item $\mcS_n$ is not solvable for $n \ge 5$.
\end{itemize}

%% ================================================================
\section{Group actions}

normal subgroups vs. orbit-stabilizer --- ?

\bfidx{orbit-stabilizer formula}

%% ================================================================
\section{Semidirect products}
\label{sec:semi}

\begin{defn}
Let $G$ be a group with $N \lhd G$ and $K \subseteq G$.  Furthermore suppose
that $G=NK$ and $N \cap K = \{1\}$.  If $K$ acts on $N$ (formally, if there is
a homomorphism $K \to \Aut(N)$), we write
$$
	N \rtimes K
$$
and call this the \bfidx{semidirect product} of $N$ and $K$.  We sometimes
write the action of $k\in K$ on $n\in N$ as $n^k$.  Since $G=NK$, any $g \in G$
may be written in the form $(n,k)$.  Multiplication in $G$ is
$$
	(n_1, k_1)(n_2, k_2) = (n_1 {n_2}^{k_1}, k_1 k_2).
$$
\end{defn}

\begin{rem}
How does inversion work?  Given $(n, k)$ we need to find $(m, j)$
such that $(n,k)(m,j)=(1,1)$.  This gives
$$
	(1,1) = (n,k)(m,j) = (n {m}^{k}, k j)
$$
which forces $j = k^{-1}$.  Then, in the first slot,
$n {m}^{k} = 1$ forces
\begin{eqnarray*}
	{m}^{k} &=& {n}^{-1} \\
	m &=& ({n}^{-1})^{k^{-1}}.
\end{eqnarray*}
Thus,
$$
	(n,k)^{-1} = ((n^{-1})^{k^{-1}}, k^{-1}).
$$
\end{rem}

\beginex
Dihedral groups may be written as
$$
	\mcD_n = \mcC_n \rtimes \mcC_2 = \pig{\rho} \rtimes \pig{\phi}
$$
where $\rho$ is the rotation of order $n$ and $\phi$ is the flip.
The flip acts on the rotations by inverting them:
$$
	\rho^i \phi^j \rho^k \phi^\ell =
	\begin{cases}
		\rho^{i+k} \phi^{j+\ell}, & j \textrm{ even} \\
		\rho^{i-k} \phi^{j+\ell}, & j \textrm{ odd} \\
	\end{cases}
$$
which is to say (since there are only two distinct powers of $\phi$)
\begin{eqnarray*}
	\rho^i      \rho^k \phi^\ell &=& \rho^{i+k} \phi^{\ell} \\
	\rho^i \phi \rho^k \phi^\ell &=& \rho^{i-k} \phi^{1+\ell}.
\end{eqnarray*}
This is the familiar transposition rule
$$
	\phi\rho^k = \rho^{-k}\phi.
$$
\mendex

\beginex
The $T$ group (the other non-abelian group of order 12, besides
$\mcA_4$ and $\mcD_6$) is
$$
	T = \Z_3 \rtimes \Z_4
$$
where $\Z_4$ acts on $\Z_3$ by inversion.  That is, $1$ and $3$ in $\Z_4$
negate elements of $\Z_3$; $0$ and $2$ in $\Z_4$ leave elements of $\Z_3$
alone.
\mendex

\beginex
Let $\mcV_4=\{e,a,b,c\}$ be the Klein-four group as usual.
Let $\mcS_3$ act on $\mcV_4$ by permuting the symbols $a$, $b$, and $c$.
Then we can write the semidirect product
$$
	\mcV_4 \rtimes \mcS_3.
$$
It can be shown (I won't here) that this is isomorphic to $\mcS_4$.
\mendex

%% ================================================================
\section{A semidirect product example}

\emph{Note:  This section is perhaps not qualifier material.  Something came up
in the 2006-07 511 course which was ``obvious'' to the speaker, but not as
obvious to everyone in the audience.  Here I work through a detailed (albeit
inelegant) computation, from first principles, in order to increase the level
of obviousness.  Moreover, the techniques here elucidate the kind of
brainstorming one might need to resort to during an exam, on scratch paper, as
part of an attempt to conjecture a more elegant solution to be turned in.}

Consider the semidirect product $\Z_m \rtimes_\phi \Z_n$.  Recall that
multiplication in $\Z_m \rtimes_\phi \Z_n$, written additively, is
$$
	(a,b) + (c,d) = (a + [\phi(b)](c), b+d).
$$
Then $\phi$ must be a homomorphism from $\Z_n$ into $\Aut(\Z_m)$.  Here I
describe the possibilities for $\phi$ and compute the center of these groups,
starting with $m=7$ and $n=3$ as a concrete example.

\emph{Some notation:} For brevity (I am not a number theorist), let $\Z_m$
denote $\Z/m\Z$.  Really, $\Z_m$ is a commutative ring with 1.  As such, it has
an \bfidx{additive group}:  all the elements of the ring, with addition as the
operation, forgetting about multiplication.  Also, the invertible elements of
the ring form a group called the \bfidx{unit group} or \bfidx{multiplicative
group} (which possesses a subgroup structure).  When I write $\Z_m$ in this
section, I refer to the additive group of the ring.  When I write $\Z_m^\times$
I refer to the multiplicative group.

\emph{Structure of the additive group:} Recall that $\Z_m$ is always cyclic of
order $m$; 1 is always a generator.  (Any element relatively prime to $m$ is
also a generator.  There are $\Phi(m)$ of these, where $\Phi$ is Euler's
totient function.  In particular, if $m$ is prime, then any non-zero element of
$\Z_m$ is a generator.)

\emph{Structure and subgroup structure of the multiplicative group:}
$\Z_m^\times$ has order $\Phi(m)$.  In particular, recall that when $m$ is
prime, $\Phi(m)=m-1$ and $\Z_m^\times$ is cyclic.  Here, 1 is not a generator
(except when $m=2$).  In general, we have to search for generators.  For
example, with $m=7$, $2^3=1$ so 2 is not a generator.  On the other hand, 3 has
order 6 mod 7 and so 3 is a generator.  Here are powers of 3 mod 7:
$$
	\begin{tabular}{|r||r|r|r|r|r|r|}
	\hline $k$   & 1 & 2 & 3 & 4 & 5 & 6 \\
	\hline $3^k$ & 3 & 2 & 6 & 4 & 5 & 1 \\
	\hline
	\end{tabular}
$$
In fact, we can use this to write down orders of elements of the isomorphic
cyclic groups $\Z_6$ and $\Z_7^\times$:
$$
	\begin{tabular}{|l||r|r|r|r|r|r|}
	\hline $x \in \Z_6$        & 1 & 2 & 3 & 4 & 5 & 6 \\
	\hline $|x|$               & 6 & 3 & 2 & 3 & 6 & 1 \\
	\hline
	\hline $x \in \Z_7^\times$ & 3 & 2 & 6 & 4 & 5 & 1 \\
	\hline $|x|$               & 6 & 3 & 2 & 3 & 6 & 1 \\
	\hline
	\end{tabular}
$$
So, $\Z_7^\times$ has two generators: 3 and 5.  A cyclic group of order $s$ has
a unique subgroup for each divisor $d$ of $s$.  Here, $\Z_7^\times$ has a
subgroup of order 2, generated by 6:  this is $\{1,6\}$.  It also has a
subgroup of order 3, generated by 2 or 4:  this is $\{1,2,4\}$.

\emph{Structure of the automorphism group:} Since $\Z_7$ is cyclic, any
homomorphism from $\Z_7$ to itself, and in particular any automorphism, is
specified by its action on $\Z_7$'s 1: $\sigma(x) = x \sigma(1)$.  Since $7$ is
prime, there are 6 generators for $\Z_7$:  all the non-zero elements.  Thus, 1
may map to any generator.  So, the elements of $\Aut(\Z_7)$ are as follows:
$$
\begin{tabular}{|l||l|l|l|l|l|l|}
\hline $\Z_7$ & $\sigma_1$ & $\sigma_2$ & $\sigma_3$ & $\sigma_4$ & $\sigma_5$ & $\sigma_6$ \\
\hline
\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
\hline 1 & 1 & 2 & 3 & 4 & 5 & 6 \\
\hline 2 & 2 & 4 & 6 & 1 & 3 & 5 \\
\hline 3 & 3 & 6 & 2 & 5 & 1 & 4 \\
\hline 4 & 4 & 1 & 5 & 2 & 6 & 3 \\
\hline 5 & 5 & 3 & 1 & 6 & 4 & 2 \\
\hline 6 & 6 & 5 & 4 & 3 & 2 & 1 \\
\hline
\end{tabular}
$$

% Z3, Z7, Aut(Z7).

Note that $\sigma_i(x) = ix$, i.e. the $i$th automorphism is just
multiplication by $i$.  How do we compose automorphisms?  We have
$\sigma_i(\sigma_j(x)) = ijx$ for any test point $x$, so $\sigma_i \circ
\sigma_j$ is $\sigma_{ij}$.  So, arithmetic on the $i$'s and $j$'s is done in
the multiplicative group $\Z_7^\times$.  This substantiates what we already
know about $\Aut(\Z_7)$, namely, that it is isomorphic to $\Z_7^\times$ which
in turn is isomorphic to $\Z_6$.  Given the above information about
$\Z_7^\times$, we see that $\Aut(\Z_7)$ is cyclic, generated by either
$\sigma_3$ or $\sigma_5$.

Recall that for any group homomorphism $\psi:A \to B$, given an element $a \in
A$ of order $s$, the order of $\psi(a)$ in $B$ must divide the order of $a$ in
$A$.  This is because, if $a^s=e_A$, $\psi(a^s) = \psi(a)^s = e_B$.

%Since $\Z_3$ is cyclic, and since $\Aut(\Z_7)$ is cyclic, to specify $\phi$ we
%need only to specify the image of $\Z_3$'s 1.  That is, for $b \in \Z_3$,
%$\phi(b) = b \phi(1)$.  Let $\phi(1) = \sigma_t$.  What values can $t$ take?

To construct the semidirect product $\Z_7 \rtimes_\phi \Z_3$, we need $\phi$ to
be a homomorphism from $\Z_3$ to $\Aut(\Z_7)$.  The possible homomorphisms from
the order-3 cyclic group $\Z_3$ to the order-6 cyclic group $\Z_7^\times$ are
specified by the image of $\Z_3$'s 1.  It can map to $\sigma_1$ (trivial
homomorphism), $\sigma_2$ (monomomorphism), or $\sigma_4$ (monomomorphism):
$$
\begin{tabular}{|l|l|l|l|}
\hline $\Z_3$ &   $\phi_1$ &   $\phi_2$ &   $\phi_3$ \\
\hline
\hline      0 & $\sigma_1$ & $\sigma_1$ & $\sigma_1$ \\
\hline      1 & $\sigma_1$ & $\sigma_2$ & $\sigma_4$ \\
\hline      2 & $\sigma_1$ & $\sigma_4$ & $\sigma_2$ \\
\hline
\end{tabular}
$$

Now I want to parameterize the possible $\phi$'s as simply as possible.  The
automorphism $\sigma_t=\phi(1)$ must be of order dividing 3.  This means that
$\sigma_t^3 = \sigma_1$.  Since the arithmetic in $\Aut(\Z_7)$ is that of the
multiplicative group $\Z_7^\times$, this means that $t^3 \equiv 1 \pmod 7$.

At this point we can write the semidirect-product arithmetic without
any reference to $\phi$.  We know that $\phi(b) = b \phi(1) = (\sigma_t)^b$,
and furthermore that $\sigma_t(x) = tx$.  This means that for $c \in \Z_7$,
$$
	[\phi(b)](c) = [\sigma_t]^b(c) = t^bc
$$
So the group arithmetic is
$$
	(a,b) + (c,d) = (a + [\phi(b)](c), b+d) = (a + c t^b, b + d).
$$

Now we can ask about the center of $\Z_7 \rtimes_\phi \Z_3$.  If $t=1$, i.e. if
$\phi$ is the trivial map, then we have the abelian group $\Z_7 \oplus \Z_3$.
Now suppose we have $t=2$, i.e. $\phi(1) = \sigma_2$.  What is the center?  We
know that $(a,b)$ is in the center if it commutes with all $(c,d)$.  A standard
trick is to say that \emph{in particular}, $(a,b)$ must commute with our
\emph{judicious choice} of $(c,d)$.  Just as a guess, let's try putting $c=1$
and $d=0$.  Then
\begin{eqnarray*}
	(a,b) + (c,d) &=& (a + c t^b, b + d) \\
	(c,d) + (a,b) &=& (c + a t^d, d + b) \\
	(a,b) + (1,0) &=& (a + t^b, b) \\
	(1,0) + (a,b) &=& (1 + a, b).
\end{eqnarray*}
For these two to be equal forces $t^b \equiv 1 \pmod 7$ for $b \in \Z_3$.  We
have $t=2$ and choices of $b$ are $0$, $1$, and $2$, so $t^b \equiv 1 \pmod 7$
only for $b=0$.  This means that $b=0$ for any $(a,b)$ in the center of $\Z_7
\rtimes_\phi \Z_3$.

At this point we need to make a second judicious choice.  We have
\begin{eqnarray*}
	(a,0) + (c,d) &=& (a + c, d) \\
	(c,d) + (a,0) &=& (c + a t^d, d).
\end{eqnarray*}
For these two to be equal requires
$$
	a - a t^d = a(1-t^d) = 0.
$$
Choose $d=1$ to get
$$a-2a = a(1-2) = 6a = 0$$
which forces $a=0$.  This, together with
$b=0$, shows that the center of $\Z_7 \rtimes_\phi \Z_3$, for non-trivial
$\phi$, is trivial.

\begin{center}
* * *
\end{center}

Next, we generalize.  What here depended on specific values $m=7$ and $n=3$?
We used the fact that $m$ was prime, and we required a solution to $t^n \equiv
1 \pmod m$.  In order for the map $\phi$ to be non-trivial, we required a
non-trivial solution, i.e. $t \not\equiv 1 \pmod m$.  This is what I have in
the past heard referred to as a \bfidx{metacyclic group} parameterized by $m$,
$n$, and $t$.  I call these two conditions on $t$ a \emphidx{constructibility
criterion}.

What about the center of $\Z_m \rtimes_\phi \Z_n$ for prime $m$?  The same two
judicious choices give us
$$
	t^b = 1
$$
and
$$
	a(1-t^d) = 0.
$$
The second of these forces $a=0$ if $m$ is prime, as long as $t$ is not 1,
which is true for the non-abelian case of interest.  The first does not always
force $b=0$.

For example, with $n=4$ and $t=2$, the constructibility criterion is
for there to be a non-trivial solution $t$ for
$$
	t^4 \equiv 1 \pmod 7 \qand t \not\equiv 1 \pmod 7.
$$
This is satisfied by $t=6$.  Then $t^b=1$ has solutions $b=0$ and $b=2$, so the
center is non-trivial:
$$
	Z(\Z_7 \rtimes_\phi \Z_3) = \{(0,0), (0,2)\}.
$$

%% ================================================================
\section{Classification of small groups}

A common question is:  classify all groups of order 20.  Often, we are given an
order of the form $p^2 q$ for primes $p$ and $q$.  If you read through various
algebra texts, e.g. \cite{bib:df}, you will see various tricks employed.  Here,
though, is a (not necessarily exhaustive!) list of the kinds of things you can
try.

\begin{itemize}

\item[(0)] The zeroth step is to know something about your destination:

	\begin{itemize}

	\item Write down all the abelian groups, using, say,
	elementary-divisor decomposition.

	\item Also write down any non-abelian groups that come to mind.  For
	example, for every even order there is a dihedral group of that order.  So
	for order 20, we know there is $\mcD_{10}$.  Likewise, if 4 divides the
	order of the group, then there is the product of a dihedral with a
	cyclic-two --- e.g. for order 20, there is $\mcD_{5} \times \mcC_2$.
	
	\end{itemize}

Listing some known groups will give you a lower bound on the number of
non-abelian groups, helping you to check your work in subsequent steps.

\item[(1)] Use the Sylow theorems.  E.g. for order $p^2q$ we have:
	\begin{eqnarray*}
	n_p &\equiv& 1 \mod p, \\
	n_q &\equiv& 1 \mod q, \\
	n_p &\mid&   q, \\
	n_q &\mid&   p^2.
	\end{eqnarray*}

\item[(2)] If you can conclude that both $n_p=1$ and $n_q=1$, then let $P$ be
the $p$-Sylow subgroup and let $Q$ be the $q$-Sylow subgroup.  Then $G = P
\times Q$.  Often, this will reduce to the abelian cases:  groups of order $p$
or $p^2$ are abelian.  However, there are non-abelian groups of order $p^3$.

\item[(3)] For the case that, say, $n_p=1$ but $n_q \ne 1$, then $G = P \rtimes
Q$.  Now you can list out the homomorphisms from $Q$ into $\Aut(P)$.  It is
handy to know that:
	\begin{itemize}
	\item $\Aut(\Z_p) \cong \F_p^\times \cong \Z_{p-1}$.
	\item $\Aut(\Z_p^n) \cong \GL(n, \F_p)$.
	Also, from \cite{bib:rotman},
	$$
		\#\GL(n, \F_p) = (p^n-1)(p^n-p)(p^n-p^2\cdots(p^n-p^{n-1}).
	$$
	\end{itemize}

\item[(4)] Petal diagrams.  [Needs a nice picture here.] Say you have the case
$p=3$ and $n_p = 4$.  Then there are four subgroups of order 3, which intersect
only at the identity.  This means there are at least 9 elements in the group, 8
of them of order 3 --- with none of the latter possibly being in a $q$-Sylow
subgroup.  Often, you can use such an argument to show that such a case would
require more elements than the order of the group.  [Insert an example here.]

\end{itemize}

Do note that Rotman soft-pedals classification of groups of a given order.
See, for example, \cite{bib:df} for a more thorough treatment.

%% ================================================================
\section{Wreath products}

\emph{Note:  This section is not qualifier material.  The subject of wreath
products came up while I was TA'ing 511 in 2006-2007, and I couldn't find any
examples as clear as the following so I thought I'd write them down for
posterity.}

\begin{defn}
The \bfidx{wreath product} (as I have seen it most clearly defined) of two
groups $A$ and $K$ is as follows: $K$ maps homomorphically into $\mcS_n$ for
some $n$.  (This makes sense when $K$ is finite.  A wreath product can also be
defined for infinite $K$.)  Then
$$A \wr K = A^n \rtimes K$$
where the action of $K$ on $A^n$ is by permuting indices on $n$-tuples in
$A^n$.  This requires specifying $n$ as well as the homomorphism from $K$ into
$\mcS_n$.  When no homomorphism is given, it is taken to be the left-regular
representation.  (Remember that for the left regular action, $n$ would be the
order of $K$.)
\end{defn}

\begin{rem}
The automorphism group of $A$ has nothing to do with the wreath product (again,
as I have seen it defined).  \emph{All} the group $K$ does is permute the
\emph{positions} of $n$-tuples of $A^n$ for some $n$ --- it does not act
automorphically on the \emph{elements} at those positions.
\end{rem}

\beginex
For $\Z \wr \Z_3$, we could have $\Z^3 \rtimes \Z_3$ with $\Z_3$ cyclically
permuting triples of integers.  I will use the exponent notation for semidirect
actions, as in section \ref{sec:semi}, and since $\Z$ is abelian, I will use
additive rather than multiplicative notation:
\begin{eqnarray*}
	((m_1, m_2, m_3), a) + ((n_1, n_2, n_3), b)
	&=& ((m_1, m_2, m_3)+(n_1, n_2, n_3)^a, a+b).
\end{eqnarray*}
If we let $\Z_3$ act on $\Z^3$ by right-shifting, then as a particular example:
\begin{eqnarray*}
	((m_1, m_2, m_3), 1) + ((n_1, n_2, n_3), 2)
	&=& ((m_1, m_2, m_3)+(n_1, n_2, n_3)^1, 1+2) \\
	&=& ((m_1, m_2, m_3)+(n_2, n_3, n_1), 0) \\
	&=& ((m_1+n_2, m_2+n_3, m_3+n_1), 0).
\end{eqnarray*}
Note that the group operation on $A^n$ (here, $\Z^3$) is just plain old
componentwise operation, \emph{except} that we first permute the positions of
the tuples in the second operand.  Hence the term \emph{wreath}.

We could also have $\Z_3$ act on $\Z^3$ by left-shifting, or by no shift at
all.  Or we could have $\Z_3$ act on $\Z^6$ by left-shifting pairs of triples:
$$
	(m_1,m_2,m_3,m_4,m_5,m_6)^1 = (m_2,m_3,m_1,m_5,m_6,m_4).
$$
Etc. etc.
\mendex

\beginex
For $\Z \wr \mcS_3$, there are several possibilities.  Again taking $n=3$,
one possibility is:
\begin{eqnarray*}
	((m_1, m_2, m_3), \sigma) + ((n_1, n_2, n_3), \tau)
	&=& ((m_1, m_2, m_3)+(n_1, n_2, n_3)^\sigma, \sigma\circ\tau).
\end{eqnarray*}
As a particular example in that construction,
\begin{eqnarray*}
	((m_1, m_2, m_3), (13)) + ((n_1, n_2, n_3), (123))
	&=& ((m_1, m_2, m_3)+(n_1, n_2, n_3)^{(13)}, (13)\circ(123)) \\
	&=& ((m_1, m_2, m_3)+(n_3, n_2, n_1), (12)) \\
	&=& ((m_1+n_3, m_2+n_2, m_3+n_1), (12)).
\end{eqnarray*}
We could also have $\mcS_3$ act on $\Z^3$ by permutations, or inverse
permutations; we could have $\mcS_3$ act on $\Z^2$ by having the odd
permutations swap 2-tuples of integers and having the even permutations leave
2-tuples of integers intact; etc.
\mendex

%% ================================================================
\section{Rings}

Let $m$ be a squarefree integer, other than 0 or 1.  Then the \bfidx{quadratic
integers} of $\Q(\sqrt{m})$, which Grove calls \plainidx{$R_m$}, are
$$
	\begin{cases}
		\Z[\frac{1+\sqrt{m}}{2}], &  m \equiv 1 \pmod 4. \\
		\Z[\sqrt{m}], &  m \equiv 2, 3 \pmod 4 \\
	\end{cases}
$$

\begin{mnem}
Which is which?  Just remember that $i = \sqrt{-1}$, $-1$ is 3 mod 4, the
integers of $\Q(i)$ are $\Z[i]$, and ``two three four''.
\end{mnem}

\begin{mnem}
\label{mnem:fepui}
Remember \bfidx{FEPUI} [feh, pooey!]: fields $\subsetneq$ Euclidean domains
$\subsetneq$ PIDs $\subsetneq$ UFDs $\subsetneq$ integral domains.
\end{mnem}

(See also CANSA for groups, mnemonic \ref{mnem:cansa}.) All these inclusions
are proper.  Standard examples (\cite{bib:df}, end of section 8.3):

\begin{itemize}
\item $\Z$ is a Euclidean domain but not a field.
\item  $\Z[\frac{1+\sqrt{-19}}{2}]$ (i.e. the ring of integers of
$\Q[\sqrt{-19}]$, as $-19 \equiv 1 \pmod 4$) is a PID which is not Euclidean.
\item $\Z[x]$ is a UFD but not a PID (consider $\pig{2}$ and $\pig{x}$).
\item  $\Z[\sqrt{-5}]$ (i.e. the ring of integers of
$\Q[\sqrt{-5}]$, as $-5 \equiv 3 \pmod 4$) is an integral domain which is
not a UFD.  (Remember: $6 = 2\cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5})$.)
\end{itemize}


%% ================================================================
\section{Fields}

galois groups for cubics

\bfidx{Eisenstien criterion}
Eisenstein --- make the distinction between irr'ty over $\Z$ vs. $\Q$
(or, ID and its QF more generally).

calculus to find TPs etc., or cubic \bfidx{discriminant} --- equivalent.

galois groups for quartics?

$\mcS_p$ trick for quintics.

%% ================================================================
\section{Modules and tensor products}

\begin{defn}
An $R$-module is \bfidxaux{free}{free module} iff it may be written as
a direct sum of copies of $R$.
\end{defn}

\beginex
An $n$-dimensional vector space over a field $K$ is isomorphic to $K^n$, hence
free.
\mendex

\begin{prop}
Let $R$ be a commutative ring with identity, and let $M$ be a two-sided
unital $R$-module.  Then
$$
	R \tensor_R M \cong M.
$$
\end{prop}

\begin{mnem}
Move all scalars over:
$$
	r \tensor m = (r\cdot 1)\tensor m = 1 \tensor rm.
$$
This works even for $r=0$, since $0\cdot 1 = 0$.
\end{mnem}

\begin{prop}[Hom modules]
Let $R$ be a commutative ring; let $M$ and $N$ be $R$-modules.
Then
$$
	\Hom_R(M, N)
$$
is an $R$-module, where module addition is given by
$$
	(\phi+\psi)(m) = \phi(m)+\psi(m)
$$
and ring-module multiplication is given by
$$
	(r\phi)(m) = r\phi(m).
$$
\end{prop}

\begin{rem}
Try to prove that $r\phi$ is actually an $R$-module homomorphism.  You will
immediately see why $R$ needs to be commutative.  (If $R$ is not commutative,
then $\Hom_R(M,N)$ is merely an abelian group.)
\end{rem}

\begin{rem}
We can instead make\index{$\mathrm{Hom}_R(M,M)$} the abelian group
$\Hom_R(M,M)$ into a ring, using addition as above, but with composition as
multiplication.
\end{rem}

\begin{rem}
The notation\index{$\mathrm{Hom}_R(M,M)$}\index{$\mathrm{End}_R(M)$}
$\Hom_R(M,M)$ is ambiguous --- is it an $R$-module with ring-module
multiplication as above, or is it a ring with composition as its
multiplication?  Sometimes people write $\End_R(M)$ to signify the latter.
\end{rem}

\begin{prop}[FOIL for hom modules]
Let $R$ be a commutative ring;
let\index{FOIL} $M$, $M_1$, $M_2$,
$N$, $N_1$, and $N_2$ be $R$-modules.  Then
$$
	\Hom_R(M_1 \oplus M_2, N) \cong \Hom_R(M_1, N) \oplus \Hom_R(M_2, N)
$$
and
$$
	\Hom_R(M, N_1 \oplus N_2) \cong \Hom_R(M, N_1) \oplus \Hom_R(M, N_2).
$$
\end{prop}

\begin{prop}[FOIL for tensor products of direct sums]
Let\index{FOIL} $M$, $M_1$, and $M_2$ be left $R$-modules;
let $N$, $N_1$, and $N_2$ be right $R$-modules.  Then
$$
	(M_1 \oplus M_2) \tensor N
	\cong (M_1 \oplus N) \tensor (M_2 \oplus N)
	\qqand
	M \tensor (N_1 \oplus N_2)
	\cong (M \oplus N_1) \tensor (M \oplus N_2)
$$
\end{prop}

\begin{cor}
Let $M$ and $N$ be free modules of ranks $m$ and $n$, respectively.
Then $M \tensor N$ has rank $mn$.
\begin{proof}
$$
	R^m \tensor R^n \cong
	\bigoplus_{i=1}^m R \tensor \bigoplus_{i=1}^n R \cong
	(R \tensor R)^{mn} \cong R^{mn}.
$$
\end{proof}
\end{cor}

How to show a module is \bfidx{not free}:  type up GD's nice solution here.

%% ================================================================
\newpage
\section{Problem solutions}

%% ----------------------------------------------------------------
\subsection{January 2003 \# 2A}

\begin{problem}
Let $G$ be a group, with $x$ an element of finite order in $G$.
Let $p$ be a prime.
Prove that there exist unique $y$ and $z$ in $G$ such that (1) $x=yz$, (2) the
order of $y$ is a power of $p$, and (3) the order of $z$ is relatively prime to
$p$.
\begin{rem*}
This proof is due to Tommy Occhipinti.
\end{rem*}
\begin{proof}
%First note that if the result is true for all $G$, it must be true in
%particular for $G=\pig{x}$.  Thus it suffices to consider $y$ and $z$
%being powers of $x$.

Since we have little else to work with other than the finite order of $x$, let
$m=|x|$.  To split up $m$, we could use Euclidean division to obtain $m=qp+r$,
or we could factor $m$ into $m=ap^k$ where $a$ is relatively prime to $p$.  The
latter approach sounds more promising since it gives us the phrase ``relatively
prime''.  Since $x^{ap^k}=1$, $x^a$ has order $p^k$, and $x^{p^k}$ has order
$a$.  But these don't give us $y$ and $z$ right away:  the product of $x^a$ and
$x^{p^k}$ isn't necessarily $1$, and furthermore these are not the only
elements of those respective orders: $(x^{ia})^{p^k}=1$ for all integers $i$
(where we may take $ia$ mod $m$).  Likewise, $(x^{jp^k})^a = 1$ for all $j$.

Since
$$
	x^{ia}x^{jp^k} =
	x^{ia + jp^k} = 1,
$$
we have
$$
	ia+jp^k \equiv 0 \pmod m.
$$
Since $a$ and $p^k$ are relatively prime by hypothesis, we can use the Chinese
Remainder Theorem (suggested by the phrase ``mod $m$'' above) to solve for
unique $i$ and $j$.

xxx to do:  this shows orders \emph{divide} $a$ and $p^k$ \ldots.  Also we have
shown uniqueness \emph{inside} $\pig x$; need to show uniqueness in all of $G$.
\end{proof}
\end{problem}

%% ----------------------------------------------------------------
\subsection{January 2006}

\begin{problem}
Show that any group of order $4n+2$, for integer $n$, contains a subgroup
of index 2.
\begin{rem*}
The idea of the following proof is due to Dinesh Thakur and Tommy Occhipinti.
\end{rem*}
\begin{proof}
Let $G$ be such a group.  Any subgroup of index 2 is normal.  When we want to
find a normal subgroup, we should always think of the kernel of a homomorphism,
since when you have one, you have the other.  The trick is to find such a
homomorphism.

A familiar map with image having order 2 is the parity map on $\mcS_n$: if we
had a symmetric group and if we had an element of odd parity, we'd be done.
Here, we don't have a symmetric group.  Not quite!

Consider the Cayley left representation of $G$.  (That is, we send $G$
injectively into $\mcS_G$ where $G$ acts on itself by left multiplication.
This sounds fancy, but just think of a Cayley table (multiplication table) for
a group.  Recall that the rows of these tables are always permutations of $G$;
also, in each row and each column, each element appears only once.)

Since $2$ divides the order of $G$, by Cauchy's theorem there exists an element
of order 2 in $G$.  Call it $\sigma$.  By the remark in the preceding
paragraph, the image of $\sigma$ has no fixed points.  Since it is of order 2,
it must therefore be the product of $2n+1$ transpositions.  This is an odd
number, and therefore the parity of $\sigma$ must be odd.

Now consider the parity map from $\mcS_G$ to $\{\pm 1\}$.  Since we just showed
that $\mcS_G$ has an odd permutation, the image of the parity map is $\{\pm
1\}$, not just $\{1\}$.  By the first group homomorphism theorem, the kernel of
the parity map must have index 2.
\end{proof}
\end{problem}

%% ----------------------------------------------------------------
\subsection{A nice fact}

Here is something which came up during summer 2006 qual prep.  I found an old,
second-hand proof of it and thought I'd type it up for future reference.

\begin{prop}
Let $G$ be a group with center $Z(G)$.  If $G/Z(G)$ is cyclic, $G$ is abelian.
\begin{proof}

Since $G/Z(G)$ is cyclic, let $\pi Z(G)$ be a generator of the quotient group.
Let $g_1, g_2$ be arbitrary elements of $G$, so $g_1Z(G), g_2Z(G)$ are
arbitrary elements of $G/Z(G)$.  Since $G/Z(G)$ is cyclic, $g_1Z(G) = \pi^i
Z(G)$ and $g_2Z(G) = \pi^j Z(G)$ for some integer $i, j$ from which $ \pi^{-i}
g_1 \in Z(G)$ and $\pi^{-j} g_2 \in Z(G)$.  Then for some $z_1, z_2 \in Z(G)$,
$\pi^{-1} g_1 = z_1$ and $\pi^{-j} g_2 = z_2$.  Then
\begin{eqnarray*}
	g_1 &=& \pi^i z_1 \\
	g_2 &=& \pi^j z_2 \\
	g_1 g_2 &=& \pi^i z_1 \pi^j z_2 \\
	&=& \pi^i \pi^j z_1 z_2 \textrm{ since $z_1, z_2 \in Z(G)$ }\\
	&=& \pi^{i+j} z_1 z_2 \\
	g_2g_1  &=& \pi^j z_2 \pi^i z_1 \\
	&=& \pi^j \pi^i z_2 z_1 \textrm{ since $z_1, z_2 \in Z(G)$ }\\
	&=& \pi^{i+j} z_1 z_2 \\
	&=& g_2g_1 
\end{eqnarray*}
Since $g_1, g_2$ were arbitrary in $G$ and since they commute, $G$ is abelian.

\end{proof}
\end{prop}
