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.
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 0 |
| 2 | 1 | 0 | 1 | 0 |
| 3 | 0 | 0 | 0 | 1 |
| 4 | 0 | 0 | 0 | 0 |
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.
| Closure | How to build it | Matrix view |
|---|---|---|
| Reflexive | R ∪ {(a, a) : a ∈ A} | set the diagonal to 1 |
| Symmetric | R ∪ R⁻¹ (add (b, a) for each (a, b)) | M OR Mᵀ |
| Transitive | R ∪ 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).
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.
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.