Counting Walks with Matrix Powers

The nth power counts the walks of length n.

Walks and their length

A walk is a sequence of edges, each one starting where the last one ended. It may use a vertex or an edge more than once. Its length is the number of edges it uses, counting a repeated edge each time.

Take the graph of a triangle ABC with D joined to C. Exactly one walk of length 2 runs from A to D: A to C, then C to D. A has two neighbors, B and C, and of those only C is joined to D.

ABCD

The one walk of length 2 from A to D, in gold: A-C-D.

Squaring the matrix

A walk of length 1 is a single edge, so the adjacency matrix A already counts them: the entry in row X, column Y is the number of walks of length 1 from X to Y.

A walk of length 2 from X to Y passes through a middle vertex K: one edge from X to K, then one from K to Y. Through K there are (row X, column K of A) × (row K, column Y of A) such walks, and adding over every middle vertex gives them all. That sum is exactly row X of A multiplied by column Y of A, the rule for an entry of a matrix product. So the entry in row X, column Y of A² counts the walks of length 2 from X to Y.

For A to D, row A of the matrix is 0, 1, 1, 0 and column D is 0, 0, 1, 0, so the entry is 0 × 0 + 1 × 0 + 1 × 1 + 0 × 0 = 1. The one product that is not 0 belongs to the middle vertex C: the walk A-C-D.

A0110101011010010A0110101011010010×

Row A of the first factor times column D of the second: 0 × 0 + 1 × 0 + 1 × 1 + 0 × 0 = 1, the entry in row A, column D of A².

A²2111121111301101

A² in full. Row A, column D, in gold, holds 1: one walk of length 2 from A to D.

Reading the square

Row C, column C of A² holds 3. A walk of length 2 from C back to C goes out along an edge and straight back along it, and C has three edges, to A, B and D: C-A-C, C-B-C and C-D-C. Every diagonal entry of A² is a degree in the same way, and the diagonal reads 2, 2, 3 and 1.

Row C, column D holds 0. A walk of length 2 from C to D needs a middle vertex joined to both, and the only neighbor of D is C itself. There is no edge from C to C, so there is no such walk.

Off the diagonal, the entry in row X, column Y of A² counts the neighbors that X and Y share. A and B share one neighbor, C, so row A, column B holds 1, for the walk A-C-B.

A²2111121111301101

Row C, column C of A², in gold, holds 3: the walks C-A-C, C-B-C and C-D-C.

Longer walks

Each further multiplication by A adds one more edge to every walk. So the entry in row X, column Y of Aⁿ counts the walks of length n from X to Y. In a directed graph the walks must follow the arrows, and the same products count them.

Find A³ as A² multiplied by A. Row A of A² is 2, 1, 1, 1 and column B of A is 1, 0, 1, 0, so row A, column B of A³ is 2 × 1 + 1 × 0 + 1 × 1 + 1 × 0 = 3. Listing them confirms it: A-B-A-B, A-C-A-B and A-B-C-B.

The products sort the walks by the vertex before the last edge. The 2 × 1 counts the 2 walks of length 2 from A back to A, A-B-A and A-C-A, each followed by the edge from A to B. The 1 × 1 counts the 1 walk from A to C, A-B-C, followed by the edge from C to B.

A³2341324144231130

A³, with row A, column B in gold: 3 walks of length 3 from A to B.

Triangles on the diagonal

The diagonal of A³ counts walks of length 3 that end where they began. With no loops, the three vertices of such a walk are all different, so it goes once round a triangle. Row A, column A of A³ holds 2, for A-B-C-A and A-C-B-A: the one triangle ABC, walked in each direction.

The diagonal of A³ reads 2, 2, 2 and 0, which adds to 6. Each triangle is counted from each of its 3 corners in each of 2 directions, 6 times in all, so the graph has 6 ÷ 6 = 1 triangle.

Walks up to a given length

Adding two matrices adds their counts entry by entry. So A + A² counts the walks of length 1 or 2. In row C, column D it holds 1 + 0 = 1: the edge CD itself, and no walk of length 2. For walks of length up to 3, add A³ as well.

A + A²2221222122311111

A + A², with row C, column D in gold: 1 walk of length 1 or 2 from C to D.

The usual mistakes

Reading A itself for walks of length 2. A counts the edges, the walks of length 1; row A, column D of A is 0, but one walk of length 2 runs from A to D.

Leaving out walks that go back and forth. A-B-A-B is a walk of length 3 from A to B, and the matrix power counts it.

Counting only the walks of length 2 when the question asks for length 2 or less. The edges themselves, counted by A, belong in the total: from C to D the answer is 1, not 0.

Taking the cube for the walks of length 2. Each power adds one edge, so A³ counts walks of length 3.

Flights and co-authors

In the first application below, an aircraft’s day of flights is a walk, so the days of two and three flights are read from A² and A³. In the second, two researchers’ shared co-authors are the walks of length 2 between them, an entry of A² off the diagonal.

Worked example: An Aircraft's Day of Flights Between Four Airports, Counted From the Route Matrix

Question A regional airline flies between four airports, K, L, M and N. There are direct routes between K and L, K and M, K and N, L and M, and M and N, each flown in both directions, and there is no direct route between L and N. An aircraft's day is a sequence of flights along these routes, each flight starting where the last one ended, and it may visit the same airport more than once. (a) An aircraft starts its day at L and must end it at N. How many different days of exactly two flights are possible? (b) Another aircraft starts at L and must end at K after exactly three flights. How many different days are possible?

  1. 1.Write the routes as an adjacency matrix, with rows and columns in the order K, L, M, N: A = 0111101011011010. A day of n flights is a walk of length n, and the entry in row X, column Y of An counts the walks of length n from X to Y.

    KLNMA =0111101011011010Order K, L, M, N. There is no route between L and N.
    KLNMA =0111101011011010Order K, L, M, N. There is no route between Land N.
    Each airport is a vertex and each route an edge: A = 0111101011011010.

  2. 2.Square the matrix: A2 = 3121121221311212. For example, row L of A times column N of A is 1 × 1 + 0 × 0 + 1 × 1 + 0 × 0 = 2.

    KLNMA =0111101011011010Order K, L, M, N. There is no route between L and N.A2=3121121221311212Row L times column N: 1 + 1 = 2
    KLNMA =0111101011011010Order K, L, M, N. There is no route between Land N.A2=3121121221311212Row L times column N: 1 + 1 = 2
    A2 = 3121121221311212. Its entry in row L, column N counts the walks of length 2 from L to N.

  3. 3.(a) The entry in row L, column N of A2 is 2, so there are 2 days of two flights: L to K to N, and L to M to N.

    KLNMA =0111101011011010Order K, L, M, N. There is no route between L and N.A2=3121121221311212Row L times column N: 1 + 1 = 2(a) 2 days: L–K–N and L–M–N
    KLNMA =0111101011011010Order K, L, M, N. There is no route between Land N.A2=3121121221311212Row L times column N: 1 + 1 = 2(a) 2 days: L–K–N and L–M–N
    (a) 2 days of two flights: through K and through M.

  4. 4.For three flights, multiply row L of A2 by column K of A: 1 × 0 + 2 × 1 + 1 × 1 + 2 × 1 = 5. This is the entry in row L, column K of A3 = A2 A.

    KLNMA23121121221311212A01111010110110100 + 2 + 1 + 2 = 5
    KLNMA23121121221311212A01111010110110100 + 2 + 1 + 2 = 5
    Row L of A2 times column K of A gives the entry in row L, column K of A3: 5.

  5. 5.(b) There are 5 days of three flights from L to K. Check by listing them: L–K–L–K, L–K–M–K, L–K–N–K, L–M–L–K and L–M–N–K.

    KLNMA23121121221311212A01111010110110100 + 2 + 1 + 2 = 5(b) 5 days: L–K–L–K, L–K–M–K, L–K–N–K, L–M–L–K and L–M–N–K
    KLNMA23121121221311212A01111010110110100 + 2 + 1 + 2 = 5(b) 5 days: L–K–L–K, L–K–M–K, L–K–N–K,L–M–L–K and L–M–N–K
    (b) 5 days of three flights from L to K.

Answer: (a) 2 days; (b) 5 days

Common mistakes

  • Reading the answer to (a) from A itself. Row L, column N of A is 0 because there is no direct route; the days of two flights are counted by A2.
  • Leaving out days that fly back and forth, such as L–K–L–K. The question allows an airport to be visited more than once, and the matrix power counts every such walk.

More adjacency matrices problems, worked step by step →

Worked example: Co-Authors in a Research Group, and Which Two Researchers the Leader Should Introduce

Question Five researchers in a group, Ada, Ben, Cho, Dev and Eli, record who has written a paper with whom. Ada has written with Ben, Cho and Eli; Ben with Ada, Cho and Dev; Cho with Ada, Ben and Eli; Dev with Ben only; and Eli with Ada and Cho. (a) How many co-authors do Cho and Dev have in common? (b) The group leader will introduce the two researchers who have not yet written together but have the most co-authors in common. Which two are they, and how many co-authors do they share?

  1. 1.Write the co-authorships as an adjacency matrix, with rows and columns in the order Ada, Ben, Cho, Dev, Eli: A = 0110110110110010100010100.

    ABCDEA Ada, B Ben, C Cho, D Dev, E EliA =0110110110110010100010100
    ABCDEA Ada, B Ben, C Cho, D Dev, E EliA =0110110110110010100010100
    Each researcher is a vertex, with an edge between two who have written a paper together.

  2. 2.A co-author shared by X and Y gives a walk of length 2 from X to Y, through that co-author, so the entry in row X, column Y of A2 counts the shared co-authors. Row Cho times column Dev is 1 × 0 + 1 × 1 + 0 × 0 + 0 × 0 + 1 × 0 = 1.

    ABCDEA Ada, B Ben, C Cho, D Dev, E EliA =0110110110110010100010100Row C times column D: 0 + 1 + 0 + 0 + 0 = 1
    ABCDEA Ada, B Ben, C Cho, D Dev, E EliA =0110110110110010100010100Row C times column D: 0 + 1 + 0 + 0 + 0 = 1
    Row Cho times column Dev counts the co-authors they share: 1.

  3. 3.(a) Cho and Dev have 1 co-author in common: Ben.

    ABCDEA Ada, B Ben, C Cho, D Dev, E EliA =0110110110110010100010100Row C times column D: 0 + 1 + 0 + 0 + 0 = 1(a) Cho and Dev share 1 co-author, Ben
    ABCDEA Ada, B Ben, C Cho, D Dev, E EliA =0110110110110010100010100Row C times column D: 0 + 1 + 0 + 0 + 0 = 1(a) Cho and Dev share 1 co-author, Ben
    (a) Cho and Dev share 1 co-author, Ben.

  4. 4.Square the whole matrix: A2 = 3121113102213111011012102. The pairs who have not written together are the 0s of A off the diagonal: Ada and Dev, Ben and Eli, Cho and Dev, and Dev and Eli.

    ABCDEA Ada, B Ben, C Cho, D Dev, E EliA2=3121113102213111011012102Gold: pairs who have not written together
    ABCDEA Ada, B Ben, C Cho, D Dev, E EliA2=3121113102213111011012102Gold: pairs who have not written together
    A2 = 3121113102213111011012102. The shaded entries are the pairs who have not written together.

  5. 5.Read their entries in A2: Ada and Dev 1, Ben and Eli 2, Cho and Dev 1, and Dev and Eli 0.

    ABCDEA Ada, B Ben, C Cho, D Dev, E EliA2=3121113102213111011012102Ada and Dev 1, Ben and Eli 2, Cho and Dev 1, Dev and Eli 0
    ABCDEA Ada, B Ben, C Cho, D Dev, E EliA2=3121113102213111011012102Ada and Dev 1, Ben and Eli 2, Cho and Dev 1, Devand Eli 0
    Among those pairs, Ben and Eli have the largest entry, 2.

  6. 6.(b) The leader introduces Ben and Eli, who share 2 co-authors, Ada and Cho. Ada and Cho also have an entry of 2, but they have already written together, so they are not a candidate.

    ABCDEA Ada, B Ben, C Cho, D Dev, E EliA2=3121113102213111011012102(b) Ben and Eli share 2 co-authors, Ada and ChoAda and Cho also show 2, but have written together
    ABCDEA Ada, B Ben, C Cho, D Dev, E EliA2=3121113102213111011012102(b) Ben and Eli share 2 co-authors, Ada and ChoAda and Cho also show 2, but have writtentogether
    (b) Ben and Eli share 2 co-authors, Ada and Cho.

Answer: (a) 1 co-author, Ben; (b) Ben and Eli, who share 2 co-authors, Ada and Cho

Common mistakes

  • Choosing the largest entry of A2 off the diagonal without checking A. Ada and Cho share 2 co-authors as well, but they have already written a paper together.
  • Reading the diagonal of A2 as shared co-authors. A diagonal entry counts the walks of length 2 from a researcher back to themselves, which is the number of their own co-authors.

More adjacency matrices problems, worked step by step →

Practice Counting Walks with Matrix Powers in the app