Answer to Question #255706 in Discrete Mathematics for Vvk

Question

Let A={1,2,3,4,5} and R be the relation on A such that R={(1,1),(1,4),(2,2),(3,4),(3,5),(4,1),(5,2),(5,5)}. Find the transitive closure of R by Warshall's Algorithm

Answer 1

Let $A=\{1,2,3,4,5\}$ and $R$ be the relation on $A$ such that $R=\{(1,1),(1,4),(2,2),(3,4),(3,5),(4,1),(5,2),(5,5)\}.$ Let us find the transitive closure of $R$ by Warshall's Algorithm:

$W^{(0)}=M_R=\begin{pmatrix} 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 1 \end{pmatrix}$

$W^{(1)}=\begin{pmatrix} 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 1 \end{pmatrix}$

$W^{(2)}=\begin{pmatrix} 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 1 \end{pmatrix}$

$W^{(3)}=\begin{pmatrix} 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 1 \end{pmatrix}$

$W^{(4)}=\begin{pmatrix} 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 1 \end{pmatrix}$

$M_{R^*}=W^{(5)}=\begin{pmatrix} 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 0\\ 1 & 1 & 0 & 1 & 1\\ 1 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 1 \end{pmatrix}$

It follows that the transitive closure $R^*$ of $R$ is the following:

$R^*=\{(1,1),(1,4),(2,2),(3,1),(3,2),(3,4),(3,5),(4,1),(4,4),(5,2),(5,5)\}.$