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

Source: https://skills101.in/learn/discrete-math/dm-warshall-closures-relation-matrices — Skills101 free tutorial (Discrete Mathematics). Updated 2026-11-21.

The [sets, relations and functions lesson](https://skills101.in/learn/discrete-math/sets-relations-functions) 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 +.

```python
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]))
```

```text
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.

```python
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")
```

```text
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](https://skills101.in/learn-img/discrete-math/transitive-closure-graph.svg)

## 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).

```python
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)
```

```text
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](https://skills101.in/learn-img/discrete-math/warshall-matrices.svg)

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 quiz and free certificate: https://skills101.in/learn/discrete-math/dm-warshall-closures-relation-matrices