Representing Relations: Matrices and Digraphs
You'll learn two visual and computational ways to represent finite relations: matrices and directed graphs.
Why Represent Relations Visually?
A relation between finite sets can be written as a set of ordered pairs, but that becomes unwieldy for large relations. Two powerful representations make relations easier to analyze: relation matrices and directed graphs (digraphs).
Relation Matrices
Given a relation R from set A = {a₁, a₂, ..., aₘ} to set B = {b₁, b₂, ..., bₙ}, we can create an m × n matrix M where:
- M[i,j] = 1 if (aᵢ, bⱼ) ∈ R
- M[i,j] = 0 otherwise
Example: If A = {1, 2, 3}, B = {x, y}, and R = {(1,x), (2,x), (2,y), (3,y)}, the matrix is:
x y
1 [ 1 0 ]
2 [ 1 1 ]
3 [ 0 1 ]
Rows represent elements of A, columns represent elements of B. A "1" means the relation holds.
Directed Graphs (Digraphs)
A digraph visualizes relations using:
- Vertices (nodes) for each element in the set(s)
- Directed edges (arrows) from a to b whenever (a,b) ∈ R
For the same relation above, you'd draw nodes for 1, 2, 3, x, y, with arrows: 1→x, 2→x, 2→y, 3→y.
Why This Matters
Matrices enable algebraic manipulation (composition becomes matrix multiplication!), while digraphs provide intuitive visualization of properties like reflexivity, symmetry, and transitivity at a glance.
Key Takeaway: Matrices and digraphs transform abstract relations into concrete structures you can compute with and visualize, making complex properties obvious and operations systematic.