A permutation is just a rearrangement of the “N” objects.

For example, if you have a deck of 52 cards, then all the different outcomes of shuffling

the deck are the permutations.

There are “N” factorial ways to permute “N” distinct things.

If you number the objects from one through “N”, then you can write a permutation

like this.

The top row are the numbers ordered one through “N”, and the bottom row are the the numbers

after the shuffling.

This notation, while clear, takes up a LOT of space.

Today, we’ll learn a more compact way to write a permutation: cycle notation.

The permutations on “N” objects can be made into a group which we call the “symmetric

group,” and we denote it by S-N.

Here’s how it works.

Look at these two permutations on 5 elements.

Each permutation can be thought of as a function where the number on top is the input, and

the number on bottom is the output.

If you think of a permutation as a function, then the group operation is function composition.

If we call the first permutation F, the second permutation G, and treat them as functions,

then F times G gives you another permutation.

You can find the product by plugging in each of the 5 numbers.

If you plug in 1 you get “F of G of 1”.

Now G sends 1 to 3, so this equals “F of 3”.

And F sends 3 to 4, so in the product, 1 goes to 4.

Next, “F of G of 2” equals “F of 1” which equals 3.

So in the product, 2 goes to 3.

If you do this for the remaining numbers, you get the permutation 4-3-2-5-1.

While this way of writing a permutation is clear, it’s very time consuming.

For each permutation, you have to write every number…

TWICE!

Cycle notation allows you to write a permutation on a single line, and often times you end

up writing fewer than N numbers.

Let’s now see how to rewrite a permutation using cycle notation.

Look at this permutation.

Since the top row is always in order, you can read a permutation aloud by only reading

the bottom line: 3-5-4-1-2.

To begin, write down the numbers 1 through 5.

We’ll start by picking the number 1.

Scratch off the number 1 from our list.

The rule is to scratch out a number the moment it appears in a mapping.

In this permutation, 1 goes to 3, so we can write an arrow showing that 1 maps to 3.

You can now scratch out the number 3.

Next, 3 goes to 4, so write an arrow showing 3 maps to 4, and then scratch out 4 from our

list.

And finally, 4 maps back to 1.

You describe these mappings in cycle notation by leaving out the arrows and writing 1-3-4

inside parentheses.

But in your mind, be sure you interpret this as saying 1 maps to 3, 3 maps to 4, and 4

maps back to 1.

There are still some numbers in our list, so we’re not done yet.

The next number that is not scratched out is 2.

So write down 2 and mark it off from our list.

2 maps to 5, so write an arrow mapping 2 to 5, and then scratch out 5 from the list.

And 5 maps back to 2, so it wraps around.

If you leave out the arrows, you get the cycle 2-5.

At this point there are no other numbers in our list, so we’re done!

The cycle decomposition of the permutation is 1-3-4 times 2-5.

Every number appears in exactly one cycle, and each cycle describes part of the permutation.

So the permutation 3-5-4-1-2 can be written as a product of two cycles.

The first cycle has length 3, so we call it a 3-cycle.

The next cycle has length 2, so we call it a 2-cycle.

A cycle of length two is also called a “transposition.”

As you can see, cycle notation is much easier to write.

But there are more things to learn about cycles, so let’s see another example.

Look at the permutation 2-4-3-1-5.

In the first example, we wrote the numbers 1 through five, and then started with 1, but

there’s no reason to start with 1.

You can start with any number you want!

Let’s start with 2.

2 maps to 4...

4 maps to 1... and 1 maps back to 2…

This gives us the cycle 2-4-1.

We can mark off these three numbers from our list.

Next we pick another number that has not yet appeared in a cycle and repeat the process.

Let’s pick 3.

3 maps to itself, so this gives us a cycle with a single number.

Scratch off 3.

And 5 maps to itself as well, this gives us another cycle with a single number.

We can scratch off 5.

So this permutation is the product of 3 cycles: a 3-cycle, a 1-cycle and another 1-cycle.

Here’s another shortcut.

Whenever you have a 1-cycle, you can go ahead and leave it out.

This is because 1-cycles do not change any number, so we can safely ignore them.

This means the permutation can be written simply as the 3-cycle 2-4-1.

But what if we had started with 4 instead of 2?

4 maps to 1...

1 maps to 2... and 2 maps back to 4, so this gives us the cycle 4-1-2.

And as before, 3 maps to 3, and 5 maps to 5, and we leave out the 1-cycles.

And for completeness, what if you had started with 1?

1 maps to 2...

2 maps to 4... and 4 maps back to 1, giving us the cycle 1-2-4.

This is curious.

It seems you get different answers depending on which number you start with.

In the last example, we got three different answers: 2-4-1...

4-1-2… and 1-2-4…

But these cycles are all the same!

In each cycle, one maps to two.. two maps to four.. and four maps to one..

We’re just writing the mappings in different orders.

Here’s how to visualize what’s going on.

Imagine these numbers are on a circle, with arrows going clockwise.

We then see that 2 maps to 4...

4 maps to 1... and 1 maps to 2.

If we start at the top, this gives us the cycle 2-4-1.

Look what happens if we rotate this circle a third of a turn.

Then we get the cycle 1-2-4.

And if we rotate another third, we get the cycle 4-1-2.

This is why they’re called cycles!

While we write the numbers in a row, in reality they represent a loop of mappings.

These three cycles all represent the same information.

A good rule of thumb is to pick the cycle that starts with the smallest number.

So in this case, we’d write it as 1-2-4.

Next, let’s talk about the order of the cycles in the decomposition.

Look at the permutation 3-5-6-4-2-1.

Let’s write this as cycle notation.

Starting with one, we see one maps to three… three maps to six… and six maps back to

one.

This gives us the three-cycle 1-3-6.

Notice how I’m checking off the numbers on top once they appear in a cycle.

Moving on to the next unchecked number we see two goes to five, which goes back to two.

This gives us the two-cycle 2-5.

Remember, a two cycle is also called a TRANSPOSITION.

This leaves only 4.

Four goes to itself, so we get the one cycle 4.

So this permutation can be written as the product of three cycles: 1-3-6…

2-5… and 4…

We don’t bother writing a one-cycle, so the permutation is the product of a three-cycle

and a transposition.

When you write a permutation as a product of cycles, the order of the cycles does not

matter.

So we could write this permutation as a three-cycle times a transposition, or as a transposition

times a three-cycle.

This is an important point.

When you decompose a permutation into a product of cycles, the order of the cycles does not

matter.

But why is this?

Here’s why.

Each cycle can be thought of as a bunch of functions bundled together.

And notice that each of the numbers appears in one and only one cycle.

So when you plug a number into these functions, it will only be affected by one of the cycles.

It passes through the other cycles unaltered.

For example, let’s look at a permutation from the symmetric group S-7.

We’ll consider the product of the 3-cycle 1-3-7 and the transposition 4-6.

Notice that the numbers 2 and 5 do not appear anywhere.

This means they are 1-cycles, and when working with cycles, 1-cycles are invisible.

Let’s now see what happens to a few numbers.

If you plug in 1, it passes through the transposition unchanged, because 1 does not appear in the

2-cycle.

When it hits the 3-cycle, 1 is mapped to 3.

Next, look at the number 2.

2 is not in either cycle, so it passes through unchanged.

If you plug in 6, the transposition maps it to 4, but the 3-cycle has no effect.

The result would be the same if we changed the order of the cycles.

And since only one cycle changes any number, the order doesn’t really matter.

But here’s the important part.

You can rearrange cycles, but only if no number appears in more than one cycle.

When you write a permutation as a product of cycles, this isn’t a problem.

You’re guaranteed each number will only appear in a single cycle.

But when you multiply two DIFFERENT permutations, this is no longer the case.

In this situation, you will often find the same number in more than one cycle.

So you can’t rearrange the cycles.

The technical way to say this is as follows: if two cycles have no number in common, then

they commute with one another.

Let’s see an example.

Instead of working with a single permutation, let’s multiply two different permutations,

A and B. First, let’s write these permutations in

cycle notation.

In A, 1 goes to 3…

3 goes to 2… and 2 goes to 1.

So A can be written as a single 3-cycle: 1-3-2.

For B, 1 goes to 3, and 3 goes back to 1.

And 2 goes to 2, so B is the product of the transposition 1-3 and the 1-cycle 2.

We ignore 1-cycles, so B is simply the 2-cycle 1-3.

Let’s now multiply A and B.

Here, the order matters, because the cycles both contain 1 and 3, so they may not commute

with each other.

If you plug in 1, the 2-cycle sends it to 3, and the 3-cycle sends 3 to 2.

If you plug in 2, the transposition doesn’t change it, but the 3-cycle sends it to 1.

And finally, if you input 3, the 2-cycle sends it to 1, and the 3-cycle then sends 1 to 3,

so 3 maps to itself.

And we can ignore 1-cycles.

So A times B is the cycle (1 2) Now look at the reverse: B times A.

In this case, 1 goes to 3, which then goes to 1.

This gives us a 1-cycle.

Next, 2 maps to 1, then the transposition sends 1 to 3.

If you plug in 3, the first cycle sends it to 2, and the next cycle does nothing to two.

So we’re back to where we started, giving us the cycle 2-3.

So A times B does NOT equal B times A.

As we’ve seen, every permutation can be written in the compact cycle notation.

If two neighboring cycles have no numbers in common, you can switch them.

But if they DO share a number, they may not commute.

And lastly, any cycle can be written in a number of ways, provided the circular order

does not change.

This method of writing permutations is a valuable time-saver when working with

symmetric groups.

Here is a challenge for you.

Suppose you have a cycle of length 2.

What is its order?

Next, pick a cycle of length 3, and compute its order.

What about a 4-cycle?

Do you see a pattern?

Please share your conjectures, and try to convince us it’s true.

Good luck, thank you, and have a nice Patreon...