Resumo Teoria de Grupos - Álgebra

Prévia do material em texto

D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
Algebra: highlights
Copyright c©2017 Eduardo Tengan & Se´rgio Tadao Martins
Learning Mathematics is not much different from learning a new language: it is a highly non-
linear and non-sequential process, relying much more on examples and everyday experiences
rather than on grammar and vocabulary lessons. But, alas, pedagogy aside, writing is linear,
and this summary (the first chapter of the Algebra trilogy of groups, rings, fields) is our attempt
to string together into some coherent narrative all topics in Group Theory we believe current
undergraduate Math students should be acquainted with. Throughout we emphasize its relations
with other subjects such as Linear Algebra, Geometry and Topology.
We would greatly appreciate receiving comments and corrections, be they grammatic/sspellling
errors, or other interesting examples or suggestions of better ways to present the material.
Groups
Basic definitions and properties
The following definition distills the “nice” properties of sets with a binary operation, such as
pQˆ, ¨q and pZ,`q.
Definition 1. A group pG, ¨q is a pair consisting of a set G and a binary operation, called
product,
GˆGÑ G
pa, bq ÞÑ a ¨ b,
which satisfies the following three axioms:
(i) (Associativity) For all a, b, c P G,
pa ¨ bq ¨ c “ a ¨ pb ¨ cq
(ii) (Existence of identity element) There exists an element e P G such that, for all a P G,
a ¨ e “ e ¨ a “ a
(iii) (Existence of inverse) Given a P G, there exists an element a´1 P G such that
a ¨ a´1 “ a´1 ¨ a “ e
If, in addition to the above three axioms, the group pG, ¨q also satisfies
(iv) (Commutativity) For all a, b P G,
a ¨ b “ b ¨ a
then pG, ¨q is called abelian1.
Associativity means that parentheses are not needed to indicate the precedence of operations.
For example, the sum in Z is associative, while the subtraction is not:
pa` bq ` c “ a` pb` cq for all a, b, c P Z
however pa´ bq ´ c ‰ a´ pb´ cq in general
Therefore in a group we can simply write x ¨ y ¨ z ¨ w ¨ x ¨ y instead of some hideous expression
ppx ¨ py ¨ zqq ¨ pw ¨ xqq ¨ y. Moreover associativity let us define powers of an element g P G: for an
integer n ą 0,
gn
def“ g ¨ g ¨ . . . ¨ gloooooomoooooon
n times
We also define g0 “ e and g´n “ pg´1qn for n ą 0.
The existence of inverse says that the usual “cancellation law” holds, but now we need be a
bit more careful, and pay attention to the side being canceled since the operation may not be
commutative. For example, the “left cancellation” a ¨x “ a ¨ y ùñ x “ y follows by multiplying
a ¨ x “ a ¨ y by a´1 on the left:
a ¨ x “ a ¨ y ùñ a´1 ¨ pa ¨ xq “ a´1 ¨ pa ¨ yq
ðñ pa´1 ¨ aq ¨ x “ pa´1 ¨ aq ¨ y (associativity)
ðñ e ¨ x “ e ¨ y ðñ x “ y pe is the identity element)
See lemma 7 for other “basic moves” which hold in any group.
Example 2. In the following table, n P N and X ‰ H is a set.
Name Set Product Identity Inverse of g Abelian?
Trivial
group
teu e ¨ e “ e e e´1 “ e yes
Integers Z ` 0 ´g yes
Nonzero
rationals
Qˆ def“ Q r t0u ¨ 1 g´1 “ 1g yes
Even/Odd teven, oddu ` even g yes
Rn Rn vector sum`
zero vector
p0, . . . , 0q
opposite vector
´g yes
Integers
mod 12
Z{12Z def“
t0, 1, 2, . . . , 11u
sum mod
12
0
´a “ 12´ a if
a ‰ 0, and
´0 “ 0
yes
General
linear
group
nˆ n real
invertible
matrices
matrix
product ¨
identity
matrix In
inverse matrix
g´1
no if
n ě 2
Symmetric
group
bijections
g : X ãÑÑ X
composi-
tion of
functions ˝
identity
function id
inverse
function g´1
no if
|X| ě 3
Some brief remarks on the above examples:
• The first example, the so-called trivial group, is the smallest group in the whole universe
(the empty set has no group structure: any group has at least the identity element);
• The sum mod 12 is the sum in a 12-hour clock: denoting the twelve hours by the symbols
0, 1, 2, . . . , 11 we have for instance 4` 11 “ 3 as 4` 11 “ 15 corresponds to 3 o’clock.
We can easily generalize this example to any positive integer n. Define the set
Z{nZ def“ t0, 1, 2, . . . , n´ 1u
whose elements are symbols r, one for each integer 0 ď r ă n, standing for the “hours”
on an n-hour clock. The sum mod n is then defined as follows:
a` b def“
#
a` b if a` b ă n
a` b´ n if a` b ě n
For example, if n “ 5 we get the following “clock” and corresponding addition table (the
entry in the a-th row and b-th column is a` b):
1after the Norwegian mathematician Niels Henrik Abel (1802–1829), after whom the prestigious Abel prize is also named.
D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
` 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
0
1
23
4
It is easy to see that 0 is the identity element of pZ{nZ,`q (thus 0 is its own inverse),
and that n´ a is the inverse of a for a “ 1, 2, . . . , n´ 1. Associativity in Z{nZ is slightly
more difficult to check directly: the idea is to interpret the symbol a as “the remain-
der in the division of a by n” (in the sum mod n, we subtract multiples of n in order
to obtain a number between 0 and n ´ 1). With this interpretation, we can check that
pa`bq`c “ a`pb`cq since both sides represent the remainder in the division of a`b`c
by n.
Later, in the section Quotients (see in particular the example 141), we will see that the
group structure of pZ{nZ,`q is induced from that of pZ,`q. We will extend the interpre-
tation of a as the remainder in the division of a by n to all integers a P Z, so that
a “ b ðñ a, b leave the same remainder in the division by n
ðñ n | a´ b pn divides a´ bq
Not only will this make it easier to check the group axioms, but it will also allow us to
define the sum in Z{nZ more succinctly, via the mnemonic relation
a` b def“ a` b
For example, in Z{5Z
12 “ 2 “ ´3 and 3` 4 “ 3` 4 “ 7 “ 2
• The last but one group is called general linear group (notation: GLnpRq). All group
axioms are easy to check, perhaps the least obvious being the associativity: let A “
paijq1ďi,jďn, B “ pbijq1ďi,jďn and C “ pcijq1ďi,jďn be three elements in GLnpRq.
To show the associativity, all we have to check is that the pi, jq-th entry in the products
ApBCq and pABqC are the same, which in fact happens:
ÿ
1ďrďn
air ¨
pr,jq-th entry in BChkkkkkkkkkikkkkkkkkkj´ ÿ
1ďsďn
brscsj
¯
looooooooooooooooooomooooooooooooooooooon
pi,jq-th entry in ApBCq
“ ÿ
1ďr,sďn
airbrscsj “
ÿ
1ďsďn
pi,sq-th entry in ABhkkkkkkkkkikkkkkkkkkj´ ÿ
1ďrďn
airbrs
¯
¨csjlooooooooooooooooooomooooooooooooooooooon
pi,jq-th entry in pABqC
• The last group is called the symmetric group of X (notation SX). Again, only associa-
tivity can raise some doubt, but we only need to stare at the commutative diagram
X X X Xh
g˝h
g
f˝g
f
for a few seconds to be convinced that f ˝ pg ˝ hq “ pf ˝ gq ˝ h as both sides represent the
same function x ÞÑ fpgphpxqqq, obtained by successively applying the arrows h, g, f in
that order.
See the section Groups that appear in Nature for more examples and details.
Remark 3. • Due to laziness, a ¨ b is usually written ab.
• In the definition of a group, the identity and inverse elements in axioms (ii) and (iii) are
unique (see lemma 7).
• One frequently writes 1 instead of e to denote the identity element of a group. It is also
common to denote the trivial group t1u simply by 1.
• In case the binary operation is clear from the context, we refer to the set G itself as a
group. Thus we will often say that Z is a group, leaving the operation ` implicit.
• For abelian groups, one usually employs additive instead of multiplicative notation: one
writes ` for the binary operation, 0 for the identity element and ´g for the inverse of
g. In this additive notation, powers of an element g are written as multiples ng (n P Z)
thereof.
From twoor more groups, it is possible to build new groups:
Definition 4. Let Gi (i P I) be any family of groups. We may define a (group) product in the
Cartesian product
G “ź
iPI
Gi
by componentwise multiplication, using the products in each Gi: given two “vectors” paiqiPI and
pbiqiPI in G, set
paiqiPI ¨ pbiqiPI def“ pai ¨ biqiPI
The set G together with this product is a group, called the direct product of the Gi. The identity
element of G is the “vector” peiqiPI whose components are the identity elements ei of each Gi;
the inverse of paiqiPI is given by pa´1i qiPI .
Example 5. We keep the notation of the example 2.
• pRn,`q is the direct product of n copies of pR,`q.
• The addition table of Z{2Z ˆ Z{3Z is given below. Note that there now are two types of
elements, denoted by the same symbol n, but belonging to different groups: the red ones in
Z{2Z “ t0, 1u, where the sum is carried out mod 2 (i.e., Z{2Z is essentially the even/odd
group), and the blue ones in Z{3Z “ t0, 1, 2u, where the sum carried out mod 3 (i.e., the
sum is that of a 3-hour clock).
` p0, 0q p1, 0q p0, 1q p1, 1q p0, 2q p1, 2q
p0, 0q p0, 0q p1, 0q p0, 1q p1, 1q p0, 2q p1, 2q
p1, 0q p1, 0q p0, 0q p1, 1q p0, 1q p1, 2q p0, 2q
p0, 1q p0, 1q p1, 1q p0, 2q p1, 2q p0, 0q p1, 0q
p1, 1q p1, 1q p0, 1q p1, 2q p0, 2q p1, 0q p0, 0q
p0, 2q p0, 2q p1, 2q p0, 0q p1, 0q p0, 1q p1, 1q
p1, 2q p1, 2q p0, 2q p1, 0q p0, 0q p1, 1q p0, 1q
• If each group in the family Gi (i P I) is abelian, the direct product śiPI Gi is also abelian.
Remark 6. Although less frequently used in practice, there are other algebraic structures which
are more general than a group. A pair pG, ¨q given by a set G and a binary operation ¨ : GˆGÑ G
is a
(i) semigroup if the operation ¨ is associative.
(ii) monoid if ¨ is associative and has identity element.
Thus
pG, ¨q group ùñ pG, ¨q monoid ùñ pG, ¨q semigroup
That is, in the universe of mathematical objects we have
D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
groups
monoids
semigroups
Elementary Properties
From the group axioms, it is easy to check that the “usual arithmetic properties” hold in a general
group:
Lemma 7 (Basic moves). Let G be a group, and g, x, y P G be any elements.
(i) (Uniqueness of the identity element) There is a unique element e P G such that e ¨ g “
g ¨ e “ g for all g P G;
(ii) (Uniqueness of the inverse of an element) Given g P G, there exists a single element
g´1 P G such that g ¨ g´1 “ g´1 ¨ g “ e;
(iii) (Left/Right cancellation)
gx “ gy ùñ x “ y and xg “ yg ùñ x “ y
(iv) (Mirror rule) pxyq´1 “ y´1x´1.
(v) (Telescopic product) pgxg´1qn “ gxng´1 for all n P Z.
(vi) gm ¨ gn “ gm`n and pgmqn “ gmn for all m,n P Z.
Proof. We do not want to waste too much time here, since verifications of this kind are like house
chores: they have to be done but definitely are not the main purpose of life (let alone Algebra!).
As an example, we will prove only (ii), leaving the rest as an exercise2.
Given g P G, let h and h1 be two inverses for g; let us show that h “ h1. We have
h
p1q“ e ¨ h p2q“ ph1gq ¨ h p3q“ h1 ¨ pghq p4q“ h1 ¨ e p5q“ h1
Here equalities (1) and (5) follow from the fact that e is the identity of G; (2) and (4), from the
fact that h1 and h are inverses of g; and (3), from associativity.

Remark 8. For an arbitrary group G, pa¨bqn ‰ an ¨bn (a, b P G, n P Z) in general; for exam-
ple, if n “ 2 then pabq2 “ abab is usually different from a2b2 “ aabb. However pa ¨ bqn “ an ¨ bn
does hold if G is abelian.
Let us see how to use the above properties to solve problems about groups.
Example 9. In a group G, an element g P G satisfies g5 “ e; g7 “ e. Show that g “ e.
Solution The trick is to write 1 as a Z-linear combination of 5 and 7, for example 7 ¨3´5 ¨4 “ 1.
Then
g “ g7¨3´5¨4 “ pg7q3 ¨ pg5q´4 “ e3 ¨ e´4 “ e
Similarly one shows that if gn “ gm “ e with gcdpm,nq “ 1 then g “ e (see lemma 27, which
shows that if gcdpm,nq “ 1 then there exist x, y P Z such that mx` ny “ 1).
Example 10. In a group G, a “ a´1 holds for all a P G. Show that G is necessarily abelian.3
Proof. Given x, y P G, we want to show that xy “ yx. We have
xy
p1q“ pxyq´1 p2q“ y´1x´1 p3q“ yx
Here, we used the hypothesis a “ a´1 for a “ xy in (1), the mirror rule in (2), and the hypothesis
a “ a´1 in (3) once more, this time for a “ y, a “ x.
Translations and “shuffle”
Despite its innocuous appearance, the following lemma is often used to explore the “inner sym-
metry” of a group.
Lemma 11 (Shuffle). Let G be a group, and let g P G. The following functions are
bijections:
λg : G ãÑÑ G pleft translation by gq
x ÞÑ gx
and
ρg : G ãÑÑ G pright translation by gq
x ÞÑ xg
Proof. It is easy to check directly that λg´1 (left translation by g
´1) is the inverse of λg ; simi-
larly, ρg´1 is the inverse of ρg .
Example 12 (Abelian Lagrange). Let G be a finite abelian group with n “ |G| elements.
Then gn “ e for all g P G.
Solution Let G “ tx1, x2, . . . , xnu (with g “ xi for some 1 ď i ď n). Since λg : G ãÑÑ G is a
bijection, and G is abelian,
λgpx1q ¨ λgpx2q ¨ . . . ¨ λgpxnq “ x1 ¨ x2 ¨ . . . ¨ xn
as the factors on the left and on the right are the same up to permutation. Rewriting the left
hand side using the definition of λg , and rearranging the order of the factors, we get
gx1 ¨ . . . ¨ gxn “ x1 ¨ . . . ¨ xn ðñ gnx1 ¨ . . . ¨ xn “ x1 ¨ . . . ¨ xn
ðñ gn “ e (cancellation)
Later (corollary 53) we will see that the above result holds for all finite groups, abelian or not.
2like a chore indeed: do one of them and sweep the rest under the rug/reader
3For example G can be the even/odd group or a direct product of copies thereof.
D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
Conjugation
Definition 13. Given a group pG, ¨q and an element g P G, the function
κg : GÑ G
x ÞÑ gxg´1
is called conjugation by g. We say that κgpxq “ gxg´1 is the conjugate of x by g.
Two important identities are given by the
Lemma 14 (Conjugate identities). Let G be a group, and let g, h P G. For all x, y P G,
κgpx ¨ yq “ κgpxq ¨ κgpyq (1)
κh
`
κgpxq˘ “ κhgpxq (2)
Proof. The identities follow directly from gxyg´1 “ pgxg´1q ¨ pgyg´1q and hpgxg´1qh´1 “
phgqxphgq´1 (using the mirror rule).
Identity (1) says that conjugation by g preserves the product in G (i.e., κg : GÑ G is a morphism,
see definition 58). In particular, κgpxnq “ `κgpxq˘n for n P N, that is, gxng´1 “ pgxg´1qn, which
is nothing other than the telescopic product of lemma 7.
Remark 15. Some authors denote κgpxq by gx, so that identity (2) can be rewritten as the
more friendly “rule of the exponent” hpgxq “ hgx. But this is very cumbersome to type (except
perhaps on an Arabic or Hebrew keyboard), so we will continue to use κg to denote conjugation
by g.
Example 16. In a group G, a, b P G satisfy a3 “ e, aba´1 “ b2. Show that b7 “ e.
Solution The natural idea is to explore conjugation: aba´1 “ b2 says that conjugating b by
a we obtain b2, i.e., κapbq “ b2. Conjugating the last equality by a, and using the conjugate
identities (1) and (2), we get
κapbq “ b2 ùñ κapκapbqq “ κapb2q ðñ κa2 pbq “
`
κapbq˘2
ðñ κa2 pbq “
`
b2
˘2 ðñ a2ba´2 “ b4
That is, by conjugating b by a2 we get b4. We may repeat the above steps, conjugating
a2ba´2 “ b4 by a:
a3ba´3 “ ab4a´1
“ paba´1q4 ptelescopic productq
“ pb2q4 “ b8 psince κapbq “ b2q
That is, conjugating b by a3 we obtain b8: a3ba´3 “ b8. But by hypothesis a3 “ e, therefore
b “ b8; canceling b, we get e “ b7.
Subgroups
Intuitively speaking, given a group G, a subgroup H of G is a subset that is a group with the
same operation of G. Formally:
Definition 17. Given a group pG, ¨q, a subset H Ď G is a subgroup of G (notation: H ď G) if
it satisfies:
(i) H ‰ H;
(ii) H is closed under taking products: a, b P H ùñ a ¨ b P H; and
(iii) H is closed under taking inverses:a P H ùñ a´1 P H.
Note that the subset H does deserve the name “subgroup” since by (ii) the operation ¨ of G
restricts to a binary operation ¨ : H ˆH Ñ H, and makes the pair pH, ¨q into a bona fide group:
• Associativity: is inherited from G;
• Existence of identity element: e P H; indeed, there exists a P H by (i), hence a´1 P H by
(iii), and therefore by (ii) e “ a ¨ a´1 belongs to H;
• Existence of inverse: follows from (iii).
Example 18. We keep the notation of the example 2.
• we have the inclusions of additive groups Z ď Q ď R ď C.
• t˘1u ď Qˆ and t˘1,˘iu ď Cˆ (here Cˆ “ C r t0u with the usual product).
• The subset 2Z of Z consisting of all even numbers is a subgroup of Z; more generally,
for all d P Z, the subset dZ consisting of all multiples of d is a subgroup of Z: dZ ď Z.
Conversely, example 23 shows that any subgroup of pZ,`q has this form.
• The set of integral powers of 2
2Z def“ t2n | n P Zu “
!
. . . ,
1
8
,
1
4
,
1
2
, 1, 2, 4, 8, . . .
)
is a subgroup of Qˆ.
• If V is a vector subspace of Rn, then V ď Rn.
• The subset of GL2pRq given by
UT2pRq def“
"ˆ
1 ˚
0 1
˙
P GL2pRq
*
is an abelian subgroup of GL2pRq. Here, ˚ denotes an arbitrary element of R.
• The set of rotation matrices
SO2pRq def“
"ˆ
cos θ ´ sin θ
sin θ cos θ
˙ ˇˇˇ
θ P R
*
is a subgroup of GL2pRq, called special orthogonal group (see example 98 for the geo-
metric meaning of SO2pRq).
• The set of matrices
SU2pCq def“
"ˆ
α ´β
β α
˙ ˇˇˇ
α, β P C, |α|2 ` |β|2 “ 1
*
is a subgroup of the multiplicative group GL2pCq (2ˆ2 complex invertible matrices). The
group SU2pCq is called special unitary group (see example 100 for more details).
Example 19 (Unit circle). The set of complex numbers with absolute value 1
S1
def“ tz P C | |z| “ 1u “ teiθ P C | θ P Ru
forms a subgroup of pCˆ, ¨q. Geometrically, this group is a circle of radius 1 centered at the
origin.
z “ eiα “ cosα` i sinα
z´1 “ z “ e´iα “ cosα´ i sinα
α
´α
D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
Writing z, w P S1 in polar form
z “ eiα “ cosα` i sinα and w “ eiβ “ cosβ ` i sinβ
we note that, in order to multiply z and w, all we need to do is add their arguments α and β:
zw “ eipα`βq “ cospα` βq ` i sinpα` βq
Observe that if z P S1 then z´1 “ z (complex conjugation) since zz “ |z|2 “ 1. Hence the
operation z ÞÑ z´1 is a reflection about the real axis.
Example 20 (Quaternion Group). The quaternion group Q8 is the subgroup of the multi-
plicative group GL2pCq (or SU2pCq, see example 18) composed of the 8 matrices
Q8
def“
"
˘
ˆ
1 0
0 1
˙
,˘
ˆ
i 0
0 ´i
˙
,˘
ˆ
0 1
´1 0
˙
,˘
ˆ
0 i
i 0
˙*
ď GL2pCq
We usually write 1 as a shorthand for the identity matrix, and
i
def“
ˆ
i 0
0 ´i
˙
j
def“
ˆ
0 1
´1 0
˙
k
def“
ˆ
0 i
i 0
˙
so that Q8 “ t˘1,˘i,˘j,˘ku. The following relations hold:
i2 “ j2 “ k2 “ ´1 ij “ ´ji “ k
jk “ ´kj “ i ki “ ´ik “ j
One way to remember them is to think of i, j, k as “imaginary units” (such as i P C) that
“anti-commute” and satisfy a “cyclic multiplication table”
i
j
k
This group originates from the unit group of the quaternion ring H.
Example 21. Let pG, ¨q be any group.
• teu ď G and G ď G.
• If G is abelian and H ď G then H is abelian.
• If Hi ď G pi P Iq is any family of subgroups of G thenč
iPI
Hi ď G
Example 22 (Center of a group). Given any group G, the subset
ZpGq def“ tz P G | gz “ zg for all g P Gu
consisting of the elements commuting with all elements of G is a subgroup of G, called center
of G (the notation ZpGq stems from the German word Zentrum). Note that ZpGq “ G if and
only if G is abelian.
Example 23 (Subgroups of Z). We have already seen (example 18) that, given an integer
d ě 0, dZ ď Z. Conversely, every H ď Z has this form. If H is trivial, then H “ dZ with
d “ 0. Otherwise, H has a positive integer: since H is nontrivial, there is an h ‰ 0 in H; but
then h P H and ´h P H, and one of them will be positive. Let d ą 0 be the smallest positive
integer in H; we claim that H “ dZ.
In fact, since H is closed under sums and opposites, dZ Ď H; for the other inclusion, we must
show that any h P H is divisible by d, so nothing more natural than to divide h by d, for heaven’s
sake! We get quotient q and remainder r with 0 ď r ă d so that
h “ dq ` r ðñ r “ h´ dq P H (since h P H and dZ Ď H)
Since d is the smallest positive integer in H, from 0 ď r ă d and r P H we conclude that r “ 0,
as required.
Example 24 (Putnam). Let G be a finite subgroup of the linear group GLnpCq (see example 2).
Let M be the sum of all matrices in G. Show that detM P Z.
Solution Let G “ tA1, . . . , Atu, so that M “ A1 ` ¨ ¨ ¨ ` At. Let us use the shuffle lemma 11.
Taking the square of M ,
M2 “ pA1 `A2 ` ¨ ¨ ¨ `Atq ¨ pA1 `A2 ` ¨ ¨ ¨ `Atq
“ A1 ¨ pA1 `A2 ` ¨ ¨ ¨ `Atq ` ¨ ¨ ¨ `At ¨ pA1 `A2 ` ¨ ¨ ¨ `Atq
shuffle“ pA1 `A2 ` ¨ ¨ ¨ `Atq ` ¨ ¨ ¨ ` pA1 `A2 ` ¨ ¨ ¨ `Atq
“ t ¨M
And from M2 “ t ¨M we get pdetMq2 “ tn ¨ detM ùñ detM “ 0 or detM “ tn with t “ |G|.
Thus in both cases detM P Z, as wished.
Definition 25. Let G be a group, and S Ď G be any subset. The subgroup generated by S
(notation: xSy) is the smallest subgroup of G containing S, that is, xSy is the intersection of all
subgroups containing S (see example 21):
xSy def“ č
HďG
HĚS
H
For typographical reasons (and also laziness), in case S “ tg1, . . . , gnu is finite we write
xg1, . . . , gny instead of the uglier notation xtg1, . . . , gnuy.
Explicitly, xSy is the subgroup consisting of all (finite, of course) products x1x2 . . . xn where each
xi is either an element of S or the inverse of an element of S (we will write xi P S˘):
xSy “ x1x2 . . . xn ˇˇ xi P S˘, n P N(
To see this, call the set on the right P . Note first that if H ď G and H Ě S then H Ě P , since
H is closed under products and inverses. Thus, in order to check that xSy “ P , it suffices to
show that P ď G, since then P will be the smallest subgroup of G containing S. In fact, P ‰ H
(e P P even when S “ H, remember that the empty product is equal to e by definition); P is
clearly closed under products; it is also closed under inverses by the mirror rule:
px1x2 . . . xnq´1 “ x´1n . . . x´12 x´11 P S pxi P S˘q
In particular, if G is abelian, given g1, . . . , gr then
xg1, . . . , gry “ gZ1 . . . gZr def“ tgn11 . . . gnrn | ni P Zu
Example 26. The subgroup of the multiplicative group Qˆ generated by 2 and 3 is the subgroup
consisting of fractions whose numerators and denominators have no prime factors other than 2
and 3:
x2, 3y “ 2Z ¨ 3Z “ t2m ¨ 3n | m,n P Zu
Example 27 (Be´zout). Let a, b P Z, and let d “ gcdpa, bq (when a “ b “ 0 we set d “ 0). In
pZ,`q,
xa, by “ Za` Zb “ Zd “ xdy
In fact, from example 23 we know that xa, by “ xty for some integer t ě 0. To conclude that
t “ d, all we need to show is that (for a ‰ 0 or b ‰ 0)
• d | t: from t P xa, by there are x, y P Z such that
ax` by “ t
Since d “ gcdpa, bq divides the left side, d divides the right side as well.
D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
• t ď d: from a, b P xty ðñ t | a and t | b, we have that t is a common divisor of a, b,
thus t ď d.
More generally, given a1, . . . , an P Z, the same proof shows that
xa1, . . . , any “ xgcdpa1, . . . , anqy
Example 28. The subgroup of pR2,`q generated by the vectors p1, 0q and p0, 1q is the set of all
Z-linear combinations of these vectors, that is,
Z2 “ Z ¨ p1, 0q ` Z ¨ p0, 1q “ tpa, bq P R2 | a, b P Zu
Geometrically, Z2 is a lattice in R2:
Example 29 (Derived subgroup). Let G be a group. The commutator of a, b P G is the
element
ra, bs def“ aba´1b´1 P G
Intuitively, ra, bs “measures” the lack of commutativity between a, b; the element ra, bs is trivial
if and only if a, b commute:
ra, bs “ e ðñ ab “ ba
The commutatorsubgroup or derived subgroup of G (notation: rG,Gs or G1) is the subgroup
of G generated by its commutators. Note that since the inverse of a commutator is a commutator
(by the mirror rule, ra, bs´1 “ paba´1b´1q´1 “ bab´1a´1 “ rb, as), G1 consists of all products
of commutators:
rG,Gs “ G1 “ ra1, b1s . . . ran, bns ˇˇ ai, bi P G,n P N (
Note that G is abelian if and only if rG,Gs is trivial.
Later, we will use the derived subgroup to construct the abelianization Gab
def“ G{rG,Gs of G
(see example 161), which, in a sense, is the “largest” abelian group that can be obtained from
G.
Order and cyclic groups
Definition 30. A group G is called cyclic if it can be generated by a single element g P G:
G “ xgy “ gZ def“ tgn | n P Zu
(in general, there are several generators g, see theorem 39).
More generally, given any group G, the subgroup xgy ď G is called the cyclic subgroup generated
by g.
Since any two powers of g commute, the cyclic subgroup xgy is always abelian, even when the
group G itself is not. In particular, cyclic groups are always abelian.
Lemma 31. Let G be a group, and g P G. Then
|xgy| “ mintd P N | gd “ e, d ą 0u
Proof. It suffices to show that
(i) if gd “ e for some integer d ą 0 then |xgy| ď d;
(ii) if |xgy| ă 8 then there exists d P N such that 0 ă d ď |xgy| and gd “ e.
In fact, if we let t “ mintd P N | gd “ e, d ą 0u, (i) shows that |xgy| ď t while (ii) shows that
|xgy| ě t. Note that these inequalities hold even if one of the terms is infinite: if |xgy| “ 8, (i)
shows that gd ‰ e for all d ą 0, that is, t “ 8. Similarly if gd ‰ e for every integer d ą 0, (ii)
shows that |xgy| “ 8.
We now turn to the proofs of (i) and (ii).
(i) Suppose that gd “ e with d ą 0. Then the powers of g “cycle4 after d steps”, as in the
d-gon below, where each vertex is multiplied by g (respectively by g´1) as we go clockwise
(respectively counterclockwise):
e “ gkd
g “ gkd`1
g2 “ gkd`2
g3 “ gkd`3
g4 “ gkd`4
gd´2 “ gkd`pd´2q
gd´1 “ gkd`pd´1q
(k P Z)
Thus xgy “ gZ “ te, g, g2, . . . , gd´1u has at most d elements (exactly d if e, g, . . . , gd´1 are
pairwise distinct).
(ii) If t
def“ |xgy| is finite then the t` 1 powers of g
e, g, g2, . . . , gt P xgy
cannot be all distinct, so there are integers i, j with 0 ď i ă j ď t such that
gi “ gj ðñ gj´i “ e. Therefore d “ j ´ i satisfies 0 ă d ď t and gd “ e.
The previous lemma allows us to make the following
Definition 32. Let G be a group, and let g P G.
(i) The order |G| of G is the cardinality of G (i.e., the number of elements in G).
(ii) The order of an element g P G is the order of the cyclic subgroup xgy. Equivalently, the
order of g is the smallest integer d ą 0 such that gd “ e (or infinity if such d does not
exist).
Items (i) and (ii) in the proof of the above lemma show that the powers of g cycle with period
exactly equal to its order. Thus we immediately get the following
Lemma 33 (Least divides). Let G be a group, and g P G be an element of finite order
d ą 0. Then
gn “ e ðñ d | n pn P Zq
Example 34. We keep the notation of example 2.
• If |X| “ n, the elements of the symmetric group SX are the permutations of the n ele-
ments in X, so its order is |SX | “ n!.
• Z is an infinite cyclic group: Z “ x1y or Z “ x´1y.
4whence the name cyclic group
D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
• The even/odd group is cyclic of order 2, generated by the element odd.
• In Qˆ, ´1 has order 2 since x´1y “ p´1qZ “ t˘1u. On the other hand, the element 5
has infinite order.
• In the multiplicative group Cˆ, i has order 4 as xiy “ iZ “ t˘1,˘iu.
• The quaternion group Q8 (example 20) has order 8. Its elements have orders
element 1 ´1 ˘i ˘j ˘k
order 1 2 4 4 4
Since no element has order 8, Q8 is not cyclic (which also follows from the fact that Q8
is not abelian).
• For |X| ě 3, the symmetric group SX is not abelian and thus not cyclic.
• The group Qˆ is not cyclic: given a, b P Z with a, b ‰ 0, xa{by ‰ Qˆ since xa{by has no
integer that is coprime to a and b.
Example 35. The “clock group” Z{12Z is cyclic of order 12, generated by 1 (for instance). In
additive notation, the powers of 1 are the multiples of 1, which form the cycle on the left in the
picture. There are other generators of this group, for instance, Z{12Z “ x5y: in other words,
“jumping in steps of 5 hours”, we cover the whole the clock with the powers (i.e. multiples) of
5, as shown on the right.
0
1
2
3
4
5
6
7
8
9
10
11
0
5 ¨ 5
10 ¨ 5
3 ¨ 5
8 ¨ 5
1 ¨ 5
6 ¨ 511 ¨ 5
4 ¨ 5
9 ¨ 5
2 ¨ 5
7 ¨ 5
In the following table, we have listed the orders of all elements in Z{12Z. For example, the order
of 3 is 4 since x3y “ t0, 3, 6, 9u, whose elements are the vertices of a square inscribed in the
“dodecagon” Z{12Z. In other words, the order of 3 is 4 since “jumping in steps of 3 hours” we
cycle after 4 jumps. Similarly 8 has order 3 since the elements of the subgroup x8y “ t0, 4, 8u
form a triangle; “jumping every 8 hours” we cycle after 3 jumps.
element 0 1 2 3 4 5 6 7 8 9 10 11
order 1 12 6 4 3 12 2 12 3 4 6 12
0
1
2
3
4
5
6
7
8
9
10
11
0
1
2
3
4
5
6
7
8
9
10
11
From the table, the orders of the elements are all divisors of the order of the group. We shall see
that this is always true for all finite groups by Lagrange’s theorem (corollary 53). We also see
that Z{12Z has 4 generators (the elements of order 12: 1, 5, 7, 11). Note that these are exactly
the numbers that are relatively prime to 12 in this list. See the theorem 39 for the general case.
Example 36. Let G be a group, and let a, b P G be two commuting elements: ab “ ba. Suppose
that a, b have finite orders m, n such that gcdpm,nq “ 1. Then ab has order mn.
In fact, letting t be the order of ab, it suffices to show that t | mn and mn | t.
• t | mn: by the “least divides” (lemma 33), we have to check that pabqmn “ e; since a, b
commute,
pabqmn “ amnbmn “ pamqnpbnqm “ en ¨ em “ e
• mn | t: as gcdpm,nq “ 1, it suffices to show that m | t and n | t. To show the latter
for instance, the idea is to raise pabqt “ e to the m-th power in order to “kill” a. Since
ab “ ba,
pabqt “ e ùñ pabqtm “ e ðñ pamqtbtm “ e ðñ btm “ e ùñ n | tm
where the last implication follows from the “least divides” applied to b. As gcdpm,nq “ 1,
n | tm ùñ n | t. Similarly, from pabqtn “ e we get m | t.
Definition 37 (Euler Totient Function ϕ). Let n be a positive integer. We define ϕpnq as
number of integers between 1 and n that are coprime to n:
ϕpnq def“ ˇˇtk P N | 1 ď k ď n and gcdpk, nq “ 1uˇˇ
For example, ϕp12q “ 4 because there are 4 integers coprime to 12 between 1 and 12: 1, 5,
7, 11, as in the last example. The next lemma gives a formula for ϕpnq in terms of the prime
factorization of n. For example, ϕp100q “ 100p1´ 1
2
qp1´ 1
5
q “ 40.
Lemma 38. Let n be a positive integer. Then
ϕpnq “ n ¨ ź
p|n
p prime
ˆ
1´ 1
p
˙
Proof. The result follows once we compute, in two different ways, the probability P of an integer
k with 1 ď k ď n being coprime to n. On the one hand, P “ ϕpnq{n. On the other, gcdpk, nq “ 1
if and only if p - k for all primes p | n. Since these independent events are to hold simultaneously,
P equals the product of the probabilities of p - k as p runs through the prime divisors of n. For
a given prime p | n, the probability of p | k is 1
p
, and the probability of p - k is p1 ´ 1
p
q, so
P “ ś
p|n
p prime
´
1´ 1
p
¯
.
Theorem 39 (Cyclic generators). Let G be a finite cyclic group of order n, generated
by g P G:
G “ xgy “ te, g, g2, . . . , gn´1u
Then for k P Z
order of gk “ n
mdcpn, kq
In particular, G “ xgky (i.e., the order of gk is n) if and only if k is coprime to n.
Hence G has ϕpnq generators.
Proof. Let d be the order of gk. “Peeling off”the greatest common factor gcdpn, kq of n and k,
we may write
n “ n0 ¨ gcdpn, kq k “ k0 ¨ gcdpn, kq
for integers n0 and k0 with gcdpn0, k0q “ 1. Hence n ¨ k0 “ k ¨n0. We want to show that d “ n0.
Since both d and n0 are positive, it suffices to check that one number divides the other and vice
versa.
• d | n0: as the order of gk is d, by the “least divides” (lemma 33) all we have to check is
that pgkqn0 “ e, which follows from gn “ e and n ¨ k0 “ k ¨ n0: pgkqn0 “ pgnqk0 “ e.
D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
• n0 | d: we have pgkqd “ e; as g has order n, n | kd by the “least divides”. Canceling out
the common factor gcdpn, kq, and remembering that n0 and k0 are coprime, we get
n | kd ðñ n0 | k0d ðñ n0 | d
The next theorem characterizes all subgroups of a cyclic group G “ te, g, g2, . . . , gn´1u of order
n in terms of the positive divisors d of n. Geometrically, the subgroup Σpdq corresponding to
d | n is the “regular pn{dq-gon” Σpdq “ te, gd, g2d, . . . , gn´du inscribed in the “regular n-gon” G.
Theorem 40 (Subgroups of a cyclic group). Let G “ xgy “ te, g, g2, . . . , gn´1u be a cyclic
group of order n, generated by g. There is a bijection between the set of all positive divisors of
n and the set of all subgroups of G:
Σ: td P N | d | nu ãÑÑ tC | C ď Gu
d ÞÑ xgdy
In particular, any subgroup of G is cyclic, and for each d | n there is a single subgroup of G of
order d, namely,
xgn{dy “ te, gn{d, g2n{d, . . . , gpd´1qn{du
Proof. Let us define the inverse5 map Ξ of Σ:
Ξ: tC | C ď Gu Ñ td P N | d | nu
C ÞÑ least integer d ą 0 such that gd P C
(we “secretly” know that C is a “regular polygon inscribed in G”, and all that Ξ does is to
associate to C the “first vertex” different from e).
Let us check that Ξ is well defined. First, note that gn “ e P C, hence such a minimal d ą 0
with gd P C indeed exists, and d ď n. In addition, d is a divisor of n, as will follow from gn “ e
once we prove that d has the “least divides” property: if m P Z is such that gm P C then d | m.
In fact, we just copy the proof of example 23: let q and r be the quotient and remainder in the
division of m by d, so that m “ qd` r with 0 ď r ă d. Then gr “ gm ¨ pgdq´q P C, and by the
minimality of d, r “ 0.
Now let us check that
• Ξ ˝ Σ “ id: given d | n, let m “ n{d; then
Σpdq “ xgdy “ te, gd, g2d, . . . , gpm´1qdqu
is a cyclic subgroup of order m, and from this explicit description we clearly get
pΞ ˝ Σqpdq “ Ξpxgdyq “ d.
• Σ ˝Ξ “ id: given C ď G, let d “ ΞpCq. Then gm P C ðñ d | m: in fact, ð follows from
gd P C and the fact that C is closed under products and inverses; ñ is the “least divides”
property above. To sum up,
C “ tgdt | t P Zu “ xgdy “ Σpdq “ pΣ ˝ ΞqpCq
Later we shall see a different (shorter) proof of the above theorem as a consequence of the
correspondence theorem (see example 152).
Lemma 41. Let G be an abelian group, and n ě 1 be an integer. Then
Grns def“ tg P G | gn “ eu
Gtor
def“ tg P G | g has finite orderu “ ď
ně1
Grns
are subgroups of G, called the n-torsion subgroup and the torsion subgroup of G respectively.
Proof. Since e P Grns, Grns ‰ H. Besides, Grns is closed under inverses: if a P Grns, i.e., an “ e
then pa´1qn “ panq´1 “ e ùñ a´1 P Grns. Since G is abelian, pabqn “ anbn for all n P Z, and
thus Grns is closed under products: given a, b P Grns ðñ an “ bn “ e, pabqn “ anbn “ e.
As Gtor is the union of the subgroups Grns ď G, it is clear that Gtor ‰ H and that Gtor
is closed under inverses. If a, b P Gtor, say a P Grns and b P Grms, then ab P Grmns:
pabqmn “ amnbmn “ panqmpbmqn “ em ¨ en “ e, hence Gtor is closed under products as
well.
Example 42. The n-torsion subgroup of Cˆ is the order n subgroup consisting of all n-th roots
of unity:
Cˆrns “ te2kpii{n | k “ 0, 1, 2, . . . , n´ 1u “ xe2pii{ny ď S1
This is a cyclic subgroup of the group S1 (see example 19), generated by e2pii{n. Geometrically,
its elements are the vertices of a regular n-gon inscribed in the circle of radius 1 centered at the
origin. The case n “ 6 is depicted below, where ω “ e2pii{6.
1
ωω2
ω3
ω4 ω5
The torsion subgroup of Cˆ is the subgroup consisting of all roots of unity, and is an infinite
subgroup of S1:
pCˆqtor “ te2piir | r P Qu ď S1
Example 43. The hypothesis of G being abelian in the previous lemma is crucial. For instance,
the matrices
a “
ˆ
0 ´1
1 0
˙
and b “
ˆ
0 1
´1 ´1
˙
of GL2pRq satisfy a4 “ 1 and b3 “ 1, but ab has infinite order. In fact,
pabqn “
ˆ
1 n
0 1
˙
for all n P Z (this is an easy induction, “easy” meaning we don’t want to write it down).
5we must use fancy capital Greek letters here!
D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
Cosets and Lagrange’s theorem
Next we keep the notations of the shuffle lemma 11: λg : G ãÑÑ G and ρg : G ãÑÑ G will denote
the left and right translations by g P G, respectively.
Definition 44. Let G be a group, and H ď G be a subgroup. A left translation of H, i.e., a
subset of G of the form
λgpHq “ g ¨H “ tgh | h P Hu for some g P G
is called a left coset of H. Similarly, a right coset of H is a subset of G of the form
ρgpHq “ H ¨ g “ thg | h P Hu for some g P G
We will denote the sets of all left and right cosets of H respectively by
G{H def“ tg ¨H | g P Gu HzG def“ tH ¨ g | g P Gu
Note that if G is abelian, right cosets are left cosets and vice versa.

Remark 45. Cosets gH, Hg are just subsets of G, never subgroups, except when gH “ H
or Hg “ H, i.e., except when g P H, as we shall see below.
Example 46. Consider the abelian group G “ pR2,`q, and let H ď G be the subgroup given by
the diagonal
H
def“ tpx, xq P R2 | x P Ru
The left (or right) cosets of H are the lines which are parallel to this diagonal:
H
p´1, 1q `H
p´4,´2q `H
p1, 0q `H
Note that two distinct vectors in R2 may give rise to the same coset of H: for example,
p´1, 1q ` H “ p´4,´2q ` H. Such “redundancy” can easily be eliminated if we restrict the
set of translation vectors. For example, there is a bijection
R «Ñ G{H
a ÞÑ pa, 0q `H
whose inverse maps the line y “ x´c in G{H to c, the abscissa of its intersection point with the
x-axis. Thus there are as many cosets of H as there are elements in the group pR,`q. Later (in
the section Quotients) we shall see how to endow the set G{H with a group structure; with this
structure, the above bijection will give an isomorphism (see definition 64) between the additive
group R and G{H.
Example 47. Consider the subgroup 3Z of the additive group Z. There are exactly 3 (left or
right) cosets of 3Z in Z:
3Z “ t. . . ,´9,´6,´3, 0, 3, 6, 9, . . .u
1` 3Z “ t. . . ,´8,´5,´2, 1, 4, 7, 10, . . .u
2` 3Z “ t. . . ,´7,´4,´1, 2, 5, 8, 11, . . .u
There are no other translations, since for instance 3`3Z “ 3Z, 4`3Z “ 1`3Z, ´2`3Z “ 1`3Z,
and so on. Note that these cosets partition Z.
In general, given d P N, there are exactly d cosets of dZ in Z,
r ` dZ pr “ 0, 1, 2, . . . , d´ 1q,
one for each possible remainder r “ 0, 1, . . . , d ´ 1 in the division by d. Two translates a ` dZ
and b` dZ are equal if and only if a and b leave the same remainder when divided by d, i.e., if
and only if d | a´ b.
Example 48. Let Z{5Z be the additive group of mod 5 integers, and consider the product group
(see definition 4) G “ Z{5Zˆ Z{5Z, represented by the following 5ˆ 5 “chessboard”.
0
0
1
1
2
2
3
3
4
4
Since the coordinates “cycle with period 5”, the best way to picture this board is as a “planifi-
cation of a torus”: by “gluing” two opposing sides of the board, we first obtain a cylinder, then
by “gluing” the other two opposite sides (now circles), we finally get a torus. Since this is not
a topology book, we refrain from “cup of tea” and “doughnut” jokes.
Consider the “diagonal subgroup” (orange on the board)
H
def“ tpa, aq P G | a P Z{5ZuThe (left or right) cosets of H are the “lines on the torus parallel to H”, i.e., the lines y “ x` c
with c P Z{5Z (for example, the line with equation y “ x ` 4 is the green one on the board).
Therefore there is a bijection
Z{5Z «Ñ G{H
c ÞÑ p0, cq `H
Example 49. Consider the group pCˆ, ¨q, and let S1 ď Cˆ be the subgroup of all complex num-
bers of absolute value 1 (see example 19). The cosets of S1 are the circles centered at the origin.
There is a bijection
Rą0 «Ñ Cˆ{S1
r ÞÑ rS1
whose inverse maps a circle to its radius.
D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
Example 50. Consider the subgroup SLnpRq of GLnpRq consisting of matrices of determinant 1
(the so-called special linear group, see the definition 88 in the section Groups that appear in
Nature for more details):
SLnpRq def“ tA P GLnpRq | detA “ 1u
Let us give an explicit description of the left cosets of SLnpRq in GLnpRq in terms of the deter-
minant. Given r P Rˆ and a matrix A P GLnpRq with detA “ r, we claim that
A ¨ SLnpRq “ tB P GLnpRq | detB “ ru p˚q
The inclusion Ď is clear by the multiplicativity of the determinant; for the opposite inclusion,
note that if detB “ r ‰ 0 then
detpA´1Bq “ detpAq´1 detpBq “ 1 ùñ A´1B P SLnpRq ðñ B P A ¨ SLnpRq
In particular, p˚q shows that there is a bijection, induced by the determinant, between the set of
left cosets of SLnpRq and Rˆ:
GLnpRq{SLnpRq «Ñ Rˆ
A ¨ SLnpRq ÞÑ detA
In general, how to identify if two translates are the same? The answer is given by the following
Lemma 51. Let G be a group, and let H ď G.
(i) (Absorption) If h P H then h ¨H “ H “ H ¨ h (the group H “absorbs” the element h).
(ii) We have g1H “ g2H ðñ g1 “ g2h for some h P H. Similarly, Hg1 “ Hg2 ðñ g1 “
hg2 for some h P H.
Proof. We will only consider left cosets.
(i) Just use the shuffle lemma 11: the left translation λh : H ãÑÑ H is a bijection, in particular
it is surjective and therefore h ¨H “ λhpHq “ H.
(ii) (ñ) Since g1 “ g1 ¨ e P g1H “ g2H, there is h P H such that g1 “ g2h.
(ð) By absorption, g1 “ g2h with h P H implies g1H “ g2hH “ g2H.
From now on, we will state results only for left cosets; the results for right cosets are analogous.
The main theorem of this section is
Theorem 52 (Lagrange). Let G be a group, and let H ď G be a subgroup. Then the
left cosets of H equipartition G, i.e.,
(i) The left cosets of H form a partition of G.
(ii) All left cosets of H have the same cardinality.
In particular, if G is finite then |G| is a multiple of |H|. More precisely, |G| “ d ¨ |H|
with d “ |G{H|:
g1H g2H g3H ¨ ¨ ¨ gdH
Proof. (i) Saying that the left cosets form a partition of G amounts to saying that:
(a) G “ ŤgPG gH, that is, the left cosets cover the whole group G, or every element g P G
belongs to some left coset ; and
(b) given g1, g2 P G, either g1 ¨ H “ g2 ¨ H or g1 ¨ H X g2 ¨ H “ H, that is, there are no
“partial intersections” as in the picture below:
‚ x “ g1h1
“ g2h2
g1H g2H
Now that the goal is clear, we can begin the proof. Item (a) is easy: g P G belongs to gH
since g “ g ¨ e P g ¨ H. To show (b), suppose that g1 ¨ H X g2 ¨ H ‰ H; we must show
that g1 ¨ H “ g2 ¨ H. Take any element x P g1 ¨ H X g2 ¨ H, and write x “ g1h1 “ g2h2
(h1, h2 P H). Then g1 “ g2h2h´11 and by “absorption” (lemma 51)
g1H “ g2h2h´11 H “ g2H
(ii) By the shuffle lemma 11, left translation by g2g
´1
1 restricts to a bijection
λ
g2g
´1
1
: g1H
«ÝÑ g2H
x ÞÝÑ g2g´11 x
between the two cosets g1H and g2H.
Corollary 53 (also called “Lagrange”). Let G be a finite group. Then the order of
any element g P G divides n “ |G|. In particular, for all g P G, we have gn “ e.
Proof. Consider the cyclic subgroup H “ xgy, and let d “ |H| be the order of g. By Lagrange’s
theorem 52 applied to H, d | n. Thus n{d P N and therefore
gn “ pgdqn{d “ en{d “ e
Corollary 54. Every group G of prime order p is cyclic.
D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
Proof. By Lagrange, a subgroup H ď G has order 1 or p, that is, H is either trivial or H “ G.
Take g P G with g ‰ e. Then xgy is a nontrivial subgroup of G, hence G “ xgy is cyclic.
Example 55 (Sunflower Count). Let G be a group of order |G| “ 25. Show that G contains
at most 6 subgroups of order 5.
Solution Given two distinct subgroups H1, H2 ď G of order 5, H1 X H2 “ teu. In fact, by
Lagrange |H1 X H2| divides |H1| “ |H2| “ 5, so |H1 X H2| “ 1 or |H1 X H2| “ 5. But since
H1 ‰ H2, H1 X H2 is a proper subgroup of Hi (i.e., H1 X H2 ‰ Hi for i “ 1, 2), the only
possibility is |H1 XH2| “ 1 ðñ H1 XH2 “ teu.
Let H1, . . . , Hn be the list of all order 5 subgroups of G. By the above, they form a “sunflower
configuration”, with n “petals” intersecting at the element identity e, each containing 4 other
elements:
e
H1
H2
...
Hn
(notice the striking similarity, apart from the sunglasses)
The “sunflower” covers 4n` 1 elements, hence 4n` 1 ď |G| “ 25, and therefore n ď 6.
This inequality is sharp: considering the product group G “ Z{5Zˆ Z{5Z of example 48, we see
that there are exactly 6 subgroups of order 5, namely the 6 “lines” through the origin (draw a
picture!)
H1 “ xp1, 0qy H2 “ xp1, 1qy H3 “ xp1, 2qy
H4 “ xp1, 3qy H5 “ xp1, 4qy H6 “ xp0, 1qy
Note that the bijection x ÞÑ x´1 of G into G sends the left coset gH to the right coset Hg´1,
and therefore induces a bijection between G{H and HzG. Thus we can define
Definition 56. Let G be a group, and let H ď G. We define the index of H in G (notation:
rG : Hs) as the number of (left or right) cosets of H in G:
rG : Hs “ |G{H| “ |HzG|
In particular, when G is finite, by Lagrange’s theorem, rG : Hs “ |G|{|H|.
Remark 57. Recall that an equivalence relation „ on a set X is a relation that is
(i) reflexive: x „ x for all x P X;
(ii) symmetric: x „ y ðñ y „ x for x, y P X;
(iii) transitive: x „ y and y „ z implies y „ z for x, y, z P X.
A key fact is that to give a partition of X is the same as to give an equivalence relation
on X. In fact, given a partition
X “ ď
iPI
Xi with Xi XXj “ H whenever i ‰ j
we may define an equivalence relation „ in X by declaring two elements equivalent if they lie
in the same set Xi of the partition:
x „ y ðñ x and y belong to the same subset Xi
Conversely, given an equivalence relation „ on X, the subsets consisting of elements equivalent
to one another, i.e., subsets of the form
x
def“ ty P X | y „ xu px P Xq
form a partition of X (the set x is called the equivalence class of x).
Given an equivalence relation „ on X, the set of all its equivalence classes
X{„ def“ tx | x P Xu
is called the quotient set of X by „. Intuitively, X{„ is the set obtained by “merging” into a
single element all the elements belonging to the same equivalence class.
By Lagrange’s theorem, the left cosets of a subgroup H ď G define an equivalence relation on
the group G:
g1, g2 P G are H-equivalent ðñ g1, g2 belong to the same left coset of H
ðñ g1H “ g2H
ðñ Dh P H such that g1 “ g2h plema 51q
Note that G{H, the set of all left cosets of H in G, is the quotient set of this equivalence relation.
Morphisms, Isomorphisms, and Automorphisms
Groups are social animals, who communicate with each other through the so-called morphisms:
Definition 58. Given two groups pG, ¨q and pH,˚q, a homomorphism (or simply (group) mor-
phism) ϕ : GÑ H is a function that preserves products, i.e.,
ϕpa ¨ bq “ ϕpaq ˚ ϕpbq pa, b P Gq
Note that the product on the left hand is that of G, while the one on the right is that of H. The
set of all homomorphisms from G to H is denoted by
HompG,Hq def“ tϕ : GÑ H | ϕ is a morphismu
Example 59. Let G and H be two groups.
• The constant function GÑ H given by g ÞÑ eH (g P G) is a group morphism, the trivial
morphism.
• If H ď G, the inclusion map H ãÑ G is a morphism. In particular, teu ãÑ G and
id : GÑ G are morphisms.• The logarithm and exponential functions
log : Rą0 Ñ R and exp: RÑ Rą0
are bijective morphisms between the additive group pR,`q and the multiplicative group
pRą0, ¨q.
• The absolute value
Cˆ Ñ Rą0
z ÞÑ |z|
is a morphism between the multiplicative groups Cˆ and Rą0.
• The determinant is a morphism between the multiplicative groups GLnpRq and Rˆ:
GLnpRq Ñ Rˆ
A ÞÑ detA
D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
• The reduction mod 12
Z� Z{12Z
n ÞÑ n
is a surjective morphism between the additive groups Z and Z{12Z.
• Any linear transformation T : V Ñ W between two vector spaces is a morphism between
the additive groups pV,`q and pW,`q.
• Let C “ tf : r0, 1s Ñ R | f is continuousu be the additive group of continuous functions
from r0, 1s to R. Then integration
C Ñ R
f ÞÑ
ż 1
0
fpxq dx
is a morphism between the additive groups C and R.
• ψ : GÑ G given by ψpgq “ g2 is a group morphism if and only if G is abelian.
• ϕ : GÑ G given by ϕpgq “ g´1 is group morphism if and only if G is abelian.
• The left translation λg : G Ñ G is almost never a group morphism. In fact, λg is a
morphism if and only if g “ e, i.e., if and only if λg “ id.
• If G is abelian and n P Z, then the exponentiation by n
µn : GÑ G
g ÞÑ gn
is a group morphism. Note that, in additive notation, exponentiation becomes the multi-
plication by n map µnpgq “ ng.
Directly from the definition, we get
Lemma 60. Let ϕ : GÑ H be a group morphism.
(i) For all n P Z and g P G,
ϕpgnq “ `ϕpgq˘n
In particular, by taking n “ 0 and n “ ´1, we get that ϕ preserves identity and inverses:
ϕpeGq “ eH and ϕpa´1q “
`
ϕpaq˘´1 pa P Gq
(ii) If ϕ is bijective then the inverse function ϕ´1 : H ãÑÑ G is also a group morphism.
(iii) If ψ : H Ñ I is another group morphism then the composition ψ ˝ϕ : GÑ I is also a group
morphism.
Example 61. Consider the cyclic group pZ,`q and let G be any group. There is a natural
bijection
Ξ: HompZ, Gq ãÑÑ G
ϕ ÞÑ ϕp1q
In other words, a morphism ϕ P HompZ, Gq is completely determined by the image ϕp1q of the
generator 1 P Z.
In fact,
• Ξ is injective: if Ξpϕq “ Ξpψq, i.e., g def“ ϕp1q “ ψp1q then
ϕpnq “ ϕpn ¨ 1q “ ϕp1qn “ gn “ ψp1qn “ ψpn ¨ 1q “ ψpnq
for all n P Z by (i) of the above lemma.
• Ξ is surjective: given g P G we can define µg P HompZ, Gq by µgpnq “ gn; then Ξpµgq “ g.
Example 62 (Kernel and image). If ϕ : GÑ H is a group morphism then the image of ϕ is
a subgroup of H: imϕ ď H. Besides, if I ď H then the pre-image of I is a subgroup of G:
ϕ´1pIq def“ tg P G | ϕpgq P Iu ď G
In particular, the pre-image of the trivial subgroup of H is a subgroup of G, called kernel of ϕ:
kerϕ
def“ ϕ´1peq “ tg P G | ϕpgq “ eu
As in Linear Algebra, the importance of the kernel is that it “measures” the lack of injectivity:
Lemma 63 (Kernel and injectivity). Let ϕ : GÑ H be a group morphism. Then ϕ
is injective if and only if kerφ “ teu.
Proof. If ϕ is injective, then
g P kerϕ ðñ ϕpgq “ e “ ϕpeq ðñ g “ e
That is, kerϕ is trivial. Conversely, if kerϕ is trivial then
ϕpaq “ ϕpbq ðñ ϕpaqϕpbq´1 “ e ðñ ϕpab´1q “ e ðñ ab´1 “ e ðñ a “ b
That is, ϕ is injective.
Definition 64. Let G and H be two groups.
(i) An isomorphism ϕ : G ãÑÑ H is a bijective morphism of groups; by lemma 60, the inverse
function ϕ´1 : H ãÑÑ G is also an isomorphism. We will denote an isomorphism between
G and H by ϕ : G
«Ñ H.
(ii) We say that G and H are isomorphic (notation: G – H or G « H) if there is an
isomorphism between them (there may be more than one isomorphism).
Intuitively, two isomorphic groups G and H are “equal up to the name of its elements”: an
isomorphism ϕ : G
«Ñ H “renames” the elements of G in terms of elements of H, preserving
products. Thus isomorphisms preserve all the properties depending solely on the group axioms.
For example, given an isomorphism ϕ : G
«Ñ H, for all g P G the elements g and ϕpgq have the
same (possibly infinite) order.
Example 65. • pR,`q – pRą0, ¨q (via the log and exp functions).
• In the notation of examples 18 and 19, we have S1 – SO2pRq via the isomorphism (given
in Cartesian and polar coordinates, respectively)
S1
«Ñ SO2pRq
a` bi ÞÑ
ˆ
a ´b
b a
˙
pa, b P Rq
eiθ ÞÑ
ˆ
cos θ ´ sin θ
sin θ cos θ
˙
pθ P Rq
• Consider the subgroup UT2pRq ď GL2pRq from example 18. There is an isomorphism
between the multiplicative group UT2pRq and the additive group R, given by
ϕ : UT2pRq «Ñ Rˆ
1 a
0 1
˙
ÞÑ a
D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
• An infinite group G is cyclic if and only if G – Z. The implication ð is clear since Z is
infinite cyclic. To see ñ, if G “ xgy then we may define a surjective function
Z «Ñ G
n ÞÑ gn
which is clearly a group morphism. This function is also injective: if gm “ gn for integers
m ą n then gm´n “ e and therefore |G| “ |xgy| ď m´ n would be finite, a contradiction.
• Similarly, a group G of order of n is cyclic if and only if G – pZ{nZ,`q.
• Rˆ and Qˆ are not isomorphic since the first group is uncountable while the second is
countable.
• The groups Z and Qˆ are not isomorphic since the torsion subgroup Ztor (see lemma 41)
is trivial while pQˆqtor “ t˘1u.
• The additive groups Z{2Zˆ Z{2Z and Z{4Z are not isomorphic since the second has ele-
ments of order 4 (1 or 3) while the first does not.
Example 66 (Hom Group). If pH,`q is an abelian group and G, any group, HompG,Hq also
has an abelian group structure: if ϕ,ψ P HompG,Hq we define ϕ` ψ by g ÞÑ ϕpgq ` ψpgq (sum
in H), which is a morphism since H is abelian:
pϕ` ψqpabq “ ϕpabq ` ψpabq “ ϕpaq ` ϕpbq ` ψpaq ` ψpbq
“ ϕpaq ` ψpaq ` ϕpbq ` ψpbq
“ pϕ` ψqpaq ` pϕ` ψqpbq pa, b P Gq
The identity element of HompG,Hq is the trivial morphism, and the inverse of ϕ is ´ϕ, which
is the morphism given by g ÞÑ ´ϕpgq (opposite in H).
For example, HompZ,Zq – Z via the bijection Ξ of example 61. Note that the morphism
µn P HompZ,Zq corresponding to n P Z is the multiplication by n: µnpxq “ nx (see exam-
ple 59).
Remark 67. An important problem in Mathematics is to classify, up to isomorphism, all finite
groups. Later, we will see several tools that help us in this task. In particular, we will be able
to list, up to isomorphism, all groups of order up to 15 (see section Groups that appear in
Nature for the meaning of the notations of the groups below):
Order Groups
1 trivial
2 Z{2Z
3 Z{3Z
4 Z{4Z; Z{2Zˆ Z{2Z
5 Z{5Z
6 Z{6Z; S3 – D3
7 Z{7Z
8 Z{8Z; Z{2Zˆ Z{4Z; Z{2Zˆ Z{2Zˆ Z{2Z; D4; Q8
9 Z{9Z; Z{3Zˆ Z{3Z
10 Z{10Z; D5
11 Z{11Z
12 Z{12Z; Z{2Zˆ Z{6Z; D6; A4; xa, b, c | a3 “ b2 “ c2 “ abcy
13 Z{13Z
14 Z{14Z; D7
15 Z{15Z
Note in particular that if G has prime order p then G is cyclic (corollary 54) and therefore
G – pZ{pZ,`q, which explains some of the entries in the table above. Example 229 covers the
last entry of the table, while the groups of order 6, 10, and 14 are treated in example 230. The
cases of order 4 and 9 follow from theorem 201.
Definition 68. Let G be a group. An automorphism of G is an isomorphism ϕ : G
«Ñ G. The
set of all automorphisms of G is denoted by
AutpGq def“ tϕ : G «Ñ G | ϕ is automorphism u
and is a group with the operation ˝ (composition of functions).
An automorphism of G is to be thought of as a symmetry of G, following the philosophy explained
in the next section.
Example 69 (Conjugation). For all groups G and g P G, conjugation κg : G «Ñ G (see defi-
nition 13) is an automorphism of G. In fact, by lemma 14 we already know that κg is a group
morphism by the conjugate identity (1), while conjugate identity (2) shows that κg is bijective
with inverse κg´1 . Note that the conjugate identity (2) also says that
GÑ AutpGq
g ÞÑ κg
is a group morphism. The kernel of this morphism is the center ZpGq of G (see example 22).
Example 70. We have AutpZq – pt˘1u, ¨q. In fact, consider theisomorphism
Ξ: Z «Ñ HompZ,Zq
n ÞÑ µn
Here µn denotes the multiplication by n as in examples 61 and 66. The map µn : Z Ñ Z
is bijective if and only if n “ ˘1. In addition, the isomorphism Ξ takes multiplication in
Z into composition of functions: µn ˝ µm “ µnm. Thus Ξ restricts to a group isomorphism
t˘1u «Ñ AutpZq.
Example 71 (Automorphisms of a finite cyclic group). Let a P N, and consider the mul-
tiplication by a mod n:
µa : Z{nZÑ Z{nZ
x ÞÑ a ¨ x def“ x` ¨ ¨ ¨ ` xlooooomooooon
a times
“ a ¨ x
(here ax denotes the element of Z{nZ corresponding to the remainder in the division of ax by
n, as in the remark of example 2). Note that µa P HompZ{nZ,Z{nZq (an instance of the expo-
nentiation by a of example 59, written in additive notation). By theorem 39, if gcdpa, nq “ 1
then µa maps the generator 1 to another generator a “ µap1q of the cyclic group Z{nZ, and
thus µa is surjective. In that case, since Z{nZ is finite, µa must also be injective, that is,
µa P AutpZ{nZ,`q.
Conversely, since an automorphism σ P AutpZ{nZ,`q preserves orders, it maps generators to
generators (i.e., elements of order n). Thus σp1q “ a for some integer a coprime to n by
theorem 39. But then, for all x “ 0, 1, 2, . . . , n´ 1,
σpxq “ σp1` ¨ ¨ ¨ ` 1looooomooooon
x times
q “ σp1q ` ¨ ¨ ¨ ` σp1qloooooooooomoooooooooon
x times
“ x ¨ a “ xa “ µapxq
That is, we have σ “ µa.
To sum up, we have
AutpZ{nZq “ tµa | 1 ď a ď n and gcdpa, nq “ 1u
and therefore |AutpZ{nZq| “ ϕpnq (see definition 37).
For instance, AutpZ{12Zq consists of 4 elements, µ1, µ5, µ7, µ11, the multiplications by 1, 5, 7
and 11 mod 12. The following table computes the composition operation in AutpZ{12Zq, where
the element of the σ-th row and τ -th column is σ ˝ τ :
D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
˝ µ1 µ5 µ7 µ11
µ1 µ1 µ5 µ7 µ11
µ5 µ5 µ1 µ11 µ7
µ7 µ7 µ11 µ1 µ5
µ11 µ11 µ7 µ5 µ1
In general, µa ˝ µb “ µab mod n in AutpZ{nZq, where x mod n denotes the remainder in the
division of x by n. That is, automorphism composition corresponds to multiplication mod n,
hence the group AutpZ{nZq is abelian, isomorphic to the unit group pZ{nZqˆ of the ring Z{nZ.
Groups that appear in Nature
The overwhelming majority of groups that appear naturally are “sets of symmetries” of an object:
Object Symmetries Group
t1, 2, . . . , nu permutations symmetric Sn
polynomial
ś
1ďiăjďn
pxi ´ xjq permutations of
the variables
alternating An
regular n-gon
rotations and
reflections
dihedral Dn
vector space V
bijective linear
transformations
general linear
GLpV q
vector space V with inner
product
orthogonal linear
transformations
orthogonal OpV q
Let us see more details below.
Symmetric group
Let X be any set. By definition, a symmetry of X is a bijection (also called permutation)
f : X ãÑÑ X (after all, any two elements of X are “equivalent” to each other). The symmetric
group SX of X is the group given by all these symmetries with the operation ˝ (composition of
functions):
SX “ tf : X ãÑÑ X | f is a bijectionu
When X “ t1, 2, . . . , nu, we shall abbreviate SX by Sn. We have |Sn| “ n!, and Sn is abelian
only for n “ 1, 2.
A permutation pi P Sn can be represented in several ways. Let us look at a concrete example
before the general description, given below.
Example 72. Consider the permutation pi P S5 given by
pip1q “ 3, pip2q “ 4, pip3q “ 1, pip4q “ 5, pip5q “ 2
We can represent pi in any of the following ways:
• Notation as a 2ˆ 5 matrix
pi “
ˆ
1 2 3 4 5
3 4 1 5 2
˙
which pictorially corresponds to
1
2
3
4
5
1
2
3
4
5
• Notation as a product of disjoint cycles
pi “ p13qp245q “ p245qp13q “ p31qp452q “ p245qp13q
corresponding to the graph
12 3
4
5
• Notation as a permutation matrix
Tpi “
¨˚
˚˝˚0 0 1 0 00 0 0 0 1
1 0 0 0 0
0 1 0 0 0
0 0 0 1 0
‹˛‹‹‚
In general: a permutation pi P Sn can be represented by
(i) Matrix notation 2ˆ n, where the second row represents the image of the first one by pi:
pi “
ˆ
1 2 3 ¨ ¨ ¨ n
pip1q pip2q pip3q ¨ ¨ ¨ pipnq
˙
Although it is convenient to write the first row in increasing order, that is not necessary.
For instance, the inverse of pi can be written
pi´1 “
ˆ
pip1q pip2q pip3q ¨ ¨ ¨ pipnq
1 2 3 ¨ ¨ ¨ n
˙
(ii) Notation as a product of disjoint cycles: a t-cycle γ P Sn is a permutation of the form
a1 ÞÑ a2, a2 ÞÑ a3, a3 ÞÑ a4, . . . , at´1 ÞÑ at, at ÞÑ a1
a ÞÑ a if a R ta1, a2, . . . , atu
for t distinct elements a1, a2, . . . , at P t1, 2, . . . , nu. We will denote this t-cycle by
γ “ pa1 a2 a3 a4 . . . atq
Note that:
• the ai’s in the above notation may be circularly permuted without changing the cycle
γ, for instance pa1 a2 . . . atq “ pa2 a3 . . . at a1q.
• the inverse of γ is obtained by “reading the cycle backwards”
γ´1 “ pat at´1 . . . a3 a2 a1q
• The order of the t-cycle γ is exactly t.
• disjoint cycles commute: if
ta1, a2, . . . , atu X tb1, b2, . . . , buu “ H,
then (remember that the product is the function composition)
pa1 a2 . . . atqpb1 b2 . . . buq “ pb1 b2 . . . buqpa1 a2 . . . atq
D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
We can write any permutation pi P Sn as the product of disjoint cycles
pi “ pa11 a12 . . . a1t1 qpa21 a22 . . . a2t2 q . . . par1 ar2 . . . artr q
with aij ‰ akl if pi, jq ‰ pk, lq. In fact, we can construct a directed graph with vertices
1, 2, . . . , n and directed edges starting at vertex i and ending at vertex pipiq for i “ 1, 2, . . . , n.
Since pi is bijective, for each vertex i, there is a single edge iÑ pipiq leaving i and a single
one pi´1piq Ñ i arriving at i. Thus, since the graph is finite, it must be a disjoint union
of cycles: each vertex i belongs to at most one cycle (since i is connected to exactly two
other vertices); and i belongs to some cycle, since starting from i and following the directed
edges, we eventually return to i, obtaining a “pure cycle,” not something like the following
picture (where two edges arrive at vertex j):
i j
Note that the above representation of pi as a product of disjoint cycles is not unique:
disjoint cycles commute and elements within a cycle can be circularly permuted. In this
notation, we usually omit the cycles of size 1 (the fixed points of the permutation).
The representation of pi as product of disjoint cycles allows one not only to quickly write
pi´1 but also to easily determine pi’s order in terms of the sizes t1, t2, . . . , tr of its cycles:
|xpiy| “ lcmpt1, t2, . . . , trq
In fact, since disjoint cycles commute,
pin “ pa11 a12 . . . a1t1 qnpa21 a22 . . . a2t2 qn . . . par1 ar2 . . . artr qn
and therefore pin “ id ðñ pai1 ai2 . . . aiti qn “ id for all i “ 1, 2, . . . , r. The result now
follows from the “least divides” lemma 33 and the fact that a t-cycle has order t.
(iii) Notation by permutation matrix: let e1 “ p1, 0, . . . , 0q, . . . , en “ p0, . . . , 0, 1q be the stan-
dard basis of Rn; given pi P Sn, consider the bijective linear transformation induced by the
corresponding permutation of the ei’s:
Tpi : Rn
«Ñ Rn
ei ÞÑ epipiq
The matrix of Tpi with respect to the standard basis, which we also denote by Tpi , yields
another way of representing the permutation pi:
Tpi “ paijq1ďi,jďn where aij “
#
1 if pipjq “ i
0 otherwise
The advantage of this representation is that composition of permutations amounts to the
usual matrix multiplication:
Tpi˝τ “ Tpi ¨ Tτ pτ, pi P Snq
That is, we have an injective group morphism
Sn ãÑ GLpRnq
pi ÞÑ Tpi
In particular, the matrix of pi´1 is the inverse of the matrix of pi: Tpi´1 “ T´1pi .
Example 73. The following is the multiplication table of S3, in cycle notation. The the entry
on the λ-th row and κ-th column represents the product λκ, in that order.
˝ p1q p123q p132q p12q p23q p13q
p1q p1q p123q p132qp12q p23q p13q
p123q p123q p132q p1q p13q p12q p23q
p132q p132q p1q p123q p23q p13q p12q
p12q p12q p23q p13q p1q p123q p132q
p23q p23q p13q p12q p132q p1q p123q
p13q p13q p12q p23q p123q p132q p1q
From the above table, we see that S3 is not abelian. Note also that ρ
def“ p123q and σ def“ p12q
generate S3:
S3 “ xρ, σy “ tp1q, ρ, ρ2, σ, ρσ, ρ2σu
The orders of the elements of S3 are
τ P S3 p1q ρ ρ2 σ ρσ ρ2σ
order of τ 1 3 3 2 2 2
Example 74 (Conjugation of cycles). If σ P Sn and pa1 a2 . . . atq P Sn is a cycle then
σ ¨ pa1 a2 . . . atq ¨ σ´1 “
`
σpa1qσpa2q . . . σpatq
˘
because σ ¨ pa1 a2 . . . atq ¨ σ´1 ¨ σpaiq “ σpai`1q for i “ 1, 2, . . . , t´ 1 and σ ¨ pa1 a2 . . . atq ¨ σ´1 ¨
σpatq “ σpa1q.
Example 75 (Center of Sn). Let us show that the center ZpSnq (see example 22) of Sn is
trivial for n ě 3. First, note that pi P ZpSnq if and only if the conjugation κpi : Sn «Ñ Sn is the
identity since piτ “ τpi ðñ piτpi´1 “ τ . Now let pi ‰ id. There exists 1 ď i ď n such that
j
def“ pipiq ‰ i. As n ě 3, we can still choose k R ti, ju; consider the 2-cycle pi kq. From the
previous example,
pi ¨ pi kq ¨ pi´1 “ `pipiqpipkq˘ “ `j pipkq˘ ‰ pi kq since j R ti, ku
Therefore κpi ‰ id and pi R ZpSnq.
The next example shows the importance of the symmetric group within the group fauna.
Example 76 (Cayley). Let G “ tg1, g2, . . . , gnu be a finite group. Given g P G (i.e., g “ gi
for some i), by the shuffle lemma 11 the left translation λg : G ãÑÑ G defines a permutation in
the symmetric group SG:
λg “
ˆ
g1 g2 ¨ ¨ ¨ gn
g ¨ g1 g ¨ g2 ¨ ¨ ¨ g ¨ gn
˙
As λg ˝ λh “ λgh, the map
G ãÑ SG
g ÞÑ λg
is a group morphism; since λg “ id ðñ g “ e, its kernel is trivial, and thus it is injective
(lemma 63). This allows us to identify G with its image in SG, showing that every finite group
is isomorphic to a subgroup of the symmetric group SG – Sn with n “ |G|.
D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
Parity of Permutations and the Alternating Group
Given a polynomial fpx1, . . . , xnq P Zrx1, . . . , xns and a permutation σ P Sn, let σpfq be the
polynomial obtained from f by permuting its the variables according to σ:
σpfpx1, . . . , xnqq def“ fpxσp1q, . . . , xσpnqq
We now build an important group morphism
Π: pSn, ˝q Ñ pt˘1u, ¨q
called the parity morphism. For this, consider the polynomial
dpx1, . . . , xnq def“
ź
1ďiăjďn
pxi ´ xjq
Since any σ P Sn permutes the 2-element subsets ti, ju Ď t1, . . . , nu, σpdq has the same factors
pxi ´ xjq as d up to sign, hence
σpdq “ ź
1ďiăjďn
pxσpiq ´ xσpjqq “ ˘d
Definition 77. Let d be the polynomial defined above. The parity morphism is the group
morphism given by
Π: Sn Ñ t˘1u
σ ÞÑ σpdq
d
That is, Πpσq “ 1 if σpdq “ d and Πpσq “ ´1 if σpdq “ ´d. The kernel of Π is called alternating
group and is denoted by
An
def“ ker Π “ tσ P Sn | σpdq “ du
In other words, An is the subgroup of Sn consisting of the symmetries of the polynomial d.
A case-by-case analysis shows that Πpσ˝τq “ Πpσq¨Πpτq for all σ, τ P Sn, i.e., Π is in fact a group
morphism. For example, if Πpτq “ 1 and Πpσq “ ´1 then pτ ˝ σqpdq “ τp´dq “ ´τpdq “ ´d,
thus Πpσ ˝ τq “ ´1 “ Πpσq ¨Πpτq.
The name parity morphism stems from the following
Definition 78. Let σ P Sn. We say that
σ is
#
even if Πpσq “ 1 ðñ σpdq “ d ðñ σ P An
odd if Πpσq “ ´1 ðñ σpdq “ ´d ðñ σ R An
In view of this definition, we introduce the notation
p´1qσ def“ Πpσq
since p´1qeven “ 1 and p´1qodd “ ´1.
Observe that p´1qeven “ 1 and p´1qodd “ ´1 defines an isomorphism from the additive group
teven, oddu to the multiplicative group t˘1u. Composing Π with the inverse isomorphism
t˘1u – teven, oddu, the identity Πpστq “ Πpσq ¨Πpτq amounts to the usual “parity table”
σ is even σ is odd
τ is even στ is even στ is odd
τ is odd στ is odd στ is even
which agrees with the “exponent law”
p´1qeven ¨ p´1qodd “ p´1qeven`odd “ p´1qodd “ ´1
and so on.
Example 79. In the notation of example 73, straight from the definitions, for the generators
σ, ρ of S3 we have
σpdq “ pxσp1q ´ xσp2qqpxσp1q ´ xσp3qqpxσp2q ´ xσp3qq
“ px2 ´ x1qpx2 ´ x3qpx1 ´ x3q “ ´d
and
ρpdq “ pxρp1q ´ xρp2qqpxρp1q ´ xρp3qqpxρp2q ´ xρp3qq
“ px2 ´ x3qpx2 ´ x1qpx3 ´ x1q “ d
Hence σ is odd and ρ is even. Since S3 “ xσ, ρy, using the parity morphism we can complete
the rest of following table:
τ P S3 p1q ρ ρ2 σ ρσ ρ2σ
p´1qτ 1 1 1 ´1 ´1 ´1
Hence A3 “ xρy “ tp1q, ρ, ρ2u is a cyclic group of order 3, generated by ρ (or ρ2).
Definition 80. A transposition in Sn is a cycle pi jq of size 2.
Example 81 (Transpositions are odd). For the transposition σ “ p12q, only the factor
px1 ´ x2q of the polynomial dpx1, . . . , xnq changes sign, so p12q is odd. By example 74, any
transposition is conjugate to p12q, and as t˘1u is abelian, conjugate permutations have the same
parity. In fact, for i ă j let τ “ p1 iqp2 jq, with the convention that τ “ p2 jq whenever i “ 1,
and τ “ p1 iq whenever j “ 2. Then
pi jq “ `τp1q τp2q˘ “ τp1 2qτ´1 ùñ Πpi jq “ Πpτq ¨Πp1 2q ¨Πpτq´1 “ Πp1 2q “ ´1
Next we show that rSn : Ans “ 2 for n ě 2. In fact, if n ě 2, there are odd permutations
in Sn (for example, transpositions). Fix τ such that p´1qτ “ ´1; so τ´1 is also odd since
Πpτ´1q “ Πpτq´1 “ p´1q´1 “ ´1. By Lagrange’s theorem 52 the left cosets of An partition Sn;
we claim that
Sn “ Anloomoon
even
Y τAnloomoon
odd
In fact, it suffices to show that the coset τAn is the set of all odd permutations of Sn. Clearly,
all elements of τAn are odd, being products of the odd permutation τ and an even permutation
in An. Conversely, given an odd permutation σ, τ´1σ is even, that is,
τ´1σ P An ðñ σ P τAn
which shows that any odd permutation belongs to τAn, as desired.
Remark 82. Since An “ ker Π, we shall see later that, by the isomorphism theorem 155, Π in-
duces an isomorphism between the quotient group Sn{An and t˘1u, which will give the “right”
proof that |Sn{An| “ 2 ðñ rSn : Ans “ 2.
Summing up, if n ě 2, there are as many even permutations as there are odd permutations in
Sn, hence
|An| “
#
1 if n “ 1
n!{2 if n ě 2
In practice, it is difficult to determine the parity of a permutation based solely on the above
definition. Hence the lemma
D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
Lemma 83 (Parity Criteria). Let σ P Sn.
(i) Transpositions are odd.
(ii) The transpositions generatea Sn. Thus, a permutation pi is even (respectively,
odd) if pi is the product of an even (respectively, odd) number of transpositions.
In particular, for an r-cycle σ “ pa1 a2 a3 . . . arq,
p´1qσ “ p´1qr`1
That is, cycles of even size are odd permutations, and cycles of odd size are even
permutations.
(iii) If Tσ is the permutation matrix corresponding to σ,
p´1qσ “ detTσ
awhich is to be expected: we can get any permutation of n objects by swapping two
elements at a time
Proof. We have already proved (i) in example 81.
(ii) Since any permutation is a product of disjoint cycles, we only need to show that cycles
are products of transpositions. More precisely, a r-cycle can be written as the product of
r ´ 1 transpositions:
pa1 a2 a3 . . . arq “ pa1 arqpa1 ar´1qpa1 ar´2q . . . pa1 a3qpa1 a2q
(iii) Since the permutation matrix Tσ of the transposition σ “ pi jq is obtained by swapping
the i-th and j-th columns of the identity matrix I, detTσ “ ´ det I “ ´1. The result now
follows from the multiplicativity of the determinant detpABq “ detpAq detpBq and from
the previous item.
Example 84 (3-cycles generate An). Every element of An is the product of an even number
of transpositions, so it suffices to show that products of the form pabqpacq and pabqpcdq (with
distinct letters representing distinct numbers) are products of 3-cycles, which is immediate:
pabqpacq “ pacbq pabqpcdq “ pacbqpacdq
Example 85. Let us show that, for n ě 3,
Sn “ xp12q, p1 2 3 . . . nqy
Let H “ xp1 2q, p1 2 3 . . . nqy. By lemma 83, Sn is generated by transpositions, hence it suffices
to show that pi jq P H for any 1 ď i ă j ď n. First, note that p1 2q, p2 3q, p3 4q, . . . , pn´ 1nq P H:
p1 23 . . . nq ¨ p1 2q ¨ p1 2 3 . . . nq´1 “ p2 3q
p1 2 3 . . . nq ¨ p2 3q ¨ p1 2 3 . . . nq´1 “ p3 4q
...
p1 2 3 . . . nq ¨ pn´ 2n´ 1q ¨ p1 2 3 . . . nq´1 “ pn´ 1nq
But p1 2q, p1 3q, p1 4q, . . . , p1nq P H as well:
p1 2q ¨ p2 3q ¨ p1 2q´1 “ p1 3q
p1 3q ¨ p3 4q ¨ p1 3q´1 “ p1 4q
...
p1n´ 1q ¨ pn´ 1nq ¨ p1n´ 1q´1 “ p1nq
Finally pi jq “ p1 iq ¨ p1 jq ¨ p1 iq´1 P H for 1 ă i ă j ď n.
General Linear Group
Let k be a field6,and V be a finite dimensional k-vector space. Let GLpV q be the subgroup of
the symmetric group SV consisting of all linear symmetries of V , i.e.,
GLpV q def“ tT : V «Ñ V | T is a bijective linear transformationu
This is one of the most important groups in Mathematics, the so-called general linear group.
Fix a basis of V ; we shall write MT for the matrix of T P GLpV q with respect to this basis. Let
GLnpkq def“ tA PMnpkq | detA ‰ 0u
be the multiplicative group of n ˆ n matrices with entries in k. There is an isomorphism (a
non-canonical one since it depends on a choice of basis of V )
GLpV q «Ñ GLnpkq
T ÞÑMT
In other words, this bijection maps composition of functions into matrix multiplication: MS˝T “
MS ¨MT . Thanks to this isomorphism, by abuse of language we will sometimes identify linear
transformations in GLpknq with their associated matrices in GLnpkq relative to the standard
basis e1 “ p1, 0, . . . , 0q, e2 “ p0, 1, . . . , 0q, . . . , en “ p0, 0, . . . , 1q.
Example 86 (General Linear Group over Finite Fields). Let Fq be the finite field with q
elements. Then
|GLnpFqq| “ pqn ´ 1qpqn ´ qqpqn ´ q2q ¨ . . . ¨ pqn ´ qn´1q
In fact, a n ˆ n matrix A is invertible if and only if its columns form a basis of Fnq . There
are qn ´ 1 choices for the first basis vector (any nonzero vector); once the first vector has been
chosen, there are qn ´ q choices for the second basis vector (any vector different from the q
multiples of the first one); once the first two basis vectors have been chosen, there are qn ´ q2
choices for the third one (any vector that is different from the q2 linear combinations of the first
two); and so on.
Example 87 (The isomorphism GL2pF2q – S3). Let F2 “ t0, 1u be the field of integers
mod 2. By the previous example, |GL2pF2q| “ p22 ´ 1qp22 ´ 2q “ 6. Explicitly, its elements are
I
def“
ˆ
1 0
0 1
˙
R
def“
ˆ
0 1
1 1
˙
S
def“
ˆ
0 1
1 0
˙
R2 “
ˆ
1 1
1 0
˙
RS “
ˆ
1 0
1 1
˙
R2S “
ˆ
1 1
0 1
˙
In particular, GL2pF2q “ xR,Sy. Consider the non-zero vectors of F22: v1 “ p1, 0q, v2 “ p0, 1q
v3 “ p1, 1q. The elements of GL2pF2q permute the vectors v1, v2, v3, so that we get a map
GL2pF2q «Ñ Stv1,v2,v3u – S3
A ÞÑ
ˆ
v1 v2 v3
Av1 Av2 Av3
˙
It is easy to check that this map is an isomorphism that takes the generators R,S of GL2pF2q
into the generators ρ, σ of S3 (in the notation of example 73): R ÞÑ ρ and S ÞÑ σ.
6i.e., a set such as Q, R, C or Fp
def“ Z{pZ (p a prime number), where you can perform the four basic operations of addition, subtraction, multiplication and division by a non-zero element.
D
RA
FT
(E
T
&
ST
M
D
ec
em
be
r 2
4,
20
17
)
Since detpA ¨Bq “ detA ¨ detB, there is a morphism of multiplicative groups
det : GLpV q� kˆ
T ÞÑ detT
Here kˆ “ k r t0u. The kernel (see example 62) of this morphism is an important subgroup of
the general linear group.
Definition 88. Let k be a field, and V be a k-vector space with dimk V “ n. The special linear
group is the subgroup of GLpV q consisting of those linear transformations with determinant 1:
SLpV q def“ kerpdetq “ tT P GLpV q | detT “ 1u
We shall also denote by
SLnpkq def“ tA P GLnpkq | detA “ 1u
the corresponding matrix group. After a choice of basis of V , the non-canonical isomorphism
GLpV q – GLnpkq restricts to an isomorphism SLpV q – SLnpkq.
We can interpret SLnpRq as the symmetry group of the vector space Rn equipped with volume
and orientation. For that, recall that the determinant of a real linear transformation has an
important geometric interpretation in terms of “oriented volume”: a real linear transformation
T : Rn Ñ Rn
• multiplies the volume by |detT |;
• preserves orientation whenever detT ą 0, otherwise it reverses orientation.
Example 89. With respect to the standard basis e1 “ p1, 0q and e2 “ p0, 1q, let T : R2 Ñ R2 be
the linear transformation given by the matrix with determinant ´3ˆ
1 2
2 1
˙
Then T reverses orientation and multiplies the area by 3: in the picture, the square of area 1
determined by e1, e2 is taken into a parallelogram of area 3, and going around the origin clock-
wise we see that the order of the images Te1 “ p1, 2q, Te2 “ p2, 1q is reversed with respect to
the original order of e1, e2.
p0, 0q e1
e2
1
T
p0, 0q
Te1
Te2
3
Elementary matrices
Let k be a field. Given λ P k and 1 ď i, j ď n with i ‰ j, we define the elementary matrix
Eijpλq to be the sum of the identity matrix In P GLnpkq with the n ˆ n matrix whose pi, jq-th
entry is λ and whose other entries are all 0. For example, for n “ 4 we have
E13pλq “
¨˚
˚˝1 0 λ 00 1 0 0
0 0 1 0
0 0 0 1
‹˛‹‚ E42pλq “
¨˚
˚˝1 0 0 00 1 0 0
0 0 1 0
0 λ 0 1
‹˛‹‚
For i ‰ j and any λ P k, Eijpλq P SLnpkq because this matrix is upper or lower triangular, thus
detEijpλq “ 1 is the product of the entries in the diagonal. Note also that, with respect to the
standard basis e1, . . . , en P kn, Eijpλq is the matrix of the linear transformation from kn to kn
given by
Eijpλqpejq “ ej ` λei Eijpλqperq “ er if r ‰ j
Lemma 90 (Steinberg relations). Let rA,Bs “ ABA´1B´1 be the commutator of A and B
(see example 29). Then for i ‰ j and r ‰ s
Eijpλq ¨ Eijpµq “ Eijpλ` µq
rEijpλq, Ejrpµqs “ Eirpλ ¨ µq if i ‰ r and j ‰ r
rEijpλq, Erspµqs “ In if i ‰ s and j ‰ r
In particular, from the first relation we see that Eijpλq´1 “ Eijp´λq.
Proof. It is enough to consider the image of the standard basis e1, . . . , en of kn by the cor-
responding linear transformations. For instance, let us show the second relation. We have
rEijpλq, Ejrpµqs “ EijpλqEjrpµqEijp´λqEjrp´µq and therefore
EijpλqEjrpµqEijp´λqEjrp´µqperq “ EijpλqEjrpµqEijp´λqper ´ µejq
“ EijpλqEjrpµqper ´ µej ` µλeiq
“ Eijpλqper ` µλeiq “ er ` µλei
which coincides with Eirpλµqperq. Similar calculations show that the images under
rEijpλq, Ejrpµqs and Eirpλµq of the other vectors of the standard basis also coincide, hence
these two linear transformations are equal.
An important fact about elementary matrices is the
Lemma 91. Let k be a field. The elementary matrices Eijpλq with i ‰ j and λ P k
generate the group SLnpkq.
The lemma follows directly from a slight variation of the Gaussian elimination process, which
reduces any matrix in SLnpkq to the identity matrix by a sequence of elementary matrix oper-
ations on rows/columns. Let A be an n ˆ n matrix with entries in k. Multiplying A by Eijpλq
corresponds to performing an elementary operation on the rows/columns of A: denoting the i-th
row vector (respectively column vector) of A by `i (respectively by ci), we have
• Eijpλq ¨A is the matrix obtained by making the substitution `i Ð `i ` λ ¨ `j in A;
• A ¨ Eijpλq is the matrix obtained by making the substitution cj Ð cj ` λ ¨ ci in A.
Instead of trying to write some complicated recipe to prove the lemma in general (that no one
will be able to follow thanks to the proliferation of indices), let us look at an
Example 92. Given the matrix
A “
¨˝
0 ´1 ´3
´3 9 5
4 ´9 2
‚˛P SL3pQq
we can perform the following sequence of elementary operations:
• Getting 1 at position p1, 1q: since detA ‰ 0, there exists a nonzero element in column
1; choose any row i ‰ 1