Answer to Question #281095 in Discrete Mathematics for Ashwini

Question

Consider a relation R= {(1, 1) (1, 3), (2, 2), (2,3) (3,1)on the set A = (1,2,3) Find transitive using warshalls algorithm... closure of the relation R consider

Answer 1

Consider a relation $R=\{ (1,1),(1, 3), (2,2), (2,3), (3,1)\}$ on the set $A=\{1,2,3\}$.

Let us state the steps of the Warshall's algorithm:

1. Let $W:=M_R,\ k:=0.$

2. Put $k:=k+1.$

3. For all $i\ne k$ such that $w_{ik}=1$ and for all $j$ let $w_{ij}=w_{ij}\lor w_{kj}.$

4. If $k=n$ then stop and $W=M_{R^*},$ else go to step 2.

Let us find transitive closure of the relation $R$ using Warshall's algorithm:

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

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

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

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

It follows that $R^*=\{ (1,1),(1, 3), (2,1),(2,2), (2,3), (3,1),(3,3)\}.$