4.4. Binary Relations 85
This agrees with the Definition 4.3.1 of composition in the special case whenR
andSare functions.
We can represent a relation,S, between two setsAD fa 1 ;:::;angandBD
fb 1 ;:::;bmgas annmmatrix,MS, of zeroes and ones, with the elements ofMS
defined by the rule
MS.i;j/D 1 IFF aiS bj:
If we represent relations as matrices in this fashion, then we can compute the
composition of two relationsRandSby a “boolean” matrix multiplication, ̋,
of their matrices. Boolean matrix multiplication is the same as matrix multiplica-
tion except that addition is replaced byORand multiplication is replaced byAND.
Namely, supposeRWB!Cis a binary relation withCD fc 1 ;:::;cpg. SoMR
is anmpmatrix. ThenMS ̋MRis annpmatrix defined by the rule:
ŒMS ̋MRç.i;j/WWDORmkD 1 ŒMS.i;k/ANDMR.k;j/ç: (4.4)Prove that the matrix representation,MRıS, ofRıSequalsMS ̋MR(note
the reversal ofRandS).