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

Solution:

Let MR denotes the matrix representation of R. Take W0=MR, we have

$W_0=M_R=\begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ \end{pmatrix}.$

As WR is 4x4 matrix, we have n=4 and we need to compute W4.

For k=1. In column 1 of W0 '1' is at position 3, hence p1=3.

In row 1 of W0 1's is at position 1, hence q1=3.

Thus, we put 1 at position (p1, q1)=(3, 3).

$W_1= \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ \end{pmatrix}.$

For k=2. In column 2 of W1 '1' is at position 4, hence p1=4.

In row 2 of W1 1's are at positions 3 and 4, hence q1=3, q2=4.

Thus, we put 1 at positions (p1, q1)=(4, 3) and (p1, q2)=(4, 4).

$W_2= \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ \end{pmatrix}.$

For k=3. In column 3 of W2 '1' are at positions 1, 2, 3 and 4, hence p1=1, p2=2, p3=3, p4=4.

In row 3 of W2 1's are at positions 1 and 3, hence q1=1, q2=3.

Thus, we put 1 at positions (p1, q1)=(1, 1), (p1, q2)=(1, 3), (p2, q1)=(2, 1), (p2, q2)=(2, 3),

(p3, q1)=(3, 1), (p3, q2)=(3, 3), (p4, q1)=(4, 1), (p4, q2)=(4, 3).

$W_3= \begin{pmatrix} 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ \end{pmatrix}.$

For k=4. In column 4 of W3 '1' are at positions 2 and 4, hence p1=2, p2=4.

In row 4 of W3 1's are at positions 1, 2, 3 and 4, hence q1=1, q2=2, q3=3, q4=4.

Thus, we put 1 at positions (p1, q1)=(2, 1), (p1, q2)=(2, 2), (p1, q3)=(2, 3), (p1, q4)=(2, 4),

(p2, q1)=(4, 1), (p2, q2)=(4, 2), (p2, q3)=(4, 3), (p2, q4)=(4, 4).

$M_R^{\infty}=W_4= \begin{pmatrix} 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ \end{pmatrix}.$

Thus, the transitive closure of R is given as .

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