I was learning group theory recently, and it’s very fun, but it’s also abstract, and that makes it confusing. “Groups are symmetries”, but groups can be anything that follows the group laws. Groups permute themselves in some way??
So I thought I’d explain it in a fun setting that makes it clear what everything is. Zoombinis are from a videogame that teach children math concepts like algebra, so the metaphor is fitting, but for copyright reasons I may rename these later (maybe goombinis?). This post is for people who are learning group theory or are curious about it, or people who love Zoombinis!
Zoombinis getting on a boat. You can actually still play the original game (via links on this page)!
Zoombinis on Abstract Algebra Island
We’ve just discovered a new Zoombini island! It’s full of all sorts of cute little zoombinis, which are a cross between pikmin/pokemon/helper elves. On this island, zoombinis live in social cliques called “groups”. When zoombinis form a group we’ll write their names together in curly braces, like {green, pink, yellow} (We’ll pretend that in a group they all have different nose colors and call them by that color).
Each group also has a magical cloning/merging machine. It takes a zoombini on the left, one on the right, and then merges them into a third zoombini! To denote “putting the green zoombini on the left and the yellow on the right side yields a pink zoombini”, we’ll write (green, yellow)→pink. (Btw, we can create as many copies of zoombinis as we need for our experiments).
Each group has set up their machine a little differently, but after watching them use it, you notice a few patterns. Regardless of the group, the machine follows a few rules:
- There’s a “neutral” zoombini: when merged with anything else, the machine outputs the other zoombini: (neutral, a) → a and (a, neutral) → a
- Every zoombini has a kind of “soulmate zoombini”, when the two merge they create the neutral zoombini.
- Merging 3 zoombinis works out the same whether you merge them as ((a,b), c) or (a, (b,c))
- Any given zoombini never merges the same way across different zoombinis: (zoombini, x) and (zoombini, y) only have the same outcome if x == y
- The machine always outputs a zoombini from the group, never a zoombini from outside the group.
The machine can have a different output depending on the side the zoombinis are put in. Eg (x, y) might give a different result than (y, x). (Note: some groups have their machine so that (a,b) always equals (b,a), they’re called “abelian” groups of zoombinis.)
Cataloguing the merging machine
You decide to catalogue the output of the merging machine for each pair of zoombini to look for patterns.
It’s a bit hard to tell all these zoombinis apart, so instead of talking about a “pink zoombini” or a “green zoombini”, you give them each an alias for easier record-keeping. You ask them all to line up, and then you number them from 1 to N. This relabelling of “pink zoombini” to the number 1, “green zoombini” to the number 2, etc, is an isomorphism because now you have a group that follows the same rules, but it’s made up of numbers instead of zoombinis.
One at a time
To catalogue the output, you take the first zoombini (#1), and then you leave it in the left side of the machine.
Then, (one by one) you put every zoombini of the group on the right side (including a copy of the first one): (1,1), (1,2), (1,3) and you record the result: (1,1)→37, (1,2)→4, (1,3)→10, etc. As a good scientist, you repeat this for every zoombini.
(1,1) → 37
(1,2) → 4
(1,3) → 10
...
Now you can look up the result of any pair in the cloning/merging machine without having to turn it on. If you rearrange the results, you get something that looks like a “multiplication table” from school, but the numbers represent zoombinis merging.
1 2 3 4 5
1 → 37 4 10 12 2 ...
Here’s a multiplication table for a particular abelian zoombini group that’s isomorphic to “the cyclic group of order 5”:
1 2 3 4 5
1 1 2 3 4 5
2 2 3 4 5 1
3 3 4 5 1 2
4 4 5 1 2 3
5 5 1 2 3 4
A permutation representation
While your original list was written in terms of pairs like (1,1)→37, you decide to reshape your data.
You open a new notebook, and give each zoombini its own page. On each page, you write the zoombini number at the top, and then you make two columns again. On the left you write down the numbers 1 through N. On the right you write down what the machine output was. So for #1, the first few rows are 1→37, 2→4, 3→10…
After a while, you stop writing down the left column because it’s always 1,2,3,4,5… . In this new format, you can quickly write down zoombini #1 as [37 4 10 12 2 ...].
You get a little sad, because now you’re just looking at numbers, you miss those cute zoombini faces! Now we’re looking at permutations of the numbers 1→N. If you finish your research maybe you can go back to playing with them!
You realize that with this permutation notation, you can re-create a copy of the merging machine:
If zoombini a maps 1→37, and zoombini b maps 37→5, then merging a and b maps 1→5, as we apply a’s mapping, then b’s mapping. If you do this for the whole 1→N list, you get the permutation that corresponds to merging zoombinis (a,b) in the machine.
This operation of “wiring together” two permutations is called “composition”, it’s mapping out what it would be like to do one permutation after another.
And this composition operation works the exact same way as the merging machine!
So we’ve found an isomorphism between the group of zoombinis and the group of permutations of the numbers 1→N.
While this sounds like we’re doing more work manipulating permutations and long lists of numbers, this is really useful.
Instead of talking about “the green zoombini”, or “zoombini #37”, we can instead say “the permutation which takes 1,2,3,4,... to 37,4,10,12,...”. Now we have a universal language for zoombinis which works for anything that follows the zoombini machine group rules. This representation works for any group, whether it’s made of zoombinis, xoombinis, or any other mathematical objects that follow the group laws.
Conclusion: Back to the “real world”
In math, a group is anything that follows the group laws. Groups can be permutations, but they can be many things:
- real numbers under addition
- NxN matrices under multiplication
- points on an elliptic curve
- paths on a graph
This idea of taking a group of N zoombinis, and looking at what each one does on the left side of the machine, and then turning that into a permutation of the numbers 1→N is called “building a permutation representation of a group”. It’s a re-presentation because we already had a map of every (left,right) outcome, but now we’ve turned that into a different thing, a presentation of the permutation group on N zoombinis. We can take any group and turn it into a set of permutations, and then use permutations as a universal language for talking about groups. Specifically, we’ve done the following steps/isomorphisms:
Group of N Zoombinis ↔ Group of N numbers ↔ Group of permutations of N elements
Each group combines the same way, and each step is even reversible (these are isomorphisms). So regardless of what a group is made of (like zoombinis), we can turn it into a group of permutations.
While group theory can be confusing, with Zoombinis it’s easy! Stayed tuned for part 2 where we’ll look at the magic powers Zoombini have to act on sets.
comments powered by Disqus