Placeholder Image

Subtitles section Play video

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

  • 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 were back to where we started, giving us the cycle 2-3.

  • So A times B does NOT equal B times A.

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

Suppose you have “N” things.

Subtitles and vocabulary

Click the word to look it up Click the word to find further inforamtion about it

B1 cycle notation write sends product plug

Cycle Notation of Permutations - Abstract Algebra

  • 6 0
    林宜悉 posted on 2020/03/06
Video vocabulary

Keywords

pattern

US /ˈpætən/

UK /'pætn/

  • noun
  • An arrangement or sequence.
  • A consistent and recurring way of behaving.
  • Model to follow in making or doing something
  • Colors or shapes which are repeated on objects
  • A excellent example or model.
  • Regular repeated behavior
  • A model or guide for making something.
  • A regular or repeated way in which something happens or is done.
  • A set of paper shapes used as a guide for cutting cloth when making clothes.
  • verb
  • To copy the way something else is made
  • other
  • To use as a model or guide.
  • To decorate with a pattern.
guarantee

US /ˌɡærənˈti/

UK /ˌɡærən'ti:/

  • noun
  • A formal assurance (typically in writing) that certain conditions will be fulfilled, especially that a product will be repaired or replaced if not of a specified quality and within a specified period.
  • A thing that assures someone of something.
  • A promise to repair a broken product
  • Promise that something will be done as expected
  • A thing serving as a security.
  • A formal assurance (typically written) that certain conditions will be fulfilled, especially concerning the quality or durability of a product.
  • other
  • To provide a formal assurance or promise, especially that something will happen or that something is of a specified quality.
  • To secure or protect (a right or opportunity).
  • Provide a formal assurance, especially that certain conditions will be fulfilled relating to a product, service, or transaction.
  • To secure or protect (a right or opportunity).
  • verb
  • To promise to repair a broken product
  • To promise that something will happen or be done
  • To promise to pay if another person fails to do so
matter

US /ˈmætɚ/

UK /'mætə(r)/

  • verb
  • To be of great importance; to count
  • noun
  • Material all things are made of that fills space
  • Problem or reason for concern
convince

US /kənˈvɪns/

UK /kən'vɪns/

  • verb
  • To persuade someone, or make them feel sure
  • other
  • To persuade someone to do something or believe something.
common

US /ˈkɑmən/

UK /'kɒmən/

  • noun
  • Area in a city or town that is open to everyone
  • A piece of open land for public use.
  • A piece of open land for public use.
  • Field near a village owned by the local community
  • adjective
  • Lacking refinement; vulgar.
  • Occurring, found, or done often; prevalent.
  • (of a noun) denoting a class of objects or a concept as opposed to a particular individual.
  • Without special rank or position; ordinary.
  • Shared; Belonging to or used by everyone
  • Typical, normal; not unusual
  • Lacking refinement; vulgar.
  • Found all over the place.
treat

US /trit/

UK /tri:t/

  • noun
  • something that tastes good and that is not eaten often
  • Something you buy for others as a surprise present
  • Something special that gives pleasure.
  • other
  • To subject to some process or action; to apply a substance to.
  • To behave towards someone in a specific way.
  • To pay for something for someone as a gift or pleasure.
  • To give medical care or attention to; try to heal.
  • verb
  • To pay for the food or enjoyment of someone else
  • To use medical methods to try to cure an illness
  • To act in a certain way toward someone
distinct

US /dɪˈstɪŋkt/

UK /dɪˈstɪŋkt/

  • adjective
  • Clearly different in nature from something else
  • Clearly different or of a different kind.
  • Not the same; different in nature or quality.
  • Clearly noticeable; easily perceived.
consume

US /kənˈsum/

UK /kən'sju:m/

  • verb
  • To eat, drink, buy or use up something
  • To take all your energy; focus the attention
  • other
  • To destroy completely; to engulf.
  • To eat, drink, or ingest (food or drink).
  • To eat or drink something
  • To completely fill someone's mind
  • To completely engross or absorb someone's attention or energy.
  • To use up (resources or energy).
scratch

US /skrætʃ/

UK /skrætʃ/

  • verb
  • To rub your skin with your fingernails to relieve itching.
  • To rub your skin with your nails to stop an itch
  • To mark or damage the surface of something with a sharp object.
  • To make a small cut or mark on a surface
  • To withdraw from a competition.
  • noun
  • Action of rubbing your skin when itchy
  • A small cut or mark on a surface
  • The beginning or starting point.
  • A shallow mark or cut on a surface.
interpret

US /ɪnˈtɚprɪt/

UK /ɪn'tɜ:prɪt/

  • verb
  • To express so that others understand it
  • To translate what is said into another language
  • other
  • To explain the meaning of something.
  • To perform a creative work (such as a play or piece of music) in a way that shows one's understanding of it.
  • To translate spoken words from one language to another.
  • To understand something in a particular way.