¶ Finding Union and Intersection of Relations Using Matrices
The boolean operations join and meet can be used to find the matrices representing the union and the intersection of two relations. Suppose R1 and R2 are relations on a set A represented by the matrices MR1 and MR2, respectively. The matrix representing the union of these relations has a 1 in the positions where either MR1 or MR2 has a 1. The matrix representing the intersection has a 1 in positions where both MR1 and MR2 have a 1. The matrices representing these relations are
Let A=[aij] be an m×k boolean matrix and B=[bij] be a k×n boolean matrix. The boolean product of A and B, denoted by A⊙B, is the matrix m×n with (i,j)th entry cij where
Suppose R is a relation from A to B and S is a relation from B to C. Suppose AB and C have m, n and p elements, respectively. Let the boolean matrices for S∘R, R, and S be MS∘R=[tij], MR=[rij], and MS=[sij], respectively. These matrices have sizes m×p, m×n, and n×p, respectively. The ordered pair (ai,cj) belongs to S∘R iff there is an element bk such that (ai,bk) belongs to R and (bk,cj) belongs to S. It follows that tij=1 iff rik=skj=1 for some k.
From the definition of boolean product this means that
Let A be a square zero-one matrix and let r be a positive integer. The rth boolean power of A is the boolean product of r factors of A. The rth boolean product of A is denoted by A[r], Hence
A[r]=r times A⊙A⊙A⊙⋯⊙A.
We also define A[0] to be In.
(Remember that In is the identity matrix of ordern, which is the n×n matrix In=[δij] (The Kronecker delta) where δij=1 if i=j and δij=0 if i=j. Hence,
In=⎣⎢⎢⎢⎢⎢⎢⎢⎡10...001...0………00...1⎦⎥⎥⎥⎥⎥⎥⎥⎤
¶ Using Matrices Representing the Composite of Two Relations to find the Powers of a relation
The matrix representing the composite of two relations can be used to find the matrix for MRn. In particular,
