Skip to main content

Section 12.2 Representing relations

If \(X\) and \(Y\) are finite sets then there are two convenient ways to represent a relation between \(X\) and \(Y\text{:}\) Boolean matrices and directed graphs.

First, let's discuss the Boolean matrix approach. Without loss of generality, label the elements of \(X\) as \(x_1, x_2, \ldots, x_m\) and those of \(Y\) as \(y_1, y_2, \ldots, y_n\text{.}\) Consider that each element \(x_i \in X\) induces the statement “\(x_i\) is related to \(y_j\)”. Remembering that Boolean matrices encode families of statements, we may define the \(m\times n\) matrix

\begin{equation*} M_R = ( m_{i,j}) \end{equation*}

where \(m_{i,j} = 1\) if and only if \(x_i\) is related to \(y_j\text{.}\)

Put simply, the \(i\)th row of the matrix will have a \(1\) in the \(j\)th spot whenever \(x_i R y_j\text{.}\)

Earlier we had the relation

\begin{equation*} \{ (x,1), (x,2), (y,2) \} \end{equation*}

from \(X = \{x,y,z\}\) to \(Y=\{1,2\}\text{.}\) There are many different matrices representing this relation depending on how the sets \(X\) and \(Y\) are ordered. When there is an “obvious” ordering, say numerical or alphabetical, we will use that one. Under these orderings the matrix for the relation is

\begin{equation*} \left( \begin{array}{cc} 1 \amp 1 \\ 0 \amp 1 \\ 0 \amp 0 \end{array} \right). \end{equation*}

Consider a relation \(R\) on a set \(X\) (again, meaning that the domain and codomain are the same set). We can also represent \(R\) visually with something called a directed graph or digraph for short. From this perspective, the elements of \(X\) are called the vertices of the graph and the pairs \((x,y)\) in the relation are called edges or arrows. An arrow is drawn from one vertex to another if those vertices are related.

Let \(X = \{a,b,c,d\}\text{,}\) and consider the relation

\begin{equation*} R = \{ (a,b), (a,d), (b,b), (b,c), (d,a) \}. \end{equation*}

The directed graph for this relation is shown below:

Directed graph for the above relation. The element \(a\) is related to \(b\) and \(d\text{;}\) \(b\) is related to itself and \(c\text{;}\) and \(d\) is related to \(a\text{.}\)
Figure 12.2.3.

Directed graph for the above relation. The element \(a\) is related to \(b\) and \(d\text{;}\) \(b\) is related to itself and \(c\text{;}\) and \(d\) is related to \(a\text{.}\)

It is possible to draw many graphs for one relation, so why can we say “the” directed graph? Observe that any graphs will have the same arrows between the same vertices. Two graphs for which there is a 1-1 correspondence that preserves the edges are isomorphic and are functionally the same. Therefore, we say “the” directed graph for a relation.

Consider the relation \(S\) on the set \(\{1,2,3,4,5,6\}\) where

\begin{equation*} S = \{(1,1), (1,2), (1,3), (2,3), (3,4), (4,2), (5,6), (6,5), (6,6)\} \end{equation*}

The matrix representing this relation (with the rows and columns ordered numerically) is

\begin{equation*} M_S = \left( \begin{array}{cccccc} 1 \amp 1 \amp 1 \amp 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \amp 1 \amp 0 \amp 0 \\ 0 \amp 1 \amp 0 \amp 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \\ 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 1 \end{array} \right) \end{equation*}

while the directed graph is shown below:

Directed graph for the above relation. \(1\) is related to itself, \(2\text{,}\) and \(3\text{;}\) \(2\) is related to \(3\text{,}\) which is related to \(4\text{;}\) \(4\) is related to \(2\text{;}\) \(5\) and \(6\) are each related to each other; \(6\) is related to itself.
Figure 12.2.5.

Directed graph for the above relation. \(1\) is related to itself, \(2\text{,}\) and \(3\text{;}\) \(2\) is related to \(3\text{,}\) which is related to \(4\text{;}\) \(4\) is related to \(2\text{;}\) \(5\) and \(6\) are each related to each other; \(6\) is related to itself.