Matrix Problem Questions

Question

The following list describes the flight routes between the cities:

H is connected to T, HX, and MN.

T is connected H, SJ, HX, MN, and ML.

ML is connected to T, SJ, HX, and MN.

SJ is connected to T, and ML.

MN is connected to MN, T, H, and HX.

HX is connected to MN, ML, T, and H.

Answer the following questions:

a) Construct the adjacency matrix of the list - be sure to state which rows and columns correspond to which city in the picture.

b) Compute A² and use it to compute the number of routes with exactly one stopover from T to HX.

c) Compute the number of routes with two or less stopovers from MN to H.

Answer 1

I'm going to assume you mean MN is connected to ML, not to itself.

With this understanding, there are no one way routes. That is, if location A is connected to location B, then B is connected to A. This insures that the adjacency matrix will be symmetric, which is nice because we don't have to be as careful keeping track of which city is the departure and which city is the arrival.

To construct the adjacency matrix of a simple graph like this (here simple means there are no "loops" from one airport to itself, and no multiple distinct flights between the same cities), first decide which column/row corresponds to which airport. For simplicity I'll use the order you chose: H corresponds to the first row/column, T corresponds to the second, etc. Put a "1" in your matrix wherever there is a flight between the row airport and the column airport, and a "0" otherwise. Doing so, you should check that you get this matrix:

⌈ ⌉

0 1 0 0 1 1

1 0 1 1 1 1

0 1 0 1 1 1 = A

0 1 1 0 0 0

1 1 1 0 0 1

1 1 1 0 1 0

⌊ ⌋

Now computing A² is just writing another copy of A next to itself and doing the matrix multiplication. In this case, since there are only 1's and 0's, it's a lot easier than most matrix multiplication (basically just adding). You should definitely do this step yourself to check your understanding of matrix multiplication. Once you do that you get:

⌈ ⌉

3 2 3 1 2 2

2 5 3 1 3 3

3 3 4 1 2 2 = A^2

1 1 1 2 2 2

2 3 2 2 4 3

2 3 2 2 3 4

⌊ ⌋

Let me repeat here that this is good practice, so really compute this to make sure you have the hang of matrix multiplication.

What does A² have to do with having exactly one stopover? It's actually closely related to the matrix multiplication you used to compute A². For example, take a look at the "3" in the (1,3) position in the matrix (top row, third from the left). The row means "departs from H" and the column means "arrives at ML". When you did the matrix multiplication, you were going across the top row in the left copy of A, and you were going down the third column in the right copy of A. You would add 1 to your result whenever there was a 1 in both places. Essentially you were looking at all the destinations out of H, and all the locations flying into ML, and adding one when they matched. This is the same as counting ways to get from H to ML with exactly one layover! The same reasoning is true to find the number of routes with one stopover from T to HX.

In fact, this reasoning generalizes. It's already obvious that A counts the number of ways to get from one airport to another with no stopovers (i.e. directly). You can apply the reasoning successively to show that A³ gives the number of ways to get from one place to another using exactly two stopovers (note that this will count some nonsensical ways, such as flying from H to T to H to T). Similarly A⁴ catalogues the number of ways to get from one place to another using exactly 3 stopovers, etc.

So if you wanted to count the number of ways to get from MN to H using two or less stopovers, you could do it by first looking up the number of direct flights (in A), then the number of routes with one stopover (in A²), and the number of routes with two stopovers (in A³), and then adding all of those numbers together.

Let me know if you'd like anything spelled out further.

Best,

Eli