We have discussed two of the many possible ways of representing a relation, namely as a digraph or as a set of ordered pairs. In this section we will discuss the representation of relations by matrices.
There are a wide variety of terms that also used to refer to the matrix of a relation. They include logical matrix, binary matrix, Boolean matrix, and -matrix. For relations on a set, the relation matrix is also referred to as an adjacency matrix, a term we will use in our future study of graphs.
We do not write only for notational purposes. In fact, can be obtained from the matrix product ; however, we must use a slightly different form of arithmetic.
Theorem6.4.7.Composition is Matrix Multiplication.
Let ,, and be finite sets where is a relation from into and is a relation from into . If and are the adjacency matrices of and , respectively, then the product using Boolean arithmetic is the relation matrix of the composition .
Remark: A convenient help in constructing the matrix of a relation from a set into a set is to write the elements from in a column preceding the first column of the matrix, and the elements of in a row above the first row. Initially, in Example 3 would be
To fill in the matrix, is 1 if and only if . So that, since the pair , the entry of corresponding to the row labeled 2 and the column labeled 5 in the matrix is a 1.
This final example gives an insight into how relational data base programs can systematically answer questions pertaining to large masses of information. Matrices (on the left) and (on the right) define the relations and where if software can be run with operating system , and if operating system can run on computer .
OS1OS2OS3OS4P1P2P3P4C1C2C3OS1OS2OS3OS4
Although the relation between the software and computers is not implicit from the data given, we can easily compute this information. The matrix of is , which is
C1C2C3P1P2P3P4
This matrix tells us at a glance which software will run on the computers listed. In this case, all software will run on all computers with the exception of program P2, which will not run on the computer C3, and programs P3 and P4, which will not run on the computer C1.
Let be the set of weekdays, Monday through Friday, let be a set of employees of a tutoring center, and let be a set of computer languages for which tutoring is offered, . We define (schedule) from into by if is scheduled to work on day . We also define from into by if can tutor students in language . If and are defined by matrices
The graph of a relation on three elements has nine entries. The three entries in the diagonal must be 1 in order for the relation to be reflexive. In addition, to make the relation symmetric, the off-diaginal entries can be paired up so that they are equal. For example if the entry in row 1 column 2 is equal to 1, the entry in row 2 column 1 must also be 1. This means that three entries, the ones above the diagonal determine the whole matrix, so there are different reflexive, symmetric relations on a three element set.
To verify that the converse is not true we need only one example. For , let and all other entries equal , and let be the zero matrix. Since and are both the zero matrix, , but since is false.