Transcript Algebra - MCCC Faculty & Staff Web Pages

Algebra
and the Rubik’s Cube
Scott Vaughen, Professor of Mathematics
Miami Dade College
Group Theory
• Group theory is a branch of modern algebra.
• It could be called the mathematical
language of symmetry.
• The first principles of group theory were
discovered by Evariste Galois in the 1830s.
Evariste Galois
• Galois died in a duel at the age of 20.
The exact circumstances of the duel may never be known.
• Galois lived during a time of political turmoil in France immediately
after the French Revolution. He was critical of the king, expelled from
school, joined a militia that was disbanded out of fear it would
overthrow the government and was even sent to jail several times for
activities considered threatening to the government.
Solvability by Radicals
•
Galois developed group theory in order to prove the following remarkable
theorem:
– There is no general formula involving the operations of arithmetic and
use of radicals for the solutions of polynomial equations of degree 5 or
higher.
ax  bx  c  0
•
2
Polynomial equations of the form
are equations of degree 2 (because 2 is the highest exponent).
•
Recall that for equations of degree 2, there is a general formula, the familiar
quadratic formula,
 b  b 2  4ac
x
2a
involving only the operations of arithmetic (adding, subtracting, multiplying
and dividing) and use of square roots.
Solvability by Radicals
• The quadratic formula was known to the ancients. Mathematicians in
the 15th century found general methods to solve degree 3 and
degree 4 polynomial equations using the operations of arithmetic,
square roots and cube roots.
• But it was not until the 1830s that Galois developed the proof that no
such method or general formula could ever be devised that would
solve every degree 5 polynomial equation.
• His proof also showed that no such general method or formula could
ever be developed to solve polynomial equations with degree greater
than 5.
• An amazing achievement – first because Galois solved a 1000 year
old question when he was just 20 years old - but also amazing in that
his proof marks the beginning of group theory and modern algebra.
Applications of Group Theory
• Since Galois’ discovery, group theory has grown into a major branch
of modern algebra.
• As the mathematical language of symmetry, it has many applications
in all branches of mathematics and also in computer science, physics
and chemistry, just to name a few…
• For example, in physics, group theory is used to describe the ways in
which elementary particles interact and in chemistry to classify the
symmetries of molecules.
• A group is a set of elements and a rule to combine them which
satisfies certain properties. Sometimes the elements of the group
are numbers, but there are many other examples: the elements of a
group could be the symmetries of a molecule, the rotations of an
object, or the different ways of rearranging a set of elements.
Definitions
• A binary operation is a rule for combining elements of a set that will
always produce another element of the same type.
• For example,
– addition is a binary operation: If you combine two numbers with addition
you get a result which is another number.
– compositions of functions is a binary operation: Composing two
functions produces another function.
– combining moves of the Rubik’s cube is a binary operation: combining
one move with another is itself another move.
Definitions
• A group is a set G with a binary operation * that satisfies the following
three properties:
– There is an identity element e, such that for all elements a in G,
e*a = a*e = a.
– For every element a in G, there is an inverse element a-1 such that
a*a-1 = a-1*a = e.
– The operation * is associative. That is, for elements a, b, c in G,
(a*b)*c = a*(b*c)
The Group of Integers with Addition
The set of integers with the operation of addition is an example of a
group:
–
There is an identity element, namely 0. We see for any integer,
x+0=0+x=x
–
Every element in the group has an inverse. Specifically, the inverse of x
is –x. In general, combining any element and it’s inverse produces the
identity. For example 6 + -6 = 0.
–
Addition of integers is associative: in general, for any integers a, b, c,
we have (a + b) + c = a + (b + c).
The Group of Rationals (without 0) and Multiplication
The set of rational numbers without 0 and the operation of multiplication
is an example of a group:
–
There is an identity element, namely 1. We see for any rational x,
x*1 = 1*x = x
–
Every element in the group has an inverse. Specifically, the inverse of x
is 1/x. In general, combining any element and it’s inverse produces the
identity. For example 6 * (1/6) = 1.
–
multiplication of rational numbers is associative: in general, for any
numbers a, b, c, we have (a*b)*c = a*(b*c).
Note: 0 is not included in this group because it would have no inverse by
multiplication (that is, there is no number times 0 that would produce
the identity 1).
The Stop Sign Group
The set of all possible rotations and reflections of the stop sign, with
composition as the operation, is an example of a group:
–
The picture below shows the result of each element of the group.
–
The elements are the motions (rotations or reflections) that are possible
and the operation in this group is the combination of two possible
motions.
This is called the dihedral group (of the octagon) with 16 elements.
The Stop Sign Group
•
The elements of the dihedral group of the octagon (the stop sign
group) are the 8 possible rotations and 8 possible reflections whose
effects (on the original sign) are shown above.
•
The operation in this group is the combination of rotations or
reflections – any combination will always result in one of the 16
results shown above.
•
We can refer to the operation in this group as “followed by”. For
example, one rotation followed by another rotation is itself another
rotation.
The Stop Sign Group
To verify that this is really a group, we can check each condition…
-
There is an identity element: In this case the identity is “do nothing”.
Notice that “do nothing” followed by move x is equal to move x.
This is analogous to the algebraic equation 1*x = x.
-
For every element, there is an inverse. The inverse of move x is
simply the move that undoes x, that is, the reverse rotation or
reflection. The inverse of x is the move that combined with x
produces the identity, as if nothing had been done.
-
The operation “followed by” is associative. Consider any three
moves a, b and c. Move a followed by (b followed by c) is the same
as (move a followed by b) followed by c. Essentially, with the
operation “followed by”, the parentheses have no effect, meaning
that the operation is associative.
The Rubik’s Cube Group
The Rubik’s cube is another example of a group:
•
There is a one-to-one correspondence between the distinct
permutations of the cube and the elements of the Rubik’s cube
group. Each different permutation represents the result of a single
element of the group, just as the different images of the stop sign
represented the result of each element in that group.
•
Different moves of the cube could correspond to the same final
permutation and would therefore correspond to the same single
element. In other words, a single element of the Rubik’s cube group
can be expressed in different ways, using different sequences of
moves, just as a rotation of 405º is the same as 45º or the rational
number 2/4 is the same as 1/2.
•
The operation in this group is the combination of moves.
•
Again, we use the expression “followed by” to represent the
operation in this group. In other words, one move followed by
another move is itself a different move of the Rubik’s cube.
A Big Group
The number of elements in the Rubik’s cube group is
43,252,003,274,489,856,000 because there are this
many possible distinct permutations of the cube that can
be reached by legal moves.
A legal move is any combination of turns of any of the
faces. Illegal moves can result from breaking the cube
apart or peeling off the stickers.
Any two legal moves can be combined and the result
would be one of those distinct permutations.
We can check that the properties of a group are
satisfied…
The Rubik’s Cube Group
To verify that the Rubik’s cube group satisfies the three properties of a
group, consider…
•
There is an identity element, namely “not doing any move”.
–
•
For each element, there is an inverse. The inverse of move x is the
move that undoes move x.
–
•
Notice, for example, “not doing any move” followed by a move x equals
the move x.
Notice, for example, how any move followed by its inverse will produce
the identity element (meaning the result is not doing any move)
The operation “followed by” (composition) is associative.
–
Given three moves, performing the first followed by the composition of
the second two is equivalent to the composition of the first two followed
by the third, provided that the order remains the same.
A Non-Example
• Consider subtraction with the integers. Is this a group?
• There is an identity, namely 0.
• Every number has an inverse. Specifically, given the integer x, there
is always an integer a such that x – a = 0. (In fact, every number
would equal it’s inverse.)
• The operation is NOT associative.
Consider: (5 – 3) – 2 = 5 – (3 – 2). This is not true, because
0 (on the left) is not equal to 4 (on the right).
This means subtraction with the integers is not a group.
Abelian Groups
• Suppose G is a group with the binary operation *.
• We say the operation * is commutative if for all x and y in G, it is true
that x*y = y*x. When the operation is commutative, we say that the
group is Abelian.
• For example,
– Addition is commutative because x + y = y + x
therefore, the group of integers with addition is Abelian.
– Multiplication is commutative because xy = yx
therefore, the group of rationals (without 0) is Abelian.
Non-commutative Binary Operations
• Not all binary operations are commutative.
• Subtraction is not commutative.
– for example 3 – 5 is not equal to 5 – 3.
• Division is not commutative.
– for example 10 ÷ 2 is not equal to 2 ÷ 10.
• The binary operation “followed by” that is used in the Stop Sign
group, the Rubik’s cube group and in any permutation group is not
commutative.
Stop Sign Group is Not Commutative
• Consider combining two elements from the Stop sign group:
– A 45º counter-clockwise rotation followed by a vertical reflection.
– A vertical reflection followed by a 45º counter-clockwise rotation.
• Combining these elements in different orders produces a different
result, illustrating the fact that the stop sign group is not
commutative.
The Rubik’s Cube Group is Not Commutative
• The Rubik’s cube group is not commutative. Consider two
example elements from the group: “R” a clockwise turn of the
right side, and “D” a clockwise turn of the down side.
Apply move R followed by D
Applying move D followed by R.
The fact that the operation “followed by” in the Rubik’s cube group is not
commutative is what makes the puzzle so difficult (aside from the large
number of permutations). Imagine if it were commutative – this would mean
that to solve the puzzle it would not matter what order the moves were applied:
simply rotating each face an appropriate number of times would suffice!
The Power of Algebra
• The power of algebra is in knowing properties that hold
true for all numbers.
• Group theory provides generalizations that would be true
in all groups.
• We know that the Rubik’s cube is an example of a group.
Therefore, anything that is true for a group in general, is
true for the Rubik’s cube.
Subgroups
• A subgroup of a group G is a subset A of G that is also a group with
the operation used in G.
• A cyclic subgroup is a subgroup generated by repeated applications
of the group operation to some element of the group.
• For example, in the “stop sign group”, rotating the stop sign by 450
counter-clockwise and following that with subsequent rotations will
generate each element of an 8 element subgroup. The 8 possible
rotations are a cyclic subgroup generated by applying the operation
“followed by” to the same element 8 times.
Subgroups of the Rubik’s Cube Group
• Every possible move of the Rubik’s cube will also generate a cyclic
subgroup. This means repeating any sequence of moves will
eventually return the cube to the original state.
• The most obvious example is to rotate one face of the cube 4 times.
This generates all 4 elements of one subgroup of the Rubik’s cube
group.
• For another example, consider the element “RLUD”. That is, turn
each of the Right, Up, Left and Down side once, clockwise, in that
order.
• This is a combination of elements but, of course, that means it is itself
an element of the group. Try repeating the element “RLUD” six times.
• If you repeat “RLUD” carefully 6 times, you will return to the original
configuration. In other words, “RLUD” generates a cyclic subgroup of
the Rubik’s cube group with order 6.
• Careful, “RULD” generates a subgroup with order 315!!!
Subgroups of the Rubik’s Cube Group
• The number of elements in a group is called the order of the group.
• An important theorem of group theory that says the order of every
subgroup must divide the order of the group.
• We can factor the order of the Rubik’s cube group into
27 14 3 2
1
2 3 5 7 11
• There is no factor of 13. Therefore, this means, for example, there
are no subgroups of order 13 in the Rubik’s cube group. In other
words, no sequence of moves that will repeat after 13 moves.
Properties of Algebra
• Solving equations in beginning algebra requires using inverses.
For example, we solve the equation 3x + 10 = 22 as follows
3x  10  22
- 10 - 10
Apply the additive inverse of 10 to both
sides to isolate the 3x term
3x  12
1
1
 3 x   12
 3
 3
x4
Apply the multiplicative inverse of 3 to both
sides to isolate the factor x.
Properties of Algebra
3x  10  22
- 10 - 10
In this example, we are using the group of
integers with addition …
because we used 10 and its inverse -10
3x  12
And we are using the group of rationals and
multiplication …
1
1
 3 x   12
 3
 3
x4
because we used 3 and its inverse 1/3.
Solving the Rubik’s Cube
• Like solving an equation, solving the Rubik’s cube requires
combining the elements of a group with inverses.
• Almost everyone learns to solve the cube by memorizing a series of
move sequences. These sequences move certain cubies around to
solve the cube layer by layer without messing up the previous work.
• The mathematics of group theory can help to understand how these
sequences were first discovered, why they actually work, and can be
used to develop new sequences.
Solving the Rubik’s Cube
• On the Rubik’s cube, every move has an inverse, which is the move
that would return the cube to the identity (as if nothing had been
done.)
• The basic moves of the cube are R, D, L, U, B which correspond to
clockwise turns of the right, down, left, up and back side of the cube.
• For example, the move R (a clockwise turn of the right side) has the
inverse, written R’ (a counter-clockwise turn of the right side)
Solving the Rubik’s Cube
• We can find the inverse of a combination move as follows:
• Consider the move RD. The inverse will be D’R’.
• Why? Because, combining these two moves will produce the
Rubik’s cube group identity, so that the final result would be as if
nothing had been done to the cube.
• For convenience, let’s call the identity of the cube “1”, which is the
identity in multiplication.
• Using this notation, notice that RDD’R’ = R(1)R’ = RR’ = 1
• So now we see the general principle to find the inverse of any
element: reverse the order and switch between clockwise and
counter-clockwise rotations.
Solving the Rubik’s Cube
• Because RDD’R’ is equal to the identity, by itself it won’t help much in
solving the cube.
• Now try the sequence RDR’D’. This is “almost” the identity. It will
move some cubies but leave lots of others unchanged, which may be
useful.
• Notice that if the Rubik’s cube group were commutative, RDR’D’
would equal the identity because, by rearranging the order, we could
rewrite it as RDD’R’ which is the identity.
• Combinations of the form xyx’y’ are called commutators in algebra
because they indicate the degree to which a group is commutative.
• To solve the Rubik’s cube you can memorize a sequence of steps.
But if you are interested in why those steps work, or improving your
method, you can begin by studying commutators and the algebra of
groups.