M417 Homework 6 Spring 2004

*Instructions*: Solutions are due Fri., March 12.

- A
*digraph* (i.e., directed graph) is a set
of vertices, some of which can be connected by an arrow
(i.e., a directed edge). For example, we can associate to
each group G its subgroup digraph, in which each subgroup H of G is
represented by a vertex v_{H}, and there is an arrow from
a vertex v_{H} to a vertex v_{H'} exactly when
H' properly contains H. A *directed path*
(of length r) in a digraph is a sequence v_{0},..., v_{r}
of vertices such that for each 1 <= i <= r there is an arrow
from v_{i-1} to v_{i}.

Show that
every directed path in the subgroup digraph of a cyclic group of order N
has length at most log_{2}N.

- Let g and x be in S
_{n}. Assume that x =
(a_{1} ... a_{r})
is an r-cycle. Show that gxg^{-1}
= (g(a_{1}) ... g(a_{r})).

- Find the centralizer of (1234) in S
_{4}. [Hint:
Apply (2).]

- Let n and N be positive integers.
- (a) If f:
**Z**_{n} -> **Z**_{N} is
a homomorphism of groups and m = f(1),
show that N divides mn, and that f(x) = mx mod N, for
all x in **Z**_{n}.
- (b) Conversely, if m is a positive integer
such that N divides mn, show that
f(x)= mx mod N defines a homomorphism
f:
**Z**_{n} -> **Z**_{N}.

- Let f: G -> H be a homomorphism of groups.
If G is finite, show that |f(G)||ker f|=|G|.