From cube-lovers-errors@mc.lcs.mit.edu Thu Apr 8 20:23:30 1999
Return-Path:
Received: from sun28.aic.nrl.navy.mil (sun28.aic.nrl.navy.mil [132.250.84.38])
by mc.lcs.mit.edu (8.9.1a/8.9.1-mod) with SMTP id UAA01802
for ; Thu, 8 Apr 1999 20:23:29 -0400 (EDT)
Precedence: bulk
Errors-To: cube-lovers-errors@mc.lcs.mit.edu
Date: Thu, 8 Apr 99 19:45:22 EDT
Message-Id: <9904082345.AA16179@aic.nrl.navy.mil>
From: Dan Hoey
To: Jerry Bryan , Cube Lovers
Subject: Conjugation done right [Re: Inventing your own techniques]
First, let's make sure everyone remembers that we're using X' as an
abbreviation for X^(-1) for inverses of permutations. People really
should read the archives, at
so they know this sort of thing, but that's getting to be a lot to
ask. Still, remember that address, because it's a good place to go
for things you forgot about the list (in fact, it would be nice if the
README mentioned that cube-lovers-request@ai.mit.edu is the e-mail
address for administrative requests to the list management, just in
case someone loses their greeting message.)
Jerry Bryan wrote:
> A process of the form Y'XY is called a conjugate, and in particular is called
> the conjugate of X by Y. Note that YXY' is also a conjugate, and in particular
> is called the conjugate of X by Y'. This can be a little confusing because a
> few books (incorrectly in my opinion) call YXY' the conjugate of X by Y.
I tried to explain this a while ago, but it's such a subtle,
counterintuitive point that I had better try again. One form of
conjugate is correct, and the other form is incorrect, but just which
is correct depends on how you write function composition. The point is
that there are two schools of function composition, "leftward" and
"rightward", and the choice of your function composition determines
how you define conjugates. It's surprising that a notational
convention can have this sort of effect, but we'll see it does.
First, I'll describe the two schools of composition. It will be
convenient to consider a set X and two permutations f and g on
X. Let h:X->X be the unique permutation that satisfies h(x) = f(g(x))
for all x in X. We could let f, g, and h be any functions, not
just permutations, but we will need for them to be permutations later,
when we use the group structure.
How do we write h in terms of f and g? The rightward school says
h = g f. This is the way we have been writing things on cube-lovers
all along: we write g f for applying a permutation g to something
and then applying f to the result. But remember that we write
h(x) = f(g(x)), which is to say that (g f)(x) = f(g(x)). The fact
that the order of f and g depends on the parenthesization is often
considered ugly, so some seriously rightward people write the function
name after the arguments: That is to say, they write (x)f instead
of f(x), (x)g instead of g(x), and (x)h = ((x)g)f = (x)(g f).
This makes function composition a kind of associative law. If you're
seeing this for the first time, I'm sure you consider it a bizarre and
useless and gratuitously confusing complication, but I assure you that
rightward functions are in wide use in some branches of the
mathematical community, chiefly in abstract algebra. But cube-lovers
was started by computer programmers, not algebraists, and programmers
have f(x) very tightly wired into their minds and parsers. So
cube-lovers uses rightward composition with leftward functions, and we
say (g f)(x) = f(g(x)). As for swapping the order of f and g, we
just get over it, but there are some people out there who will call us
disfunctional.
The leftward composition school takes a different approach: they say
h(x)=f(g(x)) means h = f g. When you follow a cube process written
by these people, you have to perform it from the right to the left.
This is also a little hard to get used to, but at least we have an
"associative" rule, (f g)(x) = f(g(x)), with f and g in the same
order, without having to write our functions after the arguments. For
this reason, most mathematicians other than algebraists find leftward
composition to be more natural. You probably learned leftward
composition in calculus or whenever. But on cube-lovers no-one wanted
to write all their cube processes from right to left, so we've pretty
much forgotten about leftward composition on the list. Remember,
though, leftward composition is pretty standard for a lot of
mathematics, and it works better for the way we write functions, so
you can't really call it wrong. And there are people who say that if
we are going to write our functions to the left we also ought to
compose them to the left.
So far so good. The rightward and leftward schools write the
composition of functions in opposite orders, but either way the
permutations still form a group under composition. As long as you
don't mix them, it shouldn't change anything else, should it? But it
really does change the definition of conjugation. (Remember
conjugation? This is a message about conjugation.)
Suppose we have a group G, not necessarily a permutation group.
Conjugation is one way of mapping G to a permutation group, where
the set being permuted is the set of group elements of G. For an
element s, I'll define the right conjugate of s, R_s, as the
permutation for which R_s(g) = s' g s for all g in G. Similarly,
the left conjugate of s, L_s is defined by L_s(g) = s g s' for
all g. It's important to notice that in either case, conjugation by
a product is the composition of conjugations. For letting s and t
be two specific elements of G, we can carry out manipulations that
hold for all elements g of G. I'll calculate with the left
conjugate in the left column and the right conjugate in the right
column:
L_s(g) = s g s'; R_s(g) = s' g s;
L_t(g) = t g t'; R_t(g) = t' g t;
L_st(g) = (st) g (st)' R_st(g) = (st)' g (st)
= s t g t' s' = t' s' g s t
= L_s(t g t') = R_t(s' g s)
= L_s(L_t(g)) = R_t(R_s(g)) (*)
These calculations were carried out using the group operation of G,
independently of how we write function composition. But let's look at
how we write the composition in our two notations.
In the rightward composition that cube-lovers has been using all
along, (*) shows that L_st = L_t L_s and R_st = R_s R_t. So the
mapping s |-> L_s is an _antihomomorphism_--it reverses the order of
multiplication--but s |-> R_s is a homomorphism. Homomorphisms are
a lot nicer than antihomomorphisms, so we should use right conjugation
all the time, right?
But consider the people who use leftward composition, (f g)(x)=f(g(x)).
So the function composition in (*) is now written L_st = L_s L_t and
R_st = R_t R_s. So with leftward composition, _left_ conjugation is
the homomorphism, and _right_ conjugation is the antihomomorphism.
It is so very convenient for conjugation to be a homomorphism that
people who use rightward composition always use right conjugation, and
people who use leftward composition always use left conjugation (unless
they think it doesn't matter and guess wrong). We're rightward
composers on cube-lovers, so conjugation by s is g |-> s' t s, but
remember that most math texts (other than algebra) will use the
leftward composition, and so they will correctly use left conjugation,
g |-> s g s'.
I learned this from Jim Saxe, when I tried using left conjugation in
the Symmetry and Local Maxima message. Jim told me that unless I
wanted to start using leftward composition I had better use right
conjugation, but I was pretty sure it really didn't matter. Jim just
splained and splained until he got across how much it really does
matter, and why the only right answer is different in different books.
Now I've done it for you, and I hope it helps.
And they said that consistency was the hobgoblin of little minds....
Dan
Hoey@AIC.NRL.Navy.Mil