Network/adjacency matrices | Year 12

01 / LEARN

Understand the idea.

Choose a convention before entering data

For these adjacency matrices, the row identifies the start and the column identifies the destination. In a simple directed network, entry 1 records one arrow and entry 0 records none. A diagonal entry records a loop back to the same vertex.

An arrow from A to B changes row A, column B only. An undirected edge is recorded in both directions, producing matching entries across the diagonal. A symmetric matrix can still have many missing edges.

Labels determine the model

Use the same vertex order for rows and columns when taking powers. If labels are reordered, reorder both dimensions together; otherwise multiplication can join connections through the wrong intermediate vertex.

Explain what nonzero entries measure. Counts of connections, journey times and probabilities have different meanings. Ordinary powers of connection-count matrices count walks; powers of travel-time entries do not automatically give shortest travel times.

Row=start; column=destination.
From / to	A	B	C
A	0	1	1
B	0	0	1
C	1	0	0

02 / WORKED EXAMPLES

See the method in action.

EXAMPLE 01

Read a directed network

List the arrows in the adjacency table above.

Worked solution

1
Read the A row using row=start.
$a_{A B} = 1, a_{A C} = 1$
The A row has entries 1 under B and C, so it records A to B and A to C.
2
Read the remaining nonzero entries.
$a_{B C} = 1, a_{C A} = 1$
The B row points to C, and the C row points to A.
3
Check for loops and collect the arrows.
$a_{A A} = a_{B B} = a_{C C} = 0$
There are no loops. The complete list is A to B, A to C, B to C and C to A; all other entries are zero.

Answer

A→B, A→C, B→C, C→A.

EXAMPLE 02

An undirected example

Rows in A,B,C order are (0,1,0),(1,0,1),(0,1,0). Describe the network.

Worked solution

1
Check the diagonal entries.
$a_{A A} = a_{B B} = a_{C C} = 0$
No vertex has a loop.
2
Pair each connection with its reverse.
$\begin{aligned} a_{A B} = a_{B A} & = 1 \\ a_{B C} = a_{C B} & = 1 \\ a_{A C} = a_{C A} & = 0 \end{aligned}$
The symmetric pairs describe undirected A–B and B–C edges, with no A–C edge.
3
Describe the complete network.
It is the undirected path A–B–C, without loops; the zero A–C pair rules out a triangle.

Answer

The undirected path A–B–C, without loops.

03 / YOUR TURN

Try it yourself.

Check your understanding

Where is C→B recorded in row-start convention?

Show answer & reasoning

Row C, column B.

C is the starting vertex and B is the destination, so C to B is recorded at row C, column B, namely $a_{C B}$ .

Keep practising

6 worksheet questions · 20 marks

Open worksheet Worked solutions

Read the questions online

Construct the adjacency matrix, ordered A,B,C, for A→B, B→A, B→C and C→C.
3 marks
Rows P,Q,R are $(\begin{array}{cccccccccc} 0 & 2 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array})$ . Entries count direct bus services. Interpret the 2.
3 marks
Rows A,B,C are $(\begin{array}{cccccccccc} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{array})$ . Can this represent an undirected network? List its links.
3 marks
Explain why zero diagonal entries do not rule out cycles.
3 marks
Use the diagram and vertex order A,B,C.
5 marks
1. (a)
  Write its adjacency matrix using row=start.
  3 marks
2. (b)
  How many arrows leave A and arrive at C?
  2 marks
Someone swaps the first two rows of an A,B,C adjacency matrix but not its columns, then calls both orders B,A,C. Explain the error.
3 marks

Read the worked solutions

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

Construct the adjacency matrix, ordered A,B,C, for A→B, B→A, B→C and C→C.
3 marks
Place a 1 for every stated arrow.
C→C belongs on the diagonal.
Rows $(\begin{array}{cccccccccc} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \end{array})$ .
Rows P,Q,R are $(\begin{array}{cccccccccc} 0 & 2 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array})$ . Entries count direct bus services. Interpret the 2.
3 marks
Use row P and column Q.
The weight is a count, not a probability or a duration.
Two direct services from P to Q.
Rows A,B,C are $(\begin{array}{cccccccccc} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{array})$ . Can this represent an undirected network? List its links.
3 marks
The matrix is symmetric; each link appears in both directions.
Yes: A–B and A–C.
Explain why zero diagonal entries do not rule out cycles.
3 marks
A→B→A is a two-step return without either vertex having a loop.
They rule out one-step loops only. Longer walks can return to the start.
Use the diagram and vertex order A,B,C.
5 marks
a) Read all arrows leaving each vertex.
b) Sum row A and column C respectively.
1. (a)
  Write its adjacency matrix using row=start.
  3 marks
  Read all arrows leaving each vertex.
  Rows $(\begin{array}{cccccccccc} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array})$ .
2. (b)
  How many arrows leave A and arrive at C?
  2 marks
  Sum row A and column C respectively.
  Two leave A; two arrive at C.
a) Rows $(\begin{array}{cccccccccc} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array})$ .; b) Two leave A; two arrive at C.
Someone swaps the first two rows of an A,B,C adjacency matrix but not its columns, then calls both orders B,A,C. Explain the error.
3 marks
The old column A is wrongly being treated as column B.
Its row and column labels no longer agree. Both must be reordered consistently.

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.

Choose a convention before entering data

Labels determine the model

See the method in action.

Read a directed network

Read the A row using row=start.

Read the remaining nonzero entries.

Check for loops and collect the arrows.

An undirected example

Check the diagonal entries.

Pair each connection with its reverse.

Describe the complete network.

Try it yourself.

Check your understanding

Keep practising