Matrix Representation of Relations

1. What Matrix Representation Means

A relation between two sets can be shown using a 0–1 matrix. The idea is simple: rows represent elements of the first set, columns represent elements of the second set, and each entry shows whether a particular ordered pair belongs to the relation.

2. How the Matrix Is Formed

Suppose a relation R is defined from set A to set B. To build the matrix, assign:

Rows → elements of A
Columns → elements of B
Entry = 1 if (a, b) ∈ R
Entry = 0 otherwise

3. Formal Definition

If A = {a₁, a₂, …, a_m} and B = {b₁, b₂, …, b_n}, then the matrix M_R of relation R is an m × n matrix defined by:

3.1. Matrix Entry Rule

M_R[i,j] = 1 \; \text{if } (a_i, b_j) \in R, \; \text{else } 0.

4. Example: Relation Between Two Sets

Let:

A = \{1,2,3\}

B = \{4,5\}

R = \{(1,4),(2,5)\}

Assign row and column order:

Rows → 1, 2, 3
Columns → 4, 5

5. Matrix for the Example

A ↓ / B →	4	5
1	1	0
2	0	1
3	0	0

Here:

1 at (1,4) → (1,4) ∈ R
1 at (2,5) → (2,5) ∈ R
0s elsewhere → no other pairs in R

6. Matrix Representation of Relations on the Same Set

If R ⊆ A × A, the matrix is square (same number of rows and columns). Diagonal entries represent self-pairs (a,a).

6.1. Example

A = \{x,y,z\}

R = \{(x,x),(x,z),(z,y)\}

The matrix (rows and columns in order x, y, z):

	x	y	z
x	1	0	1
y	0	0	0
z	0	1	0

7. How to Interpret the Matrix

From the matrix, you can quickly see:

Which pairs are included in the relation
Whether the relation is reflexive (all diagonal entries are 1)
Whether the relation is symmetric (matrix is symmetric about diagonal)
Possible chains for transitivity

8. Why Matrix Representation Is Useful

The matrix form is compact and works well for checking properties, especially for relations on the same set. It also helps when computing compositions or working with algorithms.

Maths