Answer to Question #117149 in Discrete Mathematics for Priya

Question

Let R={(1,3),(4,2),(2,4),(2,3),(3,1) } be a relation on the A={1,2,3,4}. Find the transitive closure of R using Warshall’s algorithm.

Answer 1

Let M_R denotes the matrix representation of R. Take W₀=M_R, 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 W_R is 4x4 matrix, we have n=4 and we need to compute W_4.

For k=1. In column 1 of W₀ '1' is at position 3, hence p₁=3.

In row 1 of W₀ 1's is at position 1, hence q₁=3.

Thus, we put 1 at position (p₁, q₁)=(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 W₁ '1' is at position 4, hence p₁=4.

In row 2 of W₁ 1's are at positions 3 and 4, hence q₁=3, q₂=4.

Thus, we put 1 at positions (p₁, q₁)=(4, 3) and (p₁, q₂)=(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 W₂ '1' are at positions 1, 2, 3 and 4, hence p₁=1, p₂=2, p₃=3, p₄=4.

In row 3 of W₂ 1's are at positions 1 and 3, hence q₁=1, q₂=3.

Thus, we put 1 at positions (p₁, q₁)=(1, 1), (p₁, q₂)=(1, 3), (p₂, q₁)=(2, 1), (p₂, q₂)=(2, 3),

(p₃, q₁)=(3, 1), (p₃, q₂)=(3, 3), (p₄, q₁)=(4, 1), (p₄, q₂)=(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 W₃ '1' are at positions 2 and 4, hence p₁=2, p₂=4.

In row 4 of W₃ 1's are at positions 1, 2, 3 and 4, hence q₁=1, q₂=2, q₃=3, q₄=4.

Thus, we put 1 at positions (p₁, q₁)=(2, 1), (p₁, q₂)=(2, 2), (p₁, q₃)=(2, 3), (p₁, q₄)=(2, 4),

(p₂, q₁)=(4, 1), (p₂, q₂)=(4, 2), (p₂, q₃)=(4, 3), (p₂, q₄)=(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)\}.$ .