ONT 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