Back to the on-screen lesson ·
Right-to-left composition traced letter by letter, inverses by reversing every cycle, conjugation as relabelling, and the permutation matrix that turns all of it into matrix algebra.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to compose two permutations by tracing each letter through the right-hand factor and then the left, read the result back as disjoint cycles, write down the inverse of a permutation by reversing its cycles, say why two cycles sharing a letter need not commute and what conjugation does to cycle notation, and write the permutation matrix of a permutation.
The last lesson turned a permutation into a short string of brackets. This one combines two of them. There is only one thing to decide and it has to be decided once and kept: which factor acts first. This course uses the convention that agrees with functions — the right-hand factor first — and every later computation depends on it.
The composite $\sigma\tau$ is the permutation sending $x$ to $\sigma(\tau(x))$: the right factor acts first. The inverse $\sigma^{-1}$ sends $\sigma(x)$ back to $x$. The permutation matrix of $\sigma$ is the square matrix whose entry in row $i$, column $j$ is $1$ when $\sigma(j) = i$ and $0$ otherwise; it has exactly one $1$ in each row and each column.
To compute $\sigma\tau$, take each letter $x$ and find $\sigma(\tau(x))$: push $x$ through the right factor, then through the left. It is the convention of $f(g(x))$, and books that use the other one write permutations on the right of their arguments to keep it consistent.
$$(1\,2\,3)(2\,3\,4): \quad 1 \to 1 \to 2, \quad 2 \to 3 \to 1, \quad 3 \to 4 \to 4, \quad 4 \to 2 \to 3,$$
which is $(1\,2)(3\,4)$. Trace every letter, then read the disjoint cycles off the list of images.
Inverses are free. Reverse each cycle: $(a_1\,a_2\,\ldots\,a_k)^{-1} = (a_k\,\ldots\,a_2\,a_1)$. A transposition is its own inverse. For a product of disjoint cycles, invert each in place; for a product that is not disjoint, use the reversing rule from unit 1 and write the inverted factors in the opposite order.
Powers. $\sigma^{2}$, $\sigma^{3}$ and so on are computed the same way, and for disjoint cycles each cycle may be powered separately — which is what makes the order of a permutation computable from its cycle lengths alone, in the next lesson.
The matrix form. Sending $\sigma$ to its permutation matrix turns composition into matrix multiplication, in the same order. It is the first isomorphism in this course between a group defined combinatorially and a group of matrices, and it is the reason the sign of a permutation will turn out to be a determinant.
Another way: picture
Draw the letters in a column twice, side by side, with arrows for $\tau$ from the first column to the second, and arrows for $\sigma$ from the second to a third. To find where the composite sends a letter, put your finger on it in the first column and follow two arrows. The picture makes the convention obvious: you meet $\tau$'s arrow first because $\tau$ is written next to the letter.
Another way: steps
To compose two permutations: 1. Take the letters one at a time, in order. 2. Push each through the right-hand factor. 3. Push the result through the left-hand factor, and record where it ended. 4. Read the list of images back as disjoint cycles. 5. Check that the images are a rearrangement of the letters.
$S_3$ has six elements and is the smallest non-abelian group. Its non-commuting is easy to see and worth seeing once in full:
$$(1\,2)(1\,3) = (1\,3\,2), \qquad (1\,3)(1\,2) = (1\,2\,3).$$
The two answers are different permutations — inverses of each other, in fact. Two permutations commute when they move disjoint sets of letters, and sometimes for other reasons (any permutation commutes with its own powers), but there is no general rule and none should be assumed.
There is a useful measure of the failure. For any $\sigma$ and $\tau$,
$$\sigma\tau = (\sigma\tau\sigma^{-1})\sigma,$$
so swapping the order replaces $\tau$ by its conjugate $\sigma\tau\sigma^{-1}$. And conjugation by $\sigma$ does something very concrete to cycle notation: it renames every letter. If $\tau = (a\,b\,c)$ then
$$\sigma\tau\sigma^{-1} = (\sigma(a)\,\sigma(b)\,\sigma(c)).$$
So conjugating never changes the shape of a permutation, only its labels. Two permutations of $S_n$ are conjugate exactly when they have the same cycle type — a fact that turns a question about $n!$ elements into a question about partitions of $n$, and one that will be used again in unit 3 when normal subgroups arrive.
Composing left to right. Both conventions exist in the literature, and answers computed under one are wrong under the other. This course applies the right-hand factor first, always.
Assuming a product of cycles is already in disjoint form. $(1\,2)(2\,3)$ is not disjoint. Compose it first, then read off the cycles, before applying any rule about orders or parities.
Inverting a product without reversing. $(\sigma\tau)^{-1} = \tau^{-1}\sigma^{-1}$. Reversing each cycle in place is correct only when the factors are disjoint.
Thinking a cycle and its inverse are unrelated. They are the same tour run backwards, which is why a $3$-cycle and its inverse are the two different $3$-cycles on the same three letters.
Writing the permutation matrix transposed. With the convention here, column $j$ says where $j$ goes. The transpose is the matrix of the inverse permutation, which is a genuine object and not the one asked for.
$(1\,3)(2\,4) \cdot (1\,2\,3)$, right factor first. $1 \to 2 \to 4$; $2 \to 3 \to 1$.
Two letters traced.
$3 \to 1 \to 3$; $4 \to 4 \to 2$. So the images are $4, 1, 3, 2$.
The other two.
Reading the cycles: $1 \to 4 \to 2 \to 1$, with $3$ fixed. The product is $(1\,4\,2)$.
Back to cycle notation.
$\sigma = (1\,5\,3)(2\,6)(4\,7\,8\,9)$. Reverse each cycle: $\sigma^{-1} = (3\,5\,1)(6\,2)(9\,8\,7\,4)$.
Disjoint, so each is inverted in place.
Check on one letter: $\sigma$ sends $1$ to $5$, and $\sigma^{-1}$ sends $5$ to $1$.
One letter is enough to catch a reversal error.
Note $(2\,6)$ is unchanged by reversing, as every transposition is.
Self-inverse factors.
Right factor first. $1 \to 3 \to 3$, so $1 \mapsto 3$.
One letter at a time.
$3 \to 1 \to 2$, so $3 \mapsto 2$. And $2 \to 2 \to 1$, so $2 \mapsto 1$.
The other two.
Reading the tour: $1 \to 3 \to 2 \to 1$, so the product is $(1\,3\,2)$. The other order gives $(1\,2\,3)$, its inverse.
Compose $(1\,2)(1\,3\,4)$ in $S_4$, right factor first. The middle column shows where $(1\,3\,4)$ sends each letter; fill in where the composite sends it.
| Where the right factor sends it | Where the composite sends it | |
|---|---|---|
| 1 | 3 | |
| 2 | 2 | |
| 3 | 4 | |
| 4 | 1 |
Put the steps of computing where $(1\,2\,3)(2\,3\,4)$ sends the letter $4$ into order.
Number the steps in order (write the number in the box):
In $S_4$, where does $(1\,2)(1\,3\,4)$ send the letter $2$? Compose right to left.
Answer:
Match each permutation to its inverse.
| $(1\,2)$ | $(1\,3\,2)$ | $(1\,4\,3\,2)$ | $(1\,2)(3\,4)$ | $(1\,2\,3\,4)$ | |
|---|---|---|---|---|---|
| $(1\,2\,3)$ | |||||
| $(1\,2)$ | |||||
| $(1\,2\,3\,4)$ | |||||
| $(1\,2)(3\,4)$ |
Select every statement about composing permutations that is true.
This task has no paper form; do it on a device.
Write the permutation matrix of $(1\,3\,2)$ in $S_3$: a $3 \times 3$ matrix whose entry in row $i$, column $j$ is $1$ when the permutation sends $j$ to $i$, and $0$ otherwise.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Compose $(1\,2\,3)(2\,3\,4)$ in $S_4$, right factor first. The middle column shows where $(2\,3\,4)$ sends each letter; fill in where the composite sends it.
| Where the right factor sends it | Where the composite sends it | |
|---|---|---|
| 1 | 1 | |
| 2 | 3 | |
| 3 | 4 | |
| 4 | 2 |
You can compose two permutations in the right order and invert one by reversing its cycles. Say in your own words which factor acts first and why the convention matters. Next: the order and the parity of a permutation, both read straight off its cycle lengths.
9. Your turn: compute $(1\,2)(1\,3)$ in $S_3$., step 3