Assume the Boolean matrix below is MR and that MR represents the relation R wher
ID: 2964303 • 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.
The 1 in row a column b means there is a flight from city a (Manchester) to city b (Boston). The 1 in row x column x means that there are planes in airport x. In general, 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 flights and the columns represent the destination cities.
(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 Denver to Chicago? Explain.
(b) Compute and interpret the Boolean products: MR^2, and MR^3. (Remember to use Boolean arithmetic). What do these Boolean products give you? That is, explain what the Boolean entries in the matrices MR^2 and MR^3 mean.
(c) Now call the given matrix A and compute A^2 and A^3 , using regular, not Boolean arithmetic. What do these products give you?
(d) What does MR + M^2R + M^3R + M^4R give you? (Note, this is Theorem 3 page 602 where the text
Explanation / Answer
a) Yes, as it one in row d and coloumn C , means there is a connecting flight from d to c.
b)
MR^2 = 1 1 1 1
1 1 1 1
1 1 1 1
1 0 1 1
For all having 1 means there is a flight connecting station row to station coloumn with one stop.
MR3 = 1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
This gives airport which can be reached after 2 stops.
d)
MR + MR2 + MR3 + MR4 gives that is it possible to go from airport row to airport coloum. i.e, if a value in this matrix is zero, means it is not possible to go from row station to coloumn station through any path.