Assume the Boolean matrix below is MR and that MR represents the relation R wher
ID: 1887692 • Letter: A
Question
Assume the Boolean matrix below is MR and that MR represents the relation R where R represents the connecting flights that an airline has between 4 cities: a, b, c, and d. so there is a 1 in row x column y iff there is a connecting flight between (from) city x and (to)city y That is, the rows of the matrix represent the cities of the origins of the flight and the columns represent the destination cities.
a b c d
a [ 1 1 0 0 ]
b [ 0 1 1 0 ]
c [ 0 0 1 1 ]
d [ 1 1 0 0 ]
A) Let a stand for the airport in the city of Manchester, let b stand for the airport in Boston, c stand for the Chicago airport, d for the airport in the city of Denver. Is their a flight from Manchester to Chicago
B) Compute and interpret the Boolean products: MR ^2, and MR ^3. (Use Boolean arithmetic)
C) Now call the given matrix A and compute A2 and A3 using regular not Boolean arithmetic. What do these products give you.
Explanation / Answer
a) Rows of matrix represent origin and columns are destinations. So, for the flight from Manchester to Chicago, we must look at element (a,c) and the element (a,c) is 0.
Thus, there is no flight between Manchester and Chicago.
b) using boolean arithmetic
MR^2 : [1 1 0 0] [ 1 1 0 0] [1 1 1 0]
[0 1 1 0] * [0 1 1 0] = [0 1 1 1]
[0 0 1 1] [0 0 1 1] [1 1 1 1]
[1 1 0 0] [1 1 0 0] [1 1 1 0]
Similarly, MR^3:
= [1 1 1 1]
[1 1 1 1]
[1 1 1 1]
[1 1 1 1]
c) using normal arithmetic:
A^2 = [1 2 1 0] A^3 = [1 3 3 1]
[0 1 2 1] [1 2 3 2]
[1 1 1 1] [2 3 2 1]
[1 2 1 0] [1 3 3 1]