Top banner
MY AMERICAN SCIENTIST
SEARCH

COMPUTING SCIENCE

# Group Theory in the Bedroom

An insomniac's guide to the curious mathematics of mattress flipping

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.