After turning a map into a directed graph then into a matrix, i have been asked to square the matrix in class. i ran into this question that asked me to explain what the squared matrix represents. does anyone know?
-
alice and becky live on parkway east, at the intersections of owens bridge and bay bridge, respectively. carl and david live on parkway west, at the intersections of bay bridge and owens bridge, respectively. parkway east is a one-way street running east. parkway west is one way running west. both bridges are two way. calculate what does the new matrix model represent? explain.

I'm assuming that by "turning the graph into a matrix" you're referring to the adjacency matrix associated with a given directed graph, which encodes a connection between two vertices and by the number if there's an edge beginning at and terminating at and 0 otherwise. Here is the entry of the adjacency matrix in the th row and th column.



Let's consider a simple example of a graph on three vertices , where the edge set is . (image below)

The corresponding adjacency matrix is



and squaring this gives the matrix



Let's think about what the entry is saying. We obtained it by computing the vector product,



We can interpret each term as counting the number of two-step paths we can take starting from and ending up back on . We'll require that staying in place is not an option, that a path from one vertex to itself must involve leaving the first vertex.

The first term is then 0, since there is no path from to itself:

The second term is also 0, since we can take a step from over to , but we can't go back:

The third term is 1, because we can take a step from to , and we can then undo that step by going backwards from to :

And so on. We can make the claim that (the th element of ) will give you the number of 2-edge paths from to .

And more generally, will give the number of paths consisting of steps.