For this problem set we define A = {a₁, a₂, , a_n} to be a set of n elements. A relation R over A is a subset ofA A.

Relations can be represented in a variety of ways. One method that is conceptually convenient is to represent a relation as a boolean matrix. As an example, when n= 4 we have the following:

R= {(a₁,a₂ ), (a₁,a₃ ), (a₂,a₁ ), (a₂,a₂ ), (a₃,a₄ ), (a₄,a₁)}

M= 0 1 1 0

1 1 0 0

0 0 0 1

1 0 0 0

Here, the entry in the i^th row and j^th column of the matrix, M_ij, is 1 iff the ordered pair (a_i,a_j ) R , and is 0 otherwise. Note that this defines a bijection between the set of relations on A and the set of nn matrices with 0/1 entries.

Problem 6. A relation R over A is transitive if, for every i,j,k: (a_i, a_j) R and (a_j, a_k) R implies that (a_i, a_k) R. Is the relation in the example above transitive?

Problem 8a. Compute the product matrix M² = M M, where M is the example matrix shown above (again, treating 1 as true and 0 as false). Verify that the following statement is true: M²_ij = 1 if and only if there is a directed path of length exactly 2 from a_i to a_j. Problem 8b. Prove that if R is a relation on a set of size n and M is its corresponding boolean matrix representation, then M^k_ij = 1 if and only if there is a path of length exactly k from a_i to a_j in the directed graph corresponding to R. (Hint: use induction on the length of the path.)

Problem 11. Define the n n identity matrix I : I_jj = 1, 1 j n, I_jk = 0, j k. Show that R* = (I M)ⁿ.