WEBVTT
00:15.620 --> 00:24.250
ok welcome back so what we wanted to what
we did last time is to talk about signs of
00:24.250 --> 00:35.920
permutations
00:35.920 --> 00:42.280
and this was define to be the the in some
sense you you first take the number of crossings
00:42.280 --> 00:48.309
of the permutation which could be pictorially
red of from the crossing diagram rectangle
00:48.309 --> 00:53.030
for the permutation and then if it is even
then you you declare the sign to be plus one
00:53.030 --> 00:57.420
and if the number of crossings is hard you
declare the sign of the permutation to be
00:57.420 --> 01:08.420
a minus one ok also called even odd permutations
now I want to do a few more examples of these
01:08.420 --> 01:17.370
so let's try and find science of cycles so
here's two examples of you take n to be
01:17.370 --> 01:23.340
four and you take the permutation pi to be
the cycle one two three four so which I will
01:23.340 --> 01:31.260
write first in two line notation one going
to two two going to three four one so this
01:31.260 --> 01:39.120
the the cycle return in two line notation
and also notice that the other notation for
01:39.120 --> 01:46.180
permutations that we looked at is what we
called cycle notation so in cycle notation
01:46.180 --> 01:51.820
the same permutation would be just represented
by the the four numbers one two three four
01:51.820 --> 01:57.630
written in brackets ok this is to be thought
of as meaning one goes two goes to three goes
01:57.630 --> 02:04.200
to four four goes back to one ok so what's
the sign of this pi so that's a question so
02:04.200 --> 02:12.500
let's draw the the tangle diagram for pi so
one maps to two two maps to three three maps
02:12.500 --> 02:21.019
to four and four maps to one so here's the
diagonal diagram for pi the satisfies all
02:21.019 --> 02:26.560
the rules for drawing dangle diagrams correctly
so the number of crossings is one two and
02:26.560 --> 02:37.700
three so the number of crossings
this case is three and so the permutation
02:37.700 --> 02:51.260
pi is odd now similarly of course if you drew
for permutation the diagram for the five cycle
02:51.260 --> 02:56.489
so I take five to be now I just you cycle
notation one goes to three goes to four goes
02:56.489 --> 03:03.709
to five goes to one ad again imagine drawing
the so here's the rectangle for this two
03:03.709 --> 03:12.769
goes to three three goes to four four goes
to five and five goes back to one and now
03:12.769 --> 03:20.579
the number of crossings is one two three four
so there are four crossings and therefore
03:20.579 --> 03:27.810
this permutation now is even ok because there
are four crossings so from this its kind of
03:27.810 --> 03:34.650
clear how cycles behave if you have
cycle of even length so one two three going
03:34.650 --> 03:40.739
on till some even number then that permutation
would have sign minus one and if you have
03:40.739 --> 03:47.469
a permutation cycle with odd length say
going one through five then that would have
03:47.469 --> 03:55.140
even even number of crossings and therefore
it would be n even permutation now here is
03:55.140 --> 04:02.260
slightly more general example will still look
for a four crossing but will do this with
04:02.260 --> 04:11.709
the let's say n equals ok so what is it
mean so let me take the example so let me
04:11.709 --> 04:24.050
take sigma to be the following it is a four
cycle with signs one to three to five to seven
04:24.050 --> 04:31.720
and then it leaves a remaining numbers as
this two four six ok so here's the permutation
04:31.720 --> 04:36.849
sigma written out in cycle notation so recall
what is this really mean so let's draw the
04:36.849 --> 04:41.620
triangle diagram for this so let me first
draw one three five and seven so here's one
04:41.620 --> 04:59.460
three five seven so what this permutation
does is well it is a four cycle if you think
04:59.460 --> 05:08.520
of only these numbers one three five and seven
so five goes to seven and seven maps to one
05:08.520 --> 05:16.479
ok that's the that's the diagram if you only
looked at the numbers one three five and seven
05:16.479 --> 05:20.650
and the number of crossings here is of course
the same as the number of crossing enough
05:20.650 --> 05:28.650
in the other four cycles that we true so there
will be one two three so there are exactly
05:28.650 --> 05:33.790
three cross x ok as for as these four numbers
are concern but of course we still need to
05:33.790 --> 05:47.340
thronging the other numbers so for instance
there is two four and six
05:47.340 --> 05:51.940
now what this this permutation does this is
it maps two to two so I just need to draw
05:51.940 --> 05:57.349
straight line with joins two and two is taking
care to ensure that the rules for rectangles
05:57.349 --> 06:01.919
at present so for instance I don't want have
three things passing through a single point
06:01.919 --> 06:07.800
so when I join four to four it's need to take
little care to ensure that it doesn't pass
06:07.800 --> 06:15.389
through the same point so similarly six to
six ok so here are the three etcetera curves
06:15.389 --> 06:21.170
that you need to through in two going to two
four going to four and six going to six ok
06:21.170 --> 06:27.540
so now in addition to the three crossings
that you already had amongs the the lines
06:27.540 --> 06:34.009
with joined one three five and seven what
we now have are well a few more lines the
06:34.009 --> 06:38.250
few more crossings so let's count the number
of crossing so observe that the red line with
06:38.250 --> 06:43.520
joins two to two it accounts for two crossings
because it needs the line joining one to three
06:43.520 --> 06:51.711
as well as the line joining seven to one so
there are two crossings the line the red line
06:51.711 --> 06:58.099
with join four to four again account for two
crossings the red line joining six to six
06:58.099 --> 07:07.361
again accounts for two crossings ok so the
total number of crossings is how do we count
07:07.361 --> 07:16.080
the number of crossings so the number of crossing
is therefore the following there were three
07:16.080 --> 07:22.289
original crossings plus the crossings that
come from the red lines well they look like
07:22.289 --> 07:29.180
two times well each of those red lines contributes
a true so it's two plus two plus two one for
07:29.180 --> 07:43.300
each red line so this is the crossings
involving the red lines can these are the
07:43.300 --> 07:50.289
crossings at only involve white lines so these
are crossings that don't involve the red lines
07:50.289 --> 08:00.389
not involving the red lines so as you say
these are crossings that involve at least
08:00.389 --> 08:07.509
one red lines involving a red line ok you
you count the crossings in in these different
08:07.509 --> 08:11.110
ways you look at the crossings in which at
least one of the two curves which is a red
08:11.110 --> 08:16.469
line that counted by this and then you look
at the crossings in which you don't thing
08:16.469 --> 08:21.870
about the red lines at all only look at the
white lines and so since we are only interested
08:21.870 --> 08:27.620
in whether or not this the number of crossings
is even so observe that the number of crossings
08:27.620 --> 08:39.660
in this case its still odd because it really
only depends on whether the the original number
08:39.660 --> 08:46.320
of crossings was even around the number of
crossing not involve the red lines ok so this
08:46.320 --> 08:52.820
turns out to be the the general phenomenon
so if you wrote down a permutation like this
08:52.820 --> 08:59.710
so permutation like sigma here you would often
also call this a four cycle it really only
08:59.710 --> 09:05.070
permute these four numbers in a cyclical fashion
doesn't do anything to other numbers so when
09:05.070 --> 09:10.089
you have permutation like this the sign
of this permutation is just the same as the
09:10.089 --> 09:15.940
sign of the the underline four cycle ok which
is its it's a odd permutation or if say this
09:15.940 --> 09:20.779
where a five cycle and these were all being
map to themselves the sign of this would just
09:20.779 --> 09:28.500
be the sign of that that five cycle portion
ok so this this observation here is sort
09:28.500 --> 09:35.430
of it's it's very useful so the number of
crossings is odd therefore the sign of sigma
09:35.430 --> 09:46.260
is in fact minus one so let's just do more
complicated example now which tells you how
09:46.260 --> 09:52.990
to put two different cycles together so let's
take this example now again its taken n equals
09:52.990 --> 10:06.190
seven take a permutation which maps one three
five seven to themselves but let's now do
10:06.190 --> 10:14.250
two four six also map cyclic themselves of
ok so it's a this notation here remember means
10:14.250 --> 10:19.200
that one three five and seven form a four
cycle and then two four six among themselves
10:19.200 --> 10:30.149
form a three cycles now the question is what
is the sign of such a permutation ok of course
10:30.149 --> 10:35.100
conceivably what one do is try and count the
total number of crossings we would look at
10:35.100 --> 10:40.460
you know draw the same sort of diagram
in which you would have four cycle and then
10:40.460 --> 10:45.830
triangle diagram for a three cycle but then
they would all be crash crossing each other
10:45.830 --> 10:51.800
in rather complicated fashion so instead of
sort of just counting it by group force here's
10:51.800 --> 10:56.970
something that ok here's the question so here's
the key observation that you will used is
10:56.970 --> 11:05.810
simplify this calculation so here is a key
observation
11:05.810 --> 11:16.010
you can thing of pi as a really mean the following
pi can we thought of as being the composition
11:16.010 --> 11:20.670
of two permutation so remember we talked about
the composition of permutations so this is
11:20.670 --> 11:34.120
sigma one composed with sigma two so where
well what sigma one sigma one is the permutation
11:34.120 --> 11:39.970
that we just wrote out one three five seven
the four cycle in which the remaining three
11:39.970 --> 11:56.769
are unchanged and sigma two is the three cycle
two four six with one three five seven unchanged
11:56.769 --> 12:01.779
ok the key observation is that you can now
use this notion of composition that we talked
12:01.779 --> 12:10.050
about and obtain the given permutation pi
really as a composition of two simpler pieces
12:10.050 --> 12:15.089
one being sigma one and other being sigma
two ok I leave this as an exercise for you
12:15.089 --> 12:20.601
to check that in fact the composition of these
two permutation does give you back to the
12:20.601 --> 12:29.180
original permutation pi so now we go back
to this whole business of sign and the relationship
12:29.180 --> 12:40.399
of sign to composition and so on so recall
from before
12:40.399 --> 12:46.130
the sign function is really multiplicative
with the respective composition so if I had
12:46.130 --> 12:57.459
sigma one compose sigma two the sign of composition
is just the product of the two signs
12:57.459 --> 13:04.320
ok so this is really the the the important
reason why composition are are especially
13:04.320 --> 13:08.820
suited when you want and try understand signs
if you can write your original permutation
13:08.820 --> 13:14.100
of the composition and the sign is just the
product of signs of the the individual constitution
13:14.100 --> 13:19.040
so here it's a just a sign of pi one sigma
one and sign of sigma two but observe we already
13:19.040 --> 13:26.680
talked about how to understand the sign of
sigma one ok and that exactly the think that
13:26.680 --> 13:31.720
we wrote out here sigma one is really the
permutation which which cyclically permutes
13:31.720 --> 13:38.140
one three five seven and does nothing to two
four six so it's the sign of of sigma is really
13:38.140 --> 13:43.400
just the sign of whatever this this four cycle
part is one ok this things which map to themselves
13:43.400 --> 13:48.370
the red lines so at this peek always contribute
an even number of crossings so they don't
13:48.370 --> 13:52.899
really contribute to the sign of the permutation
so the sign of sigma one would really just
13:52.899 --> 13:58.540
be the sign of the four cycle so which as
minus one as we said and similarly the sign
13:58.540 --> 14:07.800
of sigma two so notice sigma two in our definition
was just the three cycles two four six and
14:07.800 --> 14:13.470
in which the remaining just map to themselves
they are sort of like the red lines in our
14:13.470 --> 14:18.149
picture they will contribute an even number
crossings and we only really need to worry
14:18.149 --> 14:23.100
about the number of crossings between which
only involve the lines joining two four and
14:23.100 --> 14:30.600
six so here it's a sign of the three cycle
two four six it's a plus one ok and so putting
14:30.600 --> 14:38.930
these together the sign of the original permutation
pi is just the product of these two signs
14:38.930 --> 14:50.029
therefore it's a minus one ok so here is a
way of really understanding signs by making
14:50.029 --> 14:56.790
full use of the this whole of of composition
as an operation so and finally using this
14:56.790 --> 15:03.329
this business here is asking that would be
nice to do in this business if you have and
15:03.329 --> 15:20.040
let say a natural number let's do the following
total number of permutations of n number is
15:20.040 --> 15:29.199
just n factorial so for n equals four for
instance so recall this whole table that
15:29.199 --> 15:37.850
we talked about the notion of cycle types
or cycle structure
15:37.850 --> 15:43.760
so the various cycle types that we talked
about you can have four cycle or you can have
15:43.760 --> 15:49.709
a three cycle and a one cycle you can have
two cycle and other two cycle two cycle and
15:49.709 --> 15:56.139
two one cycles are four one cycles these are
the various possible cycle types when you
15:56.139 --> 16:02.200
trying to permute four numbers and the number
of permutations of each type so the number
16:02.200 --> 16:10.569
of permutations
of each of these cycle types we are worked
16:10.569 --> 16:23.339
out before it is a six eight three six and
one
16:23.339 --> 16:30.449
and finally since we talked about signs right
now it's natural to wonder which of these
16:30.449 --> 16:43.990
permutations are odd and which are even
ok so we could ask which of these permutations
16:43.990 --> 16:48.920
are odd and which are even and we already
have the the techniques to to answer these
16:48.920 --> 16:54.190
questions for instance of four cycle ok if
you have a permutation which is just a four
16:54.190 --> 17:00.660
cycle we just talked about signs of cycles
a four cycles is always odd is I just write
17:00.660 --> 17:07.880
minus one for odd now if I have three cycle
together with the one cycle so we again just
17:07.880 --> 17:14.200
did this when you have say a cycle the composition
of the products of two cycles it's you can
17:14.200 --> 17:19.030
think of it as a composition of two permutations
and so it's just the the the product of the
17:19.030 --> 17:25.120
signs of each of these case so three cycle
would be even and one cycle would be even
17:25.120 --> 17:32.730
product of two evens is again even so
this is a sign plus one similarly here we
17:32.730 --> 17:37.310
do the same think here there is a two cycle
composed with the other two cycle two cycle
17:37.310 --> 17:44.321
is odd and other two cycle is therefore also
odd so product of two odds odd permutation
17:44.321 --> 17:50.950
is any one permutation now here a two cycle
is odd one cycles are both even so odd times
17:50.950 --> 17:58.110
even times even we still give you an odd permutation
and finally each of these ones is really a
17:58.110 --> 18:07.720
even permutation so this is the the full list
which of given a cycle type is it odd or even
18:07.720 --> 18:12.180
and the answers are right there so let's count
the total number of odds and total number
18:12.180 --> 18:18.250
of even permutations so which of these are
the odds well the first row there are six
18:18.250 --> 18:23.630
odd permutations with cycle structure four
there are another six odd permutations with
18:23.630 --> 18:30.260
cycle structure two one one is between these
there are twelve permutations with twelve
18:30.260 --> 18:35.980
odd permutations and the even permutations
are there are eight of them with cycle structure
18:35.980 --> 18:42.390
three one three of them with cycle structure
two two and finally one with cycle structure
18:42.390 --> 18:49.610
one one one so these three together again
gives you twelve ok so there are half the
18:49.610 --> 18:57.760
number of odd and half the number of even
permutations ok and this is in fact statement
18:57.760 --> 19:03.330
which is two in general that n factorial divider
by two permutations should be even and the
19:03.330 --> 19:10.130
remaining n factorial by two permutations
should be odd so it's it's probably nice exercise
19:10.130 --> 19:15.350
to try and proof this fact that in general
half the number of permutations are odd and
19:15.350 --> 19:27.861
the other half so let me just state this as
as a problem problem prove that the number
19:27.861 --> 19:44.880
of even permutation is n factorial by two
19:44.880 --> 19:51.309
ok and other exercise is to try and work out
this table that I just it for n equals five
19:51.309 --> 19:58.370
ok here's is an other exercise problem that
I like you to try out is to to work out
19:58.370 --> 20:07.710
this table so write down the entries of this
table for n equals five so the same table
20:07.710 --> 20:15.200
that we just to ok write out all the possible
cycle structures for n equals five and for
20:15.200 --> 20:20.480
each of them work out the number of permutations
with that cycle structure and also work out
20:20.480 --> 20:26.909
whether that permutation would be an odd permutation
odd and even permutation and from that conclude
20:26.909 --> 20:33.220
that in at least see that half of in factorial
so five factorial in this cases hundred and
20:33.220 --> 20:39.710
twenty so you should get sixty even permutations
and sixty odd permutations even ok so ok so
20:39.710 --> 20:42.620
next time will talk about little bit more
about permutations