Closures of Relations
Solved Problems
Example 1.
Let \(A = \left\{ {1,2,3,4} \right\}.\) A binary relation \(R\) on the set \(A\) is given by the digraph
Find the reflexive closure of \(R.\)
Solution.
To build the reflexive closure of \(R,\) we just add the missing self-loops to all nodes of the digraph:
In roster form, the reflexive closure \(r\left( R \right)\) is given by
\[r\left( R \right) = \left\{ {\left( \color{red}{1,1} \right),\left( {1,2} \right),\left( {1,3} \right),\left( {1,4} \right),\left( {2,1} \right),\left( \color{red}{2,2} \right),\left( {3,1} \right),\left( {3,3} \right),\left( {3,4} \right),\left( \color{red}{4,4} \right)} \right\}.\]
Example 2.
Let \(B = \left\{ {1,2,3,4,5} \right\}.\) A binary relation \(S\) on the set \(B\) is given by the digraph
Find the symmetric closure of \(S.\)
Solution.
To form the digraph of the symmetric closure, we simply add a new edge in the reverse direction (if none already exists) for each edge in the original digraph:
The symmetric closure of \(S\) contains the following ordered pairs:
\[s\left( S \right) = \left\{ {\left( {1,2} \right),\left( {1,5} \right),\left( \color{red}{2,1} \right),\left( {2,2} \right),\left( {2,4} \right),\left( {2,5} \right),\left( {3,4} \right),\left( \color{red}{3,5} \right),\left( {4,2} \right),\left( \color{red}{4,3} \right),\left( {4,4} \right),\left( \color{red}{5,1} \right),\left( \color{red}{5,2} \right),\left( {5,3} \right)} \right\}.\]
Example 3.
Let \(R = \left\{ {\left( {a,b} \right),\left( {b,c} \right),\left( {c,a} \right)} \right\}\) be a relation defined on the set \(A = \left\{ {a,b,c} \right\}.\) Find the reflexive closure of \(R^2\) using matrix representation.
Solution.
Write the relation \(R\) is matrix form:
\[{M_R} = \left[ {\begin{array}{*{20}{c}}
0&1&0\\
0&0&1\\
1&0&0
\end{array}} \right].\]
Compute the matrix of the composition \(R^2:\)
\[{M_{{R^2}}} = {M_R} \times {M_R} = \left[ {\begin{array}{*{20}{c}}
0&1&0\\
0&0&1\\
1&0&0
\end{array}} \right] \times \left[ {\begin{array}{*{20}{c}}
0&1&0\\
0&0&1\\
1&0&0
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
{0 + 0 + 0}&{0 + 0 + 0}&{0 + 1 + 0}\\
{0 + 0 + 0}&{0 + 0 + 0}&{0 + 0 + 0}\\
{0 + 0 + 0}&{1 + 0 + 0}&{0 + 0 + 0}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
0&0&1\\
0&0&0\\
0&1&0
\end{array}} \right].\]
The reflexive closure of \(R^2\) is determined as the union of the relation \(R^2\) and the identity relation \(I:\)
\[r\left( {{R^2}} \right) = {R^2} \cup I,\]
so we have
\[{M_{r\left( {{R^2}} \right)}} = {M_{{R^2}}} + {M_I} = \left[ {\begin{array}{*{20}{c}} 0&0&1\\ 0&0&0\\ 0&1&0 \end{array}} \right] + \left[ {\begin{array}{*{20}{c}} \color{red}{1}&0&0\\ 0&\color{red}{1}&0\\ 0&0&\color{red}{1} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} \color{red}{1}&0&1\\ 0&\color{red}{1}&0\\ 0&1&\color{red}{1} \end{array}} \right].\]
The reflexive closure \(r\left( {{R^2}} \right)\) in roster form is given by
\[r\left( {{R^2}} \right) = \left\{ {\left( \color{red}{a,a} \right),\left( {a,c} \right),\left( \color{red}{b,b} \right),\left( {c,b} \right),\left( \color{red}{c,c} \right)} \right\}.\]
Example 4.
Let \(S = \left\{ {\left( {k,\ell} \right),\left( {k,n} \right),\left( {m,k} \right),} \right.\) \(\left.{\left( {m,m} \right),\left( {n,\ell} \right)} \right\}\) be a relation defined on the set \(B = \left\{ {k,\ell,m,n} \right\}.\) Find the symmetric closure of \(S\) in matrix form.
Solution.
The original relation \(S\) and the inverse relation \(S^{-1}\) are represented by the following matrices:
\[{M_S} = \left[ {\begin{array}{*{20}{c}}
0&1&0&1\\
0&0&0&0\\
1&0&1&0\\
0&1&0&0
\end{array}} \right],\;\;{M_{{S^{ - 1}}}} = \left[ {\begin{array}{*{20}{c}}
0&0&\color{red}{1}&0\\
\color{red}{1}&0&0&\color{red}{1}\\
0&0&1&0\\
\color{red}{1}&0&0&0
\end{array}} \right].\]
The matrix of the symmetric closure \(s\left( S \right)\) is determined as the sum of the matrices \(M_S\) and \(M_{S^{-1}}:\)
\[{M_{s\left( S \right)}} = {M_S} + {M_{{S^{ - 1}}}} = \left[ {\begin{array}{*{20}{c}} 0&1&0&1\\ 0&0&0&0\\ 1&0&1&0\\ 0&1&0&0 \end{array}} \right] + \left[ {\begin{array}{*{20}{c}} 0&0&\color{red}{1}&0\\ \color{red}{1}&0&0&\color{red}{1}\\ 0&0&1&0\\ \color{red}{1}&0&0&0 \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} 0&1&\color{red}{1}&1\\ \color{red}{1}&0&0&\color{red}{1}\\ 1&0&1&0\\ \color{red}{1}&1&0&0 \end{array}} \right].\]
Returning back to roster form, we have
\[s\left( S \right) = \left\{ {\left( {k,l} \right),\left( \color{red}{k,m} \right),\left( {k,n} \right),\left( \color{red}{l,k} \right),\left( \color{red}{l,n} \right),\left( {m,k} \right),\left( {m,m} \right),\left( \color{red}{n,k} \right),\left( {n,l} \right)} \right\}.\]
Example 5.
Find all paths of length \(3\) in the relation \(R.\)
Solution.
The relation has \(6\) paths of length \(3:\)
\[\begin{array}{l}
\left( {1,2} \right),\left( {2,4} \right),\left( {4,2} \right)\\
\left( {1,3} \right),\left( {3,4} \right),\left( {4,2} \right)\\
\left( {1,4} \right),\left( {4,2} \right),\left( {2,4} \right)\\
\left( {2,4} \right),\left( {4,2} \right),\left( {2,4} \right)\\
\left( {3,4} \right),\left( {4,2} \right),\left( {2,4} \right)\\
\left( {4,2} \right),\left( {2,4} \right),\left( {4,2} \right)
\end{array}\]
Example 6.
Find all paths of length \(2\) in the relation \(S.\)
Solution.
The relation has \(8\) paths of length \(2:\)
\[\begin{array}{l} \left( {1,2} \right),\left( {2,1} \right)\\ \left( {1,2} \right),\left( {2,3} \right)\\ \left( {1,3} \right),\left( {3,2} \right)\\ \left( {2,1} \right),\left( {1,2} \right)\\ \left( {2,1} \right),\left( {1,3} \right)\\ \left( {2,3} \right),\left( {3,2} \right)\\ \left( {3,2} \right),\left( {2,1} \right)\\ \left( {3,2} \right),\left( {2,3} \right) \end{array}\]
Example 7.
Let \(R = \left\{ {\left( {1,2} \right),\left( {2,3} \right),\left( {3,2} \right),\left( {4,1} \right)} \right\}\) be a binary relation on the set \(A = \left\{ {1,2,3,4} \right\}.\) Find the transitive closure of \(R.\)
Solution.
We solve the problem by calculating the connectivity relation \(R^{*}.\) The original relation \(R\) is represented in matrix form as follows:
\[{M_R} = \left[ {\begin{array}{*{20}{c}} 0&1&0&0\\ 0&0&1&0\\ 0&1&0&0\\ 1&0&0&0 \end{array}} \right].\]
Find the compositions of relations \(R^2,\) \(R^3,\) and \(R^4\) using matrix multiplication:
\[{M_{{R^2}}} = {M_R} \times {M_R} = \left[ {\begin{array}{*{20}{c}}
0&1&0&0\\
0&0&1&0\\
0&1&0&0\\
1&0&0&0
\end{array}} \right] \times \left[ {\begin{array}{*{20}{c}}
0&1&0&0\\
0&0&1&0\\
0&1&0&0\\
1&0&0&0
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
0&0&\color{red}{1}&0\\
0&\color{red}{1}&0&0\\
0&0&\color{red}{1}&0\\
0&\color{red}{1}&0&0
\end{array}} \right].\]
\[{M_{{R^3}}} = {M_{{R^2}}} \times {M_R} = \left[ {\begin{array}{*{20}{c}}
0&0&1&0\\
0&1&0&0\\
0&0&1&0\\
0&1&0&0
\end{array}} \right] \times \left[ {\begin{array}{*{20}{c}}
0&1&0&0\\
0&0&1&0\\
0&1&0&0\\
1&0&0&0
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
0&1&0&0\\
0&0&1&0\\
0&1&0&0\\
0&0&\color{red}{1}&0
\end{array}} \right].\]
\[{M_{{R^4}}} = {M_{{R^3}}} \times {M_R} = \left[ {\begin{array}{*{20}{c}}
0&1&0&0\\
0&0&1&0\\
0&1&0&0\\
0&0&1&0
\end{array}} \right] \times \left[ {\begin{array}{*{20}{c}}
0&1&0&0\\
0&0&1&0\\
0&1&0&0\\
1&0&0&0
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
0&0&\color{red}{1}&0\\
0&\color{red}{1}&0&0\\
0&0&\color{red}{1}&0\\
0&\color{red}{1}&0&0
\end{array}} \right].\]
We compute the connectivity relation \(R^{*}\) by the formula
\[{R^*} = R \cup {R^2} \cup {R^3} \cup {R^4}.\]
Since \({M_{{R^4}}} = {M_{{R^2}}},\) we can use the simplified expression:
\[{R^*} = R \cup {R^2} \cup {R^3}.\]
This yields:
\[{M_{{R^*}}} = {M_R} + {M_{{R^2}}} + {M_{{R^3}}} = \left[ {\begin{array}{*{20}{c}}
0&1&0&0\\
0&0&1&0\\
0&1&0&0\\
1&0&0&0
\end{array}} \right] + \left[ {\begin{array}{*{20}{c}}
0&0&\color{red}{1}&0\\
0&\color{red}{1}&0&0\\
0&0&\color{red}{1}&0\\
0&\color{red}{1}&0&0
\end{array}} \right] + \left[ {\begin{array}{*{20}{c}}
0&1&0&0\\
0&0&1&0\\
0&1&0&0\\
0&0&\color{red}{1}&0
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
0&1&\color{red}{1}&0\\
0&\color{red}{1}&1&0\\
0&1&\color{red}{1}&0\\
1&\color{red}{1}&\color{red}{1}&0
\end{array}} \right].\]
Hence, the transitive closure of \(R\) in roster form is given by
\[t\left( R \right) = {R^*} = \left\{ {\left( {1,2} \right),\left( \color{red}{1,3} \right),\left( \color{red}{2,2} \right),\left( {2,3} \right),\left( {3,2} \right),\left( \color{red}{3,3} \right),\left( {4,1} \right),\left( \color{red}{4,2} \right),\left( \color{red}{4,3} \right)} \right\}.\]
