COMPUTING SCIENCE
Group Theory in the Bedroom
An insomniac's guide to the curious mathematics of mattress flipping
Brian Hayes
Group Theory in the Garage
Not all household chores are as mathematically intractable as
mattress flipping. In rotating the tires of a car, for example, it's
easy to find a golden rule. One simple strategy says: Always rotate
a quarter turn clockwise. In other words, move the right-front tire
to the right-rear, move the right-rear tire to the left-rear, and so
on. The analogous counterclockwise rule works just as well. In
either case, when you repeat the process four times, the tires
return to their original positions, each one having visited all four corners.
Why is tire rotation so different from mattress flipping? It is
governed by a different group. The quarter-turn operations are
elements of a group known as the cyclic 4-group, which describes the
symmetries of a square that rotates in a plane (but cannot be lifted
out of the plane and flipped over). The fundamental symmetry
operations are turns of 0 degrees (the identity element), 90
degrees, 180 degrees and 270 degrees. (Alternatively, the 270-degree
turn could be described as a 90-degree rotation in the opposite
direction.) The multiplication table for the cyclic 4-group is shown
at left. The quarter-turn and three-quarter turn operations are
golden-rule moves within this group: Repeatedly applying either of
them cycles through all the orientations of the square.
The other group we have been discussing, the one associated with
mattress flipping, is known as the Klein 4-group, after the German
mathematician Felix Klein. This group describes the symmetries of a
rectangular object rather than a square; moreover, the rectangle
resides in three-dimensional space, so that it can be flipped over
(or, equivalently, reflected in a mirror).
Comparing the multiplication tables for the two groups reveals an
important similarity. Both tables are symmetrical with respect to
the main diagonal (running from upper left to lower right). In other
words, the symbol at row j and column k is
invariably the same as the symbol at row k and column
j. This implies that any two actions can be performed in
either sequence with the same effect. For the mattress, a roll
followed by a yaw is the same as a yaw followed by a roll. Groups
with this property are said to be commutative, or Abelian, after the
Norwegian mathematician Neils Henrik Abel.
It turns out that the cyclic 4-group and the Klein 4-group are the
only groups with exactly four elements; there is just no other way
to combine four operations and satisfy all the requirements of
grouphood. But both of the four--element groups are embedded within
a larger group, called S 4, which describes all
possible permutations of four things. Taking group theory into the
kitchen now, S 4is the group enumerating the
ways to arrange a family of four at the breakfast table. The
earliest riser can choose any of the four places; then the next
person to get out of bed has three chairs available; the third
person has two choices; and the last to arrive must take whatever's
left. Thus the number of arrangements is 4 factorial (denoted 4!),
equal to 4 x 3 x 2 x 1, or 24. The 24 elements of the group
S 4are all the ways of reshuffling the seat assignments.
Among the 24 permutations, nine are derangements—they
leave no person in the same chair. Except for the identity, all the
elements of both the Klein 4-group and the cyclic 4-group are
derangements. There are four more derangements in S
4, not members of either four-element group. These
additional derangements provide further useful patterns for rotating
tires—as shown in the illustration at left—but they
still offer no help for the mattress problem.
» Post Comment