Consider the following diagram that shows the predator-prey relationship in a willow forest ecosystem.

An arrow goes from one species to another if one is food for the other. So, for example, the arrow from flea beetle to spider means that flea beetles are food for spiders.

The diagram can be rewritten where the vertices represent the species and the edges are the arrows. Such diagram is called a directed graph, or digraph.

An adjacency matrix for a digraph is a matrix where each entry of the matrix tells how many single directed edges there are from the vertex corresponding to the row to the vertex corresponding to the column. An entry is "1" when there is a directed edge from one vertex to another. An entry is "0" when there is no directed edge from one vertex to another.

 Snail Frog Garter snake Spider Sawfly Bronze Grackle Yellow Warbler Flea Beetle Meadow Willow A B C D E F G H I

An adjacency matrix is constructed using the diagram. "1" means there is a directed edge from one vertex to another. In this matrix, I'm going to look at first row-second column. Row represents prey and Column represents predator. From "A" to "B", there is an directed edge which means that a snail is eaten by a frog. I'll denote this matrix as matrix F.

If you can "walk" from one entry to another entry by following the directed edges, then there is a path between two entries. If you walk on 1 edge, then the path has length 1. So, all the paths in the above matrix are length 1. If you walk on 2 edges to get from one entry to another entry, then there is a path between two entries of length 2.

Let's construct a matrix that shows the number of paths of length two using the diagram.

If you start from snail, there is a path of length 2 to garter snake.

If you start from meadow willow, there exists two paths of length 2 to frog. (meadow willow - flea beetle - frog; meadow willow - sawfly - frog)

If you start from meadow willow, there exists no path of length 2 to garter snake, However, there exists two paths of length 3 from meadow willow to garter snake.

With this logic in mind, let's construct an adjacency matrix that each edge represents a path of length 2. Each entry in the matrix denotes the number of paths of length 2 you can make from one entry to another.

Now multiply F x F. What is the result? It should be the same as the matrix above. For matrices, we denote by A^k the matrix obtained by multiplying A with itself k times.

Let's try to think about an adjacency matrix where each edge represents a path of length 3. So for each entry in the matrix, it denotes the number of paths of length 3. What about F^3?

Powers of an adjacency matrix gives us information about paths of certain lengths in the associated vertex-edge graph. This connection between graphs and matrices is very useful for solving a variety of problems. For example, it is difficult to accurately and systematically rank players or teams in a tournament. A vertex-edge graph gives you a good picture of the status of the tournament. The corresponding adjacency matrix can help determine the ranking of the players or teams. Consider the following situation.

The second round of a city tennis tournament involved six girls, each of whom was to play every other girl. However, the tournament was rained out after each girl had played only four matches. The results of the play were the following:

• Anne beat Julia
• Keadra beat Anne and Julia
• Julia beat Emily and Maria
• Maria beat Emily, Catherine, and Anne
• Catherine beat Emily, Keadra, and Anne

Here is the digraph representing the tournament. To read this correctly, an arrow from Anne to Julia means that Anne beat Julia.

First, represent the results of the tournament with a matrix of 0s and 1s. A "1" shows that the player represented by the row beat the player represented by the column.

• If you had to rank one girl in frist place right now, who would you choose? Give an argument based on either the digraph/matrix to support your answer.
• Find two girls where neither one seems to be ranked clearly above the other.

To obtain further information about the performance of the players, sum each row of the adjacency matrix.

• What information does Keadra's row sum give you?
• Explain how you could use row sums to rank one girl over another.
• Based on the row sums, which girls appear tied?

To help resolve some of the unclear rankings, compute the square of the adjacency matrix.

• What do entries in the squared adjacency matrix tell you about the tennis tournament?
• What information does Keadra's row sum in the squared adjacency matrix give you?
• Have any ties or unclear rankings been resolved?