Re: Relations And Their Divisitudes

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

RATD.  Note 30

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

Relational Composition as Logical Matrix Multiplication (cont.)

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

   G o H  =  Sum_ij (G o 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 boolean arithmetic
where summation corresponds to logical disjunction and multiplication
corresponds to logical conjunction.

By way of disentangling this formula, we 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^th row of G with
the j^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:

   G  =

   0 0 0 0 0 0 0
   0 0 0 0 0 0 0
   0 0 0 0 0 0 0
   0 0 1 1 1 0 0
   0 0 0 0 0 0 0
   0 0 0 0 0 0 0
   0 0 0 0 0 0 0

   H  =

   0 0 0 0 0 0 0
   0 0 0 0 0 0 0
   0 0 0 1 0 0 0
   0 0 0 1 0 0 0
   0 0 0 1 0 0 0
   0 0 0 0 0 0 0
   0 0 0 0 0 0 0

The formula for computing G o H tells us this:

   (G o H)_ij

    =   the ij^th entry in the matrix representation for G o H

    =   the entry in the i^th row and the j^th column of G o H

    =   the scalar product of the i^th row of G with the j^th column of H

    =   Sum_k (G_ik H_kj)

As it happens, we are enabled 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 o H.

   G o H  =

   0 0 0 0 0 0 0
   0 0 0 0 0 0 0
   0 0 0 0 0 0 0
   0 0 0 1 0 0 0
   0 0 0 0 0 0 0
   0 0 0 0 0 0 0
   0 0 0 0 0 0 0

Redundancy is the essence of information --

The more times you prove a thing,
the more you start to believe it.

Jon Awbrey

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o