Page 24 - Advanced Linear Algebra

8 Advanced Linear Algebra

is an equivalence relation on , whose equivalence classes are the blocks
:
of .
F
This establishes a one-to-one correspondence between equivalence relations on
: : and partitions of .
The most important problem related to equivalence relations is that of finding an
efficient way to determine when two elements are equivalent. Unfortunately, in
most cases, the definition does not provide an efficient test for equivalence and
so we are led to the following concepts.

Definition Let — be an equivalence relation on . A function ¢ : : ¦ ; , where
; of — is any set, is called an invariant if it is constant on the equivalence
classes of — , that is,
— ¬ ² ³~ ² ³
and a complete invariant if it is constant and distinct on the equivalence
classes of — , that is,
— ¯ ² ³~ ² ³

A collection ¸ ÁÃ Á ¹ of invariants is called a complete system of

invariants if
— ¯ ² ³~ ² ³ for all ~ Á à Á

Definition Let — be an equivalence relation on . A subset * ‹ : is said to be
:
(
a set of canonical forms or just a canonical form) for — if for every  , :
there is exactly one  * such that — . Put another way, each equivalence
class under — contains exactly one member of .
*
Example 0.1 Define a binary relation — on ´ - % µ by letting ² % ³ — ² % ³ if and
only if ²%³ ~ ²%³ for some nonzero constant  - . This is easily seen to be
an equivalence relation. The function that assigns to each polynomial its degree
is an invariant, since
²%³ — ²%³ ¬ deg ² ²%³³ ~ deg ² ²%³³
However, it is not a complete invariant, since there are inequivalent polynomials
with the same degree. The set of all monic polynomials is a set of canonical
forms for this equivalence relation.

Example 0.2 We have remarked that row equivalence is an equivalence relation
on C Á ²-³ . Moreover, the subset of reduced row echelon form matrices is a
set of canonical forms for row equivalence, since every matrix is row equivalent
to a unique matrix in reduced row echelon form.