Powers and numbers of connections | Year 12

01 / LEARN

The idea, step by step

Why a square counts two-step walks

An entry of $A^{2}$ adds products $a_{i k} a_{k j}$ over all possible intermediate vertices $k$ . Each product counts the ways to take a first connection to $k$ and then a second connection to the destination. The sum counts all two-step walks.

More generally, ${(A^{n})}_{i j}$ counts exactly $n$ steps when entries of $A$ count direct connections. A walk may repeat edges or vertices. A simple path usually excludes repeated vertices, so a matrix power should not be described as counting simple paths.

Exact length, alternatives and returns

For walks of one or two steps, add the relevant entries of $A + A^{2}$ . A zero in $A^{2}$ rules out only two-step walks; a shorter or longer route may exist. Include the identity matrix only if zero-step staying is an allowed alternative.

Diagonal entries count returns to the starting vertex after the specified number of steps. They do not directly count distinct cycles: repeats are allowed, and different walks may use the same edges. Larger powers are suitable for technology, but the interpretation must still identify the endpoints and exact number of moves.

Powers for the illustrated A,B,C network.
Matrix	Row 1	Row 2	Row 3
A	0, 1, 1	0, 0, 1	1, 0, 0
A squared	1, 0, 1	1, 0, 0	0, 1, 1

A common trap

Reading $A^{3}$ as a count of walks with up to three steps.

Instead: A power counts exactly its exponent’s number of steps.

02 / WORKED EXAMPLES

See the thinking

Example 1

A two-leg journey

For rows (0,1,1),(0,0,1),(1,0,0), count two-step walks A to C.

Multiply row A by column C: $0 (1) + 1 (1) + 1 (0) = 1$ .
The walk is A→B→C; the direct A→C edge has only one step.

One two-step walk.

Example 2

A return count

For the undirected path A–B–C, explain the central entry 2 of its squared adjacency matrix.

B→A→B is one two-step return.
B→C→B is another.

Two two-step returns to B, without a one-step loop.

Check your understanding

What does ${(A^{4})}_{B C} = 7$ mean under row-start convention?

Show answer

Seven four-step walks from B to C.

The exponent gives the move count; indices give start and destination.

03 / WORKSHEET

Your turn

6 questions · 18 marks · Work at your own pace.

Worksheet PDF Worked solutions

Read the questions online

For rows $A$ : (0,1,1),(0,0,1),(1,0,0), find $A^{2}$ .
3 marks
For that $A$ , find ${(A^{3})}_{A C}$ and interpret it.
3 marks
In the undirected path A–B–C, count two-step walks from A to C and from A to A.
3 marks
Two vertices have one arrow in each direction and no loops. Find the square of their adjacency matrix.
3 marks
For the illustrated network, count A-to-C walks using one or two steps.
3 marks
Why does a positive entry in $A^{5}$ not guarantee a journey through five different vertices?
3 marks

Read the worked solutions

Equivalent correct methods earn the corresponding marks. Include units where asked.

For rows $A$ : (0,1,1),(0,0,1),(1,0,0), find $A^{2}$ .
3 marks
Row 1 entries: $0 (0) + 1 (0) + 1 (1) = 1$ ; $0 (1) + 1 (0) + 1 (0) = 0$ ; $0 (1) + 1 (1) + 1 (0) = 1$ .
Row 2 entries: $0 (0) + 0 (0) + 1 (1) = 1$ ; $0 (1) + 0 (0) + 1 (0) = 0$ ; $0 (1) + 0 (1) + 1 (0) = 0$ .
Row 3 entries: $1 (0) + 0 (0) + 0 (1) = 0$ ; $1 (1) + 0 (0) + 0 (0) = 1$ ; $1 (1) + 0 (1) + 0 (0) = 1$ .
So $A^{2}$ has rows (1,0,1),(1,0,0),(0,1,1).
[(1, 0, 1); (1, 0, 0); (0, 1, 1)]
For that $A$ , find ${(A^{3})}_{A C}$ and interpret it.
3 marks
Row A of $A^{2}$ is (1,0,1).
Dot it with column C of $A$ , (1,1,0), to obtain 1.
The walk is A→C→A→C.
1: one three-step walk from A to C.
In the undirected path A–B–C, count two-step walks from A to C and from A to A.
3 marks
They are A→B→C and A→B→A.
One of each.
Two vertices have one arrow in each direction and no loops. Find the square of their adjacency matrix.
3 marks
Adjacency rows are (0,1),(1,0).
Two steps return each start to itself.
The $2 \times 2$ identity matrix.
For the illustrated network, count A-to-C walks using one or two steps.
3 marks
The direct count is 1.
The two-step count is 1. Add the alternatives.
2.
Why does a positive entry in $A^{5}$ not guarantee a journey through five different vertices?
3 marks
A walk may revisit a vertex or edge.
The exponent counts edges used, not distinct vertices.

Checking saved progress…

Continue learning

Reachability and dominance/ranking applications

Next lesson

Curriculum reference & lesson scope

SACE Board of South Australia

Stage 2 General Mathematics matrix-models option. This is the offered fifth-topic option, alongside the four compulsory topics; a school-designed Open Topic is an alternative, not prescribed content in this chapter.

Official curriculum source ↗

Back to Matrix models