Matrix Representation of Relations

A relation can be represented intuitively and easily manageable using a matrix. Matrix representation is particularly useful for computer processing and graph analysis.

Formal Description

Let A = {a₁, a₂, …, aₙ} be a set, and R a relation on A. The matrix of the relation is an n×n 0-1 matrix M, where:

The rows and columns are indexed by the elements of A in the same order. The entry M[i,j] is 1 if there is a connection from a_i to a_j, otherwise 0.

Example

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

The matrix is:

Row 1 (for 1): connected to 2, so second entry 1. Row 2 (for 2): connected to 3, so third entry 1. All others 0.

Properties in Matrix Form

• Reflexive relations have 1s on the main diagonal.
• Symmetric relations have a symmetric matrix across the main diagonal.
• For transitive relations, powers of the matrix (composition) can produce new connections.
• Matrix representation facilitates the implementation of computer algorithms.

Summary

Matrix representation of relations is a simple way to record connections: we show all connections between set elements in 0-1 matrix form. This is particularly useful in graph analysis and computer processing.

Practice Exercise