Skills101

AdvancedDiscrete Mathematics · Lesson 12 of 14 · Updated ·

Relation Matrices, Closures and Warshall's Algorithm — Composition, Reflexive, Symmetric and Transitive Closure

The sets, relations and functions lesson checked whether a relation is reflexive, symmetric or transitive. This lesson answers the next question: if a relation is not transitive, what is the smallest set of pairs you must add to make it transitive? That smallest relation is called a closure. Computing the transitive closure by hand is slow, so we use the matrix method and Warshall's algorithm, which appear in almost every BCA, MCA and B.Tech discrete maths paper.

Throughout, A = {1, 2, 3, 4} and R = {(1,2), (2,1), (2,3), (3,4)}. Think of the elements as railway stations and (a, b) ∈ R as "there is a direct train from a to b".

1. A relation as a matrix

List the elements in a fixed order. The relation matrix M has a 1 in row a, column b when (a, b) ∈ R, and 0 otherwise.

1234
10100
21010
30001
40000

Properties become easy to read:

  • Reflexive: every entry on the main diagonal is 1.
  • Symmetric: the matrix equals its transpose (M[a][b] = M[b][a]).
  • Antisymmetric: for a ≠ b, M[a][b] and M[b][a] are never both 1.

R here is none of these: the diagonal is all 0, and (2,3) is in R while (3,2) is not.

2. Composition and the Boolean product

The composition R∘R contains (a, c) when there is some b with (a, b) ∈ R and (b, c) ∈ R — a journey with exactly two trains. In matrix form this is the Boolean product M ⊙ M: the usual matrix product, but with "AND" instead of × and "OR" instead of +.

A = [1, 2, 3, 4]
R = {(1, 2), (2, 1), (2, 3), (3, 4)}

def matrix(R, A):
    return [[1 if (a, b) in R else 0 for b in A] for a in A]

def show(M, name):
    print(name)
    for row in M:
        print("  ", *row)

def bool_product(X, Y):
    n = len(X)
    return [[int(any(X[i][k] and Y[k][j] for k in range(n))) for j in range(n)] for i in range(n)]

M = matrix(R, A)
show(M, "M (R itself)")
M2 = bool_product(M, M)
show(M2, "M2 = M ⊙ M (pairs joined by a path of length 2)")
print("R∘R =", sorted((A[i], A[j]) for i in range(4) for j in range(4) if M2[i][j]))
M (R itself)
   0 1 0 0
   1 0 1 0
   0 0 0 1
   0 0 0 0
M2 = M ⊙ M (pairs joined by a path of length 2)
   1 0 1 0
   0 1 0 1
   0 0 0 0
   0 0 0 0
R∘R = [(1, 1), (1, 3), (2, 2), (2, 4)]

Check one entry by hand: (1, 3) ∈ R∘R because 1 → 2 and 2 → 3. Similarly Rⁿ holds the pairs joined by a path of exactly n steps.

3. The three closures

The closure of R with respect to a property is the smallest relation that contains R and has that property.

ClosureHow to build itMatrix view
ReflexiveR ∪ {(a, a) : a ∈ A}set the diagonal to 1
SymmetricR ∪ R⁻¹ (add (b, a) for each (a, b))M OR Mᵀ
TransitiveR ∪ R² ∪ R³ ∪ … (stop when nothing new appears)M OR M² OR … OR Mⁿ

For the transitive closure, written R⁺ or R*, you never need more than n powers on an n-element set: a path that visits more than n stations must repeat one, and the loop can be cut out.

A = [1, 2, 3, 4]
R = {(1, 2), (2, 1), (2, 3), (3, 4)}

def compose(S, T):                      # pairs (a, c) with (a, b) in S and (b, c) in T
    return {(a, c) for (a, b) in S for (b2, c) in T if b == b2}

def transitive_closure(R):
    closure, power = set(R), set(R)
    while True:
        power = compose(power, R)       # R², R³, ...
        if power <= closure:
            return closure
        closure |= power

reflexive = R | {(a, a) for a in A}
symmetric = R | {(b, a) for (a, b) in R}
transitive = transitive_closure(R)
print("reflexive closure :", sorted(reflexive))
print("symmetric closure :", sorted(symmetric))
print("transitive closure:", sorted(transitive))
print("number of pairs   :", len(reflexive), len(symmetric), len(transitive))
equivalence = transitive_closure(reflexive | symmetric)
print("equivalence closure has", len(equivalence), "pairs")
reflexive closure : [(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4)]
symmetric closure : [(1, 2), (2, 1), (2, 3), (3, 2), (3, 4), (4, 3)]
transitive closure: [(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4)]
number of pairs   : 8 6 9
equivalence closure has 16 pairs

Notice (1, 1) and (2, 2) in the transitive closure. They are not "reflexive pairs added for free"; they are real round trips: 1 → 2 → 1. Station 3 does not get (3, 3) because no train ever returns to 3.

The smallest equivalence relation containing R is the transitive closure of the reflexive and symmetric closure. Here every station is connected to every other, so it has all 4 × 4 = 16 pairs (a single equivalence class).

Graph of R with solid grey arrows 1 to 2, 2 to 1, 2 to 3 and 3 to 4, plus dashed orange arrows for the five pairs added by the transitive closure: loops on 1 and 2, and 1 to 3, 1 to 4, 2 to 4

4. Warshall's algorithm

Multiplying matrices n times costs about n⁴ steps. Warshall's algorithm gets the transitive closure in about n³ steps, and it is easy to do by hand.

The idea: build matrices W₀, W₁, …, Wₙ. W₀ = M. In Wₖ, entry (i, j) is 1 when there is a path from i to j whose middle stops all come from the first k elements. Going from Wₖ₋₁ to Wₖ we allow element k as a new middle stop:

Wₖ[i][j] = Wₖ₋₁[i][j] OR (Wₖ₋₁[i][k] AND Wₖ₋₁[k][j])

Hand method for step k: look at column k and row k of the previous matrix. For every row i with a 1 in column k, and every column j with a 1 in row k, put a 1 at (i, j).

A = [1, 2, 3, 4]
R = {(1, 2), (2, 1), (2, 3), (3, 4)}
n = len(A)
W = [[1 if (a, b) in R else 0 for b in A] for a in A]

for k in range(n):                      # allow vertex A[k] as a middle stop
    new = []
    for i in range(n):
        for j in range(n):
            if not W[i][j] and W[i][k] and W[k][j]:
                W[i][j] = 1
                new.append((A[i], A[j]))
    print(f"W{k + 1} (via {A[k]}): new pairs {new}")

print("transitive closure R* :")
for row in W:
    print("  ", *row)
W1 (via 1): new pairs [(2, 2)]
W2 (via 2): new pairs [(1, 1), (1, 3)]
W3 (via 3): new pairs [(1, 4), (2, 4)]
W4 (via 4): new pairs []
transitive closure R* :
   1 1 1 1
   1 1 1 1
   0 0 0 1
   0 0 0 0

Step 2 by hand: column 2 of W₁ has 1s in rows 1 and 2; row 2 has 1s in columns 1, 2 and 3. So set (1,1), (1,2), (1,3), (2,1), (2,2), (2,3) to 1. Only (1,1) and (1,3) were new. The result matches the set method from section 3.

Five 4 by 4 matrices W0 to W4 from Warshall's algorithm, with the newly set cells highlighted: one new 1 via 1, two via 2, two via 3 and none via 4

The same loop with "minimum distance" instead of OR is the Floyd–Warshall shortest-path algorithm you meet in DSA.

Common mistakes

  • Forgetting that the transitive closure may add loops like (1, 1). If 1 → 2 → 1, then (1, 1) must be in it.
  • Adding diagonal 1s to the transitive closure "to be safe". That gives the reflexive-transitive closure, a different relation.
  • In Warshall's algorithm, using row k of the original matrix instead of the latest one. Each step uses the previous Wₖ₋₁.
  • Using ordinary + and × in the matrix product, which gives numbers like 2. Use OR and AND (or turn every non-zero into 1).
  • Stopping the power method too early. Keep going until a new power adds nothing.

Quick recap

  • Relation matrix: 1 at (a, b) when a R b. Reflexive = diagonal all 1; symmetric = equals transpose.
  • Composition R∘R ↔ Boolean product M ⊙ M: paths of length 2.
  • Reflexive closure: add the diagonal. Symmetric: add reverses. Transitive: union of R, R², …, Rⁿ.
  • Warshall: Wₖ[i][j] = Wₖ₋₁[i][j] OR (Wₖ₋₁[i][k] AND Wₖ₋₁[k][j]); O(n³).
  • Equivalence closure = transitive closure of the reflexive and symmetric closure.

Practice what you learned

📝 Quiz: Closures and Warshall's Algorithm5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →