2.1 Binary Relations, Representations & Relational Matrix Algebra

Back to Discrete Mathematics Notes

📚Module 02: Binary Relations & ClosuresTopic 2.1: Binary Relations, Representations & Matrix Algebra⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Airline Flight Route Network

Imagine an international airline operating flights between airports:

1. The Cartesian Product ($A \times B$): If airport set $A$ contains departure cities {London, Tokyo} and set $B$ contains arrivals {New York, Paris, Dubai}, the Cartesian product $A \times B$ represents every theoretically imaginable flight path from any city in $A$ to any city in $B$ (all $2 \times 3 = 6$ possible routes).
2. The Binary Relation ($R$): The actual operating schedule of the airline is a subset of this theoretical maximum space. The airline might only fly (London, New York) and (Tokyo, Paris). That scheduled subset is a binary relation!
3. The Inverse Relation ($R^{-1}$): The return flights! If an outbound flight flies from Tokyo to Paris, its inverse flies from Paris to Tokyo.
4. Relational Composition ($R \circ S$): Connecting flights with a layover! If flight $R$ takes you from London to New York, and domestic flight $S$ takes you from New York to San Francisco, the composite relation $R \circ S$ represents the end-to-end journey from London to San Francisco via the intermediate hub.

💻 Bridging to Computer Science: Foreign Keys, Graph Databases & Adjacency Matrices

In computer science, relations are everywhere. In relational databases (RDBMS), tables model relations, and an INNER JOIN over primary-foreign key pairs is mathematically identical to relational composition. In graph databases and network routing protocols, relations are encoded as 0-1 Boolean adjacency matrices where matrix multiplication computes multi-hop reachability in $O(V^3)$ time.

📑Table of Contents

• 🌐 The Cartesian Product: Foundational Space of Ordered Pairs
  • Foundational Properties of Cartesian Products
• 🔗 Binary Relations: Subsets of the Cartesian Universe
  • Binary Relations on a Single Set
• 📊 Representations of Relations: Roster, Matrix & Digraph
  • 1. Roster Form
  • 2. Zero-One Boolean Matrix
• 🔄 Relation Complement, Inverse & Dual Invariants
• ⚡ Composition of Relations & Boolean Matrix Multiplication
  • Computing Composition via Boolean Matrix Product
  • Foundational Invariants of Relational Composition
• 🌍 Real-World Engineering Context
• 📝 Step-by-Step Worked Examples
  • Example 1: Cartesian Product and Subset Counting
  • Example 2: Matrix Representation and Inverse Derivation
  • Example 3: Relational Composition via Boolean Matrix Multiplication
• 🎯 Exam & Interview Pitfall Check

---

🌐 The Cartesian Product: Foundational Space of Ordered Pairs

Before defining a relation, we must define the combinatorial space from which relations are drawn: the Cartesian Product.

📖Definition 2.1: The Cartesian Productdefinition

Let $A$ and $B$ be two arbitrary sets. The Cartesian product $A \times B$ is the set of all ordered pairs $(a, b)$ such that the first coordinate belongs to $A$ and the second coordinate belongs to $B$:

$$A \times B = \{(a, b) \mid a \in A \land b \in B\}$$$$|A \times B| = |A| \cdot |B| = m \cdot n$$

Foundational Properties of Cartesian Products

1. Non-Commutative Nature: In general, the Cartesian product is not commutative: $$A \times B \neq B \times A \quad (\text{unless } A = B \text{ or } A = \emptyset \text{ or } B = \emptyset)$$ Concrete Witness: Let $A = \{1\}$ and $B = \{2\}$.
   • $A \times B = \{(1, 2)\}$
   • $B \times A = \{(2, 1)\}$
   • Since $(1, 2) \neq (2, 1)$, $A \times B \neq B \times A$.
2. Distributivity over Union and Intersection: $$A \times (B \cup C) = (A \times B) \cup (A \times C)$$ $$A \times (B \cap C) = (A \times B) \cap (A \times C)$$
3. Monotonicity under Subsets: $$A \subseteq B \land C \subseteq D \implies (A \times C) \subseteq (B \times D)$$

---

🔗 Binary Relations: Subsets of the Cartesian Universe

A binary relation from set $A$ to set $B$ is formally defined as any subset of their Cartesian product.

📖Definition 2.2: Binary Relation & Total Combinationsdefinition

A relation $R$ from $A$ to $B$ is a subset of $A \times B$:

$$R \subseteq A \times B \iff R \in \mathcal{P}(A \times B)$$

If $(a, b) \in R$, we write $a \, R \, b$ (read: "$a$ is related to $b$ by $R$"). If $(a, b) \notin R$, we write $a \not{R} \, b$.

If $|A| = m$ and $|B| = n$, the total number of distinct relations from $A$ to $B$ is:

$$N_{\text{relations}} = 2^{|A \times B|} = 2^{mn}$$

Binary Relations on a Single Set

When $A = B$, a subset $R \subseteq A \times A$ is called a binary relation on set $A$.

📐Formula 2.1: Relations on a Set of Size nformula

For a set $A$ containing $|A| = n$ elements:

1. The Cartesian product has cardinality $|A \times A| = n^2$.
2. The total number of possible binary relations on $A$ is: $$N_{\text{binary relations}} = 2^{n^2}$$
3. Smallest Relation: The empty relation $\emptyset$ ($|\emptyset| = 0$).
4. Largest Relation: The universal relation $A \times A$ ($|A \times A| = n^2$).
5. Identity Relation: The diagonal relation $\Delta_A = \{(x, x) \mid x \in A\}$ ($|\Delta_A| = n$).

---

📊 Representations of Relations: Roster, Matrix & Digraph

To analyze and compute over relations efficiently, computer systems utilize three representations.

Matrix Representation (M_R) vs Directed Graph (Digraph)

Comparing computational bit-level matrix storage against visual structural graphs

Matrix Form

0-1 Boolean Matrix (M_R)

🔢

Dominant Architecture / DomainComputer Memory & Vectorized Bitmasks

• •A binary matrix of size m × n where rows represent A and columns represent B.
• •M_R[i, j] = 1 if (a_i, b_j) ∈ R, and 0 if (a_i, b_j) ∉ R.
• •Enables O(1) membership lookup: check index M_R[i, j].
• •Computes relational composition via hardware-accelerated Boolean matrix multiplication.

"Ideal for algorithmic graph engines, bitsets, and transitive closure computation."

Digraph Form

Directed Graph G = (V, E)

🕸️

Dominant Architecture / DomainVisual Topology & Network Traversals

• •Vertices V represent the elements of set A.
• •A directed edge (arrow) extends from vertex a to vertex b if and only if (a, b) ∈ R.
• •Self-loops (a → a) immediately reveal diagonal reflexive pairs.
• •Bidirectional arrows (a ⇄ b) visually expose symmetric pairings.

"Ideal for human cognitive intuition, path checking, and cycle detection."

1. Roster Form

Explicit enumeration of all participating ordered pairs inside curly braces:

$$R = \{(1, 2), \; (1, 3), \; (2, 3), \; (3, 1)\}$$

2. Zero-One Boolean Matrix

For $A = \{1, 2, 3\}$ and $R = \{(1, 1), (1, 3), (2, 2), (3, 1), (3, 2)\}$:

$$M_R = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \end{pmatrix}$$

• The entry at Row 1, Column 3 is $1$ because $(1, 3) \in R$.
• The entry at Row 2, Column 1 is $0$ because $(2, 1) \notin R$.

---

🔄 Relation Complement, Inverse & Dual Invariants

Like ordinary sets, relations support complementation and inversion operations.

📖Definition 2.3: Complement of a Relationdefinition

Let $R \subseteq A \times B$. The complement of relation $R$, denoted by $R^c$ or $R'$ or $\overline{R}$, consists of all ordered pairs in $A \times B$ that do not belong to $R$:

$$R^c = (A \times B) - R = \{(a, b) \in A \times B \mid (a, b) \notin R\}$$$$|R| + |R^c| = |A \times B| = mn$$$$R \cup R^c = A \times B \qquad \text{and} \qquad R \cap R^c = \emptyset$$

In Boolean matrix form, the complement inverts every bit: $M_{R^c}[i, j] = 1 - M_R[i, j]$.

📖Definition 2.4: Inverse of a Relationdefinition

Let $R \subseteq A \times B$. The inverse of relation $R$, denoted by $R^{-1}$, is the relation from $B$ to $A$ formed by reversing the coordinates of every ordered pair in $R$:

$$R^{-1} = \{(b, a) \in B \times A \mid (a, b) \in R\}$$$$|R^{-1}| = |R| \qquad \text{and} \qquad (R^{-1})^{-1} = R$$

In Boolean matrix form, inversion corresponds exactly to the matrix transpose:

$$M_{R^{-1}} = (M_R)^T$$

---

⚡ Composition of Relations & Boolean Matrix Multiplication

The most powerful algebraic operation over relations is composition, which chains relationships across an intermediate bridge set.

Multi-Hop Relational Composition Pipeline (R ∘ S)

Tracing path existence across intermediate set B to establish direct composite linkage

Domain Set A

Bridge Set B

Codomain Set C

Composite Link (A → C)

1

Domain Set A→Bridge Set B

Relation R Linkage: (a, b) ∈ R

2

Bridge Set B→Codomain Set C

Relation S Linkage: (b, c) ∈ S

3

Domain Set A→Composite Link (A → C)

Composite Formation: (a, c) ∈ (R ∘ S)

📖Definition 2.5: Relational Composition (R ∘ S)definition

Let $R \subseteq A \times B$ and $S \subseteq B \times C$. The composite relation $R \circ S$ (also written $S \circ R$ in some functional notations; here we evaluate left-to-right: $R$ first, then $S$) is a relation from $A$ to $C$ defined by:

$$R \circ S = \{(a, c) \in A \times C \mid \exists b \in B \text{ such that } (a, b) \in R \land (b, c) \in S\}$$

Computing Composition via Boolean Matrix Product

The matrix of the composite relation $M_{R \circ S}$ is the Boolean matrix product of $M_R$ and $M_S$ (denoted $M_R \odot M_S$). In Boolean matrix arithmetic, addition is logical OR ($\lor$) and multiplication is logical AND ($\land$):

📐Formula 2.2: Boolean Matrix Multiplication for Compositionformula

$$M_{R \circ S}[i, j] = \bigvee_{k=1}^{|B|} \Big( M_R[i, k] \land M_S[k, j] \Big)$$

An entry $M_{R \circ S}[i, j] = 1$ if and only if there exists at least one index $k$ such that row $i$ of $M_R$ and column $j$ of $M_S$ both have a $1$.

Foundational Invariants of Relational Composition

1. Associativity: $$(R \circ S) \circ T = R \circ (S \circ T)$$
2. Non-Commutative: In general, $R \circ S \neq S \circ R$.
3. Reversal Law for Inverses: $$(R \circ S)^{-1} = S^{-1} \circ R^{-1}$$

---

🌍 Real-World Engineering Context

1. Database Relational Calculus & SQL JOINs: In SQL, an INNER JOIN matches rows where TableA.user_id = TableB.user_id. This query operation is literally computing the relational composition of two relations $R_1 \subseteq \text{Orders} \times \text{Users}$ and $R_2 \subseteq \text{Users} \times \text{Addresses}$.
2. Access Control Matrices (RBAC): In cloud platforms, authorization uses composition:
   • Relation $R_1$: Maps Users to Roles (User → Role).
   • Relation $R_2$: Maps Roles to Permissions (Role → Permission).
   • The composite relation $R_1 \circ R_2$ computes effective user permissions (User → Permission).
3. Network Routing & Reachability: In IP networks, routing tables maintain binary adjacency relations. Squaring the adjacency matrix ($M_R \odot M_R$) yields all 2-hop reachable routers. Higher powers $M_R^k$ compute all $k$-hop reachable nodes.

---

📝 Step-by-Step Worked Examples

Example 1: Cartesian Product and Subset Counting

Problem Statement:
Let $A = \{1, 2, 3\}$ and $B = \{x, y\}$.

1. List all elements of $A \times B$ in roster form.
2. Determine the total number of binary relations from $A$ to $B$.
3. Determine how many of these relations contain exactly 3 ordered pairs.

Step-by-Step Solution:

1. Constructing $A \times B$: $$A \times B = \{(1, x), \; (1, y), \; (2, x), \; (2, y), \; (3, x), \; (3, y)\}$$ Cardinality: $|A \times B| = |A| \cdot |B| = 3 \times 2 = 6$.
2. Total Number of Relations: Each relation is a subset of $A \times B$. By the power set formula: $$N_{\text{relations}} = 2^{|A \times B|} = 2^6 = 64$$
3. Relations Containing Exactly 3 Pairs: Selecting any 3 pairs out of the 6 available: $$\binom{6}{3} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20 \text{ relations}$$

Key Takeaway:
Counting relations with specific cardinality bounds corresponds to choosing subsets of the Cartesian product using binomial coefficients $\binom{|A \times B|}{k}$.

---

Example 2: Matrix Representation and Inverse Derivation

Problem Statement:
Let $A = \{1, 2, 3\}$ and $R = \{(1, 2), (1, 3), (2, 1), (3, 2)\}$.

1. Construct the 0-1 Boolean matrix $M_R$.
2. Derive the matrix $M_{R^{-1}}$ and express $R^{-1}$ in roster form.
3. Compute the complement relation $R^c$ and state its cardinality.

Step-by-Step Solution:

1. Constructing $M_R$: Rows and columns correspond to index order $[1, 2, 3]$:
   • Row 1: $(1, 1) \notin R \to 0$, $(1, 2) \in R \to 1$, $(1, 3) \in R \to 1 \implies [0, 1, 1]$
   • Row 2: $(2, 1) \in R \to 1$, $(2, 2) \notin R \to 0$, $(2, 3) \notin R \to 0 \implies [1, 0, 0]$
   • Row 3: $(3, 1) \notin R \to 0$, $(3, 2) \in R \to 1$, $(3, 3) \notin R \to 0 \implies [0, 1, 0]$
   $$M_R = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$$
2. Deriving $M_{R^{-1}}$ via Transpose: Transposing rows into columns: $$M_{R^{-1}} = (M_R)^T = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$$ Converting back to roster form: $$R^{-1} = \{(2, 1), \; (3, 1), \; (1, 2), \; (2, 3)\}$$
3. Computing the Complement $R^c$: $|A \times A| = 3^2 = 9$. Since $|R| = 4$, $|R^c| = 9 - 4 = 5$. Inverting the zeros in $M_R$: $$R^c = \{(1, 1), \; (2, 2), \; (2, 3), \; (3, 1), \; (3, 3)\}$$

Key Takeaway:
The inverse relation corresponds directly to matrix transposition ($(M_R)^T$), preserving cardinality while flipping directional flow.

---

Example 3: Relational Composition via Boolean Matrix Multiplication

Problem Statement:
Let $A = \{1, 2, 3\}$, and let relations $R$ and $S$ on $A$ be defined by:

• $R = \{(1, 2), (2, 3), (3, 1)\}$
• $S = \{(1, 1), (2, 3), (3, 2)\}$

Compute the composite relation $R \circ S$ using Boolean matrix multiplication.

Step-by-Step Solution:

1. Construct Matrices $M_R$ and $M_S$: $$M_R = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}, \qquad M_S = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$$
2. Compute Boolean Matrix Product $M_{R \circ S} = M_R \odot M_S$:
   • Row 1:
     • Col 1: $(0 \land 1) \lor (1 \land 0) \lor (0 \land 0) = 0$
     • Col 2: $(0 \land 0) \lor (1 \land 0) \lor (0 \land 1) = 0$
     • Col 3: $(0 \land 0) \lor (1 \land 1) \lor (0 \land 0) = 1$
     • $\implies [0, 0, 1]$
   • Row 2:
     • Col 1: $(0 \land 1) \lor (0 \land 0) \lor (1 \land 0) = 0$
     • Col 2: $(0 \land 0) \lor (0 \land 0) \lor (1 \land 1) = 1$
     • Col 3: $(0 \land 0) \lor (0 \land 1) \lor (1 \land 0) = 0$
     • $\implies [0, 1, 0]$
   • Row 3:
     • Col 1: $(1 \land 1) \lor (0 \land 0) \lor (0 \land 0) = 1$
     • Col 2: $(1 \land 0) \lor (0 \land 0) \lor (0 \land 1) = 0$
     • Col 3: $(1 \land 0) \lor (0 \land 1) \lor (0 \land 0) = 0$
     • $\implies [1, 0, 0]$
   $$M_{R \circ S} = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}$$
3. Convert Matrix to Roster Pairs: $$R \circ S = \{(1, 3), \; (2, 2), \; (3, 1)\}$$ Verification via direct chaining:
   • $(1, 2) \in R$ and $(2, 3) \in S \implies (1, 3) \in R \circ S$
   • $(2, 3) \in R$ and $(3, 2) \in S \implies (2, 2) \in R \circ S$
   • $(3, 1) \in R$ and $(1, 1) \in S \implies (3, 1) \in R \circ S$ Both methods match.

Key Takeaway:
Boolean matrix multiplication implements relational composition without manual combinatorial backtracking across intermediate elements.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "Why is the Cartesian product A × B not commutative, while |A × B| = |B × A| is commutative?"
Key Focus Points:

• Ordered Pair Asymmetry: The elements of $A \times B$ are ordered pairs $(a, b)$. In general, $(a, b) \neq (b, a)$ unless $a = b$. Thus the set of ordered pairs is structurally distinct.
• Scalar Cardinality: The cardinality is the arithmetic product of two non-negative integers $|A| \cdot |B|$. Scalar multiplication over $\mathbb{W}$ is commutative ($m \cdot n = n \cdot m$).
• Implication: $A \times B$ and $B \times A$ are equivalent sets ($|A \times B| = |B \times A|$), but not equal sets.

Question 2: "What is the reversal law for relational composition and why does it hold?"
Key Focus Points:

• Formula: $(R \circ S)^{-1} = S^{-1} \circ R^{-1}$. Notice the order of relations is reversed!
• Path Reversal Intuition: If a path goes from $a \xrightarrow{R} b \xrightarrow{S} c$, then traveling backward from $c$ to $a$ requires first stepping backward through $S$ ($c \xrightarrow{S^{-1}} b$), then stepping backward through $R$ ($b \xrightarrow{R^{-1}} a$).

Common Interview Traps: Architectural Trade-Offs

Trap 1: Is a relation from A to B the same as a relation from B to A?
Answer: No. A relation from $A$ to $B$ is a subset of $A \times B$, while a relation from $B$ to $A$ is a subset of $B \times A$. They represent completely different directional spaces unless $A = B$.

Trap 2: Does an empty set have any relations?
Answer: Yes, exactly one! If $A = \emptyset$, then $A \times A = \emptyset \times \emptyset = \emptyset$. The number of relations on $\emptyset$ is $2^{0^2} = 2^0 = 1$. The only relation is the empty relation $\emptyset$ itself.

---

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic1.3 Set Operations, Venn Diagrams, Algebraic Laws & Cardinality TheoremsNext Topic →2.2 Relational Properties: Reflexivity, Symmetry, Transitivity & Antisymmetry