Competency-Based Questions (CBQ) · Question 40 of 80
A regional airline links three cities: Delhi (city 1 ), Jaipur (city 2 ) and Lucknow (city 3 ).
Question 405 marksMedium
A regional airline links three cities: Delhi (city 1), Jaipur (city 2) and Lucknow (city 3). Its direct one-way flights are:
Delhi to Jaipur, and Delhi to Lucknow;
Jaipur to Delhi, and Jaipur to Lucknow;
Lucknow to Delhi.
The airline stores its network as the flight matrixA=[aij], where aij=1 if there is a direct flight from city i to city j, and aij=0 otherwise.
Attempt any four of the following five sub-questions.
(a) Write the flight matrix A and state its order. Why is every diagonal entry of A equal to 0?
(b) Find A′ and A−A′. Show that A−A′ is skew symmetric, and explain what its non-zero entries tell the airline.
(c) Find A2. Explain why the (i,j) entry of A2 counts the ways of flying from city i to city j using exactly two flights, and list the two-flight routes from Delhi back to Delhi.
(d) Find A+A2, and use it to find the number of ways a passenger in Lucknow can reach Jaipur using at most two flights. Name the route or routes.
(e) The airline adds the missing flight from Lucknow to Jaipur, and the new flight matrix is B. Write B, show that B is symmetric, and prove that B2 is symmetric without multiplying out. Then find B2 to confirm.
(a) Row i records the flights from city i and column j the flights to city j:
A=011100110
A is a square matrix of order 3×3. A diagonal entry aii would record a flight from a city to itself, and there are none, so every aii=0.
(b) Interchanging rows and columns,
A′=011101100,A−A′=00000−1010
Skew symmetric: (A−A′)′=A′−(A′)′=A′−A=−(A−A′). This can also be seen directly: the diagonal is zero, and the (2,3) and (3,2) entries are 1 and −1.
The (i,j) entry of A−A′ is aij−aji. It is zero when the route between cities i and j is flown both ways (or not at all), and non-zero when it is flown in one direction only. The entry +1 in position (2,3) says there is a flight from Jaipur to Lucknow but no return flight from Lucknow to Jaipur. Every other pair of cities is linked both ways.
Each term aikakj is 1 exactly when there is a flight from i to kand a flight from k to j, that is, when i→k→j is a two-flight route; otherwise it is 0. So the sum counts the two-flight routes from i to j, one for each possible stopover city k.
The (1,1) entry is 2: the two-flight routes from Delhi back to Delhi are Delhi → Jaipur → Delhi and Delhi → Lucknow → Delhi.
(d)
A+A2=011100110+210011111=221111221
Its (i,j) entry counts the journeys from i to j with one flight plus those with two flights. The (3,2) entry is a32+(A2)32=0+1=1, so there is exactly one way to get from Lucknow to Jaipur in at most two flights: Lucknow → Delhi → Jaipur. There is no direct flight.
(e) Setting b32=1:
B=011101110
bij=bji for every i and j, because now every route is flown both ways, so B′=B and B is symmetric.
which equals its own transpose. In words: from each city there are two two-flight round trips, and between any two different cities there is exactly one two-flight route, through the third city.