What does adding numbers together have in common with rotating a square piece of paper? What does rearranging a deck of cards have in common with rotating and flipping a square piece of paper? These questions are rhetorical; I know the answers, and if you don't already, I hope to help you learn.
Let's start with that square piece of paper. Suppose we have a square piece of paper, and we mark a dot on it, kind of off-center, like this.
Now, let's think about moving that piece of paper around, making sure (for now) to keep the dot visible. We can slide the paper around the table,
Or we can turn it around as we move it.
Now, there are many ways to move the paper around, so let's simplify things to make it easier to talk about. Let's add another rule. We already had "the dot must be visible". Let's add "the paper must end up occupying the same area". We can think about this as follows: we want to talk about motions where the paper ends up where it started, and if you closed your eyes, you wouldn't be able to tell which motion was done, but if you open your eyes, you can see where the dot moved to.
Let's look more closely at what I'm saying in that last sentence. Whatever we do to the paper, we currently only care about how it starts out, and how it ends up. To see why this makes sense, consider the process of rotating the paper a quarter-turn clockwise. If you stop halfway through, it's got points where it should have sides, and sides where it should have points!
You could definitely tell something was different if you felt that with your eyes closed! So, getting to one of the "allowed" positions means passing through "disallowed" positions.
Next, let's compare a half-turn clockwise to a half-turn counter-clockwise. Looking at them, we can't tell the difference between a square that was turned halfway around clockwise, and a square that was turned halfway around counter-clockwise. In contrast, consider doing these turns and stopping halfway through the turn. Each one stops at a quarter-turn. (A different quarter-turn, no less, but let's come back to that later.)
Let's look over what we can do to a square piece of paper, following these rules:
- We've seen that we can turn it a quarter-turn clockwise
- We've seen that we can turn it a quarter-turn counter-clockwise
- We've seen that we can turn it a half-turn
Stopping halfway through the half-turn rotations produced a quarter-turn, which suggests that it's possible to combine these turns into other "things to do to a square piece of paper without flipping it, but making it take up the same space at the end". Now, "things" sounds a little weird, and "things to do to a square piece of paper without flipping it, but making it take up the same space at the end" is way too long. Let's call them elements instead.
Here is the result of applying each of these three elements to the same square piece of paper.
Here are some examples of combining these elements:
- If we do a quarter-turn clockwise followed by a half-turn, we get a quarter-turn counter-clockwise.
- If we do a half turn followed by a quarter-turn counter-clockwise, we get a quarter-turn clockwise.
- If we do two half-turns, we get... hm...
It looks like that list of three elements was missing an entry. Let's try to fix that.
- We can do nothing to it
- We can turn it a quarter-turn clockwise
- We can turn it a quarter-turn counter-clockwise
- We can turn it a half-turn
Now, two half-turns combine into "nothing", and "nothing" and "something" combine into the same "something". When you consider the individual combination of "nothing" and "something", it doesn't look too impressive (all that work just to get one of the same things you put in?), but it will be useful for more than filling out that list, I promise. Now, a "do-nothing" element is called an identity element, or identity, for short.
Speaking of that list, I said there were three elements in it, then I said four! Is it possible I've missed more elements?
I'll try to convince you that I haven't.
To start with, consider the corner of the square next to the dot. Let's label that corner A. Because we're moving the paper around, not somehow moving the dot around on the paper, the dot and A are always the same distance from each other, so by looking at the dot, we can find A.
Now, let's look at these square pieces of paper with A labeled. We see that the list of four elements has one element for each corner that A can end up at. Suppose we label them B, C, and D, clockwise from A.
We can describe the listed elements as follows:
- An element that takes A to A.
- An element that takes A to B.
- An element that takes A to D.
- An element that takes A to C.
This shows that we've listed one element for each possible destination corner for A. Is it possible that there are some more elements that I've missed? Let's take a closer look at how A and the dot relate to each other, and the other corners.
If we go clockwise from A, we always see the following things in this order:
- A (to start with)
- the dot
- back to A
We can't change the relative positions of the corners and the dot. Therefore, under the constraints that we put on this system, if we know which point A has gone to, then we know which point each other point has gone to. B must be the point right after A, and so on.
Now that we know there are just four elements in the list of things to do to this square, let's try figuring out how they combine.
First off, how many combinations are there?
Well, there are four elements. A combination of elements has a first element, and a second element. There's no way that picking one element narrows down our choices for the other element, so it must be the case that each of the four choices for the "first element" can combine with each of the four choices for the "second element". So, there are four groups of four choices. Four fours. Four, plus four, plus four, plus four. You can trust me that that's sixteen, work it out for yourself, or count the little squares in the following diagram.
In the diagram, I have named each element after the destination of A. Let the left side represent the first element in the combination, and the top, the second element. The square that is directly to the right of a label on the left, and directly below a label on top, represents the combination of, first the left label, and then the top. Let's try to fill in the labels for all of the combinations. To start with, because each element is named after the destination of A, we know that A is the identity element. Therefore, if one of the elements in the combination is A, then the combination is just the other element. This gives us the top row and the left column, which you can count up as seven squares. We're nearly halfway done!
Let's look at the second column. The first column is filled in, and indicates that if we turn the square some amount and then do nothing, that is indistinguishable from just turning it that amount. To go from the first column to the second column, we just have to turn the square a quarter-turn clockwise. On a quarter-turn, B goes to C, so moving A to B twice puts A on C. Furthermore, C goes to D, so moving A to C and then A to B moves A to D. Finally, D goes to A, so moving A to D and then A to B moves A to A.
Notice that every element occurs once in the second column. This isn't surprising for the first row or column, because one of the elements involved was the identity, but it's worth thinking about what it would mean if a column didn't contain every element.
First, because there are the same number of elements as rows, an element would have to be repeated. Now, what would that imply?
Since we can describe a rotation as taking A to some point, we can also think about what point a rotation brings to A. And if we take A to a point, and then take that same point to A, then we must have taken A to A, which is the identity element. So, that means that we could apply the "reverse" element to whatever column has duplicates, and get back to the A column. But the different elements are just end-points, they don't "remember" how they got there. Therefore, if a column has duplicate elements, then those same rows must be duplicates in the A column. But the A column is just the elements, so it can't have duplicates.
So, we know that all of the columns of this table contain each element exactly once. In other words, once you've applied one element, then there is some element that takes you to any element you want.
Before we finish with the rest of the table, let's look at that idea of "taking a point to A". It's clear that an element must exist for each of the four points we can choose, because every element ends with some point at A.
So, there is some sense in which every element has an "opposite" element that "undoes" its operation. We can call this corresponding element the inverse of that element. So, the inverse of the element that takes A to B takes B to A (which is the same thing as taking A to D) and vice-versa. And, we can see from the chart that taking A to A is its own inverse. (This is generally true of identity elements: the identity applied to the identity produces the identity, so it must be its own inverse.) The only remaining element on either side is taking A to C.
This element is, in fact, its own inverse.
We may as well add this information to the chart.
We've already shown that the elements in each column must be unique. It's a little different in terms of order, but a similar argument shows that the elements in each row must be unique. If a row has non-unique elements, then there are two possible "second elements" that take that row's element to the same final element. Let's call these "second elements" the duplicating elements and the result the duplicated element. Because the columns are different, the duplicating elements must be different from each other. But suppose we performed the row's inverse element before going through the combination. So, to start with, we have the combination of first the inverse of the row, and second the combination of the row, and the element that leads to a duplicate entry. Now, it shouldn't matter precisely how we group the elements in the combinations, because we can think of the overall combination as paths made up of smaller paths. We could choose to break the above combination into three paths: the inverse of the row, the row, and the duplicating element.
If we set aside the inverse of the row to start with, then we can consider the row and the duplicating element. Then we can combine them into the duplicated element. Then, we can bring the inverse of the row element back, and combine it with the duplicated element. The result should be some element that is independent of the choice of duplicating element.
If, instead, we set aside the duplicating element, then we can consider the inverse of the row, and the row. Then, we can combine them into the identity. Then, we can bring back the duplicating element, and combine it with the identity. The result should be whatever the duplicating element was.
All we did was think in different ways about the path that the piece of paper took. So, that can't change the end result.
- If a row has non-unique elements
- We can choose two columns that have the same entry in the row.
- This gives us two distinct duplicating elements that take the row to a single duplicated element.
- The row must have an inverse element.
- If we combine the inverse of the row, and the row, and a duplicating element, then we can decide mentally whether to combine the first pair or the second pair first, without changing what happens physically.
- Grouping the second pair first tells us that, regardless of the choice of duplicating element, we get the same result.
- Grouping the first pair first tells us that the overall path is equal to the duplicating element.
- So, grouping the first pair first gives us two different results, while grouping the second pair first gives us the same result twice.
- But this is purely mental, and can't change what happens physically, so this situation is impossible.
- We only got into this situation by assuming that rows can have non-unique elements, so that assumption must be false.
Therefore, rows cannot have non-unique elements.
Because every element in a row must be unique, we can look at the rows with three elements and fill in the remaining element in each row...
And now all that's left is two squares in the bottom row, but now we can use the uniqueness requirement on the columns again, to fill in the rest of the table.
The argument I made just now relies on another property that these elements have: that we can "group" them in any way without changing the result of applying them. This is known as the associative property. In the context of rotating this piece of paper, saying "the associative property holds" is equivalent to saying "if we have three rotations, not necessarily distinct, called X, Y, and Z, then the results of 'rotating by the combination of X and Y, then by Z' and 'rotating by X, and then by the combination of Y and Z' should be the same".
So, we have a collection of elements, also called a set, and we have an operation that acts on two elements to produce another element, such that:
- one element of the set is the identity element with respect to the operation (the result of combining this element with any other, is the other element)
- every element has an inverse with respect to the operation (for each element, there is exactly one element that, when combined with it, results in the identity element)
- and combining the elements obeys the associative property (we can combine multiple elements, and it doesn't matter whether we combine "left to right" or "right to left")
(And these statements are fundamentally observations about how the elements behave, not any kind of outside imposition of properties on them.)
A set and operation with these properties is known as a group. Because of this group's simplicity, it has an additional property that is not part of the definition of a group. This property can be argued through informally, like I have done for the other properties, but it can also be established by inspecting the table.
If we imagine flipping the table across this diagonal...
The values in the cells don't change! It doesn't matter which order we combine elements, the result is the same.
This is known as the commutative property. A group whose operation obeys the commutative property is called commutative. (That is, the operation is commutative, so the group is also commutative.) A group that is commutative is sometimes called a commutative group, which is straightforward, and often called an abelian group, which is not.
Here's a suggestion of a group that is not commutative, and a teaser for next time.
This entry is done for now, due to a combination of working under a deadline and reaching a good stopping point, but there will be more. If you want to know more before then, I'm going to mention a bunch of helpful terms you can research.
- This was an illustration of basic concepts in group theory.
- The group I was describing is an example of a cyclic group, specifically C4. Cyclic groups whose order (the subscript number) is a prime number (a number that has no factors besides 1 and itself) have even more specialized properties than C4.
- The chart that I spent most of the entry constructing is called a Cayley table.
- The long argument I used to show that rows cannot have non-unique elements is a proof by contradiction.
See you then!