2.1. MATRICES 45
steps. Can you find them from the graph? What would you do if you wanted to consider 5steps? 1 1 1
1 0 0
1 1 0
5
=
28 19 13
13 9 6
19 13 9
There are 19 ways to go from 1 to 2 in five steps. Do you think you could list them all bylooking 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 worksjust as well with any number of locations. In general if you have n locations, you wouldneed to use a n× n matrix.
Example 2.1.13 Consider the following directed graph.
1 2
3 4
Write the matrix which is associated with this directed graph and find the number of waysto go from 2 to 4 in three steps.
Here you need to use a 4×4 matrix. The one you need is0 1 1 0
1 0 0 0
1 1 0 1
0 1 0 1
Then to find the answer, you just need to multiply this matrix by itself three times and lookat the entry in the second row and fourth column.
0 1 1 0
1 0 0 0
1 1 0 1
0 1 0 1
3
=
1 3 2 1
2 1 0 1
3 3 1 2
1 2 1 1
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?0 1 1 0
1 0 0 0
1 1 0 1
0 1 0 1
5
=
5 9 5 4
5 4 1 3
9 10 4 6
4 6 3 3
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 ijth entry of the product matrices.