Placeholder Image

字幕列表 影片播放

  • Suppose you have “N” things.

  • 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, well 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 thesymmetric

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

  • Well 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 were 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 were 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..

  • Were 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 theyre 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 threethree maps to sixand 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.

  • Well 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.

  • Youre 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.