Page 612 - Discrete Mathematics and Its Applications

9.3 Representing Relations 591

9.3 Representing Relations

Introduction

In this section, and in the remainder of this chapter, all relations we study will be binary relations.
Because of this, in this section and in the rest of this chapter, the word relation will always refer
to a binary relation. There are many ways to represent a relation between finite sets. As we have
seen in Section 9.1, one way is to list its ordered pairs. Another way to represent a relation is to
use a table, as we did in Example 3 in Section 9.1. In this section we will discuss two alternative
methods for representing relations. One method uses zero–one matrices. The other method uses
pictorial representations called directed graphs, which we will discuss later in this section.
Generally, matrices are appropriate for the representation of relations in computer programs.
On the other hand, people often find the representation of relations using directed graphs useful
for understanding the properties of these relations.

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 ={a 1 ,a 2 ,...,a m } to B ={b 1 ,b 2 ,...,b n }. (Here the elements of the sets A
and B have been listed in a particular, but arbitrary, order. Furthermore, when A = B we use
the same ordering for A and B.) The relation R can be represented by the matrix M R =[m ij ],
where

1if (a i ,b j ) ∈ R,

m ij =
0if (a i ,b j )/∈ R.
In other words, the zero–one matrix representing R hasa1asits (i, j) entry when a i is related
to b j ,anda0in this position if a i is not related to b j . (Such a representation depends on the
orderings used for A and B.)
The use of matrices to represent relations is illustrated in Examples 1–6.

EXAMPLE 1 Suppose that A ={1, 2, 3} and B ={1, 2}. Let R be the relation from A to B containing (a, b)
if a ∈ A, b ∈ B, and a> b. What is the matrix representing R if a 1 = 1, a 2 = 2, and a 3 = 3,
and b 1 = 1 and b 2 = 2?

Solution: Because R ={(2, 1), (3, 1), (3, 2)}, the matrix for R is

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

The 1s in M R show that the pairs (2, 1), (3, 1), and (3, 2) belong to R. The 0s show that no
other pairs belong to R. ▲

EXAMPLE 2 Let A ={a 1 ,a 2 ,a 3 } and B ={b 1 ,b 2 ,b 3 ,b 4 ,b 5 }. Which ordered pairs are in the relation R
represented by the matrix

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