Chapter 9 Relation

Relationships between elements of sets are represented using the structure called a relation, which is
just a subset of the Cartesian product of the sets. Relations can be used to solve problems such as
determining which pairs of cities are linked by airline flights in a network, finding a viable order for the
different phases of a complicated project, or producing a useful way to store information in computer
databases.

9.1 Relations and Their Properties

The most direct way to express a relationship between elements of two sets is to use ordered pairs
made up of two related elements.

Definition 9.1
Let A and B be sets. A binary relation from A to B is a subset of A × B.

a binary relation from A to B is a set R of ordered pairs where the first element of each ordered
pair comes from A and the second element comes from B. We use the notation  R b to denote that
(, b) ∈ R and  R  b to denote that (, b) ∈
/ R. Moreover, when (, b) belongs to R,  is said to be
related to b by R.

Relations can be represented graphically, as shown in Figure 1, using arrows to represent ordered
pairs. Another way to represent this relation is to use a table, which is also done in Figure 9.1.

EXAMPLE 1
Let A = {0, 1, 2} and B = {, b}. Then {(0, ), (0, b), (1, ), (2, b)} is a relation from A to B. This
means, for instance, that 0 R , but that 1 R
 b.

Figure 9.1. Displaying the Ordered Pairs in the Relation R from Example 1

Discrete Mathematics 1 Computing Department, UNISEL

9.1. RELATIONS AND THEIR PROPERTIES CHAPTER 9. RELATION

9.1.1 Relations on a Set

Relations from a set A to itself are of special interest.

Definition 9.2
A relation on a set A is a relation from A to A.

In other words, a relation on a set A is a subset of A × A.

EXAMPLE 2
Let A be the set {1, 2, 3, 4}. Which ordered pairs are in the relation R = {(, b) |  divides b}?

Solution: Because (, b) is in R if and only if  and b are positive integers not exceeding 4 such that 
divides b, we see that

R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.

Figure 9.2. Displaying the Ordered Pairs in the Relation R from Example 2
EXAMPLE 3
Consider these relations on the set of integers:

R1 = {(, b) |  ≤ b},
R2 = {(, b) |  > b},
R3 = {(, b) |  = b or  = −b},
R4 = {(, b) | || = |b|},
R5 = {(, b) |  = b + 1},
R6 = {(, b) | | + b| ≤ 3}.

Which of these relations contains each of the pairs (1, 1), (1, 2), (2, 1), (1, −1) and (2, 2)?
Solution: The pair (1, 1) is in R1 , R3 , R4 , and R6 ; (1, 2) is in R1 and R6 ; (2, 1) is in R2 , R5 , and R6 ;
(1, −1) is in R2 , R3 , and R6 ; and finally, (2, 2) is in R1 , R3 , and R4 .

Computing Department, UNISEL 2 Discrete Mathematics

CHAPTER 9. RELATION 9.1. RELATIONS AND THEIR PROPERTIES

9.1.2 Properties of Relations

There are several properties that are used to classify relations on a set. In some relations an element is
always related to itself.

Definition 9.3
A relation R on a set A is called reflexive if (, ) ∈ R for every element  ∈ A.

EXAMPLE 4
Consider the following relations on {1, 2, 3, 4}:

R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)},
R2 = {(1, 1), (1, 2), (2, 1)},
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)},
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)},
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)},
R6 = {(3, 4)}.

Which of these relations are reflexive?

Solution: Since the set is A = {1, 2, 3, 4}, a relation must contain the following four pairs to be reflex-
ive:
{(1, 1), (2, 2), (3, 3), (4, 4)}

Relation Required Pairs? (1,1), (2,2), (3,3), (4,4) Reflexive?

R1 Contains (1, 1), (2, 2), (4, 4). Missing (3, 3). No
R2 Contains (1, 1), (2, 2). Missing (3, 3) and (4, 4). No
R3 Contains (1, 1), (2, 2), (3, 3), (4, 4). Yes
R4 Contains none of the required pairs. No
R5 Contains (1, 1), (2, 2), (3, 3), (4, 4). Yes
R6 Contains none of the required pairs. No

The relations R3 and R5 are reflexive because they both contain all pairs of the form (, ), namely,
(1, 1), (2, 2), (3, 3), and (4, 4). The other relations are not reflexive because they do not contain all
of these ordered pairs. In particular, R1 , R2 , R4 , and R6 are not reflexive because (3, 3) is not in any
of these relations.

Discrete Mathematics 3 Computing Department, UNISEL

9.1. RELATIONS AND THEIR PROPERTIES CHAPTER 9. RELATION

Definition 9.4
A relation R on a set A is called symmetric if (b, ) ∈ R whenever (, b) ∈ R, for all , b ∈ A.

EXAMPLE 5
Consider the following relations on {1, 2, 3, 4}:

R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)},
R2 = {(1, 1), (1, 2), (2, 1)},
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)},
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)},
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)},
R6 = {(3, 4)}.

Which of these relations are Symmetric?

Solution: We check if every pair (, b) where  ̸= b has its reverse (b, ) in the relation:

Relation Pairs to Check (and their reverses) Symmetric?

R1 Has (3, 4), but lacks (4, 3). Has (1, 2) and (2, 1). No
Has (4, 1) but lacks (1, 4).
R2 Has (1, 2) and has (2, 1). All non-loop pairs are Yes
symmetric.
R3 Has (1, 2) and has (2, 1). Has (1, 4) and has Yes
(4, 1). All non-loop pairs are symmetric.
R4 Has (2, 1), but lacks (1, 2). Has (3, 1), but lacks No
(1, 3), etc.
R5 Has (1, 2), but lacks (2, 1). Has (1, 3), but lacks No
(3, 1), etc.
R6 Has (3, 4), but lacks (4, 3). No
The relations R2 and R3 are symmetric, because in each case (b, ) belongs to the relation when-
ever (, b) does. For R2 , the only thing to check is that both (2, 1) and (1, 2) are in the relation. For R3 ,
it is necessary to check that both (1, 2) and (2, 1) belong to the relation, and (1, 4) and (4, 1) belong
to the relation. The reader should verify that none of the other relations is symmetric. This is done by
finding a pair (, b) such that it is in the relation but (b, ) is not.

Computing Department, UNISEL 4 Discrete Mathematics

CHAPTER 9. RELATION 9.1. RELATIONS AND THEIR PROPERTIES

Definition 9.5
A relation R on a set A such that for all , b ∈ A, if (, b) ∈ R and (b, ) ∈ R then  = b is called
antisymmetric.

EXAMPLE 6
Consider the following relations on {1, 2, 3, 4}:

R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)},
R2 = {(1, 1), (1, 2), (2, 1)},
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)},
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)},
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)},
R6 = {(3, 4)}.

Which of these relations are Antiymmetric?

Solution: We check if the relation contains any pair (, b) and its reverse (b, ) where  ̸= b. If it does,
the relation is not antisymmetric.

Relation Bidirectional Non-Loop Pairs? Antisymmetric?

R1 Contains (1, 2) and (2, 1). Since 1 ̸= 2, No
this violates the condition.
R2 Contains (1, 2) and (2, 1). Since 1 ̸= 2, No
this violates the condition.
R3 Contains (1, 2) and (2, 1). Since 1 ̸= 2, No
this violates the condition.
R4 Contains only unidirectional non-loop Yes
pairs, like (2, 1) but not (1, 2).
R5 Contains only unidirectional non-loop Yes
pairs, like (1, 2) but not (2, 1).
R6 Contains only (3, 4) and not (4, 3). Yes

R4 , R5 , and R6 are all antisymmetric. For each of these relations there is no pair of elements  and
b with  ̸= b such that both (, b) and (b, ) belong to the relation. The reader should verify that none
of the other relations is antisymmetric. This is done by finding a pair (, b) with  ̸= b such that (, b)
and (b, ) are both in the relation.

Discrete Mathematics 5 Computing Department, UNISEL

9.1. RELATIONS AND THEIR PROPERTIES CHAPTER 9. RELATION

Definition 9.6
A relation R on a set A is called transitive if whenever (, b) ∈ R and (b, c) ∈ R, then (, c) ∈ R,
for all , b, c ∈ A.

EXAMPLE 7
Consider the following relations on {1, 2, 3, 4}:

R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)},
R2 = {(1, 1), (1, 2), (2, 1)},
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)},
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)},
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)},
R6 = {(3, 4)}.

Which of these relations are transitive?

Solution: We check for pairs (, b) and (b, c) that do not have the corresponding direct pair (, c) in
the relation. If we find one, the relation is not transitive.
Relation Transitivity Check Transitive?
R1 Has (4, 1) and (1, 2). Should have No
(4, 2), but (4, 2) ∈
/ R1 .
R2 Has (2, 1) and (1, 2). Should have No
(2, 2), but (2, 2) ∈
/ R2 .
R3 Has (4, 1) and (1, 2). Should have No
(4, 2), but (4, 2) ∈
/ R3 .
R4 Contains no chains of length 2 (e.g., Yes
(, b) and (b, c)). If the premise is false,
the implication is true by default (vacu-
ously true).
R5 Has (1, 2) and (2, 3). Should have Yes
(1, 3), and (1, 3) ∈ R5 . Check all pairs:
No violation is found.
R6 Contains only (3, 4). Contains no chains Yes
of length 2. (Vacuously true).
R4 , R5 , and R6 are transitive. For each of these relations, we can show that it is transitive by verifying
that if (, b) and (b, c) belong to this relation, then (, c) also does. For instance, R4 is transitive,
because (3, 2) and (2, 1), (4, 2) and (2, 1), (4, 3) and (3, 1), and (4, 3) and (3, 2) are the only such
sets of pairs, and (3, 1), (4, 1), and (4, 2) belong to R4 . The reader should verify that R5 and R6 are
transitive.
R1 is not transitive because (3, 4) and (4, 1) belong to R1 , but (3, 1) does not. R2 is not transitive
because (2, 1) and (1, 2) belong to R2 , but (2, 2) does not. R3 is not transitive because (4, 1) and
(1, 2) belong to R3 , but (4, 2) does not.

Computing Department, UNISEL 6 Discrete Mathematics

CHAPTER 9. RELATION 9.1. RELATIONS AND THEIR PROPERTIES

9.1.3 Combining Relations

Because relations from A to B are subsets of A × B, two relations from A to B can be combined in any
way two sets can be combined.

Definition 9.7
Four fundamental set operations applied to two relations, R1 and R2 . Since relations are sets of
ordered pairs, these are standard set theory operations.

Expression Operation Meaning / Set Notation

R1 ∪ R2 Union The relation consists of all ordered pairs that are
in R1 or R2 (or both).
R1 ∪ R2 = {(, b) | (, b) ∈ R1 or (, b) ∈ R2 }
R1 ∩ R2 Intersection The relation consists of all ordered pairs that are
in both R1 and R2 .
R1 ∩ R2 = {(, b) | (, b) ∈ R1 and (, b) ∈
R2 }
R1 − R2 Set Difference The relation consists of all ordered pairs that are
in R1 but NOT in R2 .
R1 − R2 = {(, b) | (, b) ∈ R1 and (, b) ∈
/
R2 }
R2 − R1 Set Difference The relation consists of all ordered pairs that are
in R2 but NOT in R1 .
R2 − R1 = {(, b) | (, b) ∈ R2 and (, b) ∈
/
R1 }
R1 ⊕ R2 Symmetric Difference The relation it includes all pairs that are in exactly
one of the two relations, but excludes any pairs
they have in common.R1 but NOT R2 and R2 but
NOT R1 R1 ⊕ R2 = (R1 ∪ R2 ) − (R1 ∩ R2 ).
R1 ⊕ R2 = (R1 ∪ R2 ) − (R1 ∩ R2 )

Discrete Mathematics 7 Computing Department, UNISEL

9.1. RELATIONS AND THEIR PROPERTIES CHAPTER 9. RELATION

R1 R2

Union (R1 ∪ R2 )

R1 R2

Intersection (R1 ∩ R2 )

R1 R2

Difference (R1 − R2 )

R1 R2

Difference (R2 − R1 )

R1 R2

Symmetric Difference (R1 ⊕ R2 )

Computing Department, UNISEL 8 Discrete Mathematics

CHAPTER 9. RELATION 9.1. RELATIONS AND THEIR PROPERTIES

EXAMPLE 8
Let A = {1, 2, 3} and B = {1, 2, 3, 4}. The relations R1 = {(1, 1), (2, 2), (3, 3)} and R2 =
{(1, 1), (1, 2), (1, 3), (1, 4)} can be combined to obtain

R1 ∪ R2 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3)},
R1 ∩ R2 = {(1, 1)},
R1 − R2 = {(2, 2), (3, 3)},
R2 − R1 = {(1, 2), (1, 3), (1, 4)}.

Solution:

(3,3) (1,3) (3,3) (1,3) (3,3) (1,3)

R (1,1) R2 R (1,1) R2 R (1,1) R2
(2,2) 1 (1,4) (2,2) 1 (1,4) (2,2) 1 (1,4)
(1,2) (1,2) (1,2)

Union: R1 ∪ R2 = {1, 2, 3, 4, 5, 6} Intersection: R1 ∩ R2 Difference: R1 − R2

(3,3) (1,3) (2,2) (1,3)

R (1,1) R2 R (1,1) R2
(2,2) 1 (1,4) (3,3) 1 (1,4)
(1,2) (1,2)

Difference: R2 − R1 Symmetric Diff: R1 ⊕ R2

Definition 9.8
Let R be a relation from a set A to a set B and S a relation from B to a set C. The composite of
R and S is the relation consisting of ordered pairs (, c), where  ∈ A, c ∈ C, and for which there
exists an element b ∈ B such that (, b) ∈ R and (b, c) ∈ S. We denote the composite of R and
S by S ◦ R.

 R : (, b) b S : (b, c) c

S ◦ R : (, c)

Set A Set B Set C

Discrete Mathematics 9 Computing Department, UNISEL

9.1. RELATIONS AND THEIR PROPERTIES CHAPTER 9. RELATION

EXAMPLE 9: What is the composite of the relations R and S, where R is the relation from {1, 2, 3} to
{1, 2, 3, 4} with
R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)}
and S is the relation from {1, 2, 3, 4} to {0, 1, 2} with

S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)} ?

Solution:

B = {1, 2, 3, 4}
A = {1, 2, 3}
C = {0, 1, 2}
1
1 0
2
2 1
3
3 2
4

S ◦ R is constructed using all ordered pairs in R and ordered pairs in S, where the second element
of the ordered pair in R agrees with the first element of the ordered pair in S. For example, the ordered
pairs (2, 3) in R and (3, 1) in S produce the ordered pair (2, 1) in S ◦ R. Computing all the ordered pairs
in the composite, we find

S ◦ R = {(1, 0), (1, 1), (2, 1), (2, 2), (3, 0), (3, 1)}.

Composing the Parent Relation with Itself

Let R be the relation on the set of all people such that (, b) ∈ R if person  is a parent of person
b. Then (, c) ∈ R ◦ R if and only if there is a person b such that (, b) ∈ R and (b, c) ∈ R, that is,
if and only if there is a person b such that  is a parent of b and b is a parent of c. In other words,
(, c) ∈ R ◦ R if and only if  is a grandparent of c.

Definition 9.9
Let R be a relation on the set A. The powers Rn , n = 1, 2, 3, . . ., are defined recursively by

R1 = R and R n+1 = Rn ◦ R.

The definition shows that

R2 = R ◦ R, R3 = R2 ◦ R = (R ◦ R) ◦ R, and so on.

EXAMPLE: Let
R = {(1, 1), (2, 1), (3, 2), (4, 3)}.
Find the powers Rn , n = 2, 3, 4, . . ..

Computing Department, UNISEL 10 Discrete Mathematics

CHAPTER 9. RELATION 9.1. RELATIONS AND THEIR PROPERTIES

Solution:

R R R R
Set A Set A Set A Set A Set A

1 1 1 1 1

2 2 2 2 2

3 3 3 3 3

4 4 4 4 4

Because R2 = R ◦ R, we find that

R2 = {(1, 1), (2, 1), (3, 1), (4, 2)}.

Furthermore, because R3 = R2 ◦ R,

R3 = {(1, 1), (2, 1), (3, 1), (4, 1)}.

Additional computation shows that R4 is the same as R3 , so

R4 = {(1, 1), (2, 1), (3, 1), (4, 1)}.

It also follows that

Rn = R3 for n = 4, 5, 6, 7, . . . .

EXERCISE
1. List the ordered pairs in the relation R from

A = {0, 1, 2, 3, 4} to B = {0, 1, 2, 3},

where (, b) ∈ R if and only if

a)  = b.
b)  + b = 4.
c)  > b.
d)  | b.
e) gcd(, b) = 1.
f) lcm(, b) = 2.

Discrete Mathematics 11 Computing Department, UNISEL

9.1. RELATIONS AND THEIR PROPERTIES CHAPTER 9. RELATION

2. For each of these relations on the set {1, 2, 3, 4}, decide whether it is reflexive, whether it is sym-
metric, whether it is antisymmetric, and whether it is transitive.
a) {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}
b) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
c) {(2, 4), (4, 2)}
d) {(1, 2), (2, 3), (3, 4)}
e) {(1, 1), (2, 2), (3, 3), (4, 4)}
f) {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)}

Definition 9.10
A relation R on the set A is irreflexive if for every  ∈ A, (, ) ∈
/ R. That is, R is irreflexive if no
element in A is related to itself.

3. Which relations in Exercise 2 are irreflexive?

Definition 9.11
A relation R is called asymmetric if (, b) ∈ R implies that (b, ) ∈
/ R.

4. Which relations in Exercise 2 are asymmetric?

Definition 9.12
Let R be a relation from a set A to a set B.
The inverse relation from B to A, denoted by R−1 , is the set of ordered pairs

R−1 = {(b, ) | (, b) ∈ R}.

The complementary relation R is the set of ordered pairs

R = {(, b) | (, b) ∈
/ R}.

5. Let R be the relation R = {(, b) |  < b} on the set of integers. Find

(a) R−1
(b) R
6. Let R be the relation R = {(, b) |  divides b} on the set of positive integers. Find
(a) R−1
(b) R

Computing Department, UNISEL 12 Discrete Mathematics

CHAPTER 9. RELATION 9.1. RELATIONS AND THEIR PROPERTIES

7. Let R1 = {(1, 2), (2, 3), (3, 4)}, and

R2 = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (3, 4)} be relations from {1, 2, 3} to
{1, 2, 3, 4}. Find
(a) R1 ∪ R2
(b) R1 ∩ R2
(c) R1 − R2
(d) R2 − R1
(e) R1 ⊕ R2
8. Let R = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 1)} and S = {(2, 1), (3, 1), (3, 2), (4, 2)}. Find S ◦ R.

8. Let R be the relation on the set {1, 2, 3, 4, 5} containing the ordered pairs

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

Find:
a) R2
b) R3
c) R4
d) R5

Discrete Mathematics 13 Computing Department, UNISEL

9.2. REPRESENTING RELATIONS CHAPTER 9. RELATION

9.2 Representing Relations

There are many ways to represent a relation between finite sets. One way is to list its ordered pairs.
Another way to represent a relation is to use a table. In this section we will discuss the alternative
methods for representing relations using zero–one matrices.

9.2.1 Representing Relations Using Matrices

A relation between finite sets can be represented using a zero–one matrix. Suppose that R is a relation
from
A = {1 , 2 , . . . , m } to B = {b1 , b2 , . . . , bn }.
(Here the elements of the sets A and B have been listed in a particular, but arbitrary, order. Further-
more, when A = B, we use the same ordering for A and B.)
The relation R can be represented by the matrix MR = [mj ], where
(
1, if ( , bj ) ∈ R,
mj =
0, if ( , bj ) ∈
/ R.
In other words, the zero–one matrix representing R has a 1 as its (, j) entry when  is related to bj ,
and a 0 in this position if  is not related to bj . (Such a representation depends on the orderings used
for A and B.)
Example 1. Suppose that A = {1, 2, 3} and B = {1, 2}. Let R be the relation from A to B containing
(, b) if  ∈ A, b ∈ B, and  > b. What is the matrix representing R?
Solution using matrix Because Because R = {(2, 1), (3, 1), (3, 2)}, the matrix for R is
 
0 0
 
MR = 
 1 0 .

1 1
The 1s in MR show that the pairs (2, 1), (3, 1), and (3, 2) belong to R. The 0s show that no other
pairs belong to R.
Solution using table Because R = {(2, 1), (3, 1), (3, 2)}, the relation matrix can be represented in
a table as follows:

R 1 2
1 0 0
2 1 0
3 1 1

Computing Department, UNISEL 14 Discrete Mathematics

CHAPTER 9. RELATION 9.2. REPRESENTING RELATIONS

9.2.2 Identify Properties of Relations using matrix relation

The matrix of a relation on a set, which is a square matrix, can be used to determine whether the relation
has certain properties.
Recall that a relation R on A is reflexive if (, ) ∈ R whenever  ∈ A. Thus, R is reflexive if and only
if ( ,  ) ∈ R for  = 1, 2, . . . , n.
Hence, R is reflexive if and only if m = 1, for  = 1, 2, . . . , n. In other words, R is reflexive if all the
elements on the main diagonal of MR are equal to 1, as shown in Figure 1.
Note that the elements off the main diagonal can be either 0 or 1.
 
1 ∗ ∗ ∗ ∗
 
∗ 1 ∗ ∗ ∗
 
 
MR = 
∗ ∗ 1 ∗ ∗
 
∗ ∗ ∗ 1 ∗
 
∗ ∗ ∗ ∗ 1

Figure 1. The Zero–One Matrix for a Reflexive Relation. (Off–diagonal elements can be 0 or 1.)

The relation R is symmetric if (, b) ∈ R implies that (b, ) ∈ R. Consequently, the relation R on
the set A = {1 , 2 , . . . , n } is symmetric if and only if (j ,  ) ∈ R whenever ( , j ) ∈ R.
In terms of the entries of MR , R is symmetric if and only if mj = 1 whenever mj = 1. This also
means mj = 0 whenever mj = 0. Consequently, R is symmetric if and only if

mj = mj , for all , j = 1, 2, . . . , n.

Recalling the definition of the transpose of a matrix from Section 2.6, we see that R is symmetric if
and only if
MR = (MR )T ,
that is, if MR 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 (, b) ∈ R and (b, ) ∈ R imply that  = b.
Consequently, the matrix of an antisymmetric relation has the property that if mj = 1 with  ̸= j,
then mj = 0. In other words, either mj = 0 or mj = 0 when  ̸= j.
The form of the matrix for an antisymmetric relation is illustrated in Figure 2(b).
   
1 1 0 1 0 0
   
(a) Symmetric: MR = 
 1 1 0 
 (b) Antisymmetric: MR = 
 0 1 0 

0 0 1 0 0 1

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

Discrete Mathematics 15 Computing Department, UNISEL

9.2. REPRESENTING RELATIONS CHAPTER 9. RELATION

9.2.3 Operations on Relations using matrix relation

Suppose that R1 and R2 are relations on a set A represented by the matrices MR1 and MR2 , respectively.
The matrix representing the union of these relations has a 1 in the positions where either MR1 or MR2
has a 1. The matrix representing the intersection of these relations has a 1 in the positions where both
MR1 and MR2 have a 1.
Thus, the matrices representing the union and intersection of these relations are

MR1 ∪R2 = MR1 ∨ MR2 and MR1 ∩R2 = MR1 ∧ MR2 .

Example 4 Suppose that the relations R1 and R2 on a set A are represented by the matrices
   
1 0 1 1 0 1
   
M R1 = 
 1 0 0 
 and M R2 = 
 0 1 1 .

0 1 0 1 0 0
What are the matrices representing R1 ∪ R2 and R1 ∩ R2 ?
Solution: The matrices of these relations are
 
1 0 1
 
MR1 ∪R2 = MR1 ∨ MR2 = 
1 1 1,
1 1 0
 
1 0 1
 
MR1 ∩R2 = MR1 ∧ MR2 = 
0 0 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 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 MS◦R = [tj ], MR = [rj ], and MS = [sj ], respectively
(these matrices have sizes m × p, m × n, and n × p, respectively).
The ordered pair ( , cj ) belongs to S ◦ R if and only if there is an element bk such that ( , bk )
belongs to R and (bk , cj ) belongs to S. It follows that tj = 1 if and only if rk = skj = 1 for some k.
From the definition of the Boolean product, this means that

MS◦R = MR ⊙ MS .

Example. Find the matrix representing the relation S◦R, where the matrices representing R and S are
   
0 0 0 0 1 0
   
   
MR =  1 0 1  , M S = 0 0 1 .
  
   
1 1 0 1 0 1

Computing Department, UNISEL 16 Discrete Mathematics

CHAPTER 9. RELATION 9.2. REPRESENTING RELATIONS

Solution: The matrix for S ◦ R is

     
0 0 0 0 1 0 0 0 0
     
     
MS◦R = MR ⊙ MS = 1 0 1 ⊙ 0 0 1 = 1 1 1
    

     
1 1 0 1 0 1 0 1 1

The matrix representing the composite of two relations can be used to find the matrix MnR . In particular,

[n]
MnR = MR ,
from the definition of Boolean powers.
Example

Find the matrix representing the relation R2 , where the matrix representing R is
 
0 1 0
 
 
MR = 0 1 1.
 
1 0 0

Solution: The matrix for R2

     
0 1 0 0 1 0 0 1 1
     
     
M R2 = M R ⊙ M R = 
 0 1 1  ⊙ 0 1 1 = 0 1 0 .
    
     
1 0 0 1 0 0 1 1 1

EXERCISES
1. Represent each of these relations on {1, 2, 3} with a matrix (with the elements of this set listed in
increasing order).
a) {(1, 1), (1, 2), (1, 3)}
b) {(1, 2), (2, 1), (2, 2), (3, 3)}
c) {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}
d) {(1, 3), (3, 1)}

2. List the ordered pairs in the relations on {1, 2, 3} corresponding to these matrices (where the rows
and columns correspond to the integers listed in increasing order).
(a)  
0 1 0
 
1 0 1
 
1 0 1

Discrete Mathematics 17 Computing Department, UNISEL

 9.2. REPRESENTING RELATIONS CHAPTER 9. RELATION

(b)  
0 1 0
 
0 1 0
 
0 1 0
(c)  
1 1 1
 
1 0 1
 
1 1 1
3. How many nonzero entries does the matrix representing the relation R on A = {1, 2, 3, . . . , 100}
consisting of the first 100 positive integers have if R is
(a) {(, b) |  > b} (b) {(, b) |  ̸= b}
4. How can the matrix for R, the complement of the relation R, be found from the matrix representing
R, when R is a relation on a finite set A?
5. How can the matrix for R−1 , the inverse of the relation R, be found from the matrix representing R,
when R is a relation on a finite set A?
6. Let R be the relation represented by the matrix
 
0 1 1
 
MR =  1 1 0 .

1 0 1

Find the matrix representing

(a) R−1 (b) R (c) R2
7. Let R1 and R2 be relations on a set A represented by the matrices
   
0 1 0 0 1 0
   
M R1 = 
1 1 1 ,
 M R2 = 
0 1 1 .


1 0 0 1 1 1

Find the matrices that represent (a) R1 ∪ R2 (b) R1 ∩ R2 (c) R2 ◦ R1 (d) R1 ◦ R1 (e) R1 ⊕ R2
8. Let R be the relation represented by the matrix
 
0 1 0
 
MR =  0 0 1 .

1 1 0

Find the matrices that represent (a) R2 (b) R3 (c) R4

Computing Department, UNISEL 18 Discrete Mathematics