Relations · step 4 of 13

Matrix & digraph representations

A relation on a finite set can be stored as a 0/1 matrix M with Mᵢⱼ = 1 exactly when (aᵢ, aⱼ) ∈ R, or drawn as a digraph with an arrow from aᵢ to aⱼ. Both representations make properties visible at a glance: reflexivity is a diagonal of ones (a loop at every vertex), symmetry is M = Mᵀ (every arrow doubled), and transitivity is a closure condition on paths.

Practise matrix & digraph representations free → All Relations subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Fix the element orderRow and column i must correspond to the same element. State the ordering — a matrix without it is unreadable.
Read reflexivity off the diagonalAll ones on the main diagonal means reflexive; all zeros means irreflexive; anything else is neither.
Read symmetry as transpositionM = Mᵀ characterises symmetry. Antisymmetry means Mᵢⱼ and Mⱼᵢ are never both 1 for i ≠ j.
Check transitivity by pathsIn the digraph, every two-step path must have its shortcut edge. In matrix terms, wherever M² has a 1, M must have one too.

Worked example

For R on {1,2,3} with matrix rows (1,1,0), (0,1,1), (0,0,1), describe the digraph and decide reflexivity and transitivity.

Pairs: (1,1),(1,2),(2,2),(2,3),(3,3).
Digraph: loops at all three vertices, plus arrows 1→2 and 2→3.
Diagonal is all ones, so R is reflexive.
Path 1→2→3 exists, but the matrix has M₁₃ = 0, so the shortcut 1→3 is missing.

Answer. Reflexive but not transitive — adding (1,3) would be required.

Where marks get dropped

These are the specific errors that cost credit on matrix & digraph representations questions — QED's rubric penalises each of them separately.

Using different orderings for rows and columns, which scrambles every reading of the matrix.
Confusing the relation matrix with an adjacency matrix of an undirected graph — relation matrices need not be symmetric.
Reading transitivity as "M² = M". The correct condition is that M² has a 1 only where M does, i.e. M² ≤ M entrywise.

Practise this until it is automatic

Unlimited fresh questions

QED generates new matrix & digraph representations problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Relations mastery is tracked so you know when this is exam-ready.

Matrix & digraph representations — frequently asked questions

How do I compose relations with matrices?

Multiply the 0/1 matrices using Boolean arithmetic: entry (i,j) is 1 if some k has Mᵢₖ = Nₖⱼ = 1. This is ordinary matrix multiplication with OR in place of addition.

What does Mⁿ tell me?

Entry (i,j) of the Boolean power Mⁿ is 1 exactly when there is a path of length n from i to j. Summing the powers gives reachability.

Which representation should I use in an exam?

Digraphs for small relations and property-spotting; matrices for composition, powers and closures. Questions often ask you to move between them, so practise both.

The rest of Relations

Properties of relations, composition, and representations. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make matrix & digraph representations exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →