Forward to §2.3 problems | Back to §2.1 problems | Up | Table of Contents | About this document


§ 2.2 Equivalence Relations: Solved problems

14. On the set { (a,b) } of all ordered pairs of positive integers, define (x1,y1) ~ (x2,y2) if x1y2 = x2y1. Show that this defines an equivalence relation.

Solution: We first show that the reflexive law holds. Given an ordered pair (a,b), we have ab = ba, and so (a,b) ~ (a,b).

We next check the symmetric law. Given (a1,b1) and (a2,b2) with (a1,b1) ~ (a2,b2), we have a1b2 = a2b1, and so a2b1 = a1b2, which shows that (a2,b2) ~ (a1,b1).

Finally, we verify the transitive law. Given (a1,b1), (a2,b2), and (a3,b3) with (a1,b1) ~ (a2,b2) and (a2,b2) ~ (a3,b3), we have the equations a1b2 = a2b1 and a2b3 = a3b2. If we multiply the first equation by b3 and the second equation by b1, we get a1b2b3 = a2b1b3 = a3b1b2. Since b2 0 we can cancel to obtain a1b3 = a3b1, showing that (a1,b1) ~ (a3,b3).     (Click here for a more details.)

Next problem | Next solution | Up | Table of Contents







































































15. On the set C of complex numbers, define z1 ~ z2 if ||z1|| = ||z2||. Show that ~ is an equivalence relation.

Note: Remember that if z = a+bi is a complex number, then ||z|| = (a2+b2).

Solution: The reflexive, symmetric, and transitive laws can be easily verified since ~ is defined in terms of an equality, and equality is itself an equivalence relation.

Comment: It is also possible to prove that ~ is an equivalence relation by observing that it is the equivalence relation that comes from the function f : C -> R defined by f(z) = ||z||, for all z in C.

Next problem | Next solution | Up | Table of Contents







































































16. Let u be a fixed vector in R3, and assume that u has length 1. For vectors v and w, define v ~ w if v · u = w · u, where · denotes the standard dot product. Show that ~ is an equivalence relation, and give a geometric description of the equivalence classes of ~ .

Solution: The reflexive, symmetric, and transitive laws for the relation ~ really depend on an equality, and can easily be verified. Since u has length 1, v · u represents the length of the projection of v onto the line determined by u. Thus two vectors are equivalent if and only if they lie in the same plane perpendicular to u. It follows that the equivalence classes of ~ are the planes in R3 that are perpendicular to u.

Comment: Instead of proving directly that ~ is an equivalence relation, you could just note that it is the equivalence relation defined by the function L : R3 -> R, where L(v) = v · u, for all v in R3.

Next problem | Next solution | Up | Table of Contents







































































17. For the function f: R -> R defined by f(x) = x2, for all x in R, describe the equivalence relation on R that is determined by f.

Solution: The equivalence relation determined by f is defined by setting a ~ b if f(a) = f(b), so a ~ b if and only if a2 = b2, or, a ~ b if and only if |a| = |b|.

Next problem | Next solution | Up | Table of Contents







































































18. For the linear transformation L: R3 -> R3 defined by

L(x,y,z) = (x + y + z, x + y + z, x + y + z) ,

for all (x,y,z) in R3, give a geometric description of the partition of R3 that is determined by L.

Solution: Since (a1,a2,a3) ~ (b1,b2,b3) if L (a1,a2,a3) = L (b1,b2,b3), it follows from the definition of L that (a1,a2,a3) ~ (b1,b2,b3) if and only if a1 + a2 + a3 = b1 + b2 + b3. For example, { (x,y,z) | L(x,y,z) = (0,0,0) } is the plane through the origin whose equation is x + y + z = 0, with normal vector (1,1,1). The other subsets in the partition of R3 defined by L are planes parallel to this one. Thus the partition consists of the planes perpendicular to the vector (1,1,1).

Next problem | Next solution | Up | Table of Contents







































































19. Define the formula f: Z12 -> Z12 by f ( [x]12 ) = [x]122, for all [x]12 in Z12. Show that the formula f defines a function. Find the image of f and the set Z12 / f of equivalence classes determined by f.

Solution: The formula for f is well-defined since if [x1]12 = [x2]12, then x1 x2 (mod 12), and so x12 x22 (mod 12), which shows that f ( [x1]12 ) = f ( [x2]12 ).

To compute the images of f we have

[0]122 = [0]12,
[± 1]122 = [1]12,
[± 2]122 = [4]12,
[± 3]122 = [9]12,
[± 4]122 = [4]12,
[± 5]122 = [1]12, and
[6]122 = [0]12.

Thus f (Z12) = { [0]12, [1]12, [4]12, [9]12 }.
The corresponding equivalence classes determined by f are
{ [0]12, [6]12 },
{ [± 1]12, [± 5]12 },
{ [± 2]12, [± 4]12 },
{ [± 3]12 }.

Next problem | Next solution | Up | Table of Contents







































































20. On the set of all n × n matrices over R, define A ~ B if there exists an invertible matrix P such that PAP-1 = B. Check that ~ defines an equivalence relation.

Solution: We have always have A ~ A since IAI-1 = A, where I is the n × n identity matrix.
Next, suppose that A ~ B. Then PAP-1 = B for some invertible matrix P, and so we get
A = P-1B(P-1)-1.
Finally, suppose that A ~ B and B ~ C. Then PAP-1 = B and QBQ-1 = C, for some invertible matrices P and Q. Substituting gives
Q(PAP-1)Q-1 = (QP)A(QP)-1 = C, and therefore A ~ C.


Forward to §2.3 | Forward to §2.3 problems | Up | Table of Contents







































































14. (detailed proof) To check that we have an equivalence relation, we will use the less formal definition :

Let S be a set. Then ~ defines an equivalence relation on S if and only if

(i) the reflexive law holds :
given any x in S, we always have x ~ x ;

(ii) the symmetric law holds :
given any x and y in S, if x ~ y , then y ~ x ;

(iii) the transitive law holds :
given any x, y and z in S, if x ~ y and y ~ z , then x ~ z .

We should first take a closer look at the way that ~ is defined. We are given that (x1,y1) ~ (x2,y2) if x1y2 = x2y1. Sometimes it helps to put everything into words: two ordered pairs are equivalent if the first component of the first pair times the second component of the second pair equals the first component of the second pair times the second component of the first pair. For example, to find pairs equivalent to (2,3) we need to solve 2 · y2 = x2 · 3. We could have (2,3) ~ (4,6) or (2,3) ~ (6,9), and so on.

Now here is the proof, in three parts.

(i) We first show that the reflexive law holds. That is, given any x in S, we must check that x ~ x.

Since the set S consists of ordered pairs of positive integers, let x = (a,b). To show that (a,b) ~ (a,b), we need to use the general condition that (x1,y1) ~ (x2,y2) if x1y2 = x2y1. In this case we have x1 = a, y1 = b, x2 = a, and y2 = b, so after we substitute these values into the general formula, we end up having to check that ab = ba. This equation does hold for all choices of a and b, because multiplication of integers satisfies the commutative law. This allows us conclude that (a,b) ~ (a,b), so x ~ x, and we have verified that the reflexive law holds.

(ii) We next check the symmetric law. We must prove that given any x and y in S, with x ~ y , we must also have y ~ x . Let x = (a1,b1) and y = (a2,b2), and assume that x ~ y . In the definition of ~ we take x1 = a1, y1 = b1, x2 = a2, and y2 = b2, Then by the formula that defines ~ we have the condition x1y2 = x2y1, which translates into a1b2 = a2b1.

Next, we will look at exactly what it is that we must prove. To show that y ~ x, in the definition of ~ we need to take x1 = a2, y1 = b2, x2 = a1, and y2 = b1, and so we must check that (x1,y1) ~ (x2,y2), or a2b1 = a1b2.

Now you can see the connection between what we are given and what we have to prove. We are given a1b2 = a2b1 and must prove that a2b1 = a1b2. All we need to do is change the order, which we can do because we are working with multiplication of ordinary integers. We conclude that the reflexive law holds because (a2,b2) ~ (a1,b1), and thus y ~ x.

(iii) Finally, we verify the transitive law. We can assume that we are given x = (a1,b1), y = (a2,b2), and z =(a3,b3) with x ~ y and y ~ z. Then (a1,b1) ~ (a2,b2) and (a2,b2) ~ (a3,b3), and if we interpret the general definition of ~ for these particular elements, we get the equations a1b2 = a2b1 and a2b3 = a3b2.

What do we have to prove? To check that x ~ z, we need (a1,b1) ~ (a3,b3), and so we must prove that a1b3 = a3b1.

If we multiply the first equation by b3 and the second equation by b1, we get a1b2b3 = a2b1b3 and b1a2b3 = b1a3b2. By rearranging terms in the second equation, and using the transitive property of equality, we get a1b2b3 = b1a3b2. Since b2 0 (the original assumption was that we are working with positive integers) we can cancel to get a1b3 = a3b1. (Note that we had to use the commutativity of multiplication several times in this chain of reasoning.) Finally, this shows that (a1,b1) ~ (a3,b3), so x ~ z, and the transitive law holds.

This completes the proof, since we have verified that ~ satisfies the reflexive, symmetric, and transitive laws.

Next problem | Next solution | Up | Table of Contents