Page 613 - Discrete Mathematics and Its Applications

592 9 / Relations

Solution: Because R consists of those ordered pairs (a i ,b j ) with m ij = 1, it follows that

R ={(a 1 ,b 2 ), (a 2 ,b 1 ), (a 2 ,b 3 ), (a 2 ,b 4 ), (a 3 ,b 1 ), (a 3 ,b 3 ), (a 3 ,b 5 )}. ▲

The matrix of a relation on a set, which is a square matrix, can be used to determine whether
therelationhascertainproperties.RecallthatarelationR onAisreflexiveif(a, a) ∈ R whenever
a ∈ A. Thus, R is reflexive if and only if (a i ,a i ) ∈ R for i = 1, 2,...,n. Hence, R is reflexive
if and only if m ii = 1, for i = 1, 2,...,n. In other words, R is reflexive if all the elements on
1
1 the main diagonal of M R are equal to 1, as shown in Figure 1. Note that the elements off the
1 main diagonal can be either 0 or 1.
The relation R is symmetric if (a, b) ∈ R implies that (b, a) ∈ R. Consequently, the
relation R on the set A ={a 1 ,a 2 ,...,a n } is symmetric if and only if (a j ,a i ) ∈ R whenever
1
1 (a i ,a j ) ∈ R. In terms of the entries of M R , R is symmetric if and only if m ji = 1 whenever
m ij = 1. This also means m ji = 0 whenever m ij = 0. Consequently, R is symmetric if and
FIGURE 1 The only if m ij = m ji , for all pairs of integers i and j with i = 1, 2,...,n and j = 1, 2,...,n.
Zero–One Matrix Recalling the definition of the transpose of a matrix from Section 2.6, we see that R is symmetric
for a Reflexive if and only if
Relation. (Off
Diagonal Ele- M R = (M R ) ,
t
ments Can
Be0or1.) that is, if M R is a symmetric matrix. The form of the matrix for a symmetric relation is illustrated
in Figure 2(a).
The relation R is antisymmetric if and only if (a, b) ∈ R and (b, a) ∈ R imply that a = b.
Consequently, the matrix of an antisymmetric relation has the property that if m ij = 1 with
i = j, then m ji = 0. Or, in other words, either m ij = 0or m ji = 0 when i = j. The form of
the matrix for an antisymmetric relation is illustrated in Figure 2(b).

1 1
0
0 0
1 0
0
0 1
(a) Symmetric (b) Antisymmetric

FIGURE 2 The Zero–One Matrices for
Symmetric and Antisymmetric Relations.

EXAMPLE 3 Suppose that the relation R on a set is represented by the matrix

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

Is R reflexive, symmetric, and/or antisymmetric?

Solution: Because all the diagonal elements of this matrix are equal to 1, R is reflexive. Moreover,
because M R is symmetric, it follows that R is symmetric. It is also easy to see that R is not
antisymmetric. ▲

The Boolean operations join and meet (discussed in Section 2.6) can be used to find the
matrices representing the union and the intersection of two relations. Suppose that R 1 and R 2
, respectively. The matrix
are relations on a set A represented by the matrices M R 1 and M R 2