2

I have a question as follows:

The stylised map below shows the bus routes in a holiday area. Lines represent equivalent routes that run each way between the resorts. Arrows indicate one-way scenic routes.

map here: map

To avoid drawing the map I will just say that there are four towns on the map which we can label A through D and the following matrix describes the routes:

         A   B   C   D
From  A  1   1   2   0 
      B  1   0   1   0
M =   C  1   1   0   2
      D  0   0   1   0

So in case of A to A there is a one way scenic route so we put 1 in A to A matrix above. The other towns do not have a route from eg Beesborough to Beesborough so we put a zero in the eg B to B matrix position.

I hope this makes sense.

Now the part of the question I just don't get is where it says calculate M^2 and explain what information it contains.

Well, I can calculate M^2 ok. But I had no idea what practically it represents. In the book answer, it says M^2 represents the number of two stage routes between each pair of resorts. But how do you make the mental leap from M^2 to number of two stage routes? How does this work?

M^2 is:

         A   B   C   D
From  A  4   3   3   4 
      B  2   2   2   2
M =   C  2   1   5   0
      D  1   1   0   2
user619818
  • 149

1 Answers1

4

We have that the $(i, j)$ entry $M_{ij}$ of $M$ represents the number of (one-stage) routes from the $i$th town, call it $X$, to the $j$th town, $Y$; we call these adjacency matrices.

The number of two-stage route between towns $X$ and $Y$ can be described as the number of (two-stage) routes $X \to A \to Y$, plus the number of routes $X \to B \to Y$, plus...

The total number of (two-stage) routes $X \to Z \to Y$ through the $k$th town, $Z$, is just the product of the number $M_{ik}$ of (one-stage) routes $X \to Z$ and the number $M_{kj}$ of (one-stage) routes $Z \to Y$, so summing over all possible middle town $Z$ there are a total of

$\sum_{k=1}^4 M_{ik} M_{kj}$

(two-stage) routes from $X$ to $Y$. But by definition, this sum is exactly the $(i, j)$ entry of $M^2$.

Travis Willse
  • 99,363