Page 23 - Advanced Linear Algebra

Preliminaries 7

Equivalence Relations
The concept of an equivalence relation plays a major role in the study of
matrices and linear transformations.

:
:
Definition Let be a nonempty set. A binary relation — on is called an
equivalence relation on if it satisfies the following conditions:
:
1)(Reflexivity )
—
for all  : .
2)(Symmetry )
— ¬ —

for all Á  : .
3)(Transitivity )
— Á — ¬ —

for all Á Á  : .

Definition Let — be an equivalence relation on . For :  : , the set of all
elements equivalent to is denoted by

´ µ~¸ : “ — ¹

and called the equivalence class of .

:
Theorem 0.8 Let — be an equivalence relation on . Then
1)  ´ µ ¯  ´ µ ¯ ´ µ ~ ´ µ
)
2 For any Á  : , we have either ´ µ ~ ´ µ or ´ µ q ´ µ ~ J .
Definition A partition of a nonempty set is a collection ¸ ( Á Ã Á ( ¹ of
:
nonempty subsets of , called the blocks of the partition, for which
:
)
1 (q ( ~ J for all £

) .
2 :~ ( r Ä r (
The following theorem sheds considerable light on the concept of an
equivalence relation.
Theorem 0.9
1 Let — ) be an equivalence relation on . Then the set of distinct equivalence
:
:
classes with respect to — are the blocks of a partition of .
)
F
2 Conversely, if is a partition of , the binary relation — defined by
:
— if and lie in the same block of F