Appendix B
Groups
The group is the basic algebraic structure with one operation. Groups appear in many contexts in this book. For example, all the signal domains introduced in Chapters 2–5 have the structure of an additive commutative group. Also, sets of transformations of domains and signals have the structure of a noncommutative group. This is used extensively in Chapter 12. This appendix provides basic definitions and properties of groups, but any standard text on abstract algebra should be consulted for a more detailed treatment, e.g, part I of Dummit and Foote (2004) or chapter 1 of Miller (1972).
- 1. A binary operation
in a set 
is a function from 
into 
. We write 
for 
.
For example, addition
is a binary operation on the set 
of integers. - 2. A binary operation
on a set 
is associative if 
for all 
.
For an associative operation, the parentheses are not required, and we can write simply
. Addition on 
is associative. - 3. A binary operation
on a set 
is commutative if 
for all 
.
Addition on
is also commutative. - 4. A semigroup is a set
with one associative binary operation 
, and is denoted 
. A semigroup is commutative if its binary operation is commutative.
The set of strictly positive integers
is a commutative semigroup. - 5. Let
be a binary operation on a set 
. An element 
is a neutral element if 
for all 
. If a neutral element exists, it is unique.
The set of strictly positive integers
under addition has no neutral element while the set of non‐negative integers 
has the neutral element 0. - 6. Let
be a semigroup with a neutral element 
. An element 
is invertible if there exists 
such that 
. Such an element 
is called the inverse of 
, and it is unique if it exists. The inverse is denoted 
in general, or 
when the operation is addition. - 7. A group is a semigroup
with a neutral element such that every element of 
is invertible. The group 
is called Abelian (or cummutative) if the operation 
is commutative. We will generally write that 
is a group under the operation 
or simply 
when the operation is clear from context.
All of the domains studied in Chapters 2–5 are examples of additive Abelian groups.
- 8. Let
be a group. The nonempty subset 
of 
is a subgroup of 
if 
is closed under the group operation and under inverses. If 
, then 
and 
. If 
is a finite group, then the number of elements in any subgroup divides the number of elements in the group (Lagrange's Theorem).
The set
for any 
is a subgroup of the additive Abelian group 
. We denote this subgroup 
. - 9. Let
be a subgroup of 
. For any 
, let
(B.1)
These are called respectively a left coset of
and a right coset of 
. If 
is an Abelian group, the left and right cosets are the same and we write 
for a coset of 
in 
.The set
is a coset of 
in 
for any 
. - 10. Let
be an Abelian group and let 
be a subgroup. For any 
, we say that 
if 
. Then 
is an equivalence relation, and the equivalence classes are the cosets of 
in 
. Any element of a coset can be used as a coset representative. The cosets of 
in 
form a partition of 
.
There are
cosets of 
in 
. We can use the elements 
as coset representatives. - 11. Let
be an Abelian group and 
a subgroup. Let 
denote the set of cosets of 
in 
. We define a binary operation 
on 
to be 
. This operation is well defined and 
is an Abelian group called the quotient group.
Note that these last two concepts can be defined on nonAbelian groups as well, but we do not use them explicitly in this book.