Section 13.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
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{.}\)
Example 13.2.1.
Earlier we had the relation
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
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.
Example 13.2.2.
Let \(X = \{a,b,c,d\}\text{,}\) and consider the relation
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{.}\)
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.
Example 13.2.4.
Consider the relation \(S\) on the set \(\{1,2,3,4,5,6\}\) where
The matrix representing this relation (with the rows and columns ordered numerically) is
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.