matrix representation of relation composition

composition Composition order Order reflect Reflect relation Relation relational composition Relational composition representation Representation simple Simple

We have it within our reach to pick up another way of representing 2-adic relations (http://planetmath.org/RelationTheory), namely, the representation as logical matrices, and also to grasp the analogy between relational composition (http://planetmath.org/RelationComposition2) and ordinary matrix multiplication as it appears in linear algebra.

First of all, while we still have the data of a very simple concrete case in mind, let us reflect on what we did in our last Example in order to find the composition $G\circ H$ of the 2-adic relations $G$ and $H$.

Here is the setup that we had before:

Let us recall the rule for finding the relational composition of a pair of 2-adic relations. Given the 2-adic relations $P\subseteq X\times Y$ and $Q\subseteq Y\times Z$, the relational composition of $P$ and $Q$, in that order, is written as $P\circ Q$, or more simply as $PQ$, and obtained as follows:

To compute $PQ$, in general, where $P$ and $Q$ are 2-adic relations, simply multiply out the two sums in the ordinary distributive algebraic way, but subject to the following rule for finding the product of two elementary relations of shapes $a:b$ and $c:d$.

To find the relational composition $G\circ H$, one may begin by writing it as a quasi-algebraic product:

$G\circ H=(4:3+4:4+4:5)(3:4+4:4+5:4)$

Multiplying this out in accord with the applicable form of distributive law one obtains the following expansion:

Applying the rule that determines the product of elementary relations produces the following array:

Since the plus sign in this context represents an operation of logical disjunction or set-theoretic aggregation, all of the positive multiplicities count as one, and this gives the ultimate result:

$G\circ H=(4:4)$

With an eye toward extracting a general formula for relation composition, viewed here on analogy with algebraic multiplication, let us examine what we did in multiplying the 2-adic relations $G$ and $H$ together to obtain their relational composite $G\circ H$.

1 Arrangement

Given the space $X=\{1,2,3,4,5,6,7\}$, whose cardinality $|X|$ is $7$, there are $|X\times X|=|X|\cdot |X|=7\cdot 7=49$ elementary relations of the form $i:j$, where $i$ and $j$ range over the space $X$. Although they might be organized in many different ways, it is convenient to regard the collection of elementary relations as being arranged in a lexicographic block of the following form:

2 Expansion

The relations $G$ and $H$ may then be regarded as logical sums of the following forms:

$G={\sum }_{ij}{G}_{ij}(i:j)$
$H={\sum }_{ij}{H}_{ij}(i:j)$

The notation ${\sum }_{ij}$ indicates a logical sum over the collection of elementary relations $i:j$, while the factors $G_{ij}$ and $H_{ij}$ are values in the boolean domain $𝔹=\{0,1\}$ that are known as the coefficients of the relations $G$ and $H$, respectively, with regard to the corresponding elementary relations $i:j$.

In general, for a 2-adic relation $L$, the coefficient $L_{ij}$ of the elementary relation $i:j$ in the relation $L$ will be 0 or 1, respectively, as $i:j$ is excluded from or included in $L$.

With these conventions in place, the expansions of $G$ and $H$ may be written out as follows:

3 Extraction

Stripping down to the bare essentials, one obtains the following matrices of coefficients for the relations $G$ and $H$.

These are the logical matrix representations of the 2-adic relations $G$ and $H$.

If the 2-adic relations $G$ and $H$ are viewed as logical sums, then their relational composition $G\circ H$ can be regarded as a product of sums, a fact that can be indicated as follows:

$G\circ H=({\sum }_{ij}{G}_{ij}(i:j))({\sum }_{ij}{H}_{ij}(i:j)).$

The composite relation $G\circ H$ is itself a 2-adic relation over the same space $X$, in other words, $G\circ H\subseteq X\times X$, and this means that $G\circ H$ must be amenable to being written as a logical sum of the following form:

$G\circ H={\sum }_{ij}{(G\circ H)}_{ij}(i:j).$

In this formula, ${(G\circ H)}_{ij}$ is the coefficient of $G\circ H$ with respect to the elementary relation $i:j$.

One of the best ways to reason out what $G\circ H$ should be is to ask oneself what its coefficient ${(G\circ H)}_{ij}$ should be for each of the elementary relations $i:j$ in turn.

So let us pose the question:

In order to answer this question, it helps to realize that the indicated product given above can be written in the following equivalent form:

$G\circ H=({\sum }_{ik}{G}_{ik}(i:k))({\sum }_{kj}{H}_{kj}(k:j)).$

A moment’s thought will tell us that ${(G\circ H)}_{ij}=1$ if and only if there is an element $k$ in $X$ such that $G_{ik}=1$ and $H_{kj}=1$.

Consequently, we have the result:

${(G\circ H)}_{ij}={\sum }_k{G}_{ik}{H}_{kj}.$

This follows from the properties of logical products and sums, specifically, from the fact that the product $G_{ik}{H}_{kj}$ is 1 if and only if both $G_{ik}$ and $H_{kj}$ are 1, and from the fact that ${\sum }_k{F}_k$ is equal to 1 just in case some $F_k$ is 1.

All that remains in order to obtain a computational formula for the relational composite $G\circ H$ of the 2-adic relations $G$ and $H$ is to collect the coefficients ${(G\circ H)}_{ij}$ over the appropriate basis of elementary relations $i:j$, as $i$ and $j$ range through $X$.

$G\circ H={\sum }_{ij}{(G\circ H)}_{ij}(i:j)={\sum }_{ij}({\sum }_k{G}_{ik}{H}_{kj})(i:j).$

This is the logical analogue of matrix multiplication in linear algebra, the difference in the logical setting being that all of the operations performed on coefficients take place in a system of logical arithmetic where summation corresponds to logical disjunction and multiplication corresponds to logical conjunction.

By way of disentangling this formula, one may notice that the form ${\sum }_k{G}_{ik}{H}_{kj}$ is what is usually called a scalar product. In this case it is the scalar product of the $i^{\text{th}}$ row of $G$ with the $j^{\text{th}}$ column of $H$.

To make this statement more concrete, let us go back to the particular examples of $G$ and $H$ that we came in with:

The formula for computing $G\circ H$ says the following:

As it happens, it is possible to make exceedingly light work of this example, since there is only one row of $G$ and one column of $H$ that are not all zeroes. Taking the scalar product, in a logical way, of the fourth row of $G$ with the fourth column of $H$ produces the sole non-zero entry for the matrix of $G\circ H$.

Title	matrix representation of relation composition
Canonical name	MatrixRepresentationOfRelationComposition
Date of creation	2013-03-22 17:50:28
Last modified on	2013-03-22 17:50:28
Owner	Jon Awbrey (15246)
Last modified by	Jon Awbrey (15246)
Numerical id	21
Author	Jon Awbrey (15246)
Entry type	Example
Classification	msc 68R01
Classification	msc 68P15
Classification	msc 08A02
Classification	msc 05C65
Classification	msc 05B30
Classification	msc 05B20
Classification	msc 03E20
Classification	msc 03B10
Related topic	RelationTheory
Related topic	AlgebraicRepresentationOfRelationComposition
Related topic	GeometricRepresentationOfRelationComposition
Related topic	GraphTheoreticRepresentationOfRelationComposition
Related topic	LogicalMatrix