MTH 461 Miami Compute the Following Compositions of Permutations Algebra Questions

MTH 461: Survey of Modern Algebra, Spring 2021Homework 3
Homework 3
1. Let G be the group of symmetries of a square in the 2-dimensional plane.
(a) Analogous to what we did for the symmetries of an equilateral triangle, write
down all symmetries of the square. What is the order of the group G?
(b) Label the 4 vertices of the square with the numbers 1, 2, 3, 4. Accounting for how
these labels are moved around by each symmetry, write down a subgroup H Ă S4
which corresponds to G.
(c) Is H all of S4 ? Is it contained in the alternating group A4 ?
2. Compute the following compositions of permutations.
(a) p1345qp234q
(b) p143qp23qp24q
(c) p1354q100
3. (a) What is ordpσq for σ P Sn equal to a cycle of length l? Explain.
(b) Recall that an arbitrary permutation σ P Sn can be written as σ “ σ1 σ2 ⋯σk where
each σi is a cycle and they are all disjoint. Show that
ordpσq “ lcmpl1 , . . . , lk q
where li is the length of the cycle σi .
(c) Write down all possible orders of elements in S7 .
4. In lecture we saw that every cycle in Sn is a product of transpositions. Use this to
explain how the parity of a cycle is determined by the length of the cycle.
5. Determine whether each permutation is even or odd.
(a) p14356q
(b) p156qp234q
(c) p17254qp1423qp154632q
1
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 6
Lecture 6: Symmetries
A symmetry of an object is a rearrangement of the object such that its geometric properties
are preserved. If the object is a subset X of points in space, then a symmetry is a 1-1 map
f ∶ X Ñ X that preserves distances and angles. For example, consider an equilateral triangle
X Ă R2 in 2-dimensional space. A symmetry maps the triangle to itself in a way which sends
vertices to vertices, and edges to edges. All symmetries of the triangle are as follows:
R1
T1


R2
T2


e
R3


Let us give each such symmetry the name as indicated in the figure. Thus R1 is “reflection
across the vertical line” and so on. We use the notation
R1 ˝ T1
to mean “first T1 then R1 .” In this case this means “rotate 120˝ counter-clockwise, then
reflect across the vertical line.” (The order is just as for functions, or maps.) We see that
R1 ˝ T1 “ R3
We also have R1 ˝ R1 “ e, R1 ˝ R2 “ T2 , T1 ˝ T2 “ e. Eventually we obtain a Cayley table:
e
R1
R2
R3
T1
T2
e
e
R1
R2
R3
T1
T2
R1
R1
e
T2
T1
R3
R2
R2
R2
T1
e
T2
R1
R3
R3
R3
T2
T1
e
R2
R1
T1
T1
R2
R3
R1
T2
e
T3
T2
R3
R1
R2
e
T1
This should look familiar: it is exactly the Cayley table for the non-abelian group of order
6 that we discussed in Lecture 1 (after renaming symbols).
1
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 6
§ The symmetries of an object forms a group.
This can be seen explicitly in the example above, but the general case is also straightforward.
The key is to think of symmetries as 1-1 maps from a set X to itself which satisfy certain
properties (the maps preserve distances and angles, for example).
Let us consider other objects. Take an isosceles triangle in the plane. Then apart from the
identity symmetry e, there is only one symmetry R, which is a reflection across the line
indicated in the figure below on the left. Further, R ˝ R “ e. Thus the group of symmetries
of an isosceles triangle is te, Ru with R2 “ e. This is a cylic group of order 2.
On the other hand, if we take an arbitrary triangle with 3 different angles, so that no two
sides are the same length, then there are no symmetries apart from the identity. See the
figure above on the right. The group of symmetries of such a triangle is teu, a trivial group.
Permutations
Let X be a finite non-empty set. Suppose |X| “ n. We think of X as an abstract collection
of n points, with no geometric information regarding the points. In this case the “symmetries
of X” are simply the 1-1 maps σ ∶ X Ñ X, i.e. the ways of rearranging the points in the
set. These are called permutations of the set X. We will not care about the names of the
elements of X, so we may as well let X “ t1, . . . , nu.
§ The group of permutations on t1, . . . , nu is called Sn, the nth symmetric group.
An element of Sn , which is a map from t1, . . . , nu to itself, may be represented as:
ˆ
˙
1
2
⋯
n
σ“
σp1q σp2q ⋯ σpnq
We also write i ↦ j to mean σ sends i to j, i.e. σpiq “ j. For example, let σ P S6 map 1 ↦ 2,
2 ↦ 3, 3 ↦ 5, 4 ↦ 6, 5 ↦ 1, 6 ↦ 4. Then we write this permutation as
ˆ
˙
1 2 3 4 5 6
σ“
2 3 5 6 1 4
Let us consider another permutation τ P S6 , given as follows:
ˆ
˙
1 2 3 4 5 6
τ“
3 1 4 2 5 6
2
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 6
Let us compute τ ˝ σ. Note that the notation means “do σ, then τ .” We find:
pτ ˝ σqp1q “ τ pσp1qq “ τ p2q “ 1
pτ ˝ σqp3q “ τ pσp3qq “ τ p5q “ 5
pτ ˝ σqp5q “ τ pσp5qq “ τ p1q “ 3
pτ ˝ σqp2q “ τ pσp2qq “ τ p3q “ 4
pτ ˝ σqp4q “ τ pσp4qq “ τ p6q “ 6
pτ ˝ σqp6q “ τ pσp6qq “ τ p4q “ 2
Writing the result in our notation introduced above we then have:
ˆ
˙
1 2 3 4 5 6
τ ˝σ “
1 4 5 6 3 2
Another more compact notation, called cycle notation, is described as follows. We illustrate
this notation in the current example, and also comment on the general case in the next
lecture. Starting with the element “1” we can successively apply the permutation σ until we
get back to “1”:
σ
σ
σ
σ
1 zÑ 2 zÑ 3 zÑ 5 zÑ 1
This forms a cycle and is denoted p1235q. The notation is meant to be cyclic, and can be
written also as p2351q, p3512q or p5123q. To describe the rest of the permutation σ we must
also know what it does to “4” and “6”. Note that
σ
σ
4 zÑ 6 zÑ 4
and this forms another cycle p46q “ p64q. We then write σ in cycle notation as follows:
σ “ p1235qp46q “ p46qp1235q
We can also write τ in cycle notation, as τ “ p1342q. Note that “5” and “6” are fixed by τ
and they do not appear in the notation, by convention. We then compute
τ ˝ σ “ p1342qp1235qp46q “ p246qp35q
by reading cycles from right to left, and this is the same answer we obtained above.
§ The nth symmetric group Sn is non-abelian if n ě 3.
Note S1 “ teu is the trivial group, and S2 “ te, p12qu is cyclic of order 2. For n “ 3 we have
S3 “ te, p12q, p23q, p31q, p123q, p132qu
This is a non-abelian group of order 6. In fact if you write out its Cayley table you may
notice it looks just like the symmetries of an equilateral triangle. This is no accident, for
S3 is essentially the same group: any symmetry of the triangle is determined by how the
3 vertices are permuted. To see that Sn is non-abelian for n ě 4, note that we can view
S3 Ă Sn as the subgroup which fixes the last n ´ 3 elements.
3
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 7
Lecture 7: Symmetric groups
In this lecture we continue our study of the symmetric groups Sn introduced last lecture,
and we then introduce the notion of even and odd permutations.
§ The order of the group Sn is given by |Sn| “ n!.
This is a basic counting exercise. Each permutation σ is a way of rearranging the elements
t1, . . . , nu. There are n possibilities for σp1q P t1, . . . , nu. Once the value of σp1q is fixed,
there are n ´ 1 possibilities left for σp2q, since it can be anything except for σp1q. Continuing
in this fashion, we see that the number of possibilities for the permutation σ P Sn is equal
to npn ´ 1qpn ´ 2q⋯2 ¨ 1 “ n!.
For example, we have seen that |S1 | “ 1 “ 1!, |S2 | “ 2 “ 2! and |S3 | “ 6 “ 3!. Recall that S3
is essentially the symmetries of an equilateral triangle, and there are 6 such symmetries.
A cycle is a permutation σ P Sn such that there exists an i P t1, . . . , nu with the property
that for each j P t1, . . . , nu either σpjq “ j or j “ σ k piq for some k P Z. In other words, every
element of t1, . . . , nu is either fixed by σ or can be obtained from i by successively applying
σ. Our notation for such a cycle, which we introduced last lecture, is as follows:
pi σpiq σ 2 piq ⋯ σ l´1 piqq
Here l is the smallest positive integer such that σ l piq “ i.
§ Every σ P Sn can be written as a product of disjoint cycles.
Two cycles are disjoint if they share no common elements in their cycle notations. For
example, p13q and p246q are disjoint cycles, while p12q and p254q are not. To prove the
statement, define a relation on the set t1, . . . , nu as follows: i „ j if and only if σ k piq “ j for
some k P Z. You can check that this defines an equivalence relation, and hence partitions
the set t1, . . . , nu, and each equivalence class forms a cycle with respect to σ.
2
4
5
1
6
3
The content of the above is that any permutation σ P Sn partitions the set t1, 2, . . . , nu into
subsets each of which σ permutes in a cyclic fashion. For example, σ “ p245qp16q P S6 is
depicted above. Note that σ fixes “3” and this does not appear in cycle notation.
§ Disjoint cycles in Sn commute.
The length of a cycle is the number of elements appearing in it: p146q is a cycle of length 3,
and p4263q is length 4. A transposition is a cycle of length 2, such as p12q.
1
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 7
§ For n ě 2, every σ P Sn is a product of transpositions.
We first note that an arbitrary cycle pa1 a2 ⋯ak q can be written
pa1 a2 ⋯ak´1 ak q “ pa3 a2 qpa4 a3 q⋯pak ak´1 qpa1 ak q
For example, p245q “ p45qp24q. The general case follows from the case of cycles, because any
σ P Sn is a product of cycles.
The way in which a cycle is written as a product of transpositions is not unique. As an
example, we have p12qp13q “ p132q “ p23qp12q in the group S3 . In fact, another formula for
writing an arbitrary cycle as a product of transpositions is as follows:
pa1 a2 ⋯ak´1 ak q “ pa1 ak qpa1 ak´1 q⋯pa1 a3 qpa1 a2 q
Even and odd permutations
Let f “ f px1 , . . . , xn q be a polynomial in n variables. Given a permutation σ P Sn define a
new polynomial σpf q to be f pxσp1q , . . . , xσpnq q. Define the special polynomial
ź
∆n “
pxi ´ xj q
1ďiăjďn
to be the product ofl all factors pxi ´ xj q where i, j range over elements of t1, . . . , nu with
i ă j. Then we may apply any permutation σ to this to obtain a new polynomial σp∆n q. It
turns out that this new polynomial is always either ∆n or ´∆n . This lets us divide permutations into two types, as follows:
§ If σp∆nq “ ∆n is called even.
If σp∆n q “ ´∆n then σ is called odd .
For example, consider σ “ p12q P S3 . Note ∆3 “ px1 ´ x2 qpx1 ´ x3 qpx2 ´ x3 q. Then
σp∆3 q “ pxσp1q ´ xσp2q qpxσp1q ´ xσp3q qpxσp2q ´ xσp3q q
“ px2 ´ x1 qpx1 ´ x3 qpx2 ´ x3 q
“ ´px1 ´ x2 qpx2 ´ x3 qpx1 ´ x3 q
“ ´∆3
Thus σ “ p12q is odd. In the next lecture we will show that the even permutations form a
subgroup of Sn called the alternating group An .
2
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 8
Alternating groups
In this lecture we continue studying even and odd permutations. We introduce and study the
alternating groups An which consist of even permutations. We then consider the rotational
symmetries of the tetrahedron, which are closely related the group A4 .
Recall that a permutation
σ P Sn is even if σp∆n q “ ∆n and odd if σp∆n q “ ´∆n . Here ∆n
ś
is the polynomial 1ďiăjďn pxi ´ xj q introduced last lecture. Define
An “ tσ P Sn ∶ σ is evenu Ă Sn
§ The subset An Ă Sn is a subgroup, called the nth alternating group.
To prove this we first record a useful relation. Given any permutations σ, σ 1 P Sn we have
pσσ 1 qp∆n q “ σpσ 1 p∆n qq
This just follows by writing out what each side means explicitly:
ź
ź
pσσ 1 qp∆n q “
pxpσσ1 qpiq ´ xpσσ1 qpjq q “
pxσpσ1 piqq ´ xσpσ1 pjqq q
1ďiăjďn
1ďiăjďn
˜
“σ
¸
ź
pxσ1 piq ´ xσ1 pjq q
“ σpσ 1 p∆n qq
1ďiăjďn
Similarly, σp´∆n q “ ´σp∆n q. Now suppose σp∆n q “ p´1qk ∆n and σ 1 p∆n q “ p´1ql ∆n . Then
pσσ 1 qp∆n q “ σpσ 1 p∆n qq “ σpp´1ql ∆n q
“ p´1ql σp∆n q “ p´1ql p´1qk ∆n
“ p´1ql`k ∆n
From this computation we see the same rules as for adding even and odd integers:
σ
σ1
even
even
even
odd
even
odd
even
odd
odd
odd
odd
odd
σσ 1
In particular, if σ, σ 1 P An (σ, σ 1 are both even) then σσ 1 P An (σσ 1 is even). Also the identity
is even, so it is in An . Further, if σ P An (σ is even), then since σσ ´1 “ e P An (σσ ´1 is even)
we must have σ ´1 P An (σ ´1 is even). Thus An is a subgroup of Sn .
An alternative characterization of the parity of a permutation is as follows:
1
MTH 461: Survey of Modern Algebra, Spring 2021
§ If σ “ τ1⋯τk
Lecture 8
where τi are transpositions, then σ is odd if and only if k is odd.
To prove this we first show that every transposition is odd. First consider the transposition
σ “ p12q P Sn . There are four kinds of factors in ∆n :
px1 ´ x2 q,
px1 ´ xj q pj ą 2q,
px2 ´ xj q pj ą 2q,
pxi ´ xj q pj ą i ą 2q
Now σ “ p12q only swaps 1 and 2. So it sends the first type of factor to its negative
px2 ´ x1 q “ ´px2 ´ x1 q. It interchanges the second and third types (preserving signs), and
fixes all factors of the fourth type. Taking the product we conclude σp∆n q “ ´∆n , where
the sign comes from the effect of σ “ p12q on the factor px1 ´ x2 q. Next, we use:
§
Let σ “ pa1 a2 ⋯ ak q P Sn be a cycle and τ P Sn any other permutation. Then
τ στ ´1 “ pτ pa1 q τ pa2 q ⋯ τ pak qq
A special case is when σ “ pi jq a transposition different from p12q with j ą i. Setting
τ “ pi 1qpj 2q we get τ ´1 στ “ p12q. If i “ 1, interpret pi 1q as e.
Now let σ be any transposition and choose τ as above such that τ στ ´1 “ p12q. Then
σ “ τ ´1 p12qτ . Let τ p∆n q “ p´1qk ∆n . Note also τ ´1 p∆n q “ p´1qk ∆n . We then compute
σp∆n q “ pτ ´1 p12qτ qp∆n q
“ τ ´1 pp12qpτ p∆n qqq
“ τ ´1 pp12qp´1qk ∆n qq
“ p´1qk τ ´1 pp12qp∆n qq
“ p´1qk τ ´1 p´∆n q
“ p´1qk`1 τ ´1 p∆n q
“ p´1q2k`1 ∆n “ ´∆n
This completes our claim that every transposition is odd. Then to prove the claim about
σ “ τ1 ⋯τk for a product of transpositions, we use the rules of the table we determined above.
Let us look at some examples. As S1 “ teu we of course have A1 “ teu. Next, S2 “ te, p12qu,
and p12q is odd, so in fact A2 “ teu as well. The 3rd symmetric group is
S3 “ te, p12q, p23q, p31q, p123q, p132qu
The three transpositions p12q, p23q, p31q are odd, so they are not in A3 . On the other hand
p123q “ p13qp12q and p132q “ p12qp13q, so these are even. Thus
A3 “ te, p123q, p132qu
Note that p123q2 “ p132q and p123q3 “ e, so A3 is a cyclic (hence abelian) group of order 3.
This is in contrast to S3 . However:
§ The alternating group An is non-abelian if and only if n ě 4.
2
MTH 461: Survey of Modern Algebra, Spring 2021
Lecture 8
Symmetries of the tetrahedron
The first non-abelian alternating group, A4 , is closely related to the rotational symmetries
of the tetrahedron in 3-dimensional space.
A tetrahedron is a solid in 3-dimensional Euclidean space which has 4 vertices and 4 sides,
each an equilateral triangle. On the next page we list the symmetries of the tetrahedron.
There are 2 types of non-identity symmetries. The first type pR1˘1 , R2˘1 , R3˘1 , R4˘1 q fixes a
vertex and rotates the tetrahedron around an axis passing through the fixed vertex by 120˝
in one of two directions. The second kind of symmetry pA, B, Cq is a 180˝ rotation through
an axis which passes through the centers of two opposite edges.
If we label the vertices of the tetrahedron by t1, 2, 3, 4u we can associate a permutation to
each symmetry. Magically, the subgroup of S4 corresponding to the symmetries of the tetrahedron is A4 ! Below we include the Cayley table.
e
R1
R1´1
R2
R2´1
R3
R3´1
R4
R4´1
A
B
C
e
e
R1
R1´1
R2
R2´1
R3
R3´1
R4
R4´1
A
B
C
R1
R1
R1´1
e
A
R4
B
R2
C
R3
R3´1
R4´1
R2´1
R1´1
R1´1
e
R1
R3´1
C
R4´1
A
R2´1
B
R2
R3
R4
R2
R2
C
R4´1
R2´1
e
R1
B
R3´1
A
R1´1
R4
R3
R2´1
R2´1
R3
A
e
R2
C
R4
B
R1´1
R4´1
R3´1
R1
R3
R3
A
R2´1
R4´1
B
R3´1
e
R1
C
R4
R1´1
R2
R3´1
R3´1
R4
B
C
R1´1
e
R3
A
R2
R1
R2´1
R4´1
R4
R4
B
R3´1
R1
A
R2´1
C
R4´1
e
R3
R2
R1´1
R4´1
R4´1
R2
C
B
R3
A
R1´1
e
R4
R2´1
R1
R3´1
A
A
R2´1
R3
R4
R1
R1´1
R4´1
R2
R3´1
e
C
B
B
B
R3´1
R4
R3
R4´1
R2
R1
R1´1
R2´1
C
e
A
C
C
R4´1
R2
R1´1
R3´1
R4
R2´1
R3
R1
B
A
e
3