1.10. SUBGROUPS 17
1.10 SUBGROUPS
An important aspect of a group is formed by its subgroups. For example, the two matrices
1 0
0 1
and
1 0
0 1
;
that form a subset of the set (1.10) form a group of their own, isomorphic to S
2
, the group of
permutations of two objects. We say that this two-element group is a subgroup of the six-element
group. We write:
S
2
S
3
;
which we may read either as “S
2
is a subgroup of S
3
” or as “S
3
is a supergroup of S
2
.”
If G is finite and a supergroup of H, then the ratio
order(G)
order(H)
is called the index of H in G. e theorem of Lagrange says that such an index is always an
integer. In other words, the order of a subgroup divides the order of its supergroup. is theorem
strongly restricts the number of subgroups of a given group. Nevertheless, most groups have a
wealth of subgroups. For example, the group S
4
(of order 4! = 24) has 30 different subgroups,
whereas S
8
(of order 8! = 40,320) has 151,221 subgroups [18].
We note that Closure(G
1
, G
2
) is a supergroup of both G
1
and G
2
.
1.11 YOUNG SUBGROUPS
Symmetric groups have a special class of subgroups called Young subgroups. ey take advan-
tage of the notion of “direct product of two groups.” We introduce such a product by giving an
example of a Young subgroup of S
5
. Assume five objects a, b, c, d, and e. ere exist a total
of 5! = 120 permutations of these objects. However, let us impose a restriction: we only allow
permutations that permute a, b, and c among each other and (simultaneously) permute d and e
among each other. is allows 3! permutations of three objects, while (independently) allowing
2! permutations of two objects. e allowed permutations form a permutation group of order
3! 2! = 12. We are allowed to “combine” each element of S
3
with each element of S
2
. erefore,
the group is called a direct product of S
3
and S
2
and denoted S
3
S
2
. We write
S
3
S
2
S
5
:
e subgroup is based on a particular partition of the number 5:
3 C 2 D 5 :
18 1. INTRODUCTION
In general, we may combine any group G
1
with any group G
2
, …, with any group G
m
.
Of course, we have
order.G
1
G
2
G
m
/ D order.G
1
/ order.G
2
/ order.G
m
/ : (1.11)
As an example, we consider the group formed by the set of all 2
2
n
Boolean functions of n Boolean
variables together with the XOR operation (see Sections 1.3 and 1.5). Because in the minterm
expansion of a particular function a particular minterm is either present or not, the group is
isomorphic to the direct product S
2
S
2
S
2
with 2
n
factors, with order
order.S
2
S
2
S
2
/ D Πorder.S
2
/
2
n
D 2
2
n
:
Each of the factors S
2
refers to what was called in Section 1.5 a minterm group.
A Young subgroup [19–21] of the symmetric group S
n
is defined as any subgroup isomor-
phic to S
n
1
S
n
2
S
n
k
, with .n
1
; n
2
; : : : ; n
k
/ a partition of the number n, that is, with
n
1
C n
2
C Cn
k
D n :
e order of this Young subgroup is n
1
Šn
2
Š : : : n
k
Š.
For example, the group S
4
has the following Young subgroups:
• one trivial subgroup isomorphic to S
4
(of order 4Š D 24),
• three subgroups isomorphic to S
2
S
2
(each of order 2Š2Š D 4),
• four subgroups isomorphic to S
1
S
3
(of order 1Š3Š D 6),
• six subgroups isomorphic to S
1
S
1
S
2
(of order 1Š1Š2Š D 2), and
• one trivial subgroup isomorphic to S
1
S
1
S
1
S
1
(of order 1).
For example,
0
B
B
@
1 0 0 0
0 0 1 0
0 0 0 1
0 1 0 0
1
C
C
A
is a member of an S
1
S
3
subgroup of S
4
.
Because S
1
is just the trivial group 1 with one element, that is, the identity element i,
Young subgroups of the form S
1
S
k
are often simply denoted by S
k
. Finally, Young subgroups
of the form S
k
S
k
S
k
(with m factors) will be written as S
m
k
.
e theorems in Section 1.8 can be interpreted in terms of Young subgroups: if we define
• N as the group of all permutations of the n objects,
• H as the group of all “horizontal permutations” of these objects, and
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.