Consider the following graph illustrated in the picture.
There are three locations in this graph, labelled 1,2, and 3. The directed lines represent a way of going from one location to another. Thus there is one way to go from location 1 to location 1. There is one way to go from location 1 to location 3. It is not possible to go from location 2 to location 3 although it is possible to go from location 3 to location 2. Lets refer to moving along one of these directed lines as a step. The following 3 × 3 matrix is a numerical way of writing the above graph. This is sometimes called a digraph, short for directed graph.

Thus a_{ij}, the entry in the i^{th} row and j^{th} column represents the number of ways to go from location i to location j in one step.
Problem: Find the number of ways to go from i to j using exactly k steps.
Denote the answer to the above problem by a_{ij}^{k}. We don’t know what it is right now unless k = 1 when it equals a_{ij} described above. However, if we did know what it was, we could find a_{ij}^{k+1} as follows.

This is because if you go from i to j in k + 1 steps, you first go from i to r in k steps and then for each of these ways there are a_{rj} ways to go from there to j. Thus a_{ir}^{k}a_{rj} gives the number of ways to go from i to j in k + 1 steps such that the k^{th} step leaves you at location r. Adding these gives the above sum. Now you recognize this as the ij^{th} entry of the product of two matrices. Thus

and so forth. From the above definition of matrix multiplication, this shows that if A is the matrix associated with the directed graph as above, then a_{ij}^{k} is just the ij^{th} entry of A^{k} where A^{k} is just what you would think it should be, A multiplied by itself k times.
Thus in the above example, to find the number of ways of going from 1 to 3 in two steps you would take that matrix and multiply it by itself and then take the entry in the first row and third column. Thus

and you see there is exactly one way to go from 1 to 3 in two steps. You can easily see this is true from looking at the graph also. Note there are three ways to go from 1 to 1 in 2 steps. Can you find them from the graph? What would you do if you wanted to consider 5 steps?

There are 19 ways to go from 1 to 2 in five steps. Do you think you could list them all by looking at the graph? I don’t think you could do it without wasting a lot of time.
Of course there is nothing sacred about having only three locations. Everything works just as well with any number of locations. In general if you have n locations, you would need to use a n × n matrix.
Example 2.1.13 Consider the following directed graph.
Write the matrix which is associated with this directed graph and find the number of ways to go from 2 to 4 in three steps.
Here you need to use a 4×4 matrix. The one you need is

Then to find the answer, you just need to multiply this matrix by itself three times and look at the entry in the second row and fourth column.

There is exactly one way to go from 2 to 4 in three steps.
How many ways would there be of going from 2 to 4 in five steps?

There are three ways. Note there are 10 ways to go from 3 to 2 in five steps.
This is an interesting application of the concept of the ij^{th} entry of the product matrices.