Matrix Multiplication Interpretation of Relation Composition

From ProofWiki
Jump to: navigation, search

Theorem

Let $A$, $B$ and $C$ be finite non-empty sets that are initial segments of $\N_{\ne 0}$.

Let $\mathcal R \subseteq B \times A$ and $\mathcal S \subseteq C \times B$ be relations.

Let $\mathbf R$ and $\mathbf S$ be matrices which we define as follows:

$\left[{r}\right]_{i j} = \begin{cases} T & : (i, j) \in \mathcal R \\ F & : (i, j) \notin \mathcal R\\ \end{cases}$
$\left[{s}\right]_{i j} = \begin{cases} T & : (i, j) \in \mathcal S \\ F & : (i, j) \notin \mathcal S\\ \end{cases}$

Then we can interpret the matrix product $\mathbf R \mathbf S$ as the composition $\mathcal S \circ \mathcal R$.

To do so we temporarily consider $\left({\left\{ {T, F}\right\}, \land, \lor}\right)$ to be our "ring" on which we are basing matrix multiplication.

Then:

$\left[{r s}\right]_{i j} = T \iff (i, j) \in \mathcal S \circ \mathcal R$


Proof

Sufficient Condition

Suppose for some $i, j$:

$\left[{r s}\right]_{i j} = T$

Then by the definition of $\lor$ there must exist some $k$ for which:

$\left[{r}\right]_{i k} \land \left[{s}\right]_{k j} = T$

which by our definition implies:

$\left({i, k}\right) \in \mathcal R$
$\left({k, j}\right) \in \mathcal S$


Then by the definition of a composite relation:

$(\left({i, j}\right) \in \mathcal R \circ \mathcal S$


Necessary Condition

Suppose for some $i, j$:

$\left({i, j}\right) \in \mathcal S \circ \mathcal R$

Then there exists a $k$ for which:

$\left({i, k}\right) \in \mathcal R$
$\left({k, j}\right) \in \mathcal S$

Hence:

$\left[{r}\right]_{i k} = T$
$\left[{s}\right]_{k j} = T$

and there exists some $k$ for which:

$\left[{r}\right]_{i k} \land \left[{s}\right]_{k j} = T$

Hence by the definition of $\lor$:

$\left[{r s}\right]_{i j} = T$

$\blacksquare$