Answer to Question #280710 in Discrete Mathematics for Ashwini

Question

Consider a relation R=\ (1,1),(1, ), (0,2), (2,3) (3,1)) on the set A=\ 1,2,3\ Find transitive closure of the relation R using algorithm Warshall's

Answer 1

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

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

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

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

Step 4. If $k=n$ then STOP: $W=M_{R^*},$ else go to Step 2.

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

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

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

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

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

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

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

It follows that $R^*=A\times A$ is a universal relation on the set $A.$