6.06 Powers of matrices

The square matrix A_{m\times m} has the same number of rows as columns.

Any square matrix can be multiplied by itself and the result is a square matrix of the same dimensions. So, we can write A_{n\times n}\times A_{n\times n}=B_{n\times n} or, more simply, A^2=B.

A matrix can only be raised to a power when it is square. We often denote the square matrix of order n as A_n.

Examples

Matrices can be used to help us answer questions such as the following: How many different routes are there from A to F that use exactly 3 edges in the network shown? Three routes are shown.

But there are many more, including some that use the same edge more than once. Here are two more.

It can be just as hard to know when to stop looking as it is to find them all. Instead, we are going to use the network's adjacency matrix to answer this for us. Let’s start by writing it out.

If two vertices are connected by an edge, there is a 1 in their corresponding row and column. If they are not connected, there is a 0 instead.

\begin{array}{cc} &\begin{array}{ccc} A&B&C&D&E&F&G \end{array} \\ \begin{array}{c} A \\ B \\ C \\D\\E\\F\\G \end{array} & \left( \begin{array}{ccc} 0&1&0&1&\,1&\,\,1&\,\,\,0\\ 1&0&1&0&\,0&\,\,0&\,\,\,0 \\ 0&1&0&0&\,0&\,\,1&\,\,\,1 \\ 1 &0&0&0&\,1&\,\,1&\,\,\,1 \\ 1&0&0&1&\,0&\,\,1&\,\,\,0 \\ 1&0&1&1&\,1&\,\,0&\,\,\,0 \\ 0&0&1&1&\,0&\,\,0&\,\,\,0 \end{array}\right) \end{array}

The number of routes of length n in a network from one vertex to another is equal to the entry in the start vertex’s row and end vertex’s column of the matrix M^n, where M is the adjacency matrix for the network.

Since we are asking about a route of length 3, we need to cube the matrix above. Using a calculator or an online tool we get the result:

\begin{array}{cc} & \begin{array}{ccc} A&B&C&D&E&F&G \end{array} \\ \begin{array}{c} A \\ B \\ C \\D\\E\\F\\G \end{array} & \left( \begin{array}{ccc} 6&6&3&9&8&10&4 \\ 6&0&5&4&3&2&1 \\ 3&5&0&3&4&8&5 \\ 9&4&3&6&8&10&6 \\ 8&3&4&8&6&8&3 \\ 10&2&8&10&8&6&2 \\ 4&1&5&6&3&2&0 \end{array}\right) \end{array}

We then look for the entry in row A, column F, to find our answer.

So there are 10 routes from A to F of length 3.

We don't know what the routes are, but if we do go looking for them and find 10 of them, we know we can stop looking.

This same idea works for directed networks as well. Consider the network below:

How many routes are there from C to B of length 7? We need to take the 7th power of the adjacency matrix which is shown.

We can then read off the answer by looking in row C, column B, to see that there are 43 different routes of length 7 from C to B in this network.

Examples

Example 2

The matrix A represents all of the single-step paths (routes of length 1) between the towns in the network shown. A = \begin{bmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{bmatrix} Both the rows and columns are in the order: Kingston, Ashland, Greenville and then Dunham.

a

Find A^{4}, the matrix that represents all possible four-step paths between the towns. Use technology to calculate A^4.

Worked Solution

Create a strategy

Use technology to calculate A^4.

Apply the idea

\displaystyle A^4

\displaystyle =

\displaystyle \begin{bmatrix} 15&7&10&7\\ 7&9&2&9\\ 10&2&8&2\\ 7&9&2&9\\ \end{bmatrix}

b

How many four-step paths can be taken from Ashland to Dunham?

Worked Solution

Create a strategy

Find the entry that is in the row for Ashland the the column for Dunham.

Apply the idea

From the original matrix A, the second row represents leaving from Ashland, and the fourth column represents going to Dunham.

The entry at the second row and fourth column of A^4 is 9.

There are 9 four-step paths from Ashland to Dunham.