Skip to main content

Discrete Mathematics for Computer Science: An open educational resource.

Ken Levasseur, Al Doerr, Michiel Smid, Oscar Levin, Charles M. Grinstead, J. Laurie Snell, Eric Lehman, F. Thomson Leighton, Albert R Meyer, Jeff Erickson, Kenneth P. Bogart, Carol Chritchlow, David Eck, OpenDSA Project, L.J. Miller

Section 10.4 Matrices of Relations

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.

Subsection 10.4.1 Representing a Relation with a Matrix

Definition 10.4.1. Adjacency Matrix.

Let \(A = \{a_1,a_2,\ldots , a_m\}\) and \(B= \{b_1,b_2,\ldots , b_n\}\) be finite sets of cardinality \(m\) and \(n\text{,}\) respectively. Let \(R\) be a relation from \(A\) into \(B\text{.}\) Then \(R\) can be represented by the \(m\times n\) matrix \(M\) defined by
\begin{equation*} M_{ij}= \left\{ \begin{array}{cc} 1 & \textrm{ if } a_i R b_j \\ 0 & \textrm{ otherwise} \\ \end{array}\right. \end{equation*}
\(M\) is called the adjacency matrix (or the relation matrix) of \(R\) .

Example 10.4.2. A simple example.

Let \(A = \{2, 5, 6\}\) and let \(R\) be the relation \(\{(2, 2), (2, 5), (5, 6), (6, 6)\}\) on \(A\text{.}\) Since \(R\) is a relation from \(A\) into the same set \(A\) (the \(B\) of the definition), we have \(a_1= 2\text{,}\) \(a_2=5\text{,}\) and \(a_3=6\text{,}\) while \(b_1= 2\text{,}\) \(b_2=5\text{,}\) and \(b_3=6\text{.}\) Next, since
  • \(2 R 2\text{,}\) we have \(M_{11}= 1\)
  • \(2 R 5\text{,}\) we have \(M_{12}= 1\)
  • \(5 R 6\text{,}\) we have \(M_{23}= 1\)
  • \(6 R 6\text{,}\) we have \(M_{33}= 1\)
All other entries of \(M\) are zero, so
\begin{equation*} M =\left( \begin{array}{ccc} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \\ \end{array} \right) \end{equation*}

Subsection 10.4.2 Composition as Matrix Multiplication

From the definition of \(R\) and of composition, we note that
\begin{equation*} R^2 = \{(2, 2), (2, 5), (2, 6), (5, 6), (6, 6)\} \end{equation*}
The adjacency matrix of \(R^2\) is
\begin{equation*} M^2 =\left( \begin{array}{ccc} 1 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \\ \end{array} \right)\text{.} \end{equation*}
We do not write \(M^2\) only for notational purposes. In fact, \(M^2\) can be obtained from the matrix product \(M M\text{;}\) however, we must use a slightly different form of arithmetic.

Definition 10.4.3. Boolean Arithmetic.

Boolean arithmetic is the arithmetic defined on \(\{0,1\}\) using Boolean addition and Boolean multiplication, defined by
Table 10.4.4.
\(0 + 0 = 0\) \(0+1 = 1 + 0=1\) \(1 + 1 = 1\)
\(0\cdot 0=0\) \(0 \cdot 1 = 1 \cdot 0 = 0\) \(1 \cdot 1 = 1\)
Notice that from Chapter 4, this is the “arithmetic of logic,” where \(+\) replaces “or” and \(\cdot\) replaces “and.”

Example 10.4.5. Composition by Multiplication.

Suppose that \(M=\left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array} \right)\) and \(N=\left( \begin{array}{cccc} 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{array} \right)\text{.}\) Then using Boolean arithmetic, \(M N =\left( \begin{array}{cccc} 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ \end{array} \right)\) and \(N M=\left( \begin{array}{cccc} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{array} \right)\text{.}\)
Remark: A convenient help in constructing the adjacency matrix of a relation from a set \(A\) into a set \(B\) is to write the elements from \(A\) in a column preceding the first column of the adjacency matrix, and the elements of \(B\) in a row above the first row. Initially, \(M\) in Example 2 would be
\begin{equation*} \begin{array}{cc} & \begin{array}{ccc} 2 & 5 & 6 \\ \end{array} \\ \begin{array}{c} 2 \\ 5 \\ 6 \\ \end{array} & \left( \begin{array}{ccc} & & \\ & & \\ & & \\ \end{array} \right) \\ \end{array} \end{equation*}
To fill in the matrix, \(M_{ij}\) is 1 if and only if \(\left(a_i,b_j\right) \in R\text{.}\) So that, since the pair \((2, 5) \in R\text{,}\) the entry of \(M\) corresponding to the row labeled 2 and the column labeled 5 in the matrix is a 1.

Example 10.4.7. Relations and Information.

This final example gives an insight into how relational data base programs can systematically answer questions pertaining to large masses of information. Matrices \(M\) (on the left) and \(N\) (on the right) define the relations \(R\) and \(S\) where \(a R b\) if software \(a\) can be run with operating system \(b\text{,}\) and \(b S c\) if operating system \(b\) can run on computer \(c\text{.}\)
\begin{equation*} \begin{array}{cc} \begin{array}{cc} & \begin{array}{cccc} \text{OS1} & \text{OS2} & \text{OS3} & \text{OS4} \end{array} \\ \begin{array}{c} \text{P1} \\ \text{P2} \\ \text{P3} \\ \text{P4} \end{array} & \left( \begin{array}{cccc} 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{array} \right) \end{array} \begin{array}{cc} & \begin{array}{ccc} \text{C1} & \text{C2} & \text{C3} \end{array} \\ \begin{array}{c} \text{OS1} \\ \text{OS2} \\ \text{OS3} \\ \text{OS4} \\ \end{array} & \left( \begin{array}{ccc} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \end{array} \right) \end{array} \end{array} \end{equation*}
Although the relation between the software and computers is not implicit from the data given, we can easily compute this information. The matrix of \(RS\) is \(MN\text{,}\) which is
\begin{equation*} \begin{array}{cc} & \begin{array}{ccc} \text{C1} & \text{C2} & \text{C3} \end{array} \\ \begin{array}{c} \text{P1} \\ \text{P2} \\ \text{P3} \\ \text{P4} \end{array} & \left( \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{array} \right) \end{array} \end{equation*}
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 program P4, which will not run on the computer C1.

Exercises 10.4.3 Exercises

1.

Let \(A_1 = \{1,2, 3, 4\}\text{,}\) \(A_2 = \{4, 5, 6\}\text{,}\) and \(A_3 = \{6, 7, 8\}\text{.}\) Let \(R_1\) be the relation from \(A_1\) into \(A_2\) defined by \(R_1 = \{(x, y) \mid y - x = 2\}\text{,}\) and let \(R_2\) be the relation from \(A_2\) into \(A_3\) defined by \(R_2 = \{(x, y) \mid y - x = 1\}\text{.}\)
  1. Determine the adjacency matrices of \(R_1\) and \(R_2\text{.}\)
  2. Use the definition of composition to find \(R_1R_2\text{.}\)
  3. Verify the result in part b by finding the product of the adjacency matrices of \(R_1\) and \(R_2\text{.}\)
Answer.
  1. \(\begin{array}{cc} & \begin{array}{ccc} 4 & 5 & 6 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{ccc} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) \\ \end{array}\) and \(\begin{array}{cc} & \begin{array}{ccc} 6 & 7 & 8 \\ \end{array} \\ \begin{array}{c} 4 \\ 5 \\ 6 \\ \end{array} & \left( \begin{array}{ccc} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{array} \right) \\ \end{array}\)
  2. \(\displaystyle R_1R_2 =\{(3,6),(4,7)\}\)
  3. \(\displaystyle \begin{array}{cc} & \begin{array}{ccc} 6 & 7 & 8 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{array} \right) \\ \end{array}\)

2.

  1. Determine the adjacency matrix of each relation given via the digraphs in Exercise 3 of Section 10.3.
  2. Using the matrices found in part (a) above, find \(R^2\) of each relation in Exercise 3 of Section 10.3.
  3. Find the digraph of \(R^2\) directly from the given digraph and compare your results with those of part (b).

3.

Suppose that the matrices in Example 10.4.5 are relations on \(\{1, 2, 3, 4\}\text{.}\) What relations do \(M\) and \(N\) describe?
Answer.
Table 10.4.8.
M : \(x R y\) if and only if \(\lvert x -y \rvert = 1\)
N : \(x S y\) if and only if \(x\) is less than \(y\text{.}\)

4.

Let \(D\) be the set of weekdays, Monday through Friday, let \(W\) be a set of employees \(\{1, 2, 3\}\) of a tutoring center, and let \(V\) be a set of computer languages for which tutoring is offered, \(\{A(PL), B(asic), C(++), J(ava), L(isp), P(ython)\}\text{.}\) We define \(S\) (schedule) from \(D\) into \(W\) by \(d S w\) if \(w\) is scheduled to work on day \(d\text{.}\) We also define \(R\) from \(W\) into \(V\) by \(w R l\) if \(w\) can tutor students in language \(l\text{.}\) If \(S\) and \(R\) are defined by matrices
\begin{equation*} M = \begin{array}{cc} & \begin{array}{ccc} 1 & 2 & 3 \\ \end{array} \\ \begin{array}{c} M \\ T \\ W \\ R \\ F \\ \end{array} & \left( \begin{array}{ccc} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \\ \end{array} \right) \\ \end{array} \textrm{ and }N= \begin{array}{cc} & \begin{array}{cccccc} A & B & C & J & L & P \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ \end{array} & \left( \begin{array}{cccccc} 0 & 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ \end{array} \right) \\ \end{array} \end{equation*}
  1. compute \(MN\) using Boolean arithmetic and give an interpretation of the relation it defines, and
  2. compute \(MN\) using regular arithmetic and give an interpretation of what the result describes.

5.

How many different reflexive, symmetric relations are there on a set with three elements?
Hint.
Consider the possible matrices.
Answer.
The diagonal entries of the matrix for such a relation must be 1. When the three entries above the diagonal are determined, the entries below are also determined. Therefore, there are \(2^3\) fitting the description.

6.

Let \(A = \{a, b, c, d\}\text{.}\) Let \(R\) be the relation on \(A\) with adjacency matrix \(\begin{array}{cc} & \begin{array}{cccc} a & b & c & d \\ \end{array} \\ \begin{array}{c} a \\ b \\ c \\ d \\ \end{array} & \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} \right) \\ \end{array}\)
  1. Explain why \(R\) is a partial ordering on \(A\text{.}\)
  2. Draw its Hasse diagram.

7.

Define relations \(R\) and \(S\) on \(\{1, 2, 3, 4\}\) by \(R = \{(a, b) \mid \lvert a-b\rvert=1\}\) and \(S=\{(a,b) \mid a-b \textrm{ is even}\}\text{.}\)
  1. Represent \(R\) and \(S\) as both graphs and matrices.
  2. Determine \(RS\text{,}\) \(R^2\text{,}\) and \(S^2\text{;}\) and represent them clearly in any way.
Answer.
  1. \(R = \begin{array}{cc} & \begin{array}{cccc} 1 & 2 & 3 & 4 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array} \right) \\ \end{array}\) and \(S = \begin{array}{cc} & \begin{array}{cccc} 1 & 2 & 3 & 4 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{cccc} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} \right) \\ \end{array}\)
  2. \(R S= \begin{array}{cc} & \begin{array}{cccc} 1 & 2 & 3 & 4 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{cccc} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ \end{array} \right) \\ \end{array}\) \(R^2 =\text{ } \begin{array}{cc} & \begin{array}{cccc} 1 & 2 & 3 & 4 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{cccc} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} \right) \\ \end{array} =S^2 = S\)

8.

  1. Prove that if \(R\) is a transitive relation on a set \(A\text{,}\) then \(R^2 \subseteq R\text{.}\)
  2. Find an example of a transitive relation for which \(R^2\neq R\text{.}\)

9.

We define \(\leq\) on the set of all \(n\times n\) relation matrices by the rule that if \(M\) and \(N\) are any two \(n\times n\) relation matrices, \(M \leq N\) if and only if \(M_{ij} \leq N_{ij}\) for all \(1 \leq i, j \leq n\text{.}\)
  1. Prove that \(\leq\) is a partial ordering on all \(n\times n\) relation matrices.
  2. Prove that \(M \leq N \Rightarrow M^2\leq N^2\) , but the converse is not true.
  3. If \(M\) and \(N\) are matrices of equivalence relations and \(M \leq N\text{,}\) how are the equivalence classes defined by \(M\) related to the equivalence classes defined by \(N\text{?}\)
Answer.
  1. Reflexive: \(M_{ij}=M_{ij}\) for all \(i,j\text{,}\) therefore \(M_{ij}\leq M_{ij}\)
    Antisymmetric: Assume \(M_{ij}\leq N_{ij}\) and \(N_{ij}\leq M_{ij}\) for all \(1\leq i,j\leq n\text{.}\) Therefore, \(M_{ij} = N_{ij}\) for all \(1\leq i,j\leq n\) and so \(M=N\)
    Transitive: Assume \(M, N,\) and \(T\) are matrices where \(M_{ij}\leq N_{ij}\) and \(N_{ij}\leq T_{ij}\text{,}\) for all \(1\leq i,j\leq n\text{.}\) Then \(M_{ij}\leq T_{ij}\) for all \(1\leq i,j\leq n\text{,}\) and so \(M\leq T\text{.}\)
  2. \begin{equation*} \begin{split} \left(M^2\right)_{ij}&=M_{i1}M_{1j}+M_{i2}M_{2j}+\cdots +M_{in}M_{nj}\\ &\leq N_{i1}N_{1j}+N_{i2}N_{2j}+\cdots +N_{in}N_{nj}\\ &=\left(N^2\right)_{ij} \Rightarrow M^2\leq N^2 \end{split}\text{.} \end{equation*}
    To verify that the converse is not true we need only one example. For \(n=2\text{,}\) let \(M_{12}=1\) and all other entries equal \(0\text{,}\) and let \(N\) be the zero matrix. Since \(M^2\) and \(N^2\) are both the zero matrix, \(M^2\leq N^2\text{,}\) but since \(M_{12}>N_{12}, M\leq N\) is false.
  3. The matrices are defined on the same set \(A=\left\{a_1,a_2,\ldots ,a_n\right\}\text{.}\) Let \(c\left(a_i\right), i=1,2,\ldots ,n\) be the equivalence classes defined by \(M\) and let \(d\left(a_i\right)\) be those defined by \(N\text{.}\) Claim: \(c\left(a_i\right)\subseteq d\left(a_i\right)\text{.}\)
    \begin{equation*} \begin{split} a_j\in c\left(a_i\right)&\Rightarrow a_i R a_j\\ &\Rightarrow M_{ij}=1 \Rightarrow N_{ij}=1\\ &\Rightarrow a_i S a_j\\ & \Rightarrow a_j \in d\left(a_i\right)\\ \end{split} \end{equation*}
PrevTopNext