Answer to Question #117152 in Combinatorics | Number Theory for Priya

Question

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

Answer 1

Let M_R denotes the matrix representation of R. Take W₀=M_R, we have

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

As M_R is 4x4 matrix, we have n=4 and we need to compute W_4.

For k=1. In column 1 of W₀ '1' are at positions 2 and 4, hence p₁=2, p₂=4.

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

Thus, we put 1 at positions (p₁, q₁)=(2, 2) and (p₂, q₁)=(4, 2).

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

For k=2. In column 2 of W₁ 1's are at positions 1, 2 and 4, hence p₁=1, p₂=2, p₃=4.

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

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

(p₂, q₁)=(2, 1), (p₂, q₂)=(2, 2), (p₂, q₃)=(2, 3), (p₃, q₁)=(4, 1), (p₃, q₂)=(4, 2), (p₃, q₃)=(4, 3).

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

For k=3. In column 3 of W₂ '1' are at positions 1, 2 and 4, hence p₁=1, p₂=2, p₃=4.

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

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

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

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

(p₂, q₁)=(2, 1), (p₂, q₂)=(2, 2), (p₂, q₃)=(2, 3), (p₂, q₄)=(2, 4),

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

All positions in W₄ are 1, thus, the transitive closure of R is given as

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