Page 617 - Discrete Mathematics and Its Applications

596 9 / Relations

Because loops are not present at all the vertices of the directed graph of S, this relation is not
reflexive. It is symmetric and not antisymmetric, because every edge between distinct vertices
is accompanied by an edge in the opposite direction. It is also not hard to see from the directed
graph that S is not transitive, because (c, a) and (a, b) belong to S,but (c, b) does not belong
to S. ▲

Exercises

1. Representeachoftheserelationson{1, 2, 3}withamatrix 9. How many nonzero entries does the matrix representing
(with the elements of this set listed in increasing order). the relation R on A ={1, 2, 3,..., 100} consisting of the
first 100 positive integers have if R is
a) {(1, 1), (1, 2), (1, 3)}
b) {(1, 2), (2, 1), (2, 2), (3, 3)} a) {(a, b) | a> b}? b) {(a, b) | a = b}?
c) {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)} c) {(a, b) | a = b + 1}? d) {(a, b) | a = 1}?
d) {(1, 3), (3, 1)} e) {(a, b) | ab = 1}?
2. Represent each of these relations on {1, 2, 3, 4} with a 10. How many nonzero entries does the matrix representing
matrix (with the elements of this set listed in increasing the relation R on A ={1, 2, 3,..., 1000} consisting of
order). the first 1000 positive integers have if R is
a) {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} a) {(a, b) | a ≤ b}?
b) {(1, 1), (1, 4), (2, 2), (3, 3), (4, 1)} b) {(a, b) | a = b ± 1}?
c) {(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), c) {(a, b) | a + b = 1000}?
d) {(a, b) | a + b ≤ 1001}?
(3, 4), (4, 1), (4, 2), (4, 3)}
e) {(a, b) | a = 0}?
d) {(2, 4), (3, 1), (3, 2), (3, 4)}
3. List the ordered pairs in the relations on {1, 2, 3} corre- 11. How can the matrix for R, the complement of the
sponding to these matrices (where the rows and columns relation R, be found from the matrix representing R,
correspond to the integers listed in increasing order). when R is a relation on a finite set A?
12. How can the matrix for R −1 , the inverse of the
⎡ ⎤ ⎡ ⎤
1 0 1 0 1 0
relation R, be found from the matrix representing R,
a) ⎣ 0 1 0 ⎦ b) ⎣ 0 1 0 ⎦
when R is a relation on a finite set A?
1 0 1 0 1 0
13. Let R be the relation represented by the matrix
⎡ ⎤
1 1 1
⎡ ⎤
c) ⎣ 10 1 ⎦ 0 1 1
1 1 1 M R = ⎣ 1 1 0 ⎦ .
4. List the ordered pairs in the relations on {1, 2, 3, 4} corre- 1 0 1
sponding to these matrices (where the rows and columns
correspond to the integers listed in increasing order). Find the matrix representing
2
⎡ ⎤ ⎡ ⎤ a) R −1 . b) R. c) R .
1 1 0 1 1 1 1 0
1 0 1 0
⎢ ⎥ ⎢ 0 1 0 0 ⎥ 14. Let R 1 and R 2 be relations on a set A represented by the
a) ⎢ ⎥ b) ⎢ ⎥ matrices
0 1 1 1
⎣ ⎦ ⎣ 0 0 1 1 ⎦
1 0 1 1 1 0 0 1 ⎡ 0 1 0 ⎤ ⎡ 0 1 0 ⎤
⎡ ⎤
0 1 0 1 M R 1 = ⎣ 1 1 1 ⎦ and M R 2 = ⎣ 0 1 1 ⎦ .
⎢ 1 0 1 0 ⎥ 1 0 0 1 1 1
c) ⎢ ⎥
⎣ 0 1 0 1 ⎦
1 0 1 0 Find the matrices that represent
5. How can the matrix representing a relation R on a set A a) R 1 ∪ R 2 . b) R 1 ∩ R 2 . c) R 2 R 1 .
◦
◦
be used to determine whether the relation is irreflexive? d) R 1 R 1 . e) R 1 ⊕ R 2 .
6. How can the matrix representing a relation R on a set A 15. Let R be the relation represented by the matrix
be used to determine whether the relation is asymmetric?
⎡ ⎤
0 1 0
7. Determine whether the relations represented by the ma-
M R = ⎣ 0 0 1 ⎦ .
trices in Exercise 3 are reflexive, irreflexive, symmetric,
antisymmetric, and/or transitive. 1 1 0
8. Determine whether the relations represented by the ma- Find the matrices that represent
trices in Exercise 4 are reflexive, irreflexive, symmetric, 2 3 4
antisymmetric, and/or transitive. a) R . b) R . c) R .