Let R Í A X B be a relation.

Further, let A = {a₁, a₂, …, a_N} and B = {b₁, b₂, …, b_N}

A matrix M_R representing the relation R can be constructed as follows.

Let the i^TH row of M_R correspond to a_i and let the j^TH column of M_R correspond to b_j .

Then IF (a_i, b_j) Î R THEN the ij^TH entry of M_R is1 ELSE the ij^TH entry of M_R is 0.

Whenever a relation is defined on the crossproduct of a set and itself the associated matrix is a square matrix. This is always true when we refer to powers of a relation.

Recall the properties of relations that we studied earlier - reflexivity, symmetry, antisymmetry and transitivity. Most of these properties (or their absence) are easily observable in matrices of relations.

Reflexivity - A matrix of a relation is reflexive iff every entry on the main diagonal of the matrix is equal to1.

Symmetry - A matrix of a relation is symmetric iff the ij^TH entry of the matrix equals the ji^TH entry of the matrix.

Antisymmetry - A matrix of a relation is antisymmetric iff whenever the ij^TH entry of the matrix equals 1 the ji^TH entry of the matrix = 0.

Transitivity - A matrix of a relation is transitive iff whenever entry (I,J) = 1 and entry (J,L) = 1 then entry (I,L) = 1.

The entries in the matrix of a relation R Í A X A are actually Boolean values written as 0 for false and 1 for true; indicating the absence or presence of elements of A X A. I.e. if the i,j entry of the matrix is 1 then (a_i, a_i) Î R else (a_i, a_i) Ï R.

Consequently, we would expect that operations on these matrices would correspond to Boolean operations. This is, in fact, the case. The Boolean operations meet (and) and join (or) may be defined on the matrices of relations just as the addition operation is defined on ordinary numeric matrices. (See pages 375 and 376 in the text).

Briefly, if R and S are relations and M_R = (a_ij) and M_S = (b_ij) then

M_R /\ M_S = (a_ij /\ b_ij) and M_R \/ M_S = (a_ij \/ b_ij)

If R and S are relations then the matrix associated with S o R is denoted M_{So R}.

M_{So R} = M_R o M_S where o is the Boolean product. (Notice again the reversal of R and S)

The Boolean product of two matrices is computed just as one would compute the ordinary product of two matrices except that AND takes the place of multiplication and OR takes the place of addition. The obvious operation tables apply.

In order to explain how one actually computes M_R o M_S let us first define the i^TH row of a matrix to be its i^TH row vector and the j^TH column of a matrix to be its j^TH column vector.

Next, let us define the Boolean product of a row vector by a column vector.

If A = (a₁, a₂, … a_N) is a row vector and B = (b₁, b₂, …b_N) is a column vector (ideally the elements of B are written in a column) then A o B = ((a₁/\ b₁) \/ (a₂/\ b₂) \/… \/ (a_N/\ b_N))

Example: Compute the Boolean product of the following vectors.

Finally, we may define the IJ^TH entry of matrix M_R o M_S to be the Boolean product of the I^TH row vector of M_R with the J^TH column vector of M_S.

Example: Find the Boolean product of matrices A and B given below.

Relations may also be represented using digraphs. The transformation is quite straightforward.

Let R Í A X A and let G be a digraph representing R.

Then each vertex of G represents an element of A and (a,b) is an edge from node a of G to node B of G iff (a,b) Î R.

Example: Draw the digraph, G, of the matrix, M, given below.

Label the nodes of the graph A, B and C.