Ch 4. Relations
4.2 Relations, Their Properties, and Applications
In discrete mathematics, we describe a connection or association between elements of two sets using relations. Formally, given two sets [latex]A[/latex] and [latex]B[/latex], a relation [latex]R[/latex] from [latex]A[/latex] to [latex]B[/latex] is a subset of the Cartesian product [latex]A \times B[/latex]. That is,
[latex]R \subseteq A \times B[/latex]
Each element of [latex]R[/latex] is an ordered pair [latex](a, b)[/latex], where [latex]a \in A[/latex] and [latex]b \in B[/latex]. If [latex](a, b) \in R[/latex], we say that [latex]a[/latex] is related to [latex]b[/latex] under the relation [latex]R[/latex], and we write this as:
[latex]a \; R \; b[/latex]
Example 4.27
Let [latex]A[/latex] = {Aiden, Benjamin, Chloe} be a set of students and [latex]B[/latex] = {Math, History} be a set of courses. We can define a relation [latex]R \subseteq A \times B[/latex] as
[latex]R[/latex] = {(Aiden, Math), (Benjamin, History), (Chloe, Math)}
This relation describes which students are enrolled in which courses. For example, Aiden is enrolled in math, Benjamin in history, and Chloe in math.
Let's now explore how relations can be represented in different formats as follows:
- ordered pairs
- graphs
- matrices
The first, and most direct, way to represent a relation is as a set of ordered pairs. Each pair [latex](a, b)[/latex] indicates that element [latex]a[/latex] from set [latex]A[/latex] is related to element [latex]b[/latex] from set [latex]B[/latex].
Example 4.28
Let [latex]A = \{ 1, 2, 3 \}[/latex] and [latex]B = \{ x, y \}[/latex]. Define a relation [latex]R \subseteq A \times B[/latex] as:
[latex]R = \{ (1, x), (2, y), (3, x) \}[/latex]
This tells us that [latex]1[/latex] is related to [latex]x[/latex], [latex]2[/latex] is related to [latex]y[/latex], and [latex]3[/latex] is related to [latex]x[/latex].
A second way to represent a relation on a set is with a directed graph (or digraph), which consists of circles, labels, and arrows. The circles and labels represent the elements of the set and are called vertices (or nodes). The arrows (or directed edges) represent the relationship between the elements. An arrow from vertex [latex]a[/latex] to vertex [latex]b[/latex] indicates that the ordered pair [latex](a, b)[/latex] is in the relation [latex]R[/latex]. A special case is a loop, which is an edge that starts and ends at the same vertex, representing the pair [latex](a, a) \in R[/latex].
Example 4.29
Let [latex]A = \{ 1, 2, 3 \}[/latex] and define a relation [latex]R = \{ (1, 2), (2, 3), (3, 1), (2, 2) \}[/latex].
The directed graph in the figure below has vertices [latex]1[/latex], [latex]2[/latex], [latex]3[/latex], directed edges [latex]1 \rightarrow 2, 2 \rightarrow 3, 3 \rightarrow 1[/latex], and a loop [latex]2 \rightarrow 2[/latex].
This digraph shows how elements are connected and is especially useful for visualizing properties like cycles, reflexivity, and transitivity, which are discussed later in this section.
A relation matrix is the third way to represent a relation between two different finite sets using a rectangular array of 0s and 1s. Let [latex]A = \{ a_{1}, a_{2}, \dots, a_{m} \}[/latex] and [latex]B = \{ b_{1}, b_{2}, \dots, b_{n} \}[/latex] be finite sets, and let [latex]R \subseteq A \times B[/latex] be a relation from [latex]A[/latex] to [latex]B[/latex]. Then the relation matrix of [latex]R[/latex] is the matrix [latex]M[/latex] whose [latex](i, j)[/latex]-entry is
[latex]M_{ij} = \begin{cases} 1, & \text{if } (a_{i}, b_{j}) \in R \\ 0, & \text{otherwise} \end{cases}[/latex]
Example 4.30
Let [latex]A = \{ a_{1}, a_{2}, a_{3} \}[/latex], [latex]B = \{ b_{1}, b_{2}, b_{3}, b_{4} \}[/latex], and a relation [latex]R \subseteq A \times B[/latex] be defined as
[latex]R = \{ (a_{1}, b_{2}), (a_{1}, b_{4}), (a_{2}, b_{1}), (a_{2}, b_{3}), (a_{3}, b_{1}), (a_{3}, b_{2}), (a_{3}, b_{4}) \}[/latex]
The relation matrix [latex]M[/latex] is a 3 x 4 matrix with row headings [latex]a_{1}, a_{2}, a_{3}[/latex] and column headings [latex]b_{1}, b_{2}, b_{3}, b_{4}[/latex]. We place a [latex]1[/latex] in position [latex](i, j)[/latex] if [latex](a_{i}, b_{j}) \in R[/latex], and [latex]0[/latex] otherwise.
[latex]M=\begin{array}{c|cccc} & b_1 & b_2 & b_3 & b_4\\\hline a_1 & 0 & 1 & 0 & 1\\ a_2 & 1 & 0 & 1 & 0\\ a_3 & 1 & 1 & 0 & 1 \end{array}[/latex]
We see that [latex]a_{2}[/latex] and [latex]a_{3}[/latex] are related to [latex]b_{1}[/latex] since in column [latex]b_{1}[/latex], [latex]a_{2}[/latex] and [latex]a_{3}[/latex] have [latex]1[/latex]s in the column. Also notice that [latex]a_{2}[/latex] is not related to [latex]b_{2}[/latex] because row [latex]a_{2}[/latex], column [latex]b_{2}[/latex] has an entry of [latex]0[/latex].
Relations defined on a set can have specific properties that describe how elements relate to each other. These properties help us classify and analyze relations in both theoretical and practical contexts. We will look at the following four properties of relations:
- reflexive
- symmetric
- antisymmetric
- transitive
In addition, we will see how ordered pairs, directed graphs, and relation matrices can represent them.
The first property of a relation [latex]R[/latex] on a set [latex]A[/latex] is called reflexive if every element is related to itself. That is,
[latex]\forall a \in A, (a, a) \in R[/latex]
This means that for a relation to be reflexive, it must contain all the pairs [latex](a, a)[/latex] for every element [latex]a[/latex] in the set.
Example 4.31
In a directed graph, a reflexive relation is represented by a loop at every vertex.
Example 4.32
Let [latex]A = \{ x, y, z \}[/latex] and [latex]R = \{ (x, x), (y, y), (z, z), (x, y) \}[/latex]. The directed graph is shown below.
Since each vertex has a loop, the relation is reflexive.
Example 4.33
In an organizational setting, a user is associated with their own email address. This relation is reflexive and for three users it can be represented by letting [latex]A = \{ \text{user}_{1}, \text{user}_{2}, \text{user}_{3} \}[/latex] and [latex]B = \{ \text{email}_{1}, \text{email}_{2}, \text{email}_{3} \}[/latex], and defining the relation
[latex]R = \{ (\text{user}_{1}, \text{email}_{1}), (\text{user}_{2}, \text{email}_{2}), (\text{user}_{3}, \text{email}_{3}) \}[/latex]
The matrix representation [latex]M[/latex] is
[latex]\begin{array}{c|ccc} & \text{email}_1 & \text{email}_2 & \text{email}_3 \\ \hline \text{user}_1 & 1 & 0 & 0 \\ \text{user}_2 & 0 & 1 & 0 \\ \text{user}_3 & 0 & 0 & 1 \end{array}[/latex]
This matrix has [latex]1[/latex]s along the diagonal, indicating that each user is associated with their email.
For a set [latex]A[/latex] and relation [latex]R[/latex], if there exists at least one element [latex]a \in A[/latex] such that [latex](a, a) \notin R[/latex], then we say that [latex]R[/latex] is not reflexive. That is, the relation fails to include all the required self-pairs.
Example 4.34
Example 4.35
Let [latex]A = \{ x, y, z \}[/latex] and define [latex]R = \{ (x, x), (x, y), (y, z) \}[/latex]. The directed graph is shown below.
Since not all vertices have loops, the relation is not reflexive.
Example 4.36
Let [latex]A = \{ 1, 2, 3 \}, B = \{a, b, c \}[/latex], and define the relation [latex]R = \{ (1, a), (2, b), (3, a) \}[/latex]. The relation matrix is
[latex]\begin{array}{c|ccc} & a & b & c \\ \hline 1 & 1 & 0 & 0 \\ 2 & 0 & 1 & 0 \\ 3 & 1 & 0 & 0 \end{array}[/latex]
We can see that row 3 has no [latex]1[/latex] in column [latex]c[/latex], that is [latex](3, c) \notin R[/latex]. So, the relation is not reflexive.
The second property of a relation [latex]R[/latex] on a set [latex]A[/latex] is called symmetric if for every pair [latex](a, b) \in R[/latex], the reverse pair [latex](b, a)[/latex] is also in [latex]R[/latex]. That is,
[latex]\forall a, b \in A, (a, b) R \rightarrow (b, a) \in R[/latex]
Example 4.37
In a directed graph, a relation is symmetric if for every directed edge from [latex]a[/latex] to [latex]b[/latex], there is a corresponding edge from [latex]b[/latex] to [latex]a[/latex].
Example 4.38
For the directed graph in the figure below, every edge has a matching reverse edge, so the relation is symmetric.
Example 4.39
Let [latex]A = \{ 1, 2, 3 \}[/latex] and define [latex]R = \{ (1, 2), (2, 1), (2, 3), (3, 2), (1, 1), (2, 2), (3, 3) \}[/latex]. The matrix representation [latex]M[/latex] is
[latex]\begin{array}{c|ccc} & 1 & 2 & 3 \\ \hline 1 & 1 & 1 & 0 \\ 2 & 1 & 1 & 1 \\ 3 & 0 & 1 & 1 \end{array}[/latex]
This matrix is symmetric across the diagonal, meaning [latex]M_{ij} = M_{ji}[/latex] for all [latex]i, j[/latex], which confirms that the relation is symmetric
A relation [latex]R[/latex] on a set [latex]A[/latex] is not symmetric if there exists at least one pair [latex](a, b) \in R[/latex] such that [latex](b, a) \notin R[/latex]. That is, the relation is one-way for at least one pair.
Example 4.40
Let [latex]A = \{ a, b, c \}[/latex] and define [latex]R = \{ (a, b), (b, c), (c, c) \}[/latex]. This relation is not symmetric because [latex](a, b) \in R[/latex] but [latex](b, a) \notin R[/latex] and [latex](b, c) \in R[/latex] but [latex](c, b) \notin R[/latex].
The directed graph is shown in the figure below.
Since there is an arrow from [latex]a \rightarrow b[/latex], but no arrow from [latex]b \rightarrow a[/latex] and there is an arrow from [latex]b \rightarrow c[/latex], but no arrow from [latex]c \rightarrow b[/latex], the relation is not symmetric.
The relation matrix [latex]M[/latex] is
[latex]\begin{array}{c|ccc} & a & b & c \\ \hline a & 0 & 1 & 0 \\ b & 0 & 0 & 1 \\ c & 0 & 0 & 1 \end{array}[/latex]
This matrix is not symmetric because [latex]M_{12} = 1[/latex] but [latex]M_{21} = 0[/latex] and [latex]M_{23} = 1[/latex] but [latex]M_{32} = 0[/latex].
The third property of a relation is that a relation R on a set A is antisymmetric if
[latex]\forall a, b \in A, (a, b) \in R \text{ and } (b, a) \in R \rightarrow a = b[/latex]
In other words, if two distinct elements are related in both directions, the relation is antisymmetric. The only time both [latex](a, b)[/latex] and [latex](b, a)[/latex] can appear is when [latex]a = b[/latex].
Example 4.41
Let [latex]A = \{ x, y, z \}[/latex] and define [latex]R = \{ (x, x), (y, y), (z, z), (x, y) \}[/latex]. Note that [latex](x, y) \in R[/latex], but [latex](y, x) \notin R[/latex]. All other pairs are of the form [latex](a, a)[/latex]. Since no two distinct elements are related in both directions, the relation is antisymmetric
The directed graph is shown in the figure below.
Note that there is one arrow from [latex]x \rightarrow y[/latex], but no arrow from [latex]y \rightarrow x[/latex], so the relation is antisymmetric.
The relation matrix [latex]M[/latex] is
[latex]\begin{array}{c|ccc} & x & y & z \\ \hline x & 1 & 1 & 0 \\ y & 0 & 1 & 0 \\ z & 0 & 0 & 1 \end{array}[/latex]
There is a [latex]1[/latex] at [latex](1, 2)[/latex], but not at [latex](2, 1)[/latex], so the relation is antisymmetric.
A relation [latex]R[/latex] on a set [latex]A[/latex] is not antisymmetric if there exist distinct elements [latex]a \neq b[/latex] such that both [latex](a, b) \in R[/latex] and [latex](b, a) \in R[/latex].
Example 4.42
Let [latex]A = \{ 1, 2 \}[/latex] and define [latex]R = \{ (1, 2), (2, 1) \}[/latex]. Since both [latex](1, 2)[/latex] and [latex](2, 1)[/latex] are in the relation and [latex]1 \neq 2[/latex], the relation is not antisymmetric.
The directed graph is shown in the figure below.
This bidirectional edge between distinct vertices violates antisymmetry.
The relation matrix [latex]M[/latex] is
[latex]\begin{array}{c|cc} & 1 & 2 \\ \hline 1 & 0 & 1 \\ 2 & 1 & 0 \end{array}[/latex]
Since both [latex]M_{12} = 1[/latex] and [latex]M_{21} = 1[/latex], and [latex]1 \neq 2[/latex], the relation is not antisymmetric.
The fourth property of a relation is that a relation [latex]R[/latex] on a set [latex]A[/latex] is transitive if:
[latex]\forall a, b, c \in A, (a, b) \in R \text{ and } (b, c) \in R \rightarrow (a, c) \in R[/latex]
This means that if an element is related to a second, and the second is related to a third, then the first must also be related to the third.
Example 4.43
Let [latex]A = \{ 1, 2, 3 \}[/latex] and define [latex]R = \{ (1, 2), (2, 3), (1, 3), (1, 1), (2, 2), (3, 3) \}[/latex]. Since [latex](1, 2) \in R[/latex] and [latex](2, 3) \in R[/latex], and [latex](1, 3) \in R[/latex], the transitive condition is satisfied. All other combinations also satisfy the condition. Thus, [latex]R[/latex] is transitive.
The directed graph is shown in the figure below.
Since [latex]1 \rightarrow 2[/latex] and [latex]2 \rightarrow 3[/latex] imply [latex]1 \rightarrow 3[/latex], the relation is transitive.
The relation matrix [latex]M[/latex] is
[latex]\begin{array}{c|ccc} & 1 & 2 & 3 \\ \hline 1 & 1 & 1 & 1 \\ 2 & 0 & 1 & 1 \\ 3 & 0 & 0 & 1 \end{array}[/latex]
We can verify that for every pair [latex](i, j)[/latex] and [latex](j, k)[/latex], the pair [latex](i, k)[/latex] is also present. Hence, the relation is transitive.
A relation [latex]R[/latex] on a set [latex]A[/latex] is not transitive if there exist elements [latex]a, b, c \in A[/latex] such that
[latex](a, b) \in R \text{ and } (b, c) \in R \text{ but } (a, c) \notin R[/latex]
Example 4.44
Let [latex]A = \{ 1, 2, 3 \}[/latex] and define [latex]R = \{ (1, 2), (2, 3) \}[/latex]. Then [latex](1, 2) \in R[/latex] and [latex](2, 3) \in R[/latex], but [latex](1, 3) \notin R[/latex]. Therefore, [latex]R[/latex] is not transitive.
The directed graph is shown in the figure below.
Since the arrow [latex]1 \rightarrow 3[/latex] is missing, the relation is not transitive.
Let the relation matrix [latex]M[/latex] be
[latex]\begin{array}{c|ccc} & 1 & 2 & 3 \\ \hline 1 & 0 & 1 & 0 \\ 2 & 0 & 0 & 1 \\ 3 & 0 & 0 & 0 \end{array}[/latex]
[latex]M_{12} = 1[/latex] and [latex]M_{23} = 1[/latex], but [latex]M_{13} = 0[/latex]. So, the relation is not transitive.
At this point, we have discussed four properties of relations, namely, reflexive, symmetric, antisymmetric, and transitive. A partial order is a relation that satisfies three of these properties: reflexive, antisymmetric, and transitive.
A set [latex]A[/latex] together with a partial order [latex]R[/latex] is called a partially ordered set, denoted [latex](A, R)[/latex].
Example 4.45
Let [latex]A = \{ 1, 2, 3 \}[/latex] and define [latex]R = \{ (1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3) \}[/latex]. All [latex](a, a)[/latex] pairs are present, so [latex]R[/latex] is reflexive. No pair [latex](a, b)[/latex] and [latex](b, a)[/latex] exists for [latex]a \neq b[/latex], so [latex]R[/latex] is antisymmetric. In [latex]R[/latex], [latex](1, 2)[/latex] and [latex](2, 3)[/latex] imply [latex](1, 3)[/latex], which is present, so [latex]R[/latex] is transitive. So, [latex]R[/latex] is a partial order on [latex]A[/latex].
The directed graph is shown in the figure below.
All self-loops are present, so [latex]R[/latex] is reflexive. No pair like [latex](2, 1)[/latex] or [latex](3, 2)[/latex] exists, so [latex]R[/latex] is antisymmetric. In [latex]R[/latex], [latex](1, 2)[/latex] and [latex](2, 3)[/latex] imply [latex](1, 3)[/latex], which is present, so [latex]R[/latex] is transitive. This is a partial order.
The relation matrix [latex]M[/latex] is
[latex]\begin{array}{c|ccc} & 1 & 2 & 3 \\ \hline 1 & 1 & 1 & 1 \\ 2 & 0 & 1 & 1 \\ 3 & 0 & 0 & 1 \end{array}[/latex]
This matrix is reflexive, since the diagonals are all [latex]1[/latex]. It is antisymmetric, since there are no symmetric off-diagonal [latex]1[/latex]s. It is transitive, for example, [latex]1 \rightarrow 2[/latex] and [latex]2 \rightarrow 3[/latex] imply [latex]1 \rightarrow 3[/latex]. So, this is a partial order.
When reasoning about relationships inside a partially ordered set, we often need to compare elements within the set. Consider two elements [latex]a[/latex] and [latex]b[/latex] in a partially ordered set [latex](A, R)[/latex]. We have the following two definitions:
- If either [latex](a, b) \in R[/latex] or [latex](b, a) \in R[/latex], then [latex]a[/latex] and [latex]b[/latex] are comparable.
- If neither [latex](a, b) \in R[/latex] nor [latex](b, a) \in R[/latex], then [latex]a[/latex] and [latex]b[/latex] are incomparable.
Example 4.46
Let [latex]A = \{ 1, 2 \}[/latex] and [latex]R = \{ (1, 1), (2, 2), (1, 2) \}[/latex]. Then [latex]1[/latex] and [latex]2[/latex] are comparable because [latex](1, 2) \in R[/latex].
Let [latex]A = \{ a, b, c \}[/latex] and [latex]R = \{ (a, a), (b, b), (c, c), (a, b) \}[/latex]. Then [latex]b[/latex] and [latex]c[/latex] are incomparable because neither [latex](b, c)[/latex] nor [latex](c, b)[/latex] is in [latex]R[/latex].
Example 4.47
Let [latex]A = \{ x, y, z \}[/latex]. Define [latex]R = \{ (x, x), (y, y), (z, z), (x, y) \}[/latex]. The directed graph is shown in the figure below.
Then [latex]x[/latex] and [latex]y[/latex] are comparable since [latex]x \rightarrow y[/latex]. But, [latex]y[/latex] and [latex]z[/latex] are incomparable, since there is no edge between them.
The relation matrix [latex]M[/latex] is
[latex]\begin{array}{c|ccc} & x & y & z \\ \hline x & 1 & 1 & 0 \\ y & 0 & 1 & 0 \\ z & 0 & 0 & 1 \end{array}[/latex]
Again, [latex]x[/latex] and [latex]y[/latex] are comparable, but [latex]y[/latex] and [latex]z[/latex] are incomparable.
When a partial order has every pair of elements comparable, we refer to it as a total order. That is, for all [latex]a, b \in A[/latex], either
[latex](a, b) \in R \quad \text{or} \quad (b, a) \in R[/latex]
In fact, a total order is a partial order with the additional property of total comparability.
Example 4.48
Let [latex]A = \{ 1, 2, 3 \}[/latex] and define [latex]R = \{ (1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3) \}[/latex]. This is the same as Example 4.45, but now we observe that every pair is comparable: [latex]1 < 2 < 3[/latex]. So, [latex]R[/latex] is a total order. Looking at the directed graph in Example 4.45, every pair is connected directly or indirectly, which implies a total order.
Looking at the relation matrix in Example 4.45, every pair [latex](i, j)[/latex] is comparable, which implies a total order.
Just like functions and matrices have inverses, so too do relations. For a relation of pairs, reversing each pair gives the inverse of [latex]R[/latex]. For the relation [latex]R \subseteq A \times B[/latex], this is written as
[latex]R^{-1} = \{ (b, a) \ | \ (a, b) \in R \}[/latex]
Example 4.49
Example 4.50
Let [latex]R = \{ (x, y), (y, z) \}[/latex]. The directed graph and inverse directed graph are in the figure below.
Each arrow is reversed in direction.
Example 4.51
Let [latex]A = \{ 1, 2 \}[/latex], [latex]B =\{ a, b \}[/latex], and [latex]R = \{ (1, a), (2, b) \}[/latex]. The relation matrix [latex]M[/latex] is
[latex]\begin{array}{c|cc} & a & b \\ \hline 1 & 1 & 0 \\ 2 & 0 & 1 \end{array}[/latex]
Then [latex]M^{-1}[/latex] with rows = [latex]B[/latex] and columns = [latex]A[/latex] is
[latex]\begin{array}{c|cc} & 1 & 2 \\ \hline a & 1 & 0 \\ b & 0 & 1 \end{array}[/latex]
Another useful operation for relations is to “chain” them together, otherwise known as composition. For two relations [latex]R[/latex] and [latex]S[/latex], the composition of [latex]R[/latex] and [latex]S[/latex] is denoted [latex]S \circ R[/latex]. If [latex]R[/latex] is defined on [latex]A \times B[/latex] and [latex]S[/latex] is defined on [latex]B \times C[/latex], then we write
[latex]S \circ R = \{ (a, c) \mid \exists b \in B \text{ such that } (a, b) \in R \text{ and } (b, c) \in S \}[/latex]
Example 4.52
Let [latex]R = \{ (1, a), (2, b) \}[/latex] and [latex]S = \{ (a, x), (b, y) \}[/latex]. Then [latex]S \circ R = \{ (1, x), (2, y) \}[/latex]
Examples 4.53
Let [latex]R = \{ (a, b), (b, c) \}[/latex] and [latex]S = \{ (b, x), (c, y) \}[/latex]. Then
[latex](a, b) \in R \text{ and } (b, x) \in S \Rightarrow (a, x) \in S \circ R[/latex]
[latex](b, c) \in R \text{ and } (c, y) \in S \Rightarrow (b, y) \in S \circ R[/latex]
The directed graph of [latex]S \circ R[/latex] is shown in the figure below.
Example 4.54
Let [latex]A = \{ 1, 2, 3 \}[/latex], [latex]B = \{ a, b, c \}[/latex], and [latex]C = \{ x, y, z \}[/latex]. Define the matrix [latex]M_{R}[/latex] for the relation [latex]R \subseteq A \times B[/latex] as
[latex]\begin{array}{c|ccc} & a & b & c \\ \hline 1 & 1 & 0 & 1 \\ 2 & 0 & 1 & 0 \\ 3 & 1 & 1 & 0 \end{array}[/latex]
and the matrix [latex]M_{S}[/latex] for the relation [latex]S \subseteq B \times C[/latex] as
[latex]\begin{array}{c|ccc} & x & y & z \\ \hline a & 0 & 1 & 1 \\ b & 1 & 0 & 1 \\ c & 1 & 1 & 0 \end{array}[/latex]
Then [latex]M = M_{R}M_{S}[/latex] is the matrix product of [latex]M_{R}[/latex] and [latex]MS[/latex] with entries computing using the formula
[latex]M_{ij} = \sum^{3}_{k=1} R_{ik} \cdot S_{kj}[/latex]
that is,
[latex]\begin{array}{c|ccc} & x & y & z \\ \hline 1 & 1 & 2 & 1 \\ 2 & 1 & 0 & 1 \\ 3 & 1 & 1 & 2 \end{array}[/latex]
Theorem 4.3 below tells us that by replacing each nonzero term in the matrix product [latex]M[/latex] by [latex]1[/latex], we obtain the matrix [latex]M_{S \circ R}[/latex]
[latex]\begin{array}{c|ccc} & x & y & z \\ \hline 1 & 1 & 1 & 1 \\ 2 & 1 & 0 & 1 \\ 3 & 1 & 1 & 1 \end{array}[/latex]
This matrix represents the relation from [latex]A \Rightarrow C[/latex] via the composition of [latex]R[/latex] and [latex]S[/latex].
The following theorem is important because it provides a compact representation of relations, enables efficient composition computation, and supports applications in computer science, logic, and graph theory.
Theorem 4.3: Matrix Representation of Composition of Relations
Let [latex]R \subseteq A \times B[/latex] be a relation from set [latex]A[/latex] to set [latex]B[/latex] and let [latex]S \subseteq B \times C[/latex] be a relation from set [latex]B[/latex] to set [latex]C[/latex]. Let [latex]M_{R}[/latex] be the matrix of [latex]R[/latex] with respect to a fixed ordering of [latex]A[/latex] and [latex]B[/latex] and [latex]M_{S}[/latex] be the matrix of [latex]S[/latex] with respect to a fixed order of [latex]B[/latex] and [latex]C[/latex]. Then the matrix of the composition [latex]S \circ R \subseteq A \times C[/latex], with respect to the same orderings of [latex]A[/latex] and [latex]C[/latex], is obtained by computing the matrix product [latex]M_{R}M_{S}[/latex], and replacing each nonzero entry with [latex]1[/latex].
Proof
Let [latex]A = \{ a_{1}, a_{2}, \dots , a_{m} \}[/latex], [latex]B = \{ b_{1}, b_{2}, \dots , b_{n} \}[/latex], and [latex]C = \{ c_{1}, c_{2}, \dots , c_{p} \}[/latex], [latex]M_{R}[/latex] be the [latex]m \times n[/latex] matrix of [latex]R[/latex], where
[latex](M_{R})_{ij} = \begin{cases} 1 & \text{if } (a_i, b_j) \in R,\\ 0 & \text{otherwise} \end{cases}[/latex]
and [latex]M_{S}[/latex] be the [latex]n \times p[/latex] matrix of [latex]S[/latex]
[latex](M_{S})_{jk} = \begin{cases} 1 & \text{if } (b_j, c_k) \in S,\\ 0 & \text{otherwise} \end{cases}[/latex]
Now consider the standard matrix product [latex]M = M_{R}M_{S}[/latex], which is an [latex]m \times p[/latex] matrix. The entry in row [latex]i[/latex], column [latex]k[/latex] is
[latex]M_{ik} = \sum^n_{j=1} R_{ij} S_{jk}[/latex]
This sum counts the number of intermediate elements [latex]b_{j} \in B[/latex] such that [latex](a_{i}, b_{j}) \in R[/latex] and [latex](b_{j}, c_{k}) \in S[/latex]. So, if there exists at least one such [latex]b_{j}[/latex], then [latex](a_{i}, c_{k}) \in S \circ R[/latex], and the sum will be greater than or equal to [latex]1[/latex].
Therefore, we define the matrix of the composition [latex]S \circ R[/latex] as
[latex](M_{S \circ R})_{ij} = \begin{cases} 1 & \text{if } M_{ij} > 0,\\ 0 & \text{if } M_{ij} = 0 \end{cases}[/latex]
This matrix correctly represents the relation [latex]S \circ R[/latex], since it includes [latex](a_{i}, c_{k})[/latex] if and only if, there exists a [latex]b_{j} \in B[/latex] such that [latex](a_{i}, b_{j}) \in R[/latex] and [latex](b_{j}, c_{k}) \in S.[/latex]
[latex]\square[/latex]
Real-World Example 4.2: Access Control in a Corporate IT System
In a corporate environment, access to resources (such as files, databases, and applications) is often managed through relationships among users, roles, and permissions.
In this scenario, let
[latex]X[/latex] = set of users = {Aiden, Benjamin}
[latex]Y[/latex] = set of roles = {Manager, Analyst}
[latex]Z[/latex] = set of permissions = {Read, Write}
Define the relations [latex]R_{1} \subseteq X \times Y[/latex] and [latex]R_{2} \subseteq Y \times Z[/latex] to be the user-to-role and role-to permission relations, respectively. Then
[latex]R_{1}[/latex] = {(Aiden, Manager), (Benjamin, Analyst)}
[latex]R_{2}[/latex] = {(Manager, Read), (Manager, Write), (Analyst, Read)}
To determine what permissions each user has, we need to compute the composition [latex]R_{2} \circ R_{1} \subseteq X \times Z[/latex]. Note that Aiden is a manager, and managers have read and write permissions. Also, Benjamin is an analyst, and analysts have read permissions, so Benjamin has read permissions. This means that
[latex]R_{2} \circ R_{1}[/latex] = {(Aiden, Read), (Aiden, Write), (Benjamin, Read)}
