Direct products revisited

One of the things I talked about last time was the cartesian product of permutation groups. Unfortunately, I got a bit confused, and probably managed to confuse everyone else too. So I thought it might be a good idea to have another go, coming from another angle.

Given two graphs g1 and g2, we can form a graph g1+g2, just by placing them side by side. For example, here's what c 4 + c 5 looks like:

It's important that you see this as a single graph with 9 vertices, rather than as two graphs with four and five vertices. Unlike the graphs we have looked at previously, this graph is not connected.

When we're writing the Haskell code for this sum of two graphs, we need to be careful. What if the vertices in the two graphs are using the same labels. In this case, c4 has vertices [1..4], c 5 has vertices [1..5]. If we're not careful, we might get this graph instead:


We need to take a disjoint union of the vertices, even if in fact they are using the same labels. The way to do this is to use Either.

So, here's the code for the disjoint sum of two graphs:

dsum g1 g2 = graph (vs,es) where
    vs = map Left (vertices g1) ++ map Right (vertices g2)
    es = (map . map) Left (edges g1) ++ (map . map) Right (edges g2)

And here it is in action:

> dsum (c 4) (c 5)
G [Left 1,Left 2,Left 3,Left 4,Right 1,Right 2,Right 3,Right 4,Right 5]
[[Left 1,Left 2],[Left 1,Left 4],[Left 2,Left 3],[Left 3,Left 4],
[Right 1,Right 2],[Right 1,Right 5],[Right 2,Right 3],[Right 3,Right 4],[Right 4,Right 5]]

Notice how, as required, our new graph has nine vertices.

Now, what are the symmetries of g1+g2 going to look like? Well suppose we already know the symmetry group of g1 - call it H - and the symmetry group of g2 - call it K. Hopefully it's obvious that given any h from H, and k from K - symmetries of g1 and g2 respectively - then doing h to the left hand side and k to the right hand side of g1+g2 will be a symmetry.

So we can think of the symmetry group of g1+g2 as consisting of elements (h,k), where we do h to the left hand side and k to the right hand side. If we do (h1,k1) then (h2,k2), it's the same as doing (h1 then h2, k1 then k2). Or, in group language, (h1,k1)*(h2,k2) = (h1*h2,k1*k2).

Another way to think about this. Normally, if we have two symmetries a and b, it matters what order we do them in. a*b (a then b) isn't necessarily the same as b*a (b then a). However, if a is a symmetry of the left hand side, and b is a symmetry of the right hand side, then the order doesn't matter. a*b = b*a. We say that a and b commute. The reason the order doesn't matter is that a is moving only left hand vertices and edges, and b is moving only right hand vertices and edges.

Because of this, there's no need to write the elements as (h,k), we can just write them as h*k. Then h1*k1 * h2*k2 = h1*h2 * k1*k2 (since we know hs and ks commute).

In this case, the symmetry group of g1+g2 is the direct product of the symmetry group of g1 and the symmetry group of g2. (Last time, I incorrectly called this the cartesian product.) In Haskell:

dp hs ks =
    [P $ M.fromList $ map (\(x,x') -> (Left x,Left x')) $ M.toList h' | P h' <- hs] ++
    [P $ M.fromList $ map (\(y,y') -> (Right y,Right y')) $ M.toList k' | P k' <- ks] 

Recall that in HaskellForMaths, permutations are implemented using Data.Map. What this is saying is that we change all the (x,x') mappings in the permutations in the first group to (Left x, Left x') mappings, and all the (y,y') mappings in the second group to (Right y, Right y') mappings. The construction ensures that the elements of h and the elements of k are acting on disjoint sets, so they will commute with one another. Hopefully you can see that the the group calculated by this function is (isomorphic to) the direct product.
(This function is called "cp" in HaskellForMaths 0.1.3, but I'll change it to "dp" in the next release.)

As expected, we have:

> mapM_ print $ graphAuts2 $ dsum (c 4) (c 5)
[[Left 1,Left 2],[Left 3,Left 4]]
[[Left 1,Left 3]]
[[Left 1,Left 4,Left 3,Left 2]]
[[Left 2,Left 4]]
[[Right 1,Right 2],[Right 3,Right 5]]
[[Right 1,Right 3],[Right 4,Right 5]]
[[Right 1,Right 4],[Right 2,Right 3]]
[[Right 1,Right 5,Right 4,Right 3,Right 2]]
[[Right 2,Right 5],[Right 3,Right 4]]

> mapM_ print $ graphAuts2 (c 4) `dp` graphAuts2 (c 5)
[[Left 1,Left 2],[Left 3,Left 4]]
[[Left 1,Left 3]]
[[Left 1,Left 4,Left 3,Left 2]]
[[Left 2,Left 4]]
[[Right 1,Right 2],[Right 3,Right 5]]
[[Right 1,Right 3],[Right 4,Right 5]]
[[Right 1,Right 4],[Right 2,Right 3]]
[[Right 1,Right 5,Right 4,Right 3,Right 2]]
[[Right 2,Right 5],[Right 3,Right 4]]

They're the same.

The number of elements in a group is called its order:

order gs = length $ elts gs

(Remember that we always represent a group by a list of generators. "order" calculates how many elements are in the group generated by gs.)

The direct product of H and K consists of all pairs hk or (h,k) from h and k. We're guaranteed that (h1,k1) /= (h2,k2), unless h1=h2 and k1=k2. Hence we will always find
order (hs `dp` ks) == order hs * order ks

So that's the direct product. Now, last time, we were looking at the complete bipartite graphs kb m n. In this graph, any permutation of the left vertices among themselves, together with any permutation of the right vertices among themselves, is a symmetry of the graph.

The set of all permutations of [1..n] is called S n. So what we're saying is that the symmetry group of kb m n contains
_S m `dp` _S n

Hopefully that makes a little more sense now.