Groups and Group Actions: Lecture 4

In which we explore permutations in more detail.

  • Theorem 9: Every permutation 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.  We proved the ‘existence’ part of this last time.  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 to do 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, 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 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 proved (i) by noting that since any permutation can be written as a product of disjoint cycles, it suffices to show that any cycle can be written as a product of transpositions.  And we have (a_1 \, a_2 \, \dotsc \, a_k) = (a_1 \, a_2)(a_1 \, a_3)\dotsm (a_1 \, a_k).  For (ii), we showed that if \sigma can be written as a product of k transpositions, then \det(P_{\sigma}) = (-1)^k.
  • Definition of the alternating group A_n.

Some comments following questions you asked me after the lecture.

  • Theorem 15 doesn’t claim that the number of transpositions is well defined, just the parity of the number of transpositions.  If I can write a permutation as a product of 6 transpositions, then I may well be able to write it as a product of 8 transpositions (in fact, I can: write it as those six transpositions followed by (1 \, 2)(1 \, 2)).  But I’ll never be able to write it as a product of 7 transpositions, or 101.
  • We used determinants of permutation matrices to prove Theorem 15(ii), and 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.

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.

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.

Preparation for Lecture 5

Can you show that the alternating group A_n really is a group?

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?


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

  1. entangled strings Says:

    I may be missing something but frankly I’m not entirely convinced that there is no circularity in the proof given for Thm 15. (ii) according to the progression of the Oxford course, in particular reflecting on the Linear Algebra II lecture notes. Following Prof. Lauder’s notes for earlier this term, he gives an axiomatic characterisation of the determinant map of a vector space endomorphism over the reals as a multilinear alternating functional that maps the given ordered set of basis to unity and then proceeds to prove its existence and uniqueness. The uniqueness proof is done by expressing each vector entry (the column vector formed by taking as its rows the coefficients of the values of each of the ordered basis elements evaluated under the given linear transformation expressed as a linear combination of its basis elements) as a linear combination of the standard unit column vectors and using the properties given by the axioms to give an explicit formula for the determinant in terms of the entries of the matrix representation of our linear transformation w.r.t. the given ordered basis. This gives the determinant map of an any arbitrary linear transformation as a linear combination of the determinants of permuted sets of basis over all possible permutations of {1, 2, …, n} (where n is the dimension of the vector space) which then we unshuffle using the alternating property of the determinant and the fact that every permutation can be expressed as a composition of transpositions. So far no problem.

    The proof then notes that Det[e_σ(1), …, e_σ(n)]=(-1)^t * Det[e_1, …, e_n]=(-1)^t where t is the number of transpositions one used to produce the given permutation σ. Prof. Lauder then writes “Observe that the value (−1)^t must be independent of how one wrote σ as a product of transpositions: it is called the sign of σ and written sign(σ).” How do we get to this observation that (-1)^t is well-defined (i.e. the number of transpositions producing a given permutuation has a well-defined parity, which is incidently Thm 15. (ii)), if we don’t know that the determinant is unique yet (which is precisely what this proof in Linear Algebra aims to show)? (Note: I don’t have the benefit of actually having attended the Prelims Linear Algebra lectures so I don’t know if any such demonstration has been provided; forgive the physicist who selectively lurks the Oxford Maths Department…) Our proof of Thm 15. (ii) depends on the uniqueness of the determinant (Or else the determinant of our premutation matrix P_σ could be off by, for example, a sign factor due to the opposite sign occuring for every one of (-1)^t in the sum appearing in the explicit formula we got for the determinant) so it seems that without knowing how we got to this (rather convenient) observation, our proof is either circular or we haven’t got anywhere (not having established that the determinant is unique). To phrase the worry borrowing your words, how did we “note something equivalent to Theorem 15 (ii)” along the proof given for the uniqueness of the determinant in the Prelims Linear Algebra course, since as far as I can see, this is the actual substance behind our proof using the determinant that a permutation cannot be both even and odd…?

  2. entangled strings Says:

    I faintly recall an approach provided elsewhere defining sgn(σ):=(product over all values of i and j satisfying 1<=i<j<=n) [σ(i)-σ(j)]/(i-j) for σ in S_n and then "conveniently" noting that this is equal to (-1)^t where t is equal to the number of any transposition producing σ; since the former is determinate the latter is as well, and thus the parity of number of transpositions is well-defined. But this 'observation' is non-trivial; I guess the intuition behind the formula would be that one may express any permutation as a product of disjoint cycles then recalling that any k-cycle can be expressed as (k-1) transposition that (the previously-defined) sgn(σ)=(-1)^t for *the given series of transpositions*, but this consideration still doesn't show that sgn(σ)=(-1)^t for *any series of transpositions producing the permutation*. Another way out would be to claim that our observation made when we noted (-1)^t is independent of how we express the permutation as a composition of transpositions is intuitive, but this defeats the purpose of proving Thm 15. (ii) in the first place…

  3. Kamil Says:

    entangled strings

    I agree with the lecturer.

    The only thing which we are assuming without a proof in Linear Algebra II is that every permutation is a product of transpositions and this we have proved now, without any use of determinants.

    Now, assuming only this, how did we know in LA II that sign(σ) is well-defined?

    We knew this just by the fact that we had proved the existance of a determinantal map D. Take any such map. Then just by the properties of such a map (from Proposition 1.2), for each permutation matrix P we have D(P) = (-1)^t where t is a number of transopsitions that we used to get P from I. Now D is just a function that we chose (maybe it wasn’t unique but it is a function) so D(P) is the value of it – it can’t change. Thus (-1)^t has the same value no matter what number of transpositions we use to get P from I. Hence for a given P, t must be always even or always odd.

    Note that we didn’t use here the uniqueness of a determinantal function.

    To sum up, in this lecture (4) we proved Theorem 15 (i) and in Linear Algebra II, assuming Theorem 15 (i) we proved that sign(σ) is well-defined so in fact now we didn’t even need to prove Theorem 15(ii).

    I hope that it was helpful.

  4. entangled strings Says:

    Come to think of it the above approach might work if we tweak it as the following.
    (1) sgn(σ):=(product over all values of i and j satisfying 1<=i<j<=n) {σ(i)-σ(j)}/(i-j)
    (2) Observing that sgn(τ)=-1 for any transposition τ
    (3) Proving sgn(σρ)=sgn(σ)sgn(ρ)
    (4) For some decomposition of the permutation as a product of transpositions σ=τ_1τ_2…τ_t showing that sgn(σ)=sgn(τ_1)sgn(τ_2)…sgn(τ_t)=(-1)^t
    (5) Hence concluding that for any series transposition producing a given permutation σ is either definitely odd or even but not both. (since sgn(σ)=(-1)^t still holds no matter how one decomposes σ as a composition of transpositions, where t is the number of transpositions used in (4) to produce σ)

    Essentially the idea of this proof is nearly identical to the proof of Thm 15. (ii) given in the lectures using determinants. (I guess this is because at the end of the day the sign function as defined above satisfies sgn(σ)=det(P_σ)). Since sgn(σ) is well-defined (explicit formula which gives an unambiguously unique value for each permutation) we don't have the same worry (provided that it is one) as we would have for the determinant.

  5. entangled strings Says:

    Kamil// Sorry I’ve just noticed your comment. Thanks for the clarification; I wasn’t sure whether I could appeal to the equality of D[e_σ(1), …, e_σ(n)]=(-1)^t for permutations having definite parity in the course of the proof of the uniqueness of the determinant map. I guess at that stage of the proof one could nevertheless grant D acting on any permuted set of basis having a definite value (by the virtue of it being a function); like you said, “maybe it wasn’t unique but it is a function”.

  6. theoremoftheweek Says:

    Everyone happy with this now? It’s good to get this straight.

    In the proof of uniqueness of determinants in Linear Algebra, you picked an arbitrary determinant function D and worked with that. It’s true that there might be other determinant functions floating around, but the point is that once we’ve fixed one, D, what it does to any particular bunch of vectors is determined. So if we find that D[e_{\sigma(1)}, \dotsc, e_{\sigma(n)}] = (-1)^t, then this must be fixed: once we know \sigma, we know (-1)^t and hence the parity of t.

    There are other ways of dealing with this stuff, but the course synopsis says “The parity of a permutation is well-defined via determinants”, so we did it via determinants!

    Hope that helps, glad you were essentially able to resolve this between yourselves.

  7. 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 )

Google+ photo

You are commenting using your Google+ 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: