Page 614 - Discrete Mathematics and Its Applications

9.3 Representing Relations 593

has
representing the union of these relations hasa1inthe positions where either M R 1 or M R 2
a 1. The matrix representing the intersection of these relations hasa1inthe positions where
have a 1. Thus, the matrices representing the union and intersection of these
both M R 1 and M R 2
relations are
and .
M R 1 ∪R 2 = M R 1 ∨ M R 2 M R 1 ∩R 2 = M R 1 ∧ M R 2

EXAMPLE 4 Suppose that the relations R 1 and R 2 on a set A are represented by the matrices

⎡ ⎤ ⎡ ⎤
1 0 1 1 0 1
= ⎣ 1 0 and = ⎣ 0 1 .
M R 1 0 ⎦ M R 2 1 ⎦
0 1 0 1 0 0
What are the matrices representing R 1 ∪ R 2 and R 1 ∩ R 2 ?

Solution: The matrices of these relations are

⎡ ⎤
10 1
= ⎣ 1 1 ,
M R 1 ∪R 2 = M R 1 ∨ M R 2 1 ⎦
1 1 0

⎡ ⎤
1 0 1
= ⎣ 0 0 .
M R 1 ∩R 2 = M R 1 ∧ M R 2 0 ⎦
0 0 0
▲
We now turn our attention to determining the matrix for the composite of relations. This
matrix can be found using the Boolean product of the matrices (discussed in Section 2.6) for
these relations. In particular, suppose that R is a relation from A to B and S is a relation
from B to C. Suppose that A, B, and C have m, n, and p elements, respectively. Let the zero–
one matrices for S ◦R, R, and S be M S ◦ R =[t ij ], M R =[r ij ], and M S =[s ij ], respectively
(these matrices have sizes m × p, m × n, and n × p, respectively). The ordered pair (a i ,c j )
belongs to S ◦R if and only if there is an element b k such that (a i ,b k ) belongs to R and (b k ,c j )
belongs to S. It follows that t ij = 1 if and only if r ik = s kj = 1 for some k. From the definition
of the Boolean product, this means that

M S ◦R = M R M S .

EXAMPLE 5 Find the matrix representing the relations S ◦R, where the matrices representing R and S are

⎡ ⎤ ⎡ ⎤
1 0 1 0 1 0
M R = ⎣ 1 1 0 ⎦ and M S = ⎣ 0 0 1 ⎦ .
0 0 0 1 0 1

Solution: The matrix for S ◦R is
⎡ ⎤
1 1 1
M S ◦R = M R M S = ⎣ 0 1 1 ⎦ .
0 0 0
▲