Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Representing relations: matrices and digraphs

How to represent a binary relation on a finite set as a directed graph (digraph) and as a (Boolean) matrix, and how relation properties correspond to simple matrix tests and graph features.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Relations appear everywhere in engineering models: a dependency between modules, reachability in state machines, predecessor/successor links in scheduling. Representing a relation as a digraph (directed graph) or as an adjacency matrix gives two practical views—graphs for visualization and matrices for algorithmic computation and proofs.

Key ideas

Start with the basic objects and build up.

  • Set: a collection of distinct elements. We write a finite set as A = {a1, a2, ..., an}.

  • Binary relation: a binary relation R on a set A is a subset R ⊆ A × A. If (x,y) ∈ R we say "x is related to y (by R)" and sometimes write x R y.

  • Directed graph (digraph): a digraph G = (V, E) consists of a set of vertices V and a set of directed edges E ⊆ V × V. To represent a relation R on A as a digraph, take V = A and E = R. Draw one node for each element of A. For each (x,y) ∈ R draw a directed arrow from x to y. If x = y (a loop), draw an arrow from the node to itself.

    Draw instructions for exam diagrams: draw n labelled points arranged in a circle or grid, label them a1, a2, ..., an. For each pair (ai, aj) in R draw a small directed arrow from ai to aj. If many arrows clutter, you may draw curved arrows or use arrowheads for direction; mark loops clearly on the node.

  • Adjacency matrix (Boolean matrix) of a relation: given A = {a1,...,an} and R ⊆ A×A, the adjacency matrix or relation matrix is the n×n matrix M = [mij] where

    • mij = 1 if (ai, aj) ∈ R,
    • mij = 0 otherwise. Here we use Boolean values 0 and 1. The row index i corresponds to the source (left element of ordered pair) and column index j to the target (right element).
  • Incidence matrix (directed): sometimes defined differently, but for directed graphs the incidence matrix B is an n×m matrix (n vertices, m edges) where each column corresponds to an edge e = (u,v); B[u,e] = -1 (or 1 depending on convention) and B[v,e] = +1; other entries 0. This is useful for flows and network problems. (Check your course convention; many discrete maths courses do not require incidence matrices for relations.)

  • Boolean matrix operations: define multiplication with logical OR and AND. For Boolean matrices A and B of compatible sizes, the Boolean product C = A ⊙ B has entries Cij = OR over k of (Aik AND Bkj). This corresponds to composition of relations: if R and S are relations with matrices A and B, then the matrix of R ∘ S is A ⊙ B.

  • Matrix tests for relation properties (assume M is adjacency matrix of R on A = {a1,...,an}):

    • Reflexive: R is reflexive iff every element relates to itself. Matrix test: all diagonal entries are 1: mii = 1 for all i. Write in matrix form: I ≤ M where I is the identity matrix with 1 on diagonal and 0 off-diagonal (in Boolean sense).
    • Irreflexive (antireflexive): mii = 0 for all i.
    • Symmetric: R is symmetric iff (x,y) ∈ R ⇒ (y,x) ∈ R for all x,y. Matrix test: M = M^T (ordinary transpose). In Boolean terms, mij = mji for all i,j.
    • Antisymmetric: R is antisymmetric iff for all i ≠ j, if mij = 1 then mji = 0. Equivalently, for all i ≠ j, not (mij = 1 and mji = 1).
    • Asymmetric: R is asymmetric iff antisymmetric and irreflexive; equivalently, for all i,j, if mij = 1 then mji = 0 (includes i=j case because mii must be 0).
    • Transitive: R is transitive iff whenever (x,y) ∈ R and (y,z) ∈ R then (x,z) ∈ R. Matrix test using Boolean product: compute M2 = M ⊙ M. R is transitive iff (M2)ij ≤ mij for all i,j (i.e. every 1 produced in M2 must already be 1 in M). In set terms: R ∘ R ⊆ R.
  • Composition of relations and matrices: If R and S are relations on A with adjacency matrices MR and MS, then the matrix of R ∘ S is MR ⊙ MS (Boolean product). The element at (i,j) is 1 iff there exists k with MR[i,k] = 1 and MS[k,j] = 1.

  • Reachability and transitive closure: The reachability relations are: R+ (transitive closure) contains (x,y) iff there exists a path of length ≥1 from x to y; R* (reflexive-transitive closure) contains (x,y) iff there exists a path of length ≥0 (including x = y via a zero-length path). In matrix terms, for a finite set A with n elements, you can compute R+ by OR-ing the Boolean powers M, M ⊙ M, M ⊙ M ⊙ M, ... up to the nth Boolean power, and R* by OR-ing I with that result; or use Warshall's algorithm (listed elsewhere in the course).

Where these tests are used: proving a relation has some property, computing closures, converting between representation for algorithms (e.g., graph algorithms often use adjacency matrices for dense graphs).

Formulas

m_ij = 1 if (a_i,a_j) ∈ R; m_ij = 0 otherwise — m_ij is the (i,j)-entry of adjacency matrix M of R; unitless; applies for finite sets A = {a1,..,an}.

(A ⊙ B)_{ij} = OR_{k=1..n} (A_{ik} AND B_{kj}) — Boolean product of n×n matrices; entries are 0/1; unitless; applies when composing relations.

R is reflexive ⇔ ∀i, m_{ii} = 1 — matrix diagonal test; unitless.

R is symmetric ⇔ M = M^T ⇔ ∀i,j, m_{ij} = m_{ji} — transpose test; unitless.

R is antisymmetric ⇔ ∀i≠j, (m_{ij} = 1 ⇒ m_{ji} = 0) — unitless.

R is transitive ⇔ M ⊙ M ≤ M ⇔ ∀i,j, ( (M ⊙ M)_{ij} = 1 ⇒ m_{ij} = 1 ) — entrywise Boolean order (0 ≤ 0, 0 ≤ 1, 1 ≤ 1; only 1 ≤ 0 is false); unitless.

Matrix(R ∘ S) = Matrix(R) ⊙ Matrix(S) — composition rule; unitless.

Worked examples

Example 1 — convert pairs → digraph → matrix; check properties

Given A = {1,2,3} and R = {(1,2), (2,3), (1,1), (3,2)}.

  1. Draw digraph: draw three labelled nodes 1,2,3. Draw an arrow 1→2, 2→3, 3→2, and a loop at 1 (1→1).

  2. Build adjacency matrix M (rows and columns in order 1,2,3):

    • m11 = 1 (because (1,1) ∈ R), m12 = 1, m13 = 0
    • m21 = 0, m22 = 0, m23 = 1
    • m31 = 0, m32 = 1, m33 = 0

    So M = [[1,1,0],[0,0,1],[0,1,0]].

  3. Check reflexive: diagonal entries are (1,0,0) so not all 1 → R is not reflexive.

  4. Check symmetric: M^T = [[1,0,0],[1,0,1],[0,1,0]] ≠ M so not symmetric.

  5. Check antisymmetric: look for i≠j with both mij and mji = 1. m23 = 1 and m32 = 1, so both present ⇒ not antisymmetric.

  6. Check transitive: compute M2 = M ⊙ M (Boolean product). Compute entries by OR over k:

    • (M2)_{1,3} = OR_k (m1k AND mk3) = (m11 AND m13) OR (m12 AND m23) OR (m13 AND m33) = (1 AND 0) OR (1 AND 1) OR (0 AND 0) = 1.
    • (M2)_{1,3} = 1 but m13 = 0 → M2 has 1 where M has 0 ⇒ not transitive.

Final: R is not reflexive, not symmetric, not antisymmetric, not transitive.

Example 2 — matrix → digraph → list of pairs

Given M = [[0,1,1],[0,1,0],[1,0,0]] on A = {a,b,c} with row/col order a,b,c.

  1. For each 1 at (i,j) list (ai,aj). Nonzero entries: m_ab = 1 → (a,b); m_ac = 1 → (a,c); m_bb = 1 → (b,b); m_ca = 1 → (c,a).

  2. Draw digraph: nodes a,b,c. Edges a→b, a→c, b→b (loop), c→a.

  3. Properties: diagonal has m_bb = 1 but m_aa = 0, m_cc = 0 so not reflexive. Symmetry? Check m_ac = 1 but m_ca = 1 too, m_ab = 1 but m_ba = 0 so not symmetric. Antisymmetric fails because m_ac and m_ca both 1. Transitive? compute M2 quickly: check a→b and b→b implies a→b (already), a→c and c→a gives a→a? (M2)_{aa} = (a→c AND c→a) = 1 so M2 has (a,a)=1 but M has m_aa=0 ⇒ not transitive.

Example 3 — composition via matrices (short trace)

Let R on {1,2} with MR = [[0,1],[0,0]] (1→2) and S with MS = [[0,0],[1,0]] (2→1). Then MR ⊙ MS = C with C11 = (m11 AND s11) OR (m12 AND s21) = (0 AND 0) OR (1 AND 1) = 1, so C11 = 1 meaning there is a composed relation 1→1 (path of length 2). The composed pairs R∘S = {(1,1)}.

Common mistakes

  • Forgetting loops: reflexive vs reflexive closure errors; when asked for reflexive closure add I (set diagonal to 1).
  • Thinking symmetry in the digraph (visual) is same as undirected: symmetric relation corresponds to pairs of opposite directed edges; undirected graphs are symmetric adjacency matrices but make that explicit.
  • For antisymmetry, mistakenly allowing loops to violate antisymmetry; antisymmetry allows loops (because condition is only for x ≠ y) unless the course defines otherwise; check your course definition.

For your exam

Typical question types: define terms (digraph, adjacency matrix), convert between representations, draw a digraph from ordered pairs, write the adjacency matrix from a digraph, test a relation for reflexive/symmetric/antisymmetric/transitive using matrix tests, compute R∘S by Boolean matrix product, compute (or explain) transitive closure conceptually or trace Warshall's algorithm (Warshall is a separate topic).

What full-marks answers include:

  • State the set ordering (node order) before giving matrix.
  • Show the matrix construction rule m_ij = 1 iff (ai,aj) ∈ R.
  • For property tests, show the relevant matrix condition (e.g., diagonal for reflexive, M = M^T for symmetric, M ⊙ M ≤ M for transitive) and apply it entrywise with a short check of counterexamples if any.
  • For diagrams, draw labelled nodes and arrows; mention loops and bidirectional edges clearly.

Quick check

  1. For A = {1,2} and R = {(1,2),(2,1)}, write the adjacency matrix and say whether R is symmetric, antisymmetric, reflexive.
  2. If M = [[1,0],[0,1]] what relation does M represent and which properties does it have?
  3. Define the Boolean product (A ⊙ B)_{ij} in words.

Answers: 1) M = [[0,1],[1,0]]; symmetric: yes; antisymmetric: no (since 1↔2 both ways); reflexive: no. 2) M is identity I: relation = {(1,1),(2,2)} (only loops); reflexive on this set? Yes (every element relates to itself); symmetric? Yes (because m_ij = m_ji holds); antisymmetric? Yes (no distinct i≠j with both directions). 3) (A ⊙ B){ij} is 1 if there exists some k such that A{ik}=1 and B_{kj}=1; otherwise 0.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?