matrix representation of relation composition


compositionMathworldPlanetmathPlanetmath \PMlinkescapephraseComposition \PMlinkescapephraseorder \PMlinkescapephraseOrder \PMlinkescapephrasereflect \PMlinkescapephraseReflect \PMlinkescapephraserelationMathworldPlanetmath \PMlinkescapephraseRelation \PMlinkescapephraserelational compositionPlanetmathPlanetmath \PMlinkescapephraseRelational composition \PMlinkescapephraserepresentation \PMlinkescapephraseRepresentation \PMlinkescapephrasesimple \PMlinkescapephraseSimple

We have it within our reach to pick up another way of representing 2-adic relations (, namely, the representation as logical matricesMathworldPlanetmath, and also to grasp the analogyMathworldPlanetmath between relational composition ( and ordinary matrix multiplicationMathworldPlanetmath 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 GH 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 PX×Y and QY×Z, the relational composition of P and Q, in that order, is written as PQ, 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 productMathworldPlanetmathPlanetmath of two elementary relations of shapes a:b and c:d.


To find the relational composition GH, one may begin by writing it as a quasi-algebraic product:


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 operationMathworldPlanetmath of logical disjunction or set-theoretic aggregation, all of the positive multiplicities count as one, and this gives the ultimate result:


With an eye toward extracting a general formulaMathworldPlanetmathPlanetmath 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 GH.

1 Arrangement

Given the space X={1,2,3,4,5,6,7}, whose cardinality |X| is 7, there are |X×X|=|X||X|=77=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 collectionMathworldPlanetmath 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:


The notation ij indicates a logical sum over the collection of elementary relations i:j, while the factors Gij and Hij 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 Lij 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 GH can be regarded as a product of sums, a fact that can be indicated as follows:


The composite relation GH is itself a 2-adic relation over the same space X, in other words, GHX×X, and this means that GH must be amenable to being written as a logical sum of the following form:


In this formula, (GH)ij is the coefficient of GH with respect to the elementary relation i:j.

One of the best ways to reason out what GH should be is to ask oneself what its coefficient (GH)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 equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath form:


A moment’s thought will tell us that (GH)ij=1 if and only if there is an element k in X such that Gik=1 and Hkj=1.

Consequently, we have the result:


This follows from the properties of logical products and sums, specifically, from the fact that the product GikHkj is 1 if and only if both Gik and Hkj are 1, and from the fact that kFk is equal to 1 just in case some Fk is 1.

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


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 kGikHkj is what is usually called a scalar productMathworldPlanetmath. In this case it is the scalar product of the ith row of G with the jth 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 GH says the following:

(GH)ij=theijthentry in the matrix representation forGH=the entry in theithrow and thejthcolumn ofGH=the scalar product of theithrow ofGwith the jthcolumn ofH=kGikHkj

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 GH.


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