COMPUTING SCIENCE
Group Theory in the Bedroom
An insomniac's guide to the curious mathematics of mattress flipping
Brian Hayes
Having run out of sheep the other night, I found myself counting the
ways to flip a mattress. Earlier that day I had flipped the very
mattress on which I was not sleeping, and the chore had left a
residue of puzzled discontent. If you're going to bother at all with
such a fussbudget bit of housekeeping, it seems like you ought to do
it right, rotating the mattress to a different position each time,
so as to pound down the lumps and fill in the sags on all the
various surfaces. The trouble is, in the long interval between flips
I always forget which way I flipped it last time. Lying awake that
night, I was turning the problem over in my head, searching for a
golden rule of mattress flipping.
The essential characteristic of a golden rule is universality: One
rule works all the time, for everyone. The famous archetype of such
rules—the one about doing unto others—certainly has this
property. So does the rule of the road: "Drive to the
right." ("Drive to the left" works just as well; what
matters is not which side you choose but that everyone make the same
choice.) Not all rules generalize so smoothly. A sign saying
"Please use other door" is not helpful when it's posted on
every door. A golden rule of mattress flipping would be
some set of geometric maneuvers that you could perform in the same
way every time in order to cycle through all the configurations of
the mattress. Following this algorithm might entail more physical
labor on each occasion—perhaps making multiple flips or
turns—but at least it would eliminate the mental effort of remembering.
If you too spend sleepless nights fretting over this problem, I'm
afraid I have some disappointing news. You will not find the golden
rule of mattress flipping in this column. As a matter of fact, no
such rule exists—at least not in the form I originally
imagined. But please read on anyway: The search for a
mattress-flipping algorithm leads to some diverting mathematics, not
just in the bedroom but also in the garage and at the breakfast
table. Furthermore, although I can offer no golden rule for mattress
flipping, I do have some practical advice.
Sleepers Awake
In the morning, when I Googled "mattress flipping," I
learned that I'm not the only one who's been obsessing about this
silly business. Linda Cobb, The Queen of Clean®, recommends
flipping on a seasonal schedule—side-to-side in spring and
fall, and end-over-end in summer and winter. Or maybe it's the other
way around; I forget. A Web site called eHow, which promises
"Clear Instructions on How To Do (just about) Everything"
offers the following counsel: "Rotate your mattress twice a
year, or more often if instructed by the manufacturer. Flip it over
completely after the first six months. Then, after another six
months, flip it over and turn it so that the head is at the foot of
the bed." Is that clear? What would it mean to flip it over
incompletely? And what's the difference, exactly, between
rotating, flipping and turning? Does the final instruction to flip
and turn do anything that couldn't be achieved with a
single motion?
Another Web page, Phyl's Furniture Facts, takes on the task of
defining some of this terminology: "Flipping means to turn it
over while rotating means to make a 1/4 turn of the mattress while
it lies flat on the bed." (I tried the quarter turn, but it
didn't look very comfortable.)
Versions of the illustration reproduced at right appear on dozens of
Web sites. When I first saw this diagram, I thought for a fleeting
moment that I had found my golden rule. A quarter turn, a flip,
another quarter turn—"AND THERE YOU ARE.... Turned Over
and End to End as well!" Maybe this was the magic formula. But
no: A quick experiment with a small model of a mattress—I used
a paperback book—showed that the elaborate sequence of
operations in the diagram has exactly the same effect as a half turn
end-over-end. (But the more-complicated procedure may be worth
following anyway, especially in a room with a low ceiling.)
A Flying Mattress Ride
To make sense of all this turning and flipping, the first thing we
need is some clear notation. A mattress can be rotated around any of
three orthogonal axes. I could label the axes x, y
and z, but I'd just forget which is which, so it seems
better to adopt the terminology of aviation. If you think of a
mattress as an airplane flying toward the headboard of the bed, then
the three axes are designated roll, pitch and
yaw as shown in the illustration to the right. The roll
axis is parallel to the longest dimension of the mattress, the pitch
axis runs along the next-longest dimension, and the yaw axis passes
through the shortest dimension.
Turning the mattress by 180 degrees around any one of these three
axes is a symmetry operation: If you start with the mattress
properly installed on the bed and then apply one of these actions,
you return to another state where the mattress fits the bed frame
correctly. Assuming that the various surfaces of the mattress are
not labeled in any way, the states before and after the symmetry
operation are indistinguishable. Note that no rotation through an
angle smaller than a half turn has this property; despite the advice
of Phyl's Furniture Facts, a quarter turn around any axis leaves the
mattress in a decidedly awkward position. And for a mattress that
has the usual, rectangular, shape (technically, it's called an
orthotope), there are no other symmetry axes. If you were to try
making a half turn around one of the diagonals, you'd be left with a
very catterwumpus bed.
A mattress has two sides suitable for sleeping on, and each of those
sides has two possible orientations—with one end or the other
toward the headboard. Thus there are four configurations overall. A
golden rule of mattress flipping would be an operation that, when
applied repeatedly, would cycle through all four configurations and
then return to the original state. It's easy to see that none of the
three basic symmetry operations, taken alone, accomplishes this
trick. If you always flip the mattress end-over-end (that is, around
the pitch axis), you alternate between just two of the four states
and never reach the other two. Repeated roll turns or yaw turns also
visit just two of the states (although not the same pairs of
states). Hence any golden rule would have to involve some
combination of motions—maybe a roll followed by a pitch
followed by a roll the other way and then a yaw, or some such
intricate dance move.
Mattress Multiplication
If you are inclined to undertake a search for such a magic
combination, by all means flip away; but it's less strenuous to
bring some mathematics to bear on the problem. Particularly helpful
is the branch of mathematics known as group theory, which is the
traditional tool for studies of symmetry.
In general, a group is a set of objects together with an operation
for combining them. For example, one can have a group in which the
objects are numbers and the combining operation is addition or
multiplication. In this case, however, the
"objects"—the elements of the group—are
themselves operations. They are the various ways of flipping a
mattress. The rule for combining the elements is simply to perform
one operation after another.
Not just any set of operations can qualify as a group; they have to
meet four criteria. First, among the operations there must be an
identity element—an operation that leaves the system
unchanged. For mattress flipping, the identity operation is obvious:
Just do nothing.
Second, every element of the group must have an inverse, an
"undo" action that returns the system to its former state.
Again this requirement is easily met for mattress flipping: Each of
the three basic rotations is its own inverse. If you flip the
mattress a half-turn around the roll axis, and then do exactly the
same thing again, you come back to where you started. The same is
true of half turns around the pitch and yaw axes. (Even more
obviously, the do-nothing identity element is also its own inverse.)
The third criterion for grouphood is that the operations obey an
associative law, so that (f g) h means the same as
f (g h), where f, g and
h are any operations in the group. For mattress flipping
this is true but not very informative, so I'll say nothing more
about it.
The final requirement is closure, which says the set of operations
is in some sense complete. More formally, if f and
g are any elements of the group, then the combination of
f followed by g must also be an operation in the
group. The implications of closure are made clear by drawing up a
"multiplication table" for the group, as in figure 2. The
table gives the result of all possible pairwise combinations of the
four operations I, R, P and Y
(which stand for the identity operation and for 180-degree rotations
around the roll, pitch and yaw axes). The crucial point is that
every such combination is equivalent to one of the fundamental
operations. For example, a roll turn followed by a yaw turn has
exactly the same effect as a pitch turn. This fact is what dooms the
search for a golden rule. The table shows that any combination of
two basic operations can be replaced by a single operation. Since we
already know that none of the single operations yields a cycle
through all four states of the mattress, it's clear that no pair of
operations can be composed to make a golden rule.
What about longer sequences of symmetry moves? They too are ruled
out. Someone might come forward to claim that a complicated,
n-step sequence of roll, pitch and yaw turns has the
desired effect. But by consulting the multiplication table, we can
replace the first two of these actions with a single turn, creating
an equivalent procedure with n-1 steps. Continuing in the
same way, we eventually reduce the entire sequence to a single
symmetry operation, which cannot be a golden rule.
But wait! Maybe there's some tricky maneuver that involves motions
other than the symmetry operations, as with the quarter
turns in the diagram in figure 1. The trouble is, any move that
qualifies as a mattress flip has to begin and end with the mattress
in one of the four canonical positions on the bed frame. In between,
you are welcome to twirl it over your head on one finger while
riding a unicycle, but when you put it down again, only the net
effect of your gyrations can be observed. And the multiplication
table for the group says that all your manipulations, no matter how
acrobatic, can be replaced by a single symmetry
operation—-either I, R, P or Y.
There is no golden rule hidden under the mattress.
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.
A Silver Rule
The absence of a golden rule for mattress flipping is a
disappointment, but it does not portend the demise of Western
Civilization. We can adapt; we can learn to live with it.
Suppose you flip your mattress at regular intervals, but each time
you choose an axis of rotation at random. This is clearly a
less-than-optimal algorithm, but how large a penalty does it carry?
Under the ideal rotation schedule, each orientation of the mattress
would get 25 percent of the wear. A quick computer simulation shows
that if you do random flips quarterly over a period of 10 years, the
most-used orientation will get 31 percent of the wear and the
least-used 19 percent. Except for those among us who suffer from a
severe Princess-and-the-Pea complex, ±6 percent is probably
good enough.
But we can do even better. We can cheat.
The no-golden-rule theorem for mattress flipping assumes that the
surfaces of the mattress are unmarked, so that the four allowed
configurations are indistinguishable. Everything changes if you
label the surfaces. Specifically, suppose you go through the four
possible orientations of the mattress and label each one with a
number from the set 0, 1, 2, 3. You might place the labels so that
in each configuration, one of these numbers is facing upward in the
corner closest to the righthand side of the headboard. Given this
labeling, the mattress-flipping algorithm calls for nothing more
than counting. Each time you are ready to make a flip, you note the
number that appears in the upper righthand corner, and calculate the
successor of that number modulo 4. (In other words, you cycle
through the sequence 0, 1, 2, 3 and then return to 0 again.) Turn
the mattress in whatever way is necessary to bring the successor
number into the upper-right position. The turn needed will not
always be around the same axis, but the closure property of the
group guarantees that you will always be able to bring the next
number into position with a single flip around some axis.
The counting algorithm is not a golden rule, but perhaps it
deserves to be called a silver one. As a practical matter, this
solution is so simple that I would expect mattress makers to adopt
it, by embossing numbers on their products. Some of the
manufacturers require periodic flipping as a condition of
maintaining a warranty, and they give complicated—often
ambiguous—instructions on how to comply. Wouldn't it be easier
just to count?
The algorithm can be simplified even further for those who can't
count as high as 3. If a mattress had lengthwise stripes on one side
and crosswise stripes on the other, you could cycle through the four
states by always flipping parallel to the stripes. Another
possibility is to somehow adapt to our purposes the label that reads
"Do not remove this label." (Now there's a golden rule!)
Pillow Talk
I'm not a mathematician, but I've been hanging around with some of
them long enough to know how the game is played. Once you've solved
a problem, the next step is to generalize it beyond all recognition.
There's a nerdy joke with the punchline, "Consider a spherical
cow"; in the same spirit I ask, "Consider a cubical mattress."
A cube has a much higher order of symmetry than the generic
orthotope of an ordinary mattress. Any of six faces can be turned
uppermost for sleeping on, and each face has four orientations, so
there are 24 states in all. (The group is S 4,
the same group we encountered at the breakfast table and in the
garage.) Is there a golden rule for flipping an unlabeled cubical
mattress—a single maneuver that can be repeated 24 times to
cycle through all the configurations? The answer is no, but I'll
leave the proof of that fact as an exercise.
There is a silver rule for cubical mattress flipping: As
with an ordinary mattress, if we label the configurations, we can
step through them one by one by counting. But there is a subtle
difference. On the ordinary mattress, there are six essentially
different ways to label the configurations—six ways to arrange
the numbers 0 through 3— but it doesn't matter which one you
choose. With any arrangement of the numbers, you can always go from
one state to the next in a single flip. For the cube, there are many
more labelings (the exact number is 23!, or
25,852,016,738,884,976,640,000), and they are not all equal. When
you tour all 24 states in numerical order, some labelings allow
every transition to be accomplished by a simple quarter turn around
the roll, the pitch or the yaw axis. Other labelings require
more-complicated maneuvers—rotations around multiple axes (or,
equivalently, around a diagonal). How many of the labelings fall
into each category? Is there any simple rule that distinguishes the
two classes?
If you have answered those questions and you still can't
get to sleep, you are welcome to go on and consider a hyper-cubical
mattress—one that takes the form of a cube in
n-dimensional space, for some n greater than 3.
The 4-D mattress has 24 square faces and 96 configurations.
As far as I know, neither Sealy nor Simmons nor anyone else is yet
selling a four-dimensional mattress. As a matter of fact, the trend
seems to be in the opposite direction. Mattress makers now promote
the one-sided, "no-flip," mattress, whose only symmetry
operation is a 180-degree turn around the yaw axis. This innovation
finally gives us a golden rule for mattress flipping, but it solves
the problem in a trivial, dull and unsatisfying way.
Still, there remain ways to increase the number of permutations, to
provide opportunities for creative problem-solving, to make life
more interesting. One could get married.
© Brian Hayes