Relations as Matrices

Boolean Matrices

A boolean matrix is a matrix whose entries are $0$ or $1$, with operations:

• And ($\land$): for multiplication-like operations
• Or ($\lor$): for addition-like operations

The Boolean Semiring

The boolean semiring $\mathbb{B} = \{0, 1\}$ has:

• Addition: $0 \lor 0 = 0$, $0 \lor 1 = 1$, $1 \lor 0 = 1$, $1 \lor 1 = 1$ (OR)
• Multiplication: $0 \land 0 = 0$, $0 \land 1 = 0$, $1 \land 0 = 0$, $1 \land 1 = 1$ (AND)

Matrix-Relation Correspondence

From Relation to Matrix

For finite sets $A = [m]$ and $B = [n]$, a relation $R : A \nrightarrow B$ corresponds to an $m \times n$ boolean matrix $\text{mat}(R)$:

$\text{mat}(R)_{ij} = \begin{cases} 1 & \text{if } iRj \\ 0 & \text{otherwise} \end{cases}$

From Matrix to Relation

Given an $m \times n$ boolean matrix $M$, define $\text{rel}(M) : [m] \nrightarrow [n]$ by:

$i\,\text{rel}(M)\,j \iff M_{ij} = 1$

Mutual Inverses

$\text{rel}(\text{mat}(R)) = R \quad \text{and} \quad \text{mat}(\text{rel}(M)) = M$

This is a bijection between relations $[m] \nrightarrow [n]$ and $m \times n$ boolean matrices.

Matrix Operations for Relations

Composition as Matrix Multiplication

For $R : [m] \nrightarrow [n]$ and $S : [n] \nrightarrow [p]$:

$\text{mat}(S \circ R) = \text{mat}(S) \otimes \text{mat}(R)$

where $\otimes$ is boolean matrix multiplication:

$(M \otimes N)_{ik} = \bigvee_{j=1}^{n} (M_{ij} \land N_{jk})$

Union as Matrix Addition

$\text{mat}(R \cup S) = \text{mat}(R) \oplus \text{mat}(S)$

where $\oplus$ is boolean matrix addition (pointwise OR):

$(M \oplus N)_{ij} = M_{ij} \lor N_{ij}$

Example

Let $R : \{1, 2\} \nrightarrow \{a, b\}$ with $R = \{(1, a), (2, b)\}$.

$\text{mat}(R) = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$

Let $S : \{a, b\} \nrightarrow \{X, Y\}$ with $S = \{(a, X), (b, Y)\}$.

$\text{mat}(S) = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$

Then $S \circ R = \{(1, X), (2, Y)\}$ and:

$\text{mat}(S) \otimes \text{mat}(R) = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \otimes \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$

Reachability via Matrix Powers

The Adjacency Matrix

For a relation $R : [n] \nrightarrow [n]$, the matrix $\text{mat}(R)$ is the adjacency matrix of the corresponding directed graph.

Path Matrices

The matrix $\text{mat}(R)^{\circ k} = \text{mat}(R) \otimes \cdots \otimes \text{mat}(R)$ (k times) encodes paths of length exactly $k$.

Computing Reachability

Define:

$M_0 = I_n \quad \text{(identity matrix)}$ $M_{k+1} = I_n \oplus (M \otimes M_k)$

Then $M_n = \text{mat}(R^{\circ *})$, the adjacency matrix of the path relation.

Why This Works

• A simple path in an $n$-vertex graph has length $< n$
• $M_k$ accumulates all paths of length $\leq k$
• By step $n$, all reachable vertices are discovered

Example

For $R = \{(1, 2), (2, 3), (3, 1)\}$ (a 3-cycle):

$\text{mat}(R) = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$

Computing $M_3$ gives $\text{mat}(R^{\circ *}) = \text{mat}(\{1, 2, 3\} \times \{1, 2, 3\})$ (everything reachable).

---

Semirings for Different Graph Problems

The power of matrix multiplication is that changing the underlying semiring changes what problem we solve.

The General Formula

Matrix multiplication over a semiring $(S, \oplus, \otimes, 0, 1)$:

$(M \otimes N)_{ik} = \bigoplus_{j=1}^{n} (M_{ij} \otimes N_{jk})$

This formula works for ANY semiring!

Comparison of Semirings

Semiring	Addition $\oplus$	Multiply $\otimes$	Zero	One	Computes
Boolean	$\lor$ (OR)	$\land$ (AND)	$0$	$1$	Reachability
Min-Plus	$\min$	$+$	$\infty$	$0$	Shortest path
Max-Plus	$\max$	$+$	$-\infty$	$0$	Longest path
Standard	$+$	$\times$	$0$	$1$	Path counting

The Boolean Semiring: Reachability

For adjacency matrix $A$:

$A^k_{ij} = 1 \iff \text{exists path of length } k \text{ from } i \text{ to } j$

$A^*_{ij} = 1 \iff \text{exists ANY path from } i \text{ to } j$

The Min-Plus Semiring: Shortest Path

For weighted adjacency matrix $W$ (where $W_{ij}$ = weight of edge $i \to j$, $\infty$ if no edge):

$W_{ij}^{(k)} = \min_{j_1, \ldots, j_{k-1}}(W_{ij_1} + W_{j_1 j_2} + \cdots + W_{j_{k-1}j})$

This is the minimum cost of any path of exactly $k$ edges.

$W^*_{ij} = \text{shortest path cost from } i \text{ to } j$

Example: Shortest Path

Consider weighted graph:

    1 --3--> 2
    |        |
    4        1
    |        |
    v        v
    3 --2--> 4

Adjacency matrix (min-plus):

$W = \begin{pmatrix} \infty & 3 & 4 & \infty \\ \infty & \infty & \infty & 1 \\ \infty & \infty & \infty & 2 \\ \infty & \infty & \infty & \infty \end{pmatrix}$

$W^2$ computes shortest paths of exactly 2 edges:

$W^2_{1,4} = \min(W_{1,2} + W_{2,4}, W_{1,3} + W_{3,4}) = \min(3+1, 4+2) = 4$

The path $1 \to 2 \to 4$ costs 4, which is cheaper than $1 \to 3 \to 4$ (cost 6).

Identity Elements in Min-Plus

• Additive identity ($\oplus$-identity): $\infty$ (since $\min(x, \infty) = x$)
• Multiplicative identity ($\otimes$-identity): $0$ (since $x + 0 = x$)

Annnihilation Property

$\infty + x = \infty$

Even if a path exists ($x$ finite), if you must traverse a non-existent edge ($\infty$), the total is impossible.

Warning: Negative Weights

The min-plus semiring works correctly only when:

• All edge weights are non-negative, OR
• The graph has no negative-weight cycles

If negative cycles exist, shortest paths may not be well-defined.

---

Summary

• Relations on finite sets correspond to boolean matrices
• Composition corresponds to boolean matrix multiplication
• Union corresponds to boolean matrix addition
• Matrix powers compute reachability in directed graphs
• Changing the semiring changes the problem: Boolean = reachability, Min-Plus = shortest path
• Min-Plus semiring: $\oplus = \min$, $\otimes = +$, identities are $\infty$ and $0$