WEBVTT
Kind: captions
Language: en
00:00:13.740 --> 00:00:17.930
.
So, welcome back so last lecture we had seen
00:00:17.930 --> 00:00:29.480
some motivations for definition of group some
examples and group action . So, when you have
00:00:29.480 --> 00:00:41.440
a group you have a set one can make this group
act ZX that is group action . And we saw formula
00:00:41.440 --> 00:00:49.670
for number of orbits and it turned out that
number of orbits is precisely number of average
00:00:49.670 --> 00:00:56.860
number of fixed points average number of fixed
point meaning, we take elements in G. Consider
00:00:56.860 --> 00:01:07.910
number of elements in X which are fixed by
G and then sum it over divided by size of
00:01:07.910 --> 00:01:11.834
the group that is the average number of fixed
points.
00:01:11.834 --> 00:01:24.039
So, before we move let me mention to you.
Certain examples of groups and actions as
00:01:24.039 --> 00:01:37.009
well and these we lead for further discussion
. So, I will start with Sn yesterday, I mentioned
00:01:37.009 --> 00:02:09.740
Sn is the group of permutations and symbols
. So, I have symbols say a1 a2 a3 an and permuting
00:02:09.740 --> 00:02:23.250
them and then there are n factorial ways . So,
there are total of n factorial permutations.
00:02:23.250 --> 00:02:36.540
Therefore, the size of the group Sn is n factorial
the way this symmetric group is defined the
00:02:36.540 --> 00:02:50.350
way Sn is defined it is very natural that,
Sn x on x what is x? X is just the collection
00:02:50.350 --> 00:03:04.130
of those n symbols a1 into an. How does it
act? It just . So, you take just element I
00:03:04.130 --> 00:03:17.990
will just called it sigma sigma is an element
of Sn and I take an element of x say a i.
00:03:17.990 --> 00:03:27.440
So, sigma was with changing the position of
ai it may be moving into jth place or whatever
00:03:27.440 --> 00:03:41.040
place. So, then I take it to be aj . So, that
is sigma has the property that
00:03:41.040 --> 00:03:56.580
sigma permutes ith element to jth position
. So, that is how the permutation group is
00:03:56.580 --> 00:04:03.439
ok. So, we have an action what about orbit?
What about number of orbits for this action
00:04:03.439 --> 00:04:23.580
? So, that is not very difficult thing
is you see Sn is collection of all permutations
00:04:23.580 --> 00:04:39.389
. Therefore, given any ai and any aj so, given
any 2 symbols so, ai aj arbitrary .
00:04:39.389 --> 00:05:01.360
So, given any 2 symbols there exists a permutation
that moves ai to aj right . So, there exists
00:05:01.360 --> 00:05:12.949
with the property that when sigma x1 ai what
you have is aj this property and therefore,
00:05:12.949 --> 00:05:24.330
as you can say as you can see number of orbits
is is just 1 because any point can move to
00:05:24.330 --> 00:05:36.580
any other point by action of Sn . Few more
examples of groups I am going to mention we
00:05:36.580 --> 00:05:51.830
shall lead those groups, in the lecture very
simple group it is 2 Z by Z mod 2Z or some
00:05:51.830 --> 00:06:00.449
times by Z2 what is Z2 .
It is a grouped with 2 elements and there
00:06:00.449 --> 00:06:07.599
are 2 elements one of them as to be identity
other has to be non trivial identity. So,
00:06:07.599 --> 00:06:17.740
I can say 0 1 or I can say identity and some
other elements say a and what is the property
00:06:17.740 --> 00:06:26.729
the property of the symbol a is one together
with the group operation I am it by a star
00:06:26.729 --> 00:06:45.639
1 is 0 so star is this is group law .
In general, we have Zn and this is called
00:06:45.639 --> 00:07:04.889
cyclic group of order n . What is Zn? Zn consists
of here, I will take about multiplicative
00:07:04.889 --> 00:07:18.360
notation 1 element which is identity the neutral
element and then some element a and then cake
00:07:18.360 --> 00:07:30.039
operation of a with itself and once more.
And you keep doing it until you do it this
00:07:30.039 --> 00:07:42.259
is n minus 1 times so the cyclic group they
are n elements. So, for the simplicity invitation
00:07:42.259 --> 00:07:57.449
a star a star a we just denote it by a to
the power 3 this has notation a to the power
00:07:57.449 --> 00:08:01.279
n minus 1.
So, cyclic groups are quite simple groups
00:08:01.279 --> 00:08:06.770
and there are some interesting actions of
cyclic groups. In fact, a group which is as
00:08:06.770 --> 00:08:17.610
easy as this can be efficiently used in checking
what I call yesterday? Parity it can be used
00:08:17.610 --> 00:08:28.330
to see parity please understand that may be
in coming lectures . So, with the parity we
00:08:28.330 --> 00:08:40.240
come back to Sn there are 2 types of elements,
there are 2 types of permutations in Sn they
00:08:40.240 --> 00:08:46.290
are. So, called even permutations and then
they are so, called odd permutations .
00:08:46.290 --> 00:08:56.670
The parity of even permutations is defined
to be 0 parity of odd permutations is defined
00:08:56.670 --> 00:09:14.980
to be 1 so what is even and odd parity ? So,
for that I will just revise some notation
00:09:14.980 --> 00:09:26.410
and here I would call those symbols which
are being permuted by the group Sn I just
00:09:26.410 --> 00:09:49.699
call them simply 1 2 3 4 and so on . This
is my X and my Sn is permutations of elements
00:09:49.699 --> 00:10:01.639
of X . So, how to express permutations? So
for that we are going to have a notation for
00:10:01.639 --> 00:10:06.000
simplicity just consider the case of say ns
by 2 3.
00:10:06.000 --> 00:10:13.410
So, this is the original position of these
3 symbols and suppose, after permutation you
00:10:13.410 --> 00:10:22.810
have something like 2 3 1. So, what it what
is happening here? 1 is going to 2 2 is going
00:10:22.810 --> 00:10:39.519
to 3 3 is going to 1 . So, I express it like
this 1 is going to 2 2 is going to 3 and 3
00:10:39.519 --> 00:10:49.100
is going to back to 1 it is going to back
1 and that is all there is no other symbol
00:10:49.100 --> 00:10:53.180
and it is 3. So, there is no forth symbol.
So, this is how we denote this permutation
00:10:53.180 --> 00:11:01.940
. So, this is a shorter mutation and yet another
notation for this is simply 1 2 3 and we read
00:11:01.940 --> 00:11:14.800
it like 1 goes to 2 2 goes to 3 and 3 comes
back to 1 let us take few other ones let
00:11:14.800 --> 00:11:29.050
us take n is equal to 4.
So, let us see suppose, these are original
00:11:29.050 --> 00:11:43.560
position and suppose 2 comes here, 1 goes
there, 4 comes here, 3 goes there; that means,
00:11:43.560 --> 00:11:50.339
after permutation at the first seat 2 is sitting
2nd seat one is sitting 3rd seat 4 is sitting
00:11:50.339 --> 00:11:56.839
and 4th seat 3 is sitting . So, how do we
express this so, notation for this is going
00:11:56.839 --> 00:12:10.300
to be what happens to 1? If 1 goes to 2 what
about 2? 2 comes back to 1 and when we have
00:12:10.300 --> 00:12:17.250
complete cycle, we just close this bracket
and then because there are another symbol.
00:12:17.250 --> 00:12:28.600
So, we can start with 4 we can start with
3. So, I have 3 3 goes to 4 and 4 comes back
00:12:28.600 --> 00:12:37.990
to 3. It is a complete cycle and for the case,
for the sake of simplicity, I just write it
00:12:37.990 --> 00:12:52.970
as 1 2 3 4 this is notation . So, simplest
types of permutations are these these are
00:12:52.970 --> 00:13:09.779
permutations is simply say 1 2;
That means, 2 symbols are being swapped. So,
00:13:09.779 --> 00:13:26.480
I have 1 2 3 4 5 see for example, 5 symbols
and there I can consider 2 3 what is 2 3?
00:13:26.480 --> 00:13:39.540
2 3 is the 1 which takes 1 2 3 4 5 is there
, which takes 3 here, 2 here, it just swaps
00:13:39.540 --> 00:13:52.850
right swaps like this and everything else
is intact . So, these special symbols these
00:13:52.850 --> 00:14:10.209
special permutations which just swap 2 positions
are called transpositions so. In fact, just
00:14:10.209 --> 00:14:18.730
by allowing 2 symbols to swap repeatedly.
So, interesting fact that we can construct
00:14:18.730 --> 00:14:28.920
all applications this keep swapping keep swapping
and that is how you construct all possible
00:14:28.920 --> 00:14:53.740
permutations? So, so repeated swapping creates
all permutations . And in other words, the
00:14:53.740 --> 00:15:16.759
way we sake in the language of group theory
Sn is generated by transpositions . So, for
00:15:16.759 --> 00:15:26.740
one transposition for example, for this how
may swapping have an appoint only one right
00:15:26.740 --> 00:15:33.020
only ones is swapped .
So, if take an element for example, . I am
00:15:33.020 --> 00:15:42.920
simply taking n is equal to into say 3 and
I am considering the element say 3 1 2 what
00:15:42.920 --> 00:15:54.970
is that? 3 is going to 1 3 is going to 1 1
is going to 2 and 2 is going to 3 .
00:15:54.970 --> 00:16:04.470
So, I am taking this permutation 3 1 2 I can
express it as product of 2 transpositions
00:16:04.470 --> 00:16:22.189
. So, I start with 1 what is happening
to 1? 1 is going to 2 I just close it and
00:16:22.189 --> 00:16:43.670
then I write it like 1 3. So, 1 goes to 2
and here nothing happens to 2 so eventually
00:16:43.670 --> 00:16:53.120
1 goes to 2. What about 2? 2 goes to 1 and
1 goes to 3. So, 2 is going to 3 what is happening
00:16:53.120 --> 00:16:59.779
to 3? Nothing is happening here and here 3
is going to 1. So, this and this the same
00:16:59.779 --> 00:17:07.240
thing first to perform this permutation and
then you perform this permutation. So, if
00:17:07.240 --> 00:17:12.010
you perform this permutation followed by this
permutation you will have the same effect.
00:17:12.010 --> 00:17:21.550
So, 3 1 2 can be obtained by this product
1 3 and 1 2 how many transpositions are there
00:17:21.550 --> 00:17:54.570
2. So, these are this is product of even number
of transpositions . So, permutation sigma
00:17:54.570 --> 00:18:13.659
is sign the parity 0 if it is product of even
number of transpositions
00:18:13.659 --> 00:18:24.320
and it is a sign parity 1 if it is product
of odd number of transpositions . One important
00:18:24.320 --> 00:18:43.600
thing is ,
it needs proof and I am not proving it that
00:18:43.600 --> 00:18:52.299
this assignment is well defined. What is the
means of that meaning of well defined? Is
00:18:52.299 --> 00:18:58.900
that if you have a permutation and suppose,
there are 2 different ways of expressing it
00:18:58.900 --> 00:19:04.500
as product of transpositions.
And if one of the ways the number of permutations
00:19:04.500 --> 00:19:13.380
which are require the number of transpositions
which will be required is again even. So,
00:19:13.380 --> 00:19:23.049
is the same thing , but but that could differ
So, one this even number could be 4 that
00:19:23.049 --> 00:19:33.700
even number could be 6 that is quite possible
. So, this is well defined and this map is
00:19:33.700 --> 00:19:39.190
called signature.
Signature map for this lecture series I will
00:19:39.190 --> 00:19:47.820
be more often using the word parity. So, parity
is the word to express how many transpositions
00:19:47.820 --> 00:19:59.390
are required to express a permutation as product
. Let see few more examples of groups and
00:19:59.390 --> 00:20:13.340
we will lead those groups in coming lectures
. So, this lecture is full of examples .
00:20:13.340 --> 00:20:29.880
Let me tell you what Dn these are dihedral
groups what dihedral groups are ? Yesterday,
00:20:29.880 --> 00:20:49.049
we had seen symmetry of rectangle . So, today
we are going to see symmetry of regular
00:20:49.049 --> 00:21:05.120
n gone. So, for n is equal to 4 the regular
angle n gone is square . So, I simply take
00:21:05.120 --> 00:21:39.630
square so, you take this square.
So, I just have some notation say 1 2 3 4
00:21:39.630 --> 00:21:50.440
I can have varies symmetries of these square
I can rotate it 90 degree, I can rotate it
00:21:50.440 --> 00:22:04.669
by 180 degree by 270 degree. I can also flip
it right so let me denote r to be
00:22:04.669 --> 00:22:20.419
rotation by 90-degree in. Let us say, anti-clockwise
direction and then with
00:22:20.419 --> 00:22:29.460
that I keep the notation r square to perform
this thing rotation 90 degree in anti-clockwise
00:22:29.460 --> 00:22:34.200
direction twice.
So, that is rotation by 180-degree r cube
00:22:34.200 --> 00:22:42.630
therefore, it rotation by 270 degrees what
about r to the power 4? That is rotation by
00:22:42.630 --> 00:22:51.470
3 6 degrees back to the same position . And
for that reason, we see that r to the power
00:22:51.470 --> 00:23:01.820
4 is identity. So, I this one represents identity
doing nothing the original position is back
00:23:01.820 --> 00:23:12.910
. What else can you do with this? You can
actually flip it about x axis yeah it will
00:23:12.910 --> 00:23:19.720
again remain a symmetry, you can flip it about
y axis that will remain the symmetry, you
00:23:19.720 --> 00:23:29.670
can flip it about diagonal say d 1 say. So,
this diagonal is d 1 and other diagonal d
00:23:29.670 --> 00:23:40.620
2.
So, you can do all these operations so certainly
00:23:40.620 --> 00:23:58.309
the symmetry group of square is going to have
all these elements 1 r r square r cube fx
00:23:58.309 --> 00:24:21.519
f by f d 1 f d 2 f is for flip . In fact,
as I said yesterday composition of 2 symmetries
00:24:21.519 --> 00:24:32.919
is again a symmetry. So, it would be a going
to exercise for you to think what is say r
00:24:32.919 --> 00:24:45.500
composed with say fx you first a flip it about
x axis and then you rotate it by 90 degree
00:24:45.500 --> 00:24:52.269
the anti-clockwise direction what is it? Is
it a new element which has not been explored
00:24:52.269 --> 00:24:58.059
here? No.
So, interesting thing is if you try to compose
00:24:58.059 --> 00:25:05.390
all these things you realize this , this set
is self-contained with respect to that composition.
00:25:05.390 --> 00:25:15.210
And therefore, this is the group of symmetries
of regular for gun square which has 8 elements.
00:25:15.210 --> 00:25:23.890
In general, for n gun what we have? Is dihedral
group, this name is dihedral group and number
00:25:23.890 --> 00:25:32.820
of elements in the dihedral group of order
n of the of group of symmetries of regular
00:25:32.820 --> 00:25:41.590
n gone. It is dihedral group is if the order
is the number of elements is 2 1 this has
00:25:41.590 --> 00:25:48.350
some contrast with the symmetries of rectangle
and I will just tell you what that is .
00:25:48.350 --> 00:26:15.820
So, you recall rectangular symmetry group
and here you have dihedral group this group
00:26:15.820 --> 00:26:29.679
had the property remember fx fy was same as
fy fx . So, if you have a rectangular, you
00:26:29.679 --> 00:26:38.799
flip it by x axis and then flip it by y axis.
It same as first to do flipping about y axis
00:26:38.799 --> 00:26:46.950
and then you will do flipping by flipping
about x axis is the same thing so. In fact,
00:26:46.950 --> 00:26:53.480
rectangular symmetry group let me denote it
by is actually notation. So, I just skip to
00:26:53.480 --> 00:27:02.100
that notation that notation is called V4,
it is called clients 4 group V4 notation.
00:27:02.100 --> 00:27:15.010
So, for every element in the group of symmetries
of a rectangle we have let a b same as b a.
00:27:15.010 --> 00:27:28.460
But if you take dn and try experiment in it
we take r and then you take say fx is actually
00:27:28.460 --> 00:27:37.380
not same as fx r. So, if you first rotate
by 90 degree and then flip about x axis it
00:27:37.380 --> 00:27:44.640
is not same as first flipping about x axis
and then rotating about 90 degree. So, when
00:27:44.640 --> 00:27:51.580
you have this property for a group for every
element for every pair the order in which
00:27:51.580 --> 00:27:58.520
you are having the operation is in material.
Then , this is called abelianess, this is
00:27:58.520 --> 00:28:12.929
called abelian group . While, Dn is an example
of what is called non abelian group .
00:28:12.929 --> 00:28:23.840
So, abelianess is an important properties
of groups let me construct new groups out
00:28:23.840 --> 00:28:30.480
of even groups.
Suppose G is a group, x is the groups so 2
00:28:30.480 --> 00:28:53.490
groups are given , you can take what is called
direct product of G and H. What is that notation
00:28:53.490 --> 00:29:13.760
is G cross H? As I said, it is just a collection
G coma H just like what we have in cartesian
00:29:13.760 --> 00:29:21.980
product just like that G comma S. So, G is
in G and H is in H cartesian product and how
00:29:21.980 --> 00:29:31.639
do we take the group operation? How do we
multiply 2 elements from this ? This
00:29:31.639 --> 00:29:42.960
is one element G1 H1 and other element is
say G2 H2. You simply take the first coordinate
00:29:42.960 --> 00:29:51.700
to be G1 G2 and where is it happening? Where
having this operation in G and then you have
00:29:51.700 --> 00:29:57.120
2nd coordinate as H1 H2 and where is it happening?
It is happening in H ?
00:29:57.120 --> 00:30:07.970
So, you can simply construct a new group out
of 2 given groups . So, for example, if you
00:30:07.970 --> 00:30:16.529
have Z2, you remember Z2 it has just 2 elements
. You take the cartesian product with Z2,
00:30:16.529 --> 00:30:24.960
what are going ? What are you going to have?
You are going to have, we are going to have
00:30:24.960 --> 00:30:38.389
0 0 0 11 0 and 1 1 and you. Of course, know
how to add them so here, if you add 0 1 with
00:30:38.389 --> 00:30:54.870
0 1 answer is 0 0 and 1 0 with 1 0 answer
is again 0 0. So, here you should observe
00:30:54.870 --> 00:31:05.020
that what I had in clients 4 group, you remember
there was a neutral element there was 1 symbol
00:31:05.020 --> 00:31:14.679
fx. There was another symbol fy they have
meanings to this symbols and then r pi .
00:31:14.679 --> 00:31:29.380
So, as you can see 1 corresponds to 0 0 fx
corresponds to say 0 1 fy corresponds to 1
00:31:29.380 --> 00:31:40.700
0 and r pi corresponds to 1 1 [noise.] In
what sense do they correspond this is identity
00:31:40.700 --> 00:31:48.092
element? Here , this has the property that,
it compose to the itself is identity. This
00:31:48.092 --> 00:31:53.850
also compose with itself is identity same
is to here same it to here like this moreover
00:31:53.850 --> 00:31:59.720
when you compose f x and f y you get r pi
you remember.
00:31:59.720 --> 00:32:06.750
Similarly, when you compose 0 1 and 1 0 in
this fashion, in the sense of direct product,
00:32:06.750 --> 00:32:15.299
you actually get this. In fact, all the relations
which are there all the group operation relation
00:32:15.299 --> 00:32:21.539
which are there are preserved when you make
this kind of a assignment. So, this this correspondence
00:32:21.539 --> 00:32:48.880
preserves group operations any map that preserves
group operation is called homomorphism. And
00:32:48.880 --> 00:32:54.350
then when homomorphism which is also invertible
is called isomorphism.
00:32:54.350 --> 00:33:14.049
So, therefore, Z2 cross Z2 and V4 they are
isomorphia a very interesting example of a
00:33:14.049 --> 00:33:24.679
group that we are going to use to resolve
one problem . If you call this I had shown
00:33:24.679 --> 00:33:32.130
you last time , the puzzle with the problem
with the glasses, inverted glasses. How to
00:33:32.130 --> 00:33:41.799
change their orientation from all inverted
to all a pride? That problem so that problem.
00:33:41.799 --> 00:33:45.161
Actually, we are going to use a group and
then introduce you to that group now that
00:33:45.161 --> 00:34:00.750
group is actually Z2 cross Z2 cross Z2 . What
is that Z2 is 0 comma 1. So, here I have 0
00:34:00.750 --> 00:34:09.110
0 0 so I am just taking once more, direct
product and settling the same fashion as we
00:34:09.110 --> 00:34:38.500
do it for cartesian product 0 0 0. So, 0 0
1 0 1 0 0 1 1 and then 100 101 1 1 0 and 1
00:34:38.500 --> 00:34:50.810
1 1 right.
So, these are 8 elements and you have the
00:34:50.810 --> 00:34:59.850
group operation exactly in the same fashion
as here. So, for example, if I add 1 1 0 add
00:34:59.850 --> 00:35:11.650
meaning to the group operation. So, 1 1 0
with 0 0 1. What I get is so 1 1 plus 0 is
00:35:11.650 --> 00:35:21.030
1 1 the 0 is kth 1 in 0 plus is 1 . So, this
is a group operation exactly what I had defined
00:35:21.030 --> 00:35:31.960
here in this same fashion. So, this is group
of 8 elements all these elements have the
00:35:31.960 --> 00:35:47.460
property. So, if let me just say if a belongs
to Z2 cross Z2 cross Z2 then order of a the
00:35:47.460 --> 00:35:54.760
a square is 1.
So, order of a is 2 except for the identity
00:35:54.760 --> 00:36:02.750
element where s square is 1, but the order
is just 1. So, this group is what we are going
00:36:02.750 --> 00:36:11.830
to be use in the permutation puzzle. So, I
hope you could understand this group and I
00:36:11.830 --> 00:36:20.120
hope you could also understand that, in Sn
when action is natural action action is from
00:36:20.120 --> 00:36:32.520
1 to 3 n the natural action of Sn then number
of orbits is .
00:36:32.520 --> 00:36:39.839
And this is in some sense answering the question
that I had raised in previous lecture and
00:36:39.839 --> 00:36:49.220
this is going to be used in the next lecture
when I try to answer problem of making all
00:36:49.220 --> 00:36:55.150
3 cups up right. So, keep watching see
you .