Powers and numbers of connections | Year 12

01 / LEARN

Understand the idea.

Why a square counts two-step walks

For a connection-count matrix, ${(A^{2})}_{i j}$ adds $a_{i k} a_{k j}$ over all intermediate vertices $k$ . Each product counts ways to go from $i$ to $k$ , then from $k$ to $j$ ; adding covers the alternatives.

In general, ${(A^{n})}_{i j}$ counts walks of exactly $n$ steps. Walks may repeat vertices or edges. A simple path has stricter conditions, so a matrix power must not automatically be described as counting simple paths.

Exact length, alternatives and returns

To count walks of one or two steps, use $A + A^{2}$ . A zero in $A^{2}$ excludes only two-step walks, not direct connections or longer walks. Include the identity only if a zero-step stay is a permitted alternative.

Diagonal entries of a power count returns after the specified number of moves. A two-step return may use an edge and its reverse without a one-step loop. State the start, destination and exact length when interpreting a computed entry.

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

02 / WORKED EXAMPLES

See the method in action.

EXAMPLE 01

A two-leg journey

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

Worked solution

1
Select the start row and destination column.
$row A = (0, 1, 1), column C = (\begin{array}{cccccccccc} 1 \\ 1 \\ 0 \end{array})$
The intermediate positions follow A, B, C order in both vectors.
2
Calculate the two-step entry.
${(A^{2})}_{A C} = 0 (1) + 1 (1) + 1 (0) = 1$
The three products count walks through intermediate A, B and C respectively.
3
Interpret the surviving contribution.
Only intermediate B contributes: A to B to C is the one two-step walk. The direct A to C arrow has one step and is not counted here.

Answer

One two-step walk.

EXAMPLE 02

A return count

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

Worked solution

1
Write the B row and B column.
$row B = (1, 0, 1), column B = (\begin{array}{cccccccccc} 1 \\ 0 \\ 1 \end{array})$
B is adjacent to A and C in the undirected path.
2
Calculate the return entry.
${(A^{2})}_{B B} = 1 (1) + 0 (0) + 1 (1) = 2$
Returning through A contributes one walk and returning through C contributes another.
3
Identify both returns.
The walks are B to A to B and B to C to B. Both use two edges; neither requires a loop at B.

Answer

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

03 / YOUR TURN

Try it yourself.

Check your understanding

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

Show answer & reasoning

Seven four-step walks from B to C.

Under row=start convention, row B and column C give the endpoints. The exponent 4 gives the exact number of moves, so there are seven four-step walks from B to C.

Keep practising

6 worksheet questions · 18 marks

Open worksheet Worked solutions

Read the questions online

For rows $A$ : $(\begin{array}{cccccccccc} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array})$ , 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$ : $(\begin{array}{cccccccccc} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array})$ , 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 $(\begin{array}{cccccccccc} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{array})$ .
$(\begin{array}{cccccccccc} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{array})$
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 $(\begin{array}{cccccccccc} 0 & 1 \\ 1 & 0 \end{array})$ .
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…

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 ↗

In this lesson

Understand the idea.

Why a square counts two-step walks

Exact length, alternatives and returns

See the method in action.

A two-leg journey

Select the start row and destination column.

Calculate the two-step entry.

Interpret the surviving contribution.

A return count

Write the B row and B column.

Calculate the return entry.

Identify both returns.

Try it yourself.

Check your understanding

Keep practising