We have it within our reach to pick up another way of representing 2-adic relations, namely, the representation as logical matrices, and also to grasp the analogy between relational composition 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 of the 2-adic relations and .

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 and , the relational composition of and , in that order, is written as , or more simply as , and obtained as follows:

To compute , in general, where and 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 and .

To find the relational composition , 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 operation 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 formula for relation composition, viewed here on analogy with algebraic multiplication, let us examine what we did in multiplying the 2-adic relations and together to obtain their relational composite .

Arrangement

Given the space , whose cardinality is , there are elementary relations of the form , where and range over the space . 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:

Expansion

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

The notation indicates a logical sum over the collection of elementary relations , while the factors and are values in the boolean domain that are known as the coefficients of the relations and , respectively, with regard to the corresponding elementary relations .

In general, for a 2-adic relation , the coefficient of the elementary relation in the relation will be 0 or 1, respectively, as is excluded from or included in .

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

Extraction

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

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

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

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

In this formula, is the coefficient of with respect to the elementary relation .

One of the best ways to reason out what should be is to ask oneself what its coefficient should be for each of the elementary relations 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:

A moment's thought will tell us that if and only if there is an element in such that and .

Consequently, we have the result:

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

All that remains in order to obtain a computational formula for the relational composite of the 2-adic relations and is to collect the coefficients over the appropriate basis of elementary relations , as and range through .

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 is what is usually called a scalar product. In this case it is the scalar product of the row of with the column of .

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

The formula for computing says the following:

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