17. Symmetries 17.1 Permutations A permutation of a set is a reordering of its elements. Another way to look at it is as a function Φ that takes as its argument a set of natural numbers of the form {1, 2, … , n} and produces another set consisting of the same elements, but in a different order. The permutation function is such that every element of the set is mapped to itself or another element of the set, and no two of them are mapped to the same element. Permutations can be notated in two ways: One is by listing the new ordering that replaces {1, … , n}. We do this by writing the n elements of our set in their new order like this: {i1, … , in }, where for each integer j in our set, ij is the element of the set to which it is mapped. Thus, for n = 5, we can write {1 3 5 4 2} to represent the permutation that takes 1 to itself, 2 to 3, 3 to 5, 4 to itself, and 5 to 2. Another way to represent a permutation is to put all the cycles of the permutation inside parentheses. It could happen, as in our last example, that 2 maps to 3, 3 to 5, and 5 back to 2. This is an example of a cycle.1 We would represent this cycle by writing it out as: (2,3,5). A cycle can have any length between 1 and n. A cycle with length k of the form (i1, … , ik) means that i1 maps to i2, i2 to i3, and so on, with ik mapping back to i1. A permutation can have multiple cycles, which can range from size 1 to n. The permutation in the previous example can be written as (1)(2,3,5)(4) in cycle notation. Using basic combinatorics, we can see that there are n! permutations of n symbols. Still another way to describe them is by using an n-by-n matrix whose entries are either 0 or 1 (this is called a permutation matrix). There is exactly one 1 in each column and row; the 1 entry of the j-th column is in the row that corresponds to the number to which element j is mapped. Thus, the example above corresponds to the matrix: 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 We shall now look at how permutations relate to trees. 1 If we represented a permutation as a directed graph by making each element of the set a vertex and the mappings as edges, then the cycles of a permutation would exactly be the cycles of the graph.17.2 Symmetry Groups We saw in notes 16 that the set of trees on 5 vertices has 125 elements, which fit into 1 of 3 patterns. There is a collection of operations that can take one tree and transform it into another tree that looks just like it. Such operations are called symmetries. In the case of trees, the symmetries are all the permutations of the five labels. For example, consider the tree { (4,1), (1,5), (2,5), (3,5) }. We can permute its vertices using the permutation {4 3 1 5 2}, and it becomes the tree { (5,4), (4,2), (3,2), (1,2) }. We see that these two trees can be drawn exactly the same way, just with different labels on the vertices: If we have two trees on the same number of vertices and there exists no permutation that takes one to the other, then they cannot have the same pattern. If we look at the trees { (1,2), (2,3), (3,4), (4,5) } and { (1,2), (1,3), (1,4), (1,5) }, we can see below that they have different patterns (one is a path and the other is a claw): If we tried to come up with a permutation that that maps one tree into the other, we would not be able to. Look at the edges of the second tree. There are four 1’s in them. In order for a permutation to exist, there must be four of some label number in the edges of the first tree that we can map to 1. However, none of the vertex labels appears four times in the edges. Thus, no permutation can exist. In general, symmetries of any system form a mathematical structure called a group. First, we will list the properties of a group, then explain in detail what each of these properties means. A group, G, is a set of elements {A, B, … } that has a law of composition which allows you to assign a single element of the group to each pair of elements. The set must include an identity element, and each element of G must have an inverse which when composed with it produces the identity element. Finally, the composition law must be associative. Our law of composition tells us that for any two elements of the group A and B, A composed with B (written as AB) always produces another element of the group. We cancompose two elements in two different orders, without necessarily getting the same result. If AB = BA, then we say that our group is a commutative group, or an abelian group. The identity element of a group, usually written as I, is the unique element of the group such that for any A in G, AI = IA = A. For every element A of G, the inverse of A is an element of G, written as A-1 , such that AA-1 = A-1A = I. The inverse of I is I. Associativity tells us that for any A,B, and C in G, AB composed with C is equal to A composed with BC. More compactly, (AB)C = A(BC). The symmetry operations that we described before are groups with the law of composition that reads: A composed with B means that we perform operation B and then operation A. The identity of this group is the operation that does nothing. So for trees, the law of composition would be the permutations of the vertex labels, and the identity operation would be the permutation {1 2 3 4 5} which maps every label to itself. There are two properties of symmetry operations that are essential in making them a group. The first is that a symmetry operation followed by another symmetry operation is itself a symmetry operation. This tells us that if A and B are symmetry operations, then AB is as well. This implies that performing two permutations does define a law of composition and produces an element of the set of symmetries for every pair of elements composed. The second property is reflexivity. A symmetry operation must be reversible. If doing something maintains symmetry, then undoing it does as well. This means that each symmetry operation has an inverse that is also a symmetry operation. Taking all this together, we see that the symmetry operations form a group under the rules that we have just defined. You are used to dealing with groups because integers, …