6.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.

Representing a Relation with a Matrix

Definition 6.4.1: Adjacency Matrix

Let 𝐴 ={𝑎1,𝑎2,…,𝑎𝑚} and 𝐵 ={𝑏1,𝑏2,…,𝑏𝑛} be finite sets of cardinality 𝑚 and 𝑛, respectively. Let 𝑟 be a relation from 𝐴 into 𝐵. Then 𝑟 can be represented by the 𝑚 ×𝑛 matrix 𝑅 defined by

𝑅𝑖⁢𝑗={1 if 𝑎𝑖⁢𝑟⁢𝑏𝑗0 otherwise

𝑅 is called the adjacency matrix (or the relation matrix) of 𝑟.

Example 6.4.1: A Simple Example

Let 𝐴 ={2,5,6} and let 𝑟 be the relation {(2,2),(2,5),(5,6),(6,6)} on 𝐴. Since 𝑟 is a relation from 𝐴 into the same set 𝐴 (the 𝐵 of the definition), we have 𝑎1 =2, 𝑎2 =5, and 𝑎3 =6, while 𝑏1 =2, 𝑏2 =5, and 𝑏3 =6. Next, since

• 2⁢𝑟⁢2, we have 𝑅11 =1
• 2⁢𝑟⁢5, we have 𝑅12 =1
• 5⁢𝑟⁢6, we have 𝑅23 =1
• 6⁢𝑟⁢6, we have 𝑅33 =1

All other entries of 𝑅 are zero, so

𝑅=⎛⎜ ⎜ ⎜ ⎜⎝110001001⎞⎟ ⎟ ⎟ ⎟⎠

Composition as Matrix Multiplication

From the definition of 𝑟 and of composition, we note that

𝑟2={(2,2),(2,5),(2,6),(5,6),(6,6)}

The adjacency matrix of 𝑟2 is

𝑅2=⎛⎜ ⎜ ⎜ ⎜⎝111001001⎞⎟ ⎟ ⎟ ⎟⎠.

We do not write 𝑅2 only for notational purposes. In fact, 𝑅2 can be obtained from the matrix product 𝑅⁢𝑅; however, we must use a slightly different form of arithmetic.

Definition 6.4.2: Boolean Arithmetic

Boolean arithmetic is the arithmetic defined on {0,1} using Boolean addition and Boolean multiplication, defined by

Table 6.4.1

0 +0 =0	0 +1 =1 +0 =1	1 +1 =1
0 ⋅0 =0	0 ⋅1 =1 ⋅0 =0	1 ⋅1 =1

Notice that from Chapter 3, this is the “arithmetic of logic,” where + replaces “or” and ⋅ replaces “and.”

Example 6.4.2: Composition by Multiplication

Suppose that 𝑅 =⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝0100101001010010⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠ and 𝑆 =⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝0111001100010000⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠. Then using Boolean arithmetic, 𝑅⁢𝑆 =⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝0011011100110001⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠ and 𝑆⁢𝑅 =⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝1111011100100000⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠.

Theorem 6.4.1: Composition is Matrix Multiplication

Let 𝐴1, 𝐴2, and 𝐴3 be finite sets where 𝑟1 is a relation from 𝐴1 into 𝐴2 and 𝑟2 is a relation from 𝐴2 into 𝐴3. If 𝑅1 and 𝑅2 are the adjacency matrices of 𝑟1 and 𝑟2, respectively, then the product 𝑅1⁢𝑅2 using Boolean arithmetic is the adjacency matrix of the composition 𝑟1⁢𝑟2.

Remark: A convenient help in constructing the adjacency 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 adjacency matrix, and the elements of 𝐵 in a row above the first row. Initially, 𝑅 in Example 6.4.1 would be

256256⎛⎜ ⎜ ⎜ ⎜⎝⎞⎟ ⎟ ⎟ ⎟⎠

To fill in the matrix, 𝑅𝑖⁢𝑗 is 1 if and only if (𝑎𝑖,𝑏𝑗) ∈𝑟. So that, since the pair (2,5) ∈𝑟, the entry of 𝑅 corresponding to the row labeled 2 and the column labeled 5 in the matrix is a 1.

Example 6.4.3: 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 𝑅 (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 𝑐.

OS1OS2OS3OS4P1P2P3P4⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝1010110000010011⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠⁢C1C2C3OS1OS2OS3OS4⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝110010001011⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠

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⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝111110011011⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠

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.

Exercises

Exercise 6.4.1

Let 𝐴1 ={1,2,3,4}, 𝐴2 ={4,5,6}, and 𝐴3 ={6,7,8}. Let 𝑟1 be the relation from 𝐴1 into 𝐴2 defined by 𝑟1 ={(𝑥,𝑦) ∣𝑦 −𝑥 =2}, and let 𝑟2 be the relation from 𝐴2 into 𝐴3 defined by 𝑟2 ={(𝑥,𝑦) ∣𝑦 −𝑥 =1}.

1. Determine the adjacency matrices of 𝑟1 and 𝑟2.
2. Use the definition of composition to find 𝑟1⁢𝑟2.
3. Verify the result in part b by finding the product of the adjacency matrices of 𝑟1 and 𝑟2.

Answer

1. 4561234⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝000100010001⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠ and 678456⎛⎜ ⎜ ⎜ ⎜⎝000100010⎞⎟ ⎟ ⎟ ⎟⎠
2. 𝑟1⁢𝑟2 ={(3,6),(4,7)}
3. 6781234⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝000000100010⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠

Exercise 6.4.2

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

Exercise 6.4.3

Suppose that the matrices in Example 6.4.2 are relations on {1,2,3,4}. What relations do 𝑅 and 𝑆 describe?

Answer

Table 6.4.2

R : 𝑥⁢𝑟⁢𝑦 if and only if |𝑥 −𝑦| =1

S : 𝑥⁢𝑠⁢𝑦 if and only if 𝑥 is less than 𝑦.

Exercise 6.4.4

Let 𝐷 be the set of weekdays, Monday through Friday, let 𝑊 be a set of employees {1,2,3} 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

𝑆=123𝑀𝑇𝑊𝑅𝐹⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝101011101010110⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠ and 𝑅=𝐴𝐵𝐶𝐽𝐿𝑃123⎛⎜ ⎜ ⎜ ⎜⎝011001110101010011⎞⎟ ⎟ ⎟ ⎟⎠

1. compute 𝑆⁢𝑅 using Boolean arithmetic and give an interpretation of the relation it defines, and
2. compute 𝑆⁢𝑅 using regular arithmetic and give an interpretation of what the result describes.

Exercise 6.4.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 23 fitting the description.

Exercise 6.4.6

Let 𝐴 ={𝑎,𝑏,𝑐,𝑑}. Let 𝑟 be the relation on 𝐴 with adjacency matrix 𝑎𝑏𝑐𝑑𝑎𝑏𝑐𝑑⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝1000010011100101⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠

1. Explain why 𝑟 is a partial ordering on 𝐴.
2. Draw its Hasse diagram.

Exercise 6.4.7

Define relations 𝑝 and 𝑞 on {1,2,3,4} by 𝑝 ={(𝑎,𝑏) ∣|𝑎 −𝑏| =1} and 𝑞 ={(𝑎,𝑏) ∣𝑎 −𝑏 is even}.

1. Represent 𝑝 and 𝑞 as both graphs and matrices.
2. Determine 𝑝⁢𝑞, 𝑝2, and 𝑞2; and represent them clearly in any way.

Answer

1. 12341234⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝0100101001010010⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠ and 12341234⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝1010010110100101⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠
2. 𝑃⁢𝑄 =12341234⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝0100101001010010⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠ 𝑃2 = 12341234⎛⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜⎝0100101001010010⎞⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟⎠ =𝑄2

Exercise 6.4.8

1. Prove that if 𝑟 is a transitive relation on a set 𝐴, then 𝑟2 ⊆𝑟.
2. Find an example of a transitive relation for which 𝑟2 ≠𝑟.

Exercise 6.4.9

We define ≤ on the set of all 𝑛 ×𝑛 relation matrices by the rule that if 𝑅 and 𝑆 are any two 𝑛 ×𝑛 relation matrices, 𝑅 ≤𝑆 if and only if 𝑅𝑖⁢𝑗 ≤𝑆𝑖⁢𝑗 for all 1 ≤𝑖,𝑗 ≤𝑛.

1. Prove that ≤ is a partial ordering on all 𝑛 ×𝑛 relation matrices.
2. Prove that 𝑅 ≤𝑆 ⇒𝑅2 ≤𝑆2 , but the converse is not true.
3. If 𝑅 and 𝑆 are matrices of equivalence relations and 𝑅 ≤𝑆, how are the equivalence classes defined by 𝑅 related to the equivalence classes defined by 𝑆?

Answer

1. Reflexive: 𝑅𝑖⁢𝑗 =𝑅𝑖⁢𝑗 for all 𝑖, 𝑗, therefore 𝑅𝑖⁢𝑗 ≤𝑅𝑖⁢𝑗
   Antisymmetric: Assume 𝑅𝑖⁢𝑗 ≤𝑆𝑖⁢𝑗 and 𝑆𝑖⁢𝑗 ≤𝑅𝑖⁢𝑗 for all 1 ≤𝑖, 𝑗 ≤𝑛. Therefore, 𝑅𝑖⁢𝑗 =𝑆𝑖⁢𝑗 for all 1 ≤𝑖, 𝑗 ≤𝑛 and so 𝑅 =𝑆
   Transitive: Assume 𝑅, 𝑆, and 𝑇 are matrices where 𝑅𝑖⁢𝑗 ≤𝑆𝑖⁢𝑗 and 𝑆𝑖⁢𝑗 ≤𝑇𝑖⁢𝑗, for all 1 ≤𝑖, 𝑗 ≤𝑛. Then 𝑅𝑖⁢𝑗 ≤𝑇𝑖⁢𝑗 for all 1 ≤𝑖, 𝑗 ≤𝑛, and so 𝑅 ≤𝑇.
2. (𝑅2)𝑖⁢𝑗=𝑅𝑖⁢1⁢𝑅1⁢𝑗+𝑅𝑖⁢2⁢𝑅2⁢𝑗+⋯+𝑅𝑖⁢𝑛⁢𝑅𝑛⁢𝑗≤𝑆𝑖⁢1⁢𝑆1⁢𝑗+𝑆𝑖⁢2⁢𝑆2⁢𝑗+⋯+𝑆𝑖⁢𝑛⁢𝑆𝑛⁢𝑗=(𝑆2)𝑖⁢𝑗⇒𝑅2≤𝑆2(6.4.1)
   To verify that the converse is not true we need only one example. For 𝑛 =2, let 𝑅12 =1 and all other entries equal 0, and let 𝑆 be the zero matrix. Since 𝑅2 and 𝑆2 are both the zero matrix, 𝑅2 ≤𝑆2, but since 𝑅12 >𝑆12, 𝑅 ≤𝑆 is false.
3. The matrices are defined on the same set 𝐴 ={𝑎1, 𝑎2,⋯,𝑎𝑛}. Let 𝑐⁡(𝑎𝑖), 𝑖 =1, 2,⋯,𝑛 be the equivalence classes defined by 𝑅 and let 𝑑(𝑎𝑖) be those defined by 𝑆. Claim: 𝑐⁡(𝑎𝑖) ⊆𝑑⁡(𝑎𝑖).
   𝑎𝑗∈𝑐⁡(𝑎𝑖)⇒𝑎𝑖⁢𝑟⁢𝑎𝑗⇒𝑅𝑖⁢𝑗=1⇒𝑆𝑖⁢𝑗=1⇒𝑎𝑖⁢𝑠⁢𝑎𝑗⇒𝑎𝑗∈𝑑⁡(𝑎𝑖)(6.4.2)