Course contentsShow
← Mathematics
Lesson 2541 of 3,12151. Discrete Math — Sets, Relations, FunctionsFree lesson

Representing Relations: Matrices and Digraphs

Represent finite relations using matrices and directed graphs to visualize and analyze their structure.

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.