12,080
edits
Changes
MyWikiBiz, Author Your Legacy — Friday November 22, 2024
Jump to navigationJump to searchupdate with TeX formatting
==Matrix representation==
==Matrix representation==
We have it within our reach to pick up another way of representing dyadic relations, namely, the representation as [[logical matrix|logical matrices]], and also to grasp the analogy between relational composition and ordinary [[matrix multiplication]] as it appears in [[linear algebra]].
We have it within our reach to pick up another way of representing dyadic relations, namely, the representation as ''[[logical matrix|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 ''G'' ο ''H'' of the dyadic relations ''G'' and ''H''.
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 <math>G \circ H\!</math> of the dyadic relations <math>G\!</math> and <math>H.\!</math>
Here is the setup that we had before:
Here is the setup that we had before:
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''X'' || = || {1, 2, 3, 4, 5, 6, 7}
|
<math>\begin{matrix}
X & = & \{ 1, 2, 3, 4, 5, 6, 7 \}
\end{matrix}</math>
|}
|}
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''G'' || = || 4:3 || + || 4:4 || + || 4:5 || ⊆ || ''X'' × ''X''
|
<math>\begin{matrix}
G & = & 4:3 & + & 4:4 & + & 4:5 & \subseteq & X \times X
\\
H & = & 3:4 & + & 4:4 & + & 5:4 & \subseteq & X \times X
\end{matrix}</math>
|}
|}
Let us recall the rule for finding the relational composition of a pair of dyadic relations. Given the dyadic relations ''P'' ⊆ ''X'' × ''Y'', ''Q'' ⊆ ''Y'' × ''Z'', the relational composition of ''P'' and ''Q'', in that order, is written as ''P'' ο ''Q'' or more simply as ''PQ'' and obtained as follows:
Let us recall the rule for finding the relational composition of a pair of dyadic relations. Given the dyadic relations <math>P \subseteq X \times Y\!</math> and <math>Q \subseteq Y \times Z,\!</math> the composition of <math>P ~\text{on}~ Q\!</math> is written as <math>P \circ Q,\!</math> or more simply as <math>PQ,\!</math> and obtained as follows:
To compute ''PQ'', in general, where ''P'' and ''Q'' are dyadic 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 compute <math>PQ,\!</math> in general, where <math>P\!</math> and <math>Q\!</math> are dyadic 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 <math>a:b\!</math> and <math>c:d.\!</math>
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || (a:b)(c:d) || = || (a:d) || if b = c
|
<math>\begin{matrix}
(a:b)(c:d) & = & (a:d) & \text{if}~ b = c
\\
(a:b)(c:d) & = & 0 & \text{otherwise}
\end{matrix}</math>
|}
|}
To find the relational composition ''G'' ο ''H'', one may begin by writing it as a quasi-algebraic product:
To find the relational composition <math>G \circ H,\!</math> one may begin by writing it as a quasi-algebraic product:
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''G'' ο ''H'' || = || (4:3 + 4:4 + 4:5)(3:4 + 4:4 + 5:4)
|
<math>\begin{matrix}
G \circ H & = & (4\!:\!3 ~+~ 4\!:\!4 ~+~ 4\!:\!5)(3\!:\!4 ~+~ 4\!:\!4 ~+~ 5\!:\!4)
\end{matrix}</math>
|}
|}
Multiplying this out in accord with the applicable form of distributive law one obtains the following expansion:
Multiplying this out in accord with the applicable form of distributive law one obtains the following expansion:
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''G'' ο ''H'' || = || (4:3)(3:4) || + || (4:3)(4:4) || + || (4:3)(5:4) || +
|
<math>\begin{matrix}
G \circ H
& = & (4:3)(3:4) & + & (4:3)(4:4) & + & (4:3)(5:4) & +
\\
& & (4:4)(3:4) & + & (4:4)(4:4) & + & (4:4)(5:4) & +
\\
& & (4:5)(3:4) & + & (4:5)(4:4) & + & (4:5)(5:4)
\end{matrix}</math>
|}
|}
Applying the rule that determines the product of elementary relations produces the following array:
Applying the rule that determines the product of elementary relations produces the following array:
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''G'' ο ''H'' || = || (4:4) || + || 0 || + || 0 || +
|
<math>\begin{matrix}
G \circ H
& = & 4:4 & + & 0 & + & 0 & +
\\
& & 0 & + & 4:4 & + & 0 & +
\\
& & 0 & + & 0 & + & 4:4
\end{matrix}</math>
|}
|}
Since the plus sign in this context represents an operation of logical disjunction or set-theoretic aggregation, all of the positive multiplicites count as one, and this gives the ultimate result:
Since the plus sign in this context represents an operation of logical disjunction or set-theoretic aggregation, all of the positive multiplicites count as one, and this gives the ultimate result:
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''G'' ο ''H'' || = || (4:4)
| <math>\begin{matrix}G \circ H & = & 4:4\end{matrix}</math>
|}
|}
With an eye toward extracting a general formula for relation composition, viewed here on analogy to algebraic multiplication, let us examine what we did in multiplying the dyadic relations ''G'' and ''H'' together to obtain their relational composite ''G'' o ''H''.
With an eye toward extracting a general formula for relation composition, viewed here on analogy to algebraic multiplication, let us examine what we did in multiplying the dyadic relations <math>G\!</math> and <math>H\!</math> together to obtain their relational composite <math>G \circ H.\!</math>
Given the space ''X'' = {1, 2, 3, 4, 5, 6, 7}, whose cardinality |''X''| is 7, there are |''X'' × ''X''| = |''X''| · |''X''| = 7 · 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:
Given the space <math>X = \{ 1, 2, 3, 4, 5, 6, 7 \},\!</math> whose cardinality <math>|X|\!</math> is <math>7,\!</math> there are <math>|X \times X| = |X| \cdot |X|\!</math> <math>=\!</math> <math>7 \cdot 7 = 49\!</math> elementary relations of the form <math>i:j,\!</math> where <math>i\!</math> and <math>j\!</math> range over the space <math>X.\!</math> Although they might be organized in many different ways, it is convenient to regard the collection of elementary relations as arranged in a lexicographic block of the following form:
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || 1:1 || 1:2 || 1:3 || 1:4 || 1:5 || 1:6 || 1:7
|
<math>\begin{matrix}
1\!:\!1 & 1\!:\!2 & 1\!:\!3 & 1\!:\!4 & 1\!:\!5 & 1\!:\!6 & 1\!:\!7
\\
2\!:\!1 & 2\!:\!2 & 2\!:\!3 & 2\!:\!4 & 2\!:\!5 & 2\!:\!6 & 2\!:\!7
\\
3\!:\!1 & 3\!:\!2 & 3\!:\!3 & 3\!:\!4 & 3\!:\!5 & 3\!:\!6 & 3\!:\!7
\\
4\!:\!1 & 4\!:\!2 & 4\!:\!3 & 4\!:\!4 & 4\!:\!5 & 4\!:\!6 & 4\!:\!7
\\
5\!:\!1 & 5\!:\!2 & 5\!:\!3 & 5\!:\!4 & 5\!:\!5 & 5\!:\!6 & 5\!:\!7
\\
6\!:\!1 & 6\!:\!2 & 6\!:\!3 & 6\!:\!4 & 6\!:\!5 & 6\!:\!6 & 6\!:\!7
\\
7\!:\!1 & 7\!:\!2 & 7\!:\!3 & 7\!:\!4 & 7\!:\!5 & 7\!:\!6 & 7\!:\!7
\end{matrix}</math>
|}
|}
The relations ''G'' and ''H'' may then be regarded as logical sums of the following forms:
The relations <math>G\!</math> and <math>H\!</math> may then be regarded as logical sums of the following forms:
{| cellpadding=8 style="text-align:center"
{| align="center" cellpadding="8" width="90%"
| || ''G'' || = || ∑<sub>''ij''</sub> ''G''<sub>''ij''</sub>(''i'':''j'')
|
<math>\begin{matrix}
G & = & \displaystyle\sum_{ij} G_{ij} (i\!:\!j)
\\[20pt]
H & = & \displaystyle\sum_{ij} H_{ij} (i\!:\!j)
\end{matrix}\!</math>
|}
|}
The notation ∑<sub>''ij''</sub> indicates a logical sum over the collection of elementary relations ''i'':''j'', while the factors ''G''<sub>''ij''</sub> and ''H''<sub>''ij''</sub> are values in the boolean domain '''B''' = {0, 1} that are known as the ''coefficients'' of the relations ''G'' and ''H'', respectively, with regard to the corresponding elementary relations ''i'':''j''.
The notation <math>\textstyle\sum_{ij}\!</math> indicates a logical sum over the collection of elementary relations <math>i\!:\!j\!</math> while the factors <math>G_{ij}\!</math> and <math>H_{ij}\!</math> are values in the ''[[boolean domain]]'' <math>\mathbb{B} = \{ 0, 1 \}~\!</math> that are called the ''coefficients'' of the relations <math>G\!</math> and <math>H,\!</math> respectively, with regard to the corresponding elementary relations <math>i\!:\!j.\!</math>
In general, for a dyadic relation ''L'', the coefficient ''L''<sub>''ij''</sub> 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''.
In general, for a dyadic relation <math>L,\!</math> the coefficient <math>L_{ij}\!</math> of the elementary relation <math>i\!:\!j\!</math> in the relation <math>L\!</math> will be <math>0\!</math> or <math>1,\!</math> respectively, as <math>i\!:\!j\!</math> is excluded from or included in <math>L.\!</math>
With these conventions in place, the expansions of ''G'' and ''H'' may be written out as follows:
With these conventions in place, the expansions of <math>G\!</math> and <math>H\!</math> may be written out as follows:
{| cellpadding=6 style="text-align:center"
{| align="center" cellpadding="4" width="90%"
| || ''G'' || = || 4:3 || + || 4:4 || + || 4:5 || =
|
<math>\begin{matrix}G & = & 4:3 & + & 4:4 & + & 4:5 & =\end{matrix}</math>
|-
|-
|
|
<math>\begin{smallmatrix}
0 \cdot (1:1) & + & 0 \cdot (1:2) & + & 0 \cdot (1:3) & + & 0 \cdot (1:4) & + & 0 \cdot (1:5) & + & 0 \cdot (1:6) & + & 0 \cdot (1:7) & +
\\
0 \cdot (2:1) & + & 0 \cdot (2:2) & + & 0 \cdot (2:3) & + & 0 \cdot (2:4) & + & 0 \cdot (2:5) & + & 0 \cdot (2:6) & + & 0 \cdot (2:7) & +
\\
0 \cdot (3:1) & + & 0 \cdot (3:2) & + & 0 \cdot (3:3) & + & 0 \cdot (3:4) & + & 0 \cdot (3:5) & + & 0 \cdot (3:6) & + & 0 \cdot (3:7) & +
\\
0 \cdot (4:1) & + & 0 \cdot (4:2) & + & \mathbf{1} \cdot (4:3) & + & \mathbf{1} \cdot (4:4) & + & \mathbf{1} \cdot (4:5) & + & 0 \cdot (4:6) & + & 0 \cdot (4:7) & +
\\
0 \cdot (5:1) & + & 0 \cdot (5:2) & + & 0 \cdot (5:3) & + & 0 \cdot (5:4) & + & 0 \cdot (5:5) & + & 0 \cdot (5:6) & + & 0 \cdot (5:7) & +
\\
0 \cdot (6:1) & + & 0 \cdot (6:2) & + & 0 \cdot (6:3) & + & 0 \cdot (6:4) & + & 0 \cdot (6:5) & + & 0 \cdot (6:6) & + & 0 \cdot (6:7) & +
\\
0 \cdot (7:1) & + & 0 \cdot (7:2) & + & 0 \cdot (7:3) & + & 0 \cdot (7:4) & + & 0 \cdot (7:5) & + & 0 \cdot (7:6) & + & 0 \cdot (7:7)
\end{smallmatrix}</math>
|}
|}
{| cellpadding=6 style="text-align:center"
{| align="center" cellpadding="4" width="90%"
| || ''H'' || = || 3:4 || + || 4:4 || + || 5:4 || =
|
<math>\begin{matrix}H & = & 3:4 & + & 4:4 & + & 5:4 & =\end{matrix}</math>
|-
|-
|
|
<math>\begin{smallmatrix}
0 \cdot (1:1) & + & 0 \cdot (1:2) & + & 0 \cdot (1:3) & + & 0 \cdot (1:4) & + & 0 \cdot (1:5) & + & 0 \cdot (1:6) & + & 0 \cdot (1:7) & +
\\
0 \cdot (2:1) & + & 0 \cdot (2:2) & + & 0 \cdot (2:3) & + & 0 \cdot (2:4) & + & 0 \cdot (2:5) & + & 0 \cdot (2:6) & + & 0 \cdot (2:7) & +
\\
0 \cdot (3:1) & + & 0 \cdot (3:2) & + & 0 \cdot (3:3) & + & \mathbf{1} \cdot (3:4) & + & 0 \cdot (3:5) & + & 0 \cdot (3:6) & + & 0 \cdot (3:7) & +
\\
0 \cdot (4:1) & + & 0 \cdot (4:2) & + & 0 \cdot (4:3) & + & \mathbf{1} \cdot (4:4) & + & 0 \cdot (4:5) & + & 0 \cdot (4:6) & + & 0 \cdot (4:7) & +
\\
0 \cdot (5:1) & + & 0 \cdot (5:2) & + & 0 \cdot (5:3) & + & \mathbf{1} \cdot (5:4) & + & 0 \cdot (5:5) & + & 0 \cdot (5:6) & + & 0 \cdot (5:7) & +
\\
0 \cdot (6:1) & + & 0 \cdot (6:2) & + & 0 \cdot (6:3) & + & 0 \cdot (6:4) & + & 0 \cdot (6:5) & + & 0 \cdot (6:6) & + & 0 \cdot (6:7) & +
\\
0 \cdot (7:1) & + & 0 \cdot (7:2) & + & 0 \cdot (7:3) & + & 0 \cdot (7:4) & + & 0 \cdot (7:5) & + & 0 \cdot (7:6) & + & 0 \cdot (7:7)
\end{smallmatrix}</math>
|}
|}
Stripping down to the bare essentials, one obtains the following matrices of coefficients for the relations ''G'' and ''H''.
Stripping down to the bare essentials, one obtains the following matrices of coefficients for the relations <math>G\!</math> and <math>H.\!</math>
{| style="text-align:center; width=30%"
{| align="center" cellpadding="8" width="90%"
| style="width:20px" | || ''G'' || =
|
<math>G ~=~ \begin{pmatrix}
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
\end{pmatrix}</math>
|}
|}
{| style="text-align:center; width=30%"
{| align="center" cellpadding="8" width="90%"
| style="width:20px" | || ''H'' || =
|
<math>H ~=~ \begin{pmatrix}
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
\end{pmatrix}</math>
|}
|}
These are the logical matrix representations of the dyadic relations ''G'' and ''H''.
These are the logical matrix representations of the dyadic relations <math>G\!</math> and <math>H.\!</math>
If the dyadic relations ''G'' and ''H'' are viewed as logical sums, then their relational composition ''G'' ο ''H'' can be regarded as a product of sums, a fact that can be indicated as follows:
If the dyadic relations <math>G\!</math> and <math>H\!</math> are viewed as logical sums then their relational composition <math>G \circ H\!</math> can be regarded as a product of sums, a fact that can be indicated as follows:
{| align="center" cellpadding="8" width="90%"
| <math>G \circ H ~=~ (\sum_{ij} G_{ij} (i\!:\!j))(\sum_{ij} H_{ij} (i\!:\!j)).\!</math>
|}
The composite relation ''G'' ο ''H'' is itself a dyadic relation over the same space ''X'', in other words, ''G'' ο ''H'' ⊆ ''X'' × ''X'', and this means that ''G'' ο ''H'' must be amenable to being written as a logical sum of the following form:
The composite relation ''G'' ο ''H'' is itself a dyadic relation over the same space ''X'', in other words, ''G'' ο ''H'' ⊆ ''X'' × ''X'', and this means that ''G'' ο ''H'' must be amenable to being written as a logical sum of the following form:
By way of disentangling this formula, one may notice that the form ∑<sub>''k''</sub> (''G''<sub>''ik''</sub>''H''<sub>''kj''</sub>) is what is usually called a "scalar product". In this case it is the scalar product of the ''i''<sup>th</sup> row of ''G'' with the ''j''<sup>th</sup> column of ''H''.
By way of disentangling this formula, one may notice that the form ∑<sub>''k''</sub> (''G''<sub>''ik''</sub>''H''<sub>''kj''</sub>) is what is usually called a "scalar product". In this case it is the scalar product of the ''i''<sup>th</sup> row of ''G'' with the ''j''<sup>th</sup> 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:
To make this statement more concrete, let us go back to the examples of <math>G\!</math> and <math>H\!</math> we came in with:
{| style="text-align:center; width=30%"
{| align="center" cellpadding="8" width="90%"
| style="width:20px" | || ''G'' || =
|
<math>G ~=~ \begin{pmatrix}
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
\end{pmatrix}</math>
|}
|}
{| style="text-align:center; width=30%"
{| align="center" cellpadding="8" width="90%"
| style="width:20px" | || ''H'' || =
|
<math>H ~=~ \begin{pmatrix}
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
\end{pmatrix}</math>
|}
|}
The formula for computing ''G'' ο ''H'' says the following:
The formula for computing <math>G \circ H\!</math> says the following:
{| cellpadding="2"
{| cellpadding="2"
