Groups and Group Actions: Lecture 4

In which we explore permutations in more detail.

  • Theorem 9: Every permutation in S_n can be written as a product of disjoint cycles. Moreover, this is unique up to cycling elements within cycles and permuting the order of the cycles.  To check existence (of decomposition as a product of disjoint cycles), we considered the orbit of some a_1, which is permuted via a cycle, and then considered orbits of new elements until there were none left.  Note that the process is guaranteed to terminate because we have only finitely many elements to consider so at some point the disjoint cycles will use them all up.   To check uniqueness, we took two equal products of disjoint cycles and showed that in fact they are the same (up to shuffling cycles and cycling cycles), by considering what they do to 1 and then to other elements.
  • Definition of the cycle type of a permutation.
  • Proposition 10: Let \pi \in S_n be written as \pi = \sigma_1 \sigma_2 \dotsm \sigma_k as a product of disjoint cycles.  For 1 \leq i \leq k, let \sigma_i have length \ell_i.  Then the order of \pi is \mathrm{lcm}(\ell_1, \dotsc,\ell_k).  The proof is a good exercise.
  • Definition of what it means for two permutations to be conjugate.
  • Lemma 11: Let (a_1\,a_2\,\dotsc\,a_k) \in S_n be a cycle, and take \sigma \in S_n.  Then \sigma^{-1} (a_1\,a_2\,\dotsc\,a_k) \sigma = (a_1\sigma\,a_2\,\sigma \dotsc\,a_k \sigma) This is an exercise on Sheet 2.
  • Theorem 12: Let \sigma, \tau be permutations in S_n.  They are conjugate if and only if they have the same cycle type.  To show that if they’re conjugate then they have the same cycle type, we wrote \tau as a product of disjoint cycles, then noted that conjugating each of them yields a cycle of the same length (by Lemma 11), so \sigma must have the same cycle type as \tau.  For the other direction, we wrote \sigma and \tau as products of disjoint cycles with the same cycle type, and then we were able to use Lemma 11 to write down an explicit permutation so that conjugating \sigma by it gives \tau.
  • Definition of a permutation matrix (a square matrix in which each row and each column contains exactly one entry that is 1, with all other entries 0), and of the permutation matrix P_{\sigma} corresponding to a permutation \sigma \in S_n.
  • Lemma 13: If \sigma, \tau \in S_n, then P_{\sigma \tau} = P_{\sigma} P_{\tau}.  We proved this by using our previous observation that for a permutation \pi, we have (P_{\pi})_{i,j} = \delta_{i\pi, j}.
  • Lemma 14: If \sigma \in S_n is a transposition, then \det(P_{\sigma}) = -1.  If \sigma = (i\,j), then P_{\sigma} is the identity matrix with two rows i and j swapped, so \det(P_{\sigma}) is -1 times the determinant of the identity matrix, so is -1.
  • Theorem 15: (i) Any permutation can be written as a product of transpositions.  (ii) A permutation cannot be both even and odd.  We’ll prove this next time.

Understanding today’s lecture

Practise writing permutations as products of disjoint cycles, this is a really important thing to be able to do!  Can you then find the inverses of those permutations?

Can you prove Proposition 10?  (Remember that you can leave a comment below if you have any queries.)

It would definitely be worth thinking about the link between our work here on permutation matrices and your previous work on determinants — this will act as good revision of part of the Linear Algebra II course, as well as helping you to understand the new material in this course.  We used determinants of permutation matrices to prove Lemma 14, and we’ll use them for Theorem 15(ii). In the Linear Algebra II course you used transpositions to think about determinants, so do we have a circular argument?  Happily no: we didn’t use determinants to prove Theorem 15 (i), so we know that any permutation can be written as a product of transpositions, and that was the property you used to study determinants in the Linear Algebra course.  Along the way, you noted something equivalent to Theorem 15 (ii), when you discussed the sign of a permutation.  Phew.

Further reading

Don’t forget that Richard Earl’s online notes have lots of worked examples and other little comments that are well worth looking at.  One good approach would be to try to do the worked examples for yourself, and then check your answers with his.

Some of you might be interested in the book Visual Group Theory, by Nathan Carter, which covers (at least most if not all of) the content of this course, from a rather different perspective — experience suggests that some students find his approach very helpful.

There’s a Wikipedia page that discusses ideas relating to Theorem 15.  Of course, there are lots of group theory books out there that go into this too.

How much do you know about the group theorist Hanna Neumann?

Preparation for Lecture 5

Can you prove Theorem 15?

What can you say about the cycle type of an even permutation?

In Linear Algebra I, you had the ‘subspace test’, which streamlined the process of checking whether a subset of a vector space is a subspace.  What might a ‘subgroup test’ look like?

If I give you a group G and an element g \in G, is there a subgroup that contains g?

Is a subgroup of a cyclic group also itself a cyclic group?

2 Responses to “Groups and Group Actions: Lecture 4”

  1. Groups and Group Actions: Lecture 5 | Theorem of the week Says:

    […] Expositions of interesting mathematical results « Groups and Group Actions: Lecture 4 […]

  2. Groups and Group Actions: Lecture 6 | Theorem of the week Says:

    […] Definition of what it means for two elements of a group to be conjugate (building on a definition for permutations). […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: