A.3 Equivalence relations · Matrix Theory

Much of the book classifies objects up to some notion of sameness: matrices up to row operations (Section 3.2.4), vector spaces up to isomorphism and square matrices up to change of basis (Section 4.5), vectors up to an element of a subspace (Section 4.6). Each notion is an equivalence relation, and each one cuts its set into classes. This section sets up the general language: equivalence classes, quotient sets, functions on quotient sets, and invariants.

A.3.1Equivalence relations

Definition A.3.1 (Equivalence relation). A relation on a set $𝑋$ is a subset $𝑅 \subseteq 𝑋 \times 𝑋$ ; we write $𝑥 \sim 𝑦$ for $(𝑥, 𝑦) \in 𝑅$ . A relation $\sim$ is an equivalence relation if it is

reflexive: $𝑥 \sim 𝑥$ for every $𝑥 \in 𝑋$ ;
symmetric: if $𝑥 \sim 𝑦$ , then $𝑦 \sim 𝑥$ ;
transitive: if $𝑥 \sim 𝑦$ and $𝑦 \sim 𝑧$ , then $𝑥 \sim 𝑧$ .

Example A.3.2 (Equivalence relations).

(a)Equality on any set.
(b)Let $𝑛 \geq 1$ . Congruence modulo $𝑛$ on $ℤ$ : $𝑥 \equiv 𝑦 (mod 𝑛)$ if $𝑛$ divides $𝑥 - 𝑦$ . It is reflexive since $𝑛 ∣ 0$ , symmetric since $𝑛 ∣ 𝑥 - 𝑦$ implies $𝑛 ∣ 𝑦 - 𝑥$ , and transitive since $𝑥 -$ $𝑧 =$ $(𝑥 - 𝑦) +$ $(𝑦 - 𝑧)$ .
(c)Any function $𝑓 : 𝑋 \to 𝑌$ defines the relation $𝑥 \underset{𝑓}{\sim} 𝑥^{'}$ if $𝑓 (𝑥) = 𝑓 (𝑥^{'})$ . It inherits the three properties from equality in $𝑌$ . For instance, “ $𝐴 \sim 𝐵$ if $rank 𝐴 = rank 𝐵$ ” is an equivalence relation on $𝐹^{𝑚 \times 𝑛}$ .
(d)Row equivalence of matrices (Proposition 3.2.22), similarity of square matrices (Proposition 4.5.24), isomorphism of vector spaces (Proposition 4.5.4), and congruence modulo a subspace $𝑈$ , $𝐯 - 𝐰 \in 𝑈$ (Remark 4.6.16).

Each axiom can fail on its own, and the failures of transitivity are the instructive ones.

Non-example A.3.3 (Relations that are not equivalence relations).

(a) $\leq$ on $ℝ$ is reflexive and transitive but not symmetric.
(b)On a vector space $𝑉$ , let $𝐯 \sim 𝐰$ if one of $𝐯, 𝐰$ is a scalar multiple of the other. This is reflexive and symmetric, but not transitive when $dim 𝑉 \geq 2$ : for independent $𝐯, 𝐰$ we have $𝐯 \sim 𝟎$ and $𝟎 \sim 𝐰$ , since $𝟎 = 0 𝐯 = 0 𝐰$ , but not $𝐯 \sim 𝐰$ . On $𝑉 ∖ {𝟎}$ , the relation becomes “ $𝐰 = 𝑐 𝐯$ for some $𝑐 \neq 0$ ”, which is an equivalence relation (Exercise A.3.16).
(c)On $𝐹^{𝑛 \times 𝑛}$ , let $𝐴 \sim 𝐵$ if $𝐴 𝐵 = 𝐵 𝐴$ . This is reflexive and symmetric, but every $𝐴$ commutes with $𝐼$ , so transitivity would make all matrices commute, which fails for $𝑛 \geq 2$ (Example 2.1.19).
(d)On $ℝ$ , let $𝑥 \sim 𝑦$ if $| 𝑥 - 𝑦 | \leq 1$ . Then $0 \sim 1 \sim 2$ but not $0 \sim 2$ . “Close to” is rarely transitive.

A.3.2Classes and partitions

Definition A.3.4 (Equivalence class). Let $\sim$ be an equivalence relation on $𝑋$ . The equivalence class of $𝑥 \in 𝑋$ is

[𝑥] = {𝑦 \in 𝑋 | 𝑥 \sim 𝑦} .

Any element of $[𝑥]$ is called a representative of the class.

For congruence modulo $𝑛$ , the class of $𝑥$ is $𝑥 +$ $𝑛 ℤ =$ ${𝑥 + 𝑛 𝑘 | 𝑘 \in ℤ}$ . For congruence modulo a subspace $𝑈$ , it is the coset $𝐯 + 𝑈$ (Lemma 4.6.14). For $\underset{𝑓}{\sim}$ , it is the fiber $𝑓^{- 1} (𝑓 (𝑥))$ (Definition A.1.3). The next lemma says that classes behave like cosets: two classes are equal or disjoint, and any element of a class can name it.

Lemma A.3.5 (Equal classes). Let

\sim

be an equivalence relation on

𝑋

and

𝑥, 𝑦 \in 𝑋

. The following are equivalent:

(i) $𝑥 \sim 𝑦$ ;
(ii) $[𝑥] = [𝑦]$ ;
(iii) $[𝑥] \cap [𝑦] \neq \emptyset$ .

Proof.routine

Uses. Definition A.3.1 (Equivalence relation), Definition A.3.4 (Equivalence class)

Techniques. Proving TFAE (Technique 2.7.1), Double containment (Technique 1.3.14)

Hint 1. Prove (i)

\Rightarrow

(ii)

\Rightarrow

(iii)

\Rightarrow

(i). Which axiom does each step use?

Hint 2. For (i)

\Rightarrow

(ii), take

𝑧 \in [𝑦]

and chain

𝑥 \sim 𝑦 \sim 𝑧

. For (iii)

\Rightarrow

(i), take

𝑧

in both classes and chain

𝑥 \sim 𝑧

with

𝑧 \sim 𝑦

Sketch. (i)

\Rightarrow

(ii): if

𝑥 \sim 𝑦

and

𝑦 \sim 𝑧

, then

𝑥 \sim 𝑧

, so

[𝑦] \subseteq [𝑥]

; by symmetry

[𝑥] \subseteq [𝑦]

. (ii)

\Rightarrow

(iii):

𝑥 \in [𝑥]

by reflexivity. (iii)

\Rightarrow

(i): if

𝑥 \sim 𝑧

and

𝑦 \sim 𝑧

, then

𝑥 \sim 𝑧 \sim 𝑦

(i) $\Rightarrow$ (ii). Suppose $𝑥 \sim 𝑦$ . If $𝑧 \in [𝑦]$ , then $𝑦 \sim 𝑧$ , so $𝑥 \sim 𝑧$ by transitivity, and $𝑧 \in [𝑥]$ . Thus $[𝑦] \subseteq [𝑥]$ . By symmetry $𝑦 \sim 𝑥$ , and the same argument gives $[𝑥] \subseteq [𝑦]$ .

(ii) $\Rightarrow$ (iii). By reflexivity $𝑥 \in [𝑥] = [𝑦]$ , so $𝑥 \in [𝑥] \cap [𝑦]$ .

(iii) $\Rightarrow$ (i). Let $𝑧 \in [𝑥] \cap [𝑦]$ , so $𝑥 \sim 𝑧$ and $𝑦 \sim 𝑧$ . By symmetry $𝑧 \sim 𝑦$ , and by transitivity $𝑥 \sim 𝑦$ . □

Definition A.3.6 (Partition). A partition of a set

𝑋

is a set

Π

of nonempty subsets of

𝑋

, called blocks, such that every element of

𝑋

lies in exactly one block.

Theorem A.3.7 (Equivalence relations are partitions). Let $𝑋$ be a set.

(a)If $\sim$ is an equivalence relation on $𝑋$ , its equivalence classes form a partition of $𝑋$ .
(b)If $Π$ is a partition of $𝑋$ , the relation “ $𝑥 \sim 𝑦$ if $𝑥$ and $𝑦$ lie in the same block” is an equivalence relation, and its classes are the blocks of $Π$ .
(c)These two constructions are inverse to each other. So equivalence relations on $𝑋$ correspond bijectively to partitions of $𝑋$ .

Proof.routine

Uses. Lemma A.3.5 (Equal classes), Definition A.3.6 (Partition), Definition A.3.1 (Equivalence relation)

Hint 1. For (a), every class is nonempty and

𝑥 \in [𝑥]

. Two classes that share an element are equal by Lemma A.3.5.

Hint 2. For (b), each axiom follows from “exactly one block”. For the classes, the class of

𝑥

is the block containing

𝑥

Hint 3. For (c), start from

\sim

, pass to its classes, and then to “same class”; by Lemma A.3.5,

𝑥

and

𝑦

are in the same class iff

𝑥 \sim 𝑦

Sketch. (a)

𝑥 \in [𝑥]

, and if

𝑥 \in [𝑦] \cap [𝑧]

, then

[𝑦] = [𝑥] = [𝑧]

. (b) Same block is reflexive, symmetric and transitive because each element is in exactly one block, and the class of

𝑥

is its block. (c) Partition then relation:

𝑥

𝑦

in the same class iff

𝑥 \sim 𝑦

, which recovers

\sim

. Relation then partition: by (b) the classes are the blocks.

(a) Each class $[𝑥]$ is nonempty, since $𝑥 \in [𝑥]$ by reflexivity, so every element lies in at least one class. If $𝑥 \in [𝑦]$ and $𝑥 \in [𝑧]$ , then $[𝑦] \cap [𝑧] \neq \emptyset$ , so $[𝑦] = [𝑧]$ by Lemma A.3.5. So $𝑥$ lies in exactly one class.

(b) Let $𝐵 (𝑥)$ denote the block containing $𝑥$ . Then $𝑥 \sim 𝑦$ means $𝐵 (𝑥) = 𝐵 (𝑦)$ , and this is an equivalence relation by Example A.3.2(c), applied to the function $𝑥 \mapsto 𝐵 (𝑥)$ . The class of $𝑥$ is ${𝑦 | 𝐵 (𝑦) = 𝐵 (𝑥)} =$ $𝐵 (𝑥)$ , since $𝑦 \in 𝐵 (𝑥)$ if and only if $𝐵 (𝑦) = 𝐵 (𝑥)$ .

(c) Start with $\sim$ , form the partition into classes, and let $\approx$ be “in the same class”. Then $𝑥 \approx 𝑦$ means that the class containing $𝑥$ , which is $[𝑥]$ , is the class containing $𝑦$ , which is $[𝑦]$ . By Lemma A.3.5 this happens if and only if $𝑥 \sim 𝑦$ , so $\approx$ is $\sim$ . In the other order, starting with a partition, (b) says that the classes of the relation are the blocks, so we recover the partition. □

For congruence modulo a subspace, (a) is Corollary 4.6.15. In practice, the theorem is used to define a partition by giving a relation, which is easier to check: three axioms instead of “exactly one block”.

A.3.3Quotient sets and well-defined functions

Definition A.3.8 (Quotient set). Let $\sim$ be an equivalence relation on $𝑋$ . The quotient set $𝑋 / \sim$ is the set of equivalence classes, and the quotient map is

𝑞 : 𝑋 \to 𝑋 / \sim, 𝑞 (𝑥) = [𝑥] .

The quotient map is surjective, and $𝑞 (𝑥) = 𝑞 (𝑦)$ if and only if $𝑥 \sim 𝑦$ (Lemma A.3.5), so passing to the quotient set turns $\sim$ into equality. That is the purpose of the construction: in $𝑋 / \sim$ , equivalent elements have become equal. The quotient space $𝑉 / 𝑈$ of Definition 4.6.20 is the quotient set for congruence modulo $𝑈$ , with a vector space structure added.

Example A.3.9 ( $ℤ / 𝑛 ℤ$ as a quotient set). Let $𝑛 \geq 2$ , and let $\sim$ be congruence modulo $𝑛$ . By Proposition A.2.4, each $𝑥 \in ℤ$ is congruent to exactly one $𝑟 \in {0, 1, \dots, 𝑛 - 1}$ , namely $𝑟 = 𝑥 mod 𝑛$ . So each class contains exactly one of $0, 1, \dots, 𝑛 - 1$ , and

ℤ / \sim = {[0], [1], \dots, [𝑛 - 1]},

with these $𝑛$ classes distinct. In Definition 1.1.19, $ℤ / 𝑛 ℤ$ was defined as the set ${0, 1, \dots, 𝑛 - 1}$ of remainders; we identify the remainder $𝑟$ with its class $[𝑟]$ . Under this identification, Lemma 1.1.21(a) says that $[𝑎] + [𝑏] = [𝑎 + 𝑏]$ and $[𝑎] [𝑏] = [𝑎 𝑏]$ . These formulas define operations on classes, because the right side does not depend on the representatives: if $𝑎 \sim 𝑎^{'}$ and $𝑏 \sim 𝑏^{'}$ , then $𝑛$ divides $(𝑎 + 𝑏) - (𝑎^{'} + 𝑏^{'})$ and $𝑎 𝑏 -$ $𝑎^{'} 𝑏^{'} =$ $𝑎 (𝑏 - 𝑏^{'}) +$ $(𝑎 - 𝑎^{'}) 𝑏^{'}$ .

The last sentence is the general issue with quotient sets. A function on $𝑋 / \sim$ is usually given by a formula in a representative, and the formula must not depend on which representative is used (Technique 4.6.18). The theorem below says exactly when such a formula defines a function, and what properties the function then has.

Theorem A.3.10 (Functions on a quotient set). Let $\sim$ be an equivalence relation on $𝑋$ with quotient map $𝑞 : 𝑋 \to 𝑋 / \sim$ , and let $𝑔 : 𝑋 \to 𝑌$ .

(a)There is a function $𝑔 : 𝑋 / \sim \to 𝑌$ with $𝑔 \circ 𝑞 = 𝑔$ if and only if $𝑔$ is constant on classes: $𝑥 \sim 𝑥^{'}$ implies $𝑔 (𝑥) = 𝑔 (𝑥^{'})$ . In that case $𝑔$ is unique, and $𝑔 ([𝑥]) = 𝑔 (𝑥)$ .
(b)Such a $𝑔$ is injective if and only if $𝑔 (𝑥) = 𝑔 (𝑥^{'})$ implies $𝑥 \sim 𝑥^{'}$ .
(c)Such a $𝑔$ is surjective if and only if $𝑔$ is surjective.

Proof.routine

Uses. Definition A.3.8 (Quotient set), Lemma A.3.5 (Equal classes), Definition A.1.2 (Function)

Techniques. Check that a definition does not depend on the representative (Technique 4.6.18), Uniqueness via two candidates (Technique 1.1.8)

Hint 1. If

𝑔 \circ 𝑞 = 𝑔

, then

𝑔 ([𝑥]) = 𝑔 (𝑥)

for every

𝑥

, which settles uniqueness and the formula.

Hint 2. For existence, define

𝑔 (𝐶)

for a class

𝐶

𝑔 (𝑥)

for any

𝑥 \in 𝐶

. What has to be checked for this to be a function?

Hint 3. For (b), translate:

𝑔 ([𝑥]) =

𝑔 ([𝑥^{'}])

means

𝑔 (𝑥) = 𝑔 (𝑥^{'})

, and

[𝑥] = [𝑥^{'}]

means

𝑥 \sim 𝑥^{'}

. For (c),

im 𝑔 = im 𝑔

because

𝑞

is surjective.

Sketch. If

𝑔 \circ 𝑞 = 𝑔

, then

𝑔 (𝑥) =

𝑔 ([𝑥]) =

𝑔 ([𝑥^{'}]) =

𝑔 (𝑥^{'})

when

𝑥 \sim 𝑥^{'}

, and

𝑔

is forced to be

[𝑥] \mapsto 𝑔 (𝑥)

. Conversely, if

𝑔

is constant on classes, this formula is independent of the representative, so it defines

𝑔

. Injectivity of

𝑔

reads “

𝑔 (𝑥) =

𝑔 (𝑥^{'}) \Rightarrow

[𝑥] =

[𝑥^{'}]

”. Since

𝑞

is surjective,

𝑔

and

𝑔

have the same image.

(a) Suppose $𝑔 \circ 𝑞 = 𝑔$ . Then $𝑔 ([𝑥]) = 𝑔 (𝑥)$ for every $𝑥$ , which determines $𝑔$ , since every class is $[𝑥]$ for some $𝑥$ . And if $𝑥 \sim 𝑥^{'}$ , then $[𝑥] = [𝑥^{'}]$ by Lemma A.3.5, so $𝑔 (𝑥) =$ $𝑔 ([𝑥]) =$ $𝑔 ([𝑥^{'}]) =$ $𝑔 (𝑥^{'})$ .

Conversely, suppose $𝑔$ is constant on classes. For a class $𝐶 \in 𝑋 / \sim$ , all $𝑥 \in 𝐶$ satisfy $𝑥 \sim 𝑥_{0}$ for a fixed $𝑥_{0} \in 𝐶$ , so $𝑔$ takes the single value $𝑔 (𝑥_{0})$ on $𝐶$ . Setting $𝑔 (𝐶)$ equal to this value defines a function $𝑋 / \sim \to 𝑌$ , and $𝑔 ([𝑥]) = 𝑔 (𝑥)$ because $𝑥 \in [𝑥]$ .

(b) $𝑔$ is injective if and only if $𝑔 ([𝑥]) =$ $𝑔 ([𝑥^{'}])$ implies $[𝑥] = [𝑥^{'}]$ for all $𝑥, 𝑥^{'} \in 𝑋$ , that is, if and only if $𝑔 (𝑥) = 𝑔 (𝑥^{'})$ implies $𝑥 \sim 𝑥^{'}$ .

(c) Since $𝑞$ is surjective, the values of $𝑔$ are exactly the values $𝑔 (𝑞 (𝑥)) = 𝑔 (𝑥)$ , so $im 𝑔 = im 𝑔$ . □

Taking $\sim$ to be $\underset{𝑓}{\sim}$ gives a factorization of every function.

Corollary A.3.11 (Factoring a function). Let $𝑓 : 𝑋 \to 𝑌$ , and let $\underset{𝑓}{\sim}$ be the relation $𝑓 (𝑥) = 𝑓 (𝑥^{'})$ . Then $𝑓 ([𝑥]) = 𝑓 (𝑥)$ is a well-defined bijection $𝑋 / \sim_{𝑓} \to im 𝑓$ . So $𝑓$ is the composite

𝑋 \overset{𝑞}{⟶} 𝑋 / \sim_{𝑓} \overset{𝑓}{⟶} im 𝑓 \overset{𝜄}{⟶} 𝑌

of a surjection, a bijection, and the injective inclusion $𝜄 (𝑦) = 𝑦$ .

Proof.routine

Uses. Theorem A.3.10 (Functions on a quotient set)

Hint 1. Apply Theorem A.3.10 to

𝑓

, viewed as a function

𝑋 \to im 𝑓

Hint 2. Both conditions, in (a) and in (b) of the theorem, are the definition of

\underset{𝑓}{\sim}

Sketch. For

𝑔 = 𝑓 : 𝑋 \to im 𝑓

, “

𝑥 \underset{𝑓}{\sim} 𝑥^{'} \Rightarrow

𝑔 (𝑥) =

𝑔 (𝑥^{'})

” and its converse both hold by definition of

\underset{𝑓}{\sim}

, and

𝑔

is surjective. So

𝑓

exists and is injective and surjective. Composing with

𝑞

and

𝜄

recovers

𝑓

View

𝑓

as a surjective function

𝑔 : 𝑋 \to im 𝑓

. By definition of

\underset{𝑓}{\sim}

𝑥 \underset{𝑓}{\sim} 𝑥^{'}

if and only if

𝑔 (𝑥) = 𝑔 (𝑥^{'})

. So

𝑔

is constant on classes, and

𝑓

exists by Theorem A.3.10(a); it is injective by (b) and surjective by (c). For every

𝑥

𝜄 (𝑓 (𝑞 (𝑥))) =

𝑓 (𝑥)

. □

For a linear map $𝑇 : 𝑉 \to 𝑊$ , $𝑇 (𝐯) = 𝑇 (𝐯^{'})$ if and only if $𝐯 - 𝐯^{'} \in ker 𝑇$ , so $\underset{𝑇}{\sim}$ is congruence modulo $ker 𝑇$ and $𝑉 / \sim_{𝑇}$ is the quotient space $𝑉 / ker 𝑇$ . The corollary then says that $𝑇$ is a bijection $𝑉 / ker 𝑇 \to im 𝑇$ , and the first isomorphism theorem (Theorem 4.6.34) adds that it is linear.

A.3.4Invariants and normal forms

To classify objects up to $\sim$ is to describe the quotient set $𝑋 / \sim$ : decide when two given objects are equivalent, and list one object from each class.

Definition A.3.12 (Invariant, normal form). Let $\sim$ be an equivalence relation on $𝑋$ .

An invariant of $\sim$ is a function $𝑔 : 𝑋 \to 𝑌$ that is constant on classes: $𝑥 \sim 𝑥^{'}$ implies $𝑔 (𝑥) = 𝑔 (𝑥^{'})$ .
An invariant is complete if moreover $𝑔 (𝑥) = 𝑔 (𝑥^{'})$ implies $𝑥 \sim 𝑥^{'}$ .
A set of normal forms for $\sim$ is a subset $𝑁 \subseteq 𝑋$ that contains exactly one element of each class.

By Theorem A.3.10, an invariant is a function on $𝑋 / \sim$ , and a complete invariant is an injective one, so it identifies $𝑋 / \sim$ with the set of its values. A set of normal forms $𝑁$ is mapped bijectively onto $𝑋 / \sim$ by $𝑞$ , and “the normal form of $𝑥$ ” is a complete invariant with values in $𝑁$ . The classification results of the book all have this shape:

For row equivalence on $𝐹^{𝑚 \times 𝑛}$ , the RREF is a complete invariant, and the matrices in RREF are normal forms (Corollary 3.3.18). So is the kernel (Corollary 3.3.20).
For isomorphism of finite-dimensional vector spaces, the dimension is a complete invariant (Theorem 4.5.6), and $𝐹^{0}, 𝐹^{1}, 𝐹^{2}, \dots$ are normal forms.
For the relation $𝐵 = 𝑃 𝐴 𝑄$ with $𝑃$ , $𝑄$ invertible, the rank is a complete invariant, with normal forms $(\begin{matrix} 𝐼_{𝑟} & 0 \\ 0 & 0 \end{matrix})$ (Theorem 3.5.27).
For similarity, rank, trace, and determinant are invariants (Proposition 4.5.27, Proposition 5.4.17), but even all of them together are not complete: $𝐼_{2}$ and $(\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix})$ share them and are not similar. Over $ℂ$ , the Jordan form, with a fixed ordering of the blocks, provides normal forms (Section 10.3).
For congruence modulo $𝑛$ , the remainder $𝑥 mod 𝑛$ is a complete invariant, with normal forms $0, 1, \dots, 𝑛 - 1$ (Example A.3.9).

Technique A.3.13 (Classify by a complete invariant). To decide when two objects are equivalent, find a quantity that equivalent objects share (an invariant), and then prove that it is complete. To prove that $𝑥$ and $𝑥^{'}$ are not equivalent, one invariant on which they differ is enough (Technique 4.5.29). To prove that they are equivalent, completeness is needed, and it is usually proved by reducing every object to a normal form that depends only on the invariant: if both $𝑥$ and $𝑥^{'}$ are equivalent to the same normal form, they are equivalent to each other by symmetry and transitivity.

Reach for it whenever a question asks “when are these the same up to $\dots$ ?” or “how many essentially different $\dots$ are there?”. The canonical example is Theorem 3.5.27, where row and column operations reduce every matrix to $(\begin{matrix} 𝐼_{𝑟} & 0 \\ 0 & 0 \end{matrix})$ with $𝑟$ the rank.

Used in 1 practice exercise

1 practice exercise.

Exercises

Exercise A.3.14.routine Decide which of the following are equivalence relations. For those that are, describe the classes.

(a)On $ℝ$ : $𝑥 \sim 𝑦$ if $𝑥 - 𝑦 \in ℤ$ .
(b)On $ℤ$ : $𝑥 \sim 𝑦$ if $𝑥 𝑦 > 0$ .
(c)On $𝐹^{𝑚 \times 𝑛}$ : $𝐴 \sim 𝐵$ if $rank 𝐴 = rank 𝐵$ .
(d)On $𝑉 ∖ {𝟎}$ , for a vector space $𝑉$ : $𝐯 \sim 𝐰$ if $span (𝐯) = span (𝐰)$ .
(e)On $𝑃 (𝑋)$ , for a set $𝑋$ with at least two elements: $𝐴 \sim 𝐵$ if $𝐴 \cap 𝐵 \neq \emptyset$ .

Solution.

Uses. Definition A.3.1 (Equivalence relation), Example A.3.2 (Equivalence relations)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Relations of the form “

𝑔 (𝑥) = 𝑔 (𝑦)

” are always equivalence relations (Example A.3.2(c)). Which of these have that form?

Hint 2. Check reflexivity at the “degenerate” elements:

0

in (b) and

\emptyset

in (e).

Sketch. (a) Yes, classes

𝑥 + ℤ

, one for each

𝑥 \in [0, 1)

. (b) No:

0 \sim 0

fails. (c) Yes,

\underset{rank}{\sim}

; classes are the matrices of rank

𝑟

0 \leq 𝑟 \leq min (𝑚, 𝑛)

. (d) Yes,

\underset{𝑔}{\sim}

for

𝑔 (𝐯) = span (𝐯)

; classes are the lines through

𝟎

with

𝟎

removed. (e) No:

\emptyset \sim \emptyset

fails, and so does transitivity.

(a) Yes. $𝑥 - 𝑥 = 0 \in ℤ$ ; if $𝑥 - 𝑦 \in ℤ$ , then $𝑦 - 𝑥 \in ℤ$ ; and $𝑥 -$ $𝑧 =$ $(𝑥 - 𝑦) +$ $(𝑦 - 𝑧)$ . The class of $𝑥$ is $𝑥 + ℤ$ . Each class contains exactly one element of $[0, 1)$ , namely $𝑥 - ⌊ 𝑥 ⌋$ , so the classes are indexed by $[0, 1)$ .

(b) No: $0 \cdot 0 = 0$ , so $0 \sim 0$ fails. (On $ℤ ∖ {0}$ it is an equivalence relation, “same sign”, with two classes.)

(c) Yes: it is $\underset{𝑔}{\sim}$ for $𝑔 = rank$ . The classes are the sets of matrices of rank $𝑟$ for $𝑟 =$ $0,$ $1,$ $\dots,$ $min (𝑚, 𝑛)$ , each nonempty (the matrix $(\begin{matrix} 𝐼_{𝑟} & 0 \\ 0 & 0 \end{matrix})$ has rank $𝑟$ ).

(d) Yes: it is $\underset{𝑔}{\sim}$ for $𝑔 (𝐯) = span (𝐯)$ . The class of $𝐯$ is $span (𝐯) ∖ {𝟎} =$ ${𝑐 𝐯 | 𝑐 \neq 0}$ , a line through $𝟎$ with $𝟎$ removed. Compare Non-example A.3.3(b).

(e) No: $\emptyset \cap \emptyset = \emptyset$ , so $\emptyset \sim \emptyset$ fails. Transitivity fails too: for distinct $𝑎, 𝑏 \in 𝑋$ , ${𝑎} \sim {𝑎, 𝑏}$ and ${𝑎, 𝑏} \sim {𝑏}$ , but ${𝑎} \cap {𝑏} = \emptyset$ .

Exercise A.3.15.standard Count the equivalence relations on

[3]

and on

[4]

Solution.

Uses. Theorem A.3.7 (Equivalence relations are partitions)

Hint 1. By Theorem A.3.7, count partitions instead.

Hint 2. Sort the partitions by their block sizes. For

[4]

the possible block sizes are

4

;

3 + 1

;

2 + 2

;

2 + 1 + 1

;

1 + 1 + 1 + 1

Sketch. Count partitions.

[3]

: one with one block, three of type

2 + 1

, one into singletons:

5

[4]

1 + 4 + 3 + 6 + 1 = 15

by block sizes

4

3 + 1

2 + 2

2 + 1 + 1

1 + 1 + 1 + 1

By Theorem A.3.7, equivalence relations on $𝑋$ correspond to partitions of $𝑋$ , so we count partitions by their block sizes.

For $[3]$ : one partition with a single block; three of type $2 + 1$ (choose the singleton); one into three singletons. Total $5$ .

For $[4]$ : one of type $4$ ; four of type $3 + 1$ (choose the singleton); three of type $2 + 2$ (the block containing $1$ is ${1, 𝑗}$ for $𝑗 = 2, 3, 4$ ); six of type $2 + 1 + 1$ (choose the pair, $(\binom{4}{2}) = 6$ ); one into singletons. Total $1 + 4 + 3 + 6 + 1 = 15$ .

Exercise A.3.16.standard Let $𝐹$ be a field and $𝑛 \geq 0$ . On $𝐹^{𝑛 + 1} ∖ {𝟎}$ , let $𝐯 \sim 𝐰$ if $𝐰 = 𝑐 𝐯$ for some nonzero $𝑐 \in 𝐹$ .

(a)Show that $\sim$ is an equivalence relation, and describe its classes in terms of one-dimensional subspaces of $𝐹^{𝑛 + 1}$ .
(b)If $𝐹$ has $𝑞$ elements, show that the quotient set has $(𝑞^{𝑛 + 1} - 1) / (𝑞 - 1) =$ $1 +$ $𝑞 +$ $\dots +$ $𝑞^{𝑛}$ elements.

Solution.

Uses. Definition A.3.1 (Equivalence relation), Theorem A.3.7 (Equivalence relations are partitions), Exercise A.1.28, Proposition 1.2.35 (Zero products)

Hint 1. For symmetry use

𝑐^{- 1}

; for transitivity multiply the scalars.

Hint 2. Each class has the same number of elements. How many nonzero multiples does a nonzero vector have?

Hint 3. The classes partition a set of

𝑞^{𝑛 + 1} - 1

elements into blocks of size

𝑞 - 1

Sketch. Reflexive (

𝑐 = 1

), symmetric (

𝐯 = 𝑐^{- 1} 𝐰

), transitive (

𝐮 = 𝑐 𝑑 𝐯

). The class of

𝐯

span (𝐯) ∖ {𝟎}

, and the map

𝑐 \mapsto 𝑐 𝐯

from

𝐹 ∖ {0}

onto it is injective, so each class has

𝑞 - 1

elements. So there are

(𝑞^{𝑛 + 1} - 1) / (𝑞 - 1)

classes.

(a) Reflexivity: $𝐯 = 1 𝐯$ . Symmetry: if $𝐰 = 𝑐 𝐯$ with $𝑐 \neq 0$ , then $𝐯 = 𝑐^{- 1} 𝐰$ . Transitivity: if $𝐰 = 𝑐 𝐯$ and $𝐮 = 𝑑 𝐰$ , then $𝐮 = (𝑑 𝑐) 𝐯$ with $𝑑 𝑐 \neq 0$ . The class of $𝐯$ is ${𝑐 𝐯 | 𝑐 \neq 0} =$ $span (𝐯) ∖ {𝟎}$ , the line through $𝐯$ with $𝟎$ removed (by Proposition 1.2.35, $𝑐 𝐯 = 𝟎$ only for $𝑐 = 0$ ). So the classes correspond to the one-dimensional subspaces of $𝐹^{𝑛 + 1}$ . The quotient set is the projective space of $𝐹^{𝑛 + 1}$ , and the coordinates of a representative are the homogeneous coordinates of its class (Definition 4.7.41).

(b) For $𝐯 \neq 𝟎$ , the map $𝐹 ∖ {0} \to [𝐯]$ , $𝑐 \mapsto 𝑐 𝐯$ , is surjective by definition and injective since $𝑐 𝐯 = 𝑑 𝐯$ gives $(𝑐 - 𝑑) 𝐯 = 𝟎$ , so $𝑐 = 𝑑$ . So every class has $𝑞 - 1$ elements. The set $𝐹^{𝑛 + 1} ∖ {𝟎}$ has $𝑞^{𝑛 + 1} - 1$ elements (Exercise A.1.28), and by Theorem A.3.7 it is the disjoint union of the classes. If there are $𝑁$ classes, then $𝑁 (𝑞 - 1) = 𝑞^{𝑛 + 1} - 1$ , so $𝑁 =$ $(𝑞^{𝑛 + 1} - 1) / (𝑞 - 1) =$ $1 +$ $𝑞 +$ $\dots +$ $𝑞^{𝑛}$ . For example, $𝔽_{2}^{3}$ has $7$ one-dimensional subspaces.

Exercise A.3.17.standard Let

𝑅

and

𝑆

be equivalence relations on

𝑋

, viewed as subsets of

𝑋 \times 𝑋

. Prove or disprove: (a)

𝑅 \cap 𝑆

is an equivalence relation; (b)

𝑅 \cup 𝑆

is an equivalence relation.

Solution.

Uses. Definition A.3.1 (Equivalence relation)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Each axiom is a closure condition. Which of them survive intersections?

Hint 2. For unions, take congruence mod

2

and congruence mod

3

ℤ

, and look at

0

2

5

Sketch. (a) True: each axiom for

𝑅 \cap 𝑆

follows from the same axiom for

𝑅

and for

𝑆

. (b) False: with

𝑅

congruence mod

2

and

𝑆

mod

3

(0, 2) \in 𝑅

and

(2, 5) \in 𝑆

, but

(0, 5) \notin 𝑅 \cup 𝑆

(a) True. $(𝑥, 𝑥)$ lies in $𝑅$ and in $𝑆$ . If $(𝑥, 𝑦) \in 𝑅 \cap 𝑆$ , then $(𝑦, 𝑥) \in 𝑅$ and $(𝑦, 𝑥) \in 𝑆$ . If $(𝑥, 𝑦),$ $(𝑦, 𝑧) \in$ $𝑅 \cap$ $𝑆$ , then $(𝑥, 𝑧) \in 𝑅$ by transitivity of $𝑅$ , and $(𝑥, 𝑧) \in 𝑆$ likewise. In terms of classes, the class of $𝑥$ under $𝑅 \cap 𝑆$ is the intersection of its classes under $𝑅$ and $𝑆$ .

(b) False. On $ℤ$ , let $𝑅$ be congruence modulo $2$ and $𝑆$ congruence modulo $3$ . Then $(0, 2) \in 𝑅$ and $(2, 5) \in 𝑆$ , so both lie in $𝑅 \cup 𝑆$ , but $5 - 0$ is divisible by neither $2$ nor $3$ , so $(0, 5) \notin 𝑅 \cup 𝑆$ . Transitivity fails. ( $𝑅 \cup 𝑆$ is still reflexive and symmetric.)

Exercise A.3.18.routine Find the error in the following argument.

Claim: A relation that is symmetric and transitive is reflexive. Proof: Let $𝑥 \in 𝑋$ and pick $𝑦$ with $𝑥 \sim 𝑦$ . By symmetry $𝑦 \sim 𝑥$ , and by transitivity, $𝑥 \sim 𝑦$ and $𝑦 \sim 𝑥$ give $𝑥 \sim 𝑥$ .

Solution.

Uses. Definition A.3.1 (Equivalence relation)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Is there always a

𝑦

with

𝑥 \sim 𝑦

Hint 2. Try the empty relation on a nonempty set.

Sketch. The step “pick

𝑦

with

𝑥 \sim 𝑦

” assumes such a

𝑦

exists. The empty relation on

{1}

is symmetric and transitive (vacuously) but not reflexive. The argument does show

𝑥 \sim 𝑥

for every

𝑥

related to something.

The argument assumes that some

𝑦

with

𝑥 \sim 𝑦

exists, and nothing guarantees this. For instance, the empty relation

𝑅 = \emptyset

𝑋 = {1}

is symmetric and transitive, since their hypotheses are never satisfied, but

1 \sim 1

fails. What the argument does prove is that a symmetric and transitive relation is reflexive on the set of elements that are related to at least one element. So in checking an equivalence relation, reflexivity cannot be skipped.

Exercise A.3.19.standard Let

𝑚, 𝑛 \geq 2

, and write

{[𝑎]}_{𝑛}

for the class of

𝑎 \in ℤ

under congruence modulo

𝑛

. Show that the formula

𝑓 ({[𝑎]}_{𝑛}) = {[𝑎]}_{𝑚}

defines a function

ℤ / 𝑛 ℤ \to ℤ / 𝑚 ℤ

if and only if

𝑚

divides

𝑛

. When it does, show that

𝑓

is surjective, and bijective only if

𝑚 = 𝑛

Solution.

Uses. Theorem A.3.10 (Functions on a quotient set), Example A.3.9 ( $ℤ / 𝑛 ℤ$ as a quotient set)

Techniques. Check that a definition does not depend on the representative (Technique 4.6.18)

Hint 1. By Theorem A.3.10, the formula defines a function iff

𝑎 \equiv 𝑎^{'} (mod 𝑛)

implies

𝑎 \equiv 𝑎^{'} (mod 𝑚)

Hint 2. For “only if”, use the pair

𝑎 = 0

𝑎^{'} = 𝑛

Hint 3. Surjectivity:

{[𝑎]}_{𝑚} = 𝑓 ({[𝑎]}_{𝑛})

. Count the elements for bijectivity.

Sketch. Well defined iff

𝑛 ∣ 𝑎 - 𝑎^{'}

implies

𝑚 ∣ 𝑎 - 𝑎^{'}

. If

𝑚 ∣ 𝑛

, this holds; conversely,

𝑎 = 𝑛

𝑎^{'} = 0

gives

𝑚 ∣ 𝑛

𝑓

is surjective since

𝑞_{𝑚} = 𝑓 \circ 𝑞_{𝑛}

is. A bijection needs

𝑛 =

| ℤ / 𝑛 ℤ | =

| ℤ / 𝑚 ℤ | =

𝑚

Let $𝑔 : ℤ \to ℤ / 𝑚 ℤ$ , $𝑔 (𝑎) = {[𝑎]}_{𝑚}$ . By Theorem A.3.10(a), the formula defines a function $𝑓$ with $𝑓 ({[𝑎]}_{𝑛}) = 𝑔 (𝑎)$ if and only if $𝑔$ is constant on classes mod $𝑛$ , that is, if and only if $𝑛 ∣ 𝑎 - 𝑎^{'}$ implies $𝑚 ∣ 𝑎 - 𝑎^{'}$ for all $𝑎, 𝑎^{'} \in ℤ$ .

If $𝑚 ∣ 𝑛$ and $𝑛 ∣ 𝑎 - 𝑎^{'}$ , then $𝑚 ∣ 𝑎 - 𝑎^{'}$ . Conversely, if the implication holds, apply it to $𝑎 = 𝑛$ and $𝑎^{'} = 0$ : since $𝑛 ∣ 𝑛$ , we get $𝑚 ∣ 𝑛$ .

Suppose $𝑚 ∣ 𝑛$ . Since $𝑔$ is surjective, so is $𝑓$ (Theorem A.3.10(c)). By Example A.3.9, $ℤ / 𝑛 ℤ$ has $𝑛$ elements and $ℤ / 𝑚 ℤ$ has $𝑚$ , so if $𝑓$ is bijective, then $𝑛 = 𝑚$ (Corollary A.1.18). Conversely, for $𝑚 = 𝑛$ , $𝑓$ is the identity. For example, reduction mod $2$ is a well-defined function $ℤ / 4 ℤ \to ℤ / 2 ℤ$ , but “reduction mod $3$ ” is not: ${[0]}_{4} = {[4]}_{4}$ while ${[0]}_{3} \neq {[4]}_{3}$ .

Exercise A.3.20.hard Let $𝑅$ be any relation on $𝑋$ . Define $𝑥 \approx 𝑦$ if there is a finite sequence $𝑥 =$ $𝑥_{0},$ $𝑥_{1},$ $\dots,$ $𝑥_{𝑘} =$ $𝑦$ , with $𝑘 \geq 0$ , such that for each $𝑖$ , $(𝑥_{𝑖 - 1}, 𝑥_{𝑖}) \in 𝑅$ or $(𝑥_{𝑖}, 𝑥_{𝑖 - 1}) \in 𝑅$ .

(a)Show that $\approx$ is an equivalence relation containing $𝑅$ , and that it is contained in every equivalence relation that contains $𝑅$ . It is the equivalence relation generated by $𝑅$ .
(b)Let $𝑅$ be the relation on $𝐹^{𝑚 \times 𝑛}$ given by “ $𝐵$ is obtained from $𝐴$ by one elementary row operation”. Show that the equivalence relation generated by $𝑅$ is row equivalence (Definition 3.2.21).

Solution.

Uses. Definition A.3.1 (Equivalence relation), Definition 3.2.21 (Row equivalence), Proposition 3.2.10 (Inverses of elementary matrices)

Techniques. Double containment (Technique 1.3.14)

Hint 1. For (a): the empty chain (

𝑘 = 0

) gives reflexivity; reversing a chain gives symmetry; concatenating gives transitivity.

Hint 2. For minimality, if

\sim

is an equivalence relation containing

𝑅

, show by induction on

𝑘

that each

𝑥_{0} \sim 𝑥_{𝑘}

, using symmetry for the backward steps.

Hint 3. For (b), elementary row operations can be undone by elementary row operations (Proposition 3.2.10), so a backward step is also a forward step.

Sketch. (a) Chains of length

0

, reversed chains, and concatenated chains give the three axioms; a one-step chain shows

𝑅 \subseteq \approx

. If

\sim \supseteq 𝑅

is an equivalence relation, each step of a chain is in

\sim

(by symmetry for backward steps), and transitivity along the chain gives

𝑥 \sim 𝑦

. (b) By (a) the generated relation is the smallest equivalence relation containing

𝑅

; row equivalence contains

𝑅

and is an equivalence relation, and conversely a row equivalence

𝐵 = 𝐸_{𝑘} \dots 𝐸_{1} 𝐴

is a chain of forward

𝑅

-steps.

(a) Reflexivity: the chain $𝑥_{0} = 𝑥$ with $𝑘 = 0$ . Symmetry: a chain $𝑥_{0}, \dots, 𝑥_{𝑘}$ from $𝑥$ to $𝑦$ , read backwards, is a chain from $𝑦$ to $𝑥$ , since the condition on consecutive pairs is symmetric. Transitivity: a chain from $𝑥$ to $𝑦$ followed by one from $𝑦$ to $𝑧$ is a chain from $𝑥$ to $𝑧$ . If $(𝑥, 𝑦) \in 𝑅$ , then $𝑥, 𝑦$ is a chain with $𝑘 = 1$ , so $𝑅 \subseteq \approx$ .

Now let $\sim$ be an equivalence relation with $𝑅 \subseteq \sim$ , and let $𝑥 = 𝑥_{0}, \dots, 𝑥_{𝑘} = 𝑦$ be a chain. We show $𝑥_{0} \sim 𝑥_{𝑗}$ by induction on $𝑗$ . For $𝑗 = 0$ this is reflexivity. If $𝑥_{0} \sim 𝑥_{𝑗 - 1}$ , then $(𝑥_{𝑗 - 1}, 𝑥_{𝑗}) \in 𝑅$ gives $𝑥_{𝑗 - 1} \sim 𝑥_{𝑗}$ , and $(𝑥_{𝑗}, 𝑥_{𝑗 - 1}) \in 𝑅$ gives $𝑥_{𝑗} \sim 𝑥_{𝑗 - 1}$ , hence $𝑥_{𝑗 - 1} \sim 𝑥_{𝑗}$ by symmetry. Either way $𝑥_{0} \sim 𝑥_{𝑗}$ by transitivity. So $𝑥 \approx 𝑦$ implies $𝑥 \sim 𝑦$ .

(b) Row equivalence is an equivalence relation (Proposition 3.2.22) and contains $𝑅$ , so by (a) it contains the generated relation $\approx$ . Conversely, if $𝐵 = 𝐸_{𝑘} \dots 𝐸_{1} 𝐴$ with $𝐸_{𝑖}$ elementary, then $𝐴,$ $𝐸_{1} 𝐴,$ $𝐸_{2} 𝐸_{1} 𝐴,$ $\dots,$ $𝐵$ is a chain in which each step is one elementary row operation, so $𝐴 \approx 𝐵$ . Hence the two relations are equal. The backward steps allowed in $\approx$ add nothing here because each elementary operation is undone by another one (Proposition 3.2.10). This is exactly why row equivalence is symmetric.

More practice

The practice bank has 3 exercises on this section’s topics.