Find the zero-one matrix of the transitive closure of the

Concept: The transitive closure of a relation R on a finite set is the smallest relation that contains R and is also transitive: it records, for every ordered pair of nodes, whether one node can be REACHED from the other by following one or more edges. Written as a zero-one (boolean) matrix this is the reachability matrix. A reliable way to compute it is Warshall's algorithm: scan each node k as a possible intermediate and set entry (i, j) to 1 whenever i can reach k and k can reach j.

Application: Read the edges from \(A\) using row = source and column = target: node 1 has edges 1→1 and 1→3; node 2 has 2→2; node 3 has 3→1 and 3→2. Now apply Warshall, scanning the intermediate node k = 1, then 2, then 3.

1. k = 1 (intermediate node 1): node 3 reaches 1 and node 1 reaches 3, so 3 can reach 3 — set entry (3, 3) = 1.

2. k = 2 (intermediate node 2): node 2 reaches only itself, so it introduces no new indirect path.

3. k = 3 (intermediate node 3): node 1 reaches 3 and node 3 reaches 2, so 1 can reach 2 — set entry (1, 2) = 1.

Collecting every reachable ordered pair gives the reachability matrix

\(\begin{bmatrix} 1 & 1& 1\\ 0 & 1 & 0\\ 1& 1& 1 \end{bmatrix}\)

Cross-check: Trace reachability directly. From node 1: 1→3 then 3→2, so node 1 reaches 1, 2 and 3 — row [1 1 1]. From node 2: only the self-loop 2→2 — row [0 1 0]. From node 3: 3→1, 3→2, and 3→1→3, so node 3 reaches 1, 2 and 3 — row [1 1 1]. This matches the matrix above, confirming the closure.