## Permutations and Applications

Numbers are remarkably tricky. We tend not to notice because we live in a world that is immersed in a sea of numbers. We see and deal with numbers all the time, to the point where most basic manipulations seem simple and obvious. It was not always this way of course. In times past anything much beyond counting on fingers was the domain of the educated few. If I ask you what half of 60 is, you’ll tell me 30 straight away; if I ask you to stop and think about how you know that to be true you’ll have to think a little more, and start to realise that there is a significant amount of learning there; learning that you now take for granted. Almost everyone uses numbers regularly every day in our current society, be it through money, weights and measures, times of day, or in the course of their work. Through this constant exposure and use we’ve come to instinctively manipulate numbers without having to even think about it anymore (in much the same way that you no longer have to sound out words letter by letter to read). That means that when we meet a new abstraction, like the symmetries discussed in Shifting Patterns, it seems comparatively complex and unnatural. In reality the algebra of symmetries is in many ways just as natural as the algebra of numbers, we just lack experience. Thus, the only way forward is to look at more examples, and see how they might apply to the world around us.

In terms of examples I would like to take a step into the more abstract — rather than dealing with a physical example and determining an abstraction from it, we’ll start with a slightly abstract example and explore from there. The example I have in mind is that of permutations. By a permutation I simply mean a rearrangement of unspecified objects, mapping one position to another. We can view a permutation as a kind of wiring diagram, with the permutation:

meaning that we shift whatever is in position 1 to position 3, whatever is in position 2 to position 1, and whatever is in position 3 to position 2. Hopefully you can see how such rearrangements are essentially what we were doing in Shifting Patterns, but here we aren’t starting out with a specific pattern in mind, but considering all such rearrangements in general.

As before we can combine two rearrangements together to get another. In this case we simply connect one wiring diagram to the next and follow the paths from the top right the way to the bottom. We can then simplify that down to a direct wiring diagram as before.

The first thing to note is that the number of objects we are permuting, or wiring together, matters. If we take, as our first and simplest case, permutations of two items, then we find there are only two permutations: the null permutation where we do nothing (the first item is connected to the first item, and the second item is connected to the second item), and a simple swap where we reverse the items (connect the first item to the second, and the second item to the first). Using the algebraic terms we established previously we end up a two element algebra: let s be the permutation where we swap, and then we have the rule:

ss = ⋅

(swapping the two items, then swapping them again, is the same as doing nothing)
which completely describes our algebra*.

On the other hand, as soon as we consider permutations of three objects we find things get more complicated. There are a total of 6 (that’s 3×2×1) permutations of three objects. If we select two basic permutations appropriately we can generate them all as various combinations of the two. There are, in fact, several different pairs we could select (though the resulting algebra will turn out to be the same, no matter how we do it — the names might change, but the underlying rules will be the same), and I’ve opted for these two

where a swaps the first two elements and leaves the third alone, and b swaps the second two elements, and leaves the first alone. Now as with the permutations of two elements, if we swap a pair, and then swap them again, we end up back where we started, so we can see that we have the following two rules:

aa = ⋅
bb = ⋅

Now, however, we have the possibility of combining together a and b. We already saw that ab results in the first item going to the third place, the second item to the first position, and the third item to the second position:

but if we swap things around to find ba we get

which reverses the situation, with the third item moving the first place, while the first and second items get bumped to second and third place respectively. So at the very least we know that we don’t have commutativity — that is abba. Instead we find the rule that defines this algebra is as follows:

We can see that this gives us all the permutations by counting up the combinations of a and b that haven’t been ruled out as being reducible to something simpler. We have

1. The null permutation: ⋅
2. a
3. b
4. ab
5. ba
6. aba

and anything with four or more as and bs will be reducible. Why is that? Since aa = ⋅ and bb = ⋅ any sequence will have to alternate as and bs, otherwise we can just cancel down consecutive pairs. On the other hand, if we have a sequence of more than three alternating as and bs then we’ll have a sequence aba or bab that we can convert using the fact that aba = bab, and end up with a pair of consecutive as or bs that we can then cancel down. For example, if we tried to have a sequence of four as and bs like abab, then we can say

abab = a(bab) = a(aba) = (aa)ba = ⋅ba = ba

With a little thought you can see that this sort of procedure can reduce any sequence of four or more as and bs down to one of three or less. So for permutations of three objects we get an algebra that is described by three rules:

aa = ⋅
bb = ⋅
aba = bab

If we were to consider permutations of four items we would have 24 permutations (that’s 4×3×2×1) to deal with, and things would be more complicated yet again. Permutations of five items provide a total of 120 (5×4×3×2×1) permutations, and an even more complicated algebra with yet more subtle and interesting properties.

There are two things that you should take notice of here. The first is that even simple changes to a pattern — as simple as changing the number of items involved — can give rise to very different dynamics. The character of the algebra that arises from permutations of two objects is very different from that of the three object permutation algebra, and four objects is different again. To reiterate the point: different patterns can have surprisingly different and remarkable dynamics. The second thing that you should be noticing is that while we can work with permutations as wiring diagrams and connect them up to see what combinations will result, ultimately everything about the dynamics of the permutations is contained within the algebra we get from it; and the algebra can be described and manipulated using very simple rules. While the pattern provides the algebra, the algebra in turn tells us everything we need to know about the dynamics of the pattern. The advantage of the algebra is that we can reduce the whole problem of patterns to the simple task of manipulating algebraic expressions according to particular rules. By abstracting up to the algebra, we’ve made the problem much easier to think about and manipulate.

Hopefully by this stage you’re developing a feel for how this abstraction process works. With numbers we start with a collection and abstract away all the details save a single property: the quantity. Here we have something a little more complex; we start with a pattern and abstract away as much of the detail as possible, while still retaining some information about the nature of the pattern. That information can be efficiently encoded into a sort of algebra, in the same way that we encode information about quantity into symbols (numbers). The exact nature and rules of the algebra we generate is the information about the pattern that we have kept. Now, numbers allow us to reason about quantity in general via arithmetic, which we can reduce to a game of manipulating symbols. Our abstraction of pattern allows us to reason about patterns via their associated algebra, which we can also reduce to a game of manipulating symbols. We have turned thinking about patterns into a kind of arithmetic; and doing so allows us to be systematic in studying and analysing such patterns.

This, of course, raises the question of why we should be interested in studying and analysing patterns at all. The same question can be asked as to why we should be interested in studying and analysing quantity. The difference is that our culture is steeped in analysis of and use of quantity; we take its usefulness for granted. So let’s step back, and ask why using numbers is useful. As was pointed out in The Slow Road, numbers and quantity are useful because they are everywhere — we can apply quantitative analysis to almost everything (and often do, sometimes even where it isn’t appropriate). It is worth pointing out that patterns and symmetry are every bit as prevalent in the world. All around us things can be described in terms of their patterns. Pick any collection of objects you care to set your eyes upon, and they will form some manner of pattern; perhaps they will only have a trivial symmetry, or perhaps they will have more complex symmetries. The point is that, just like numbers, symmetries are all around us. The study of pattern and symmetry in the manner we’ve been describing is very new however, and this means it hasn’t entered the mainstream consciousness, nor the language, in the same way that numbers have. We don’t describe the world around us in the language of mathematical symmetry, at least not in the same way that we describe the world around us in terms of numbers. Slowly that will change, but it will take a very long time indeed (centuries probably). That means that, in the meantime, the areas to which the language of mathematical symmetry will be applied, and the people who will apply it, will be restricted to those already using advanced mathematical methods. Right now that tends to mean fields such as physics and chemistry.
To give examples of applying our abstraction of pattern to physics and/or chemistry runs the risk of delving into the technical details of those subjects, as well as requiring math that is currently beyond the scope of our discussion. For that reason, you’ll have to forgive me if I gloss over things quite liberally in what follows.

Everything has a pattern, and symmetries associated with that pattern, even if it is just the trivial symmetry. In the case of chemistry the obvious thing to start looking at is molecules. Unsurprisingly, the structure of a molecule has a pattern that depends, to a large extent, on its constituent elements. More interestingly, molecules often have interesting symmetries. We can, using a naive view, picture a molecule as a pattern of coloured balls, not dissimilar to our patterns of coloured marbles discussed in Shifting Patterns. Of course the patterns are now in 3 dimensions rather than 2, and connections between the balls/marbles are important, but the fundamental idea is there. Consider, for instance, the following picture of the ammonium molecule (NH4):

We can, with little trouble, consider the various ways in which we can rearrange the 4 indistinguishable hydrogen atoms and yet keep the underlying structure that makes it an ammonium molecule. That is, using our abstraction of pattern, we can describe an algebra that captures the features that make the pattern of four hydrogen atoms and one nitrogen atom a molecule of ammonium. Furthermore, we can do the same for any other molecule we care to consider. The exact algebra that results will differ from molecule to molecule, with the individual idiosyncrasies of the different algebras describing the the individual idiosyncrasies of the different molecules. To understand the particular nature of the associated algebra is to understand a great deal about the particular nature of the molecule.

It is, of course, possible to do this sort of analysis just by staring at the patterns and never resorting to the sort of abstraction we’ve been discussing. This approach runs the risk of being both haphazard, and superficial. By contrast, working in terms of pattern abstraction algebras affords us the ability to be both comprehensive and systematic in our analysis. Rather than trying to divine properties out of thin air via visual inspection, we take the resulting algebra and, by merely pushing symbols around on a piece of paper, pick apart every last nuance of its behaviour. Indeed, this sort of analysis (which extends to a level of detail in characterising the algebra that we won’t touch on for some time) is now fundamental to understanding much in chemistry, from spectroscopy to crystallography. Similar approaches to patterns and symmetry of particles lead to a variety of important results in quantum physics.

Our world is filled with patterns that are worth analysing with a systematic approach: understanding the peculiarities of the algebras associated to those patterns can tell us a great deal about our world. New applications of this theory to new fields are still regularly occurring. There is a quiet revolution underway that is changing how we see and describe the world, and the abstraction of pattern is at its heart.

* Through this post I will continue to use algebra in a generic sense to describe the symbolic calculus that we can associate to a pattern. This is a reminder that, in mathematics, algebra also has a more precise definition that does not apply to the objects under consideration here. I do not mean algebra in that more specific sense when using the word here.

### 7 Responses to “Permutations and Applications”

1. Jesse Says:

In terms of examples I would lie to take a step into the more abstract

Ah, I see. Lies, damn lies, and abstractions is it? đź™‚

2. Leland McInnes Says:

My typos are ever present I see. I’ll see if I can clean this up a little.

3. tychew Says:

I like the last teaser on molecules very much — any further pointers to this topic? Do you have any references on this aspect of chemistry? It’ll be cool to be able to shed more light on chemical bonds and their behaviour: I’m no chemist, but this looks more like math…

4. Leland McInnes Says:

tychew: As much as I would like to provide good pointers, I’m unfortunately far from an expert in chemistry, and am quite unfamiliar with the texts that would provide the sort of introduction you’re probably after. I do know that there are many such books available. Probably the bext thing to do is to head to your local library and look up any books that have “group theory” and “chemistry” in the title. A selection of such books includes:

If all else fails there’s this website, which provides an introduction to some of the ideas involved:

http://www.du.edu/~jcalvert/phys/groups.htm

5. tychew Says:

Great stuff. The keyword here (not surprisingly, but not obvious to me at first) is group theory and chemistry. Thanks for the links!

6. The Narrow Road » Blog Archive » Grouping Symmetries Says:

[…] In the previous entries Shifting Patterns and Permutations and Applications we have looked at how patterns and symmetry can be abstracted into algebras. Each different pattern provided its own unique algebra, with different algebraic rules. These are, in a sense, our islands; each different and unique and beautiful. What we need to explore now is the entire bay. To do this we need to take a step back, or more accurately up, and try to examine the whole. The aim is to abstract across all the different algebras that different patterns generate. We could, perhaps, liken this to the process of developing algebra from numbers by abstraction; here, however, we have different pattern-algebras standing in place of different numbers. In abstracting up from numbers to basic algebra we looked for those properties that held true regardless of the particular numbers under consideration — each different number has its own unique properties (indeed, there is a vast richness of material here that is studied in number theory) — but there are certain properties that are common to all. What we seek is a set of basic algebraic rules that are true for all pattern-algebras; each different pattern algebra may have its own idiosyncratic rules, but hopefully we can find a basic set of underlying rules. In practice we’re going to hope for even more than that. Not only do we want the algebraic rules we determine to be common to all pattern-algebras, we would very much like it if any algebra that satisfied the basic rules turned out to the pattern-algebra for some pattern. That is, we want a two way correspondence: every pattern-algebra should satisfy these rules, and everything that satisfies these rules should be a pattern-algebra. […]

7. charles ainsworth San Marcos High School science Says:

Where did you get that great diagram of an ammonium molecule?
I need them for my chemistry class!
thanks,
charles ainsworth