3.15 Adjacency matrices

Write adjacency matrices for undirected and directed graphs, count walks of a given length with matrix powers, read weighted adjacency tables, and build the transition matrix of a random walk, as in Google's PageRank.

IB Mathematics: Applications and Interpretation
Part of 3 Geometry and trigonometry
HL only

Key terms introduced here

Each is in the Maths AI glossary, with every other term in the subject.

Adjacency matrix: The square matrix of a graph with $n$ vertices in which the entry in row $i$ , column $j$ is the number of edges from vertex $i$ to vertex $j$ .

Carry on with 3.15 in Augment

With a free account, Augment remembers where you stopped and what you have practiced.

Start free Open 3.15 in Augment

3.15 Adjacency matrices · IB Maths AI | Augment Education

3.15 Adjacency matrices

IB Mathematics: Applications and Interpretation
Part of 3 Geometry and trigonometry
HL only

Key terms introduced here

Each is in the Maths AI glossary, with every other term in the subject.

Adjacency matrix: The square matrix of a graph with $n$ vertices in which the entry in row $i$ , column $j$ is the number of edges from vertex $i$ to vertex $j$ .

Carry on with 3.15 in Augment

With a free account, Augment remembers where you stopped and what you have practiced.

Start free Open 3.15 in Augment

Notes on 3.15 Adjacency matrices

45 min readLast reviewed 15 Oct 2026

Learning objectives

Write down the adjacency matrix of an undirected or directed graph, including loops and multiple edges, and draw a graph from its adjacency matrix.
Identify walks in a graph and state the length of a walk.
Find the number of walks of length $k$ between two vertices using the $k$ th power of the adjacency matrix.
Find the number of walks of length at most $k$ (or less than $k$ ) by adding powers of the adjacency matrix.
Find the number of closed walks of a given length from the diagonal of a power of the adjacency matrix.
Interpret entries of matrix powers in context, including zero entries.
Draw a weighted graph from a weighted adjacency table and use the table to answer questions about costs, distances or times.
Construct the transition matrix of a random walk on a strongly connected undirected or directed graph, and interpret its long-run behaviour, as in the PageRank algorithm.

Introduction

A drawing of a graph is easy for a person to read, but a calculator or computer needs the same information in numerical form. To work with a network numerically, the graph is stored as a grid of numbers: one row and one column for each vertex, with each entry counting the edges between a pair of vertices. This grid is a matrix, so the matrix algebra of subtopic 1.14, Matrices, applies to it. Multiplying the matrix by itself counts routes through the network, and dividing its entries by the numbers of edges at each vertex turns it into a table of probabilities for a traveller moving at random.

These ideas are used every day. An airline's table of direct flights, squared, gives the number of one-stop connections between cities. A search engine models a person clicking links at random and ranks web pages by how often that person arrives at each one; this is the PageRank algorithm developed by Larry Page and Sergey Brin at Stanford University in 1996.

Adjacency matrices

The adjacency matrix of an undirected graph

To store a graph with $n$ vertices, list the vertices in a fixed order and make an $n \times n$ square matrix. Row $i$ and column $i$ both belong to the $i$ th vertex. The entry in row $i$

The figure of graph G and its adjacency matrix shows five vertices, A to E, with six edges. Row A has 1s in columns B, C and D, because A is joined to exactly those three vertices, and 0s in columns A and E.

Graph G with vertices A, B, C, D, E and edges AB, AC, AD, BC, CD, DE, beside its 5 by 5 adjacency matrix with rows and columns labelled A to E: rows 0 1 1 1 0; 1 0 1 0 0; 1 1 0 1 0; 1 0 1 0 1; 0 0 0 1 0. — Each 1 records an edge. The matrix is symmetric about its leading diagonal, and each row adds up to the degree of its vertex.

With rows and columns in the order A, B, C, D, E, the matrix is

M = \begin{pmatrix} 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{pmatrix}

Three properties follow from the way the matrix is built.

The leading diagonal is all zeros when the graph has no loops, because no vertex is joined to itself.
Each row sum is the degree of that vertex (for a graph without loops): row A adds to 3, and A has degree 3. The column sums give the same numbers.
The matrix is symmetric. An edge joining A and B also joins B and A, so the entry in row A, column B equals the entry in row B, column A.

Symmetry gives a quick check on a matrix written down in a hurry: any entry that does not match its mirror image across the diagonal is an error. It also means that for an undirected graph the total of all the entries is twice the number of edges, which is the degree-sum fact of subtopic 3.14 in matrix form.

Loops and multiple edges

Two kinds of edge from subtopic 3.14 need a rule. Multiple edges simply give entries greater than 1: if two separate edges join vertices J and K, the entries in positions (J, K) and (K, J) are both 2. A loop at a vertex adds 1 to the diagonal entry for that vertex.

The loop convention matters for counting walks: a loop is one edge, and using it once moves a walker one step along the graph while staying at the same vertex. A diagonal entry of 1 therefore means "one way to step from this vertex to itself".

The adjacency matrix of a directed graph

In a directed graph an edge from P to Q does not give an edge from Q to P, so the matrix needs a convention about direction. The standard convention is

\text{entry in row } i, \text{ column } j = \text{number of edges from vertex } i \text{ to vertex } j ,

so rows are "from" and columns are "to". A directed graph's adjacency matrix is usually not symmetric. Each row sum is the out-degree of that vertex, and each column sum is its in-degree.

Directed graph with edges P→Q, Q→R, R→P, Q→S, S→Q, S→T, T→P, R→T, beside its adjacency matrix (rows from, columns to, order P to T): rows 0 1 0 0 0; 0 0 1 1 0; 1 0 0 0 1; 0 1 0 0 1; 1 0 0 0 0. — Row R has 1s in columns P and T because the edges leave R towards P and T. The matrix is not symmetric: R → P is an edge but P → R is not.

Walks

Moving through a graph

A walk is a journey through a graph along its edges, with each edge starting at the vertex where the last one finished. Nothing forbids going back along the same edge or visiting a vertex twice: A → B → A → C is a walk in graph G.

Walks are the most general kind of route. Subtopic 3.16 introduces more restricted kinds: a trail repeats no edge, a path repeats no vertex, and closed versions of these are circuits and cycles. Every trail and every path is a walk, but most walks are neither.

The length is the number of steps taken. A walk of length $k$ lists $k + 1$ vertices, because the starting vertex has to be written down before any step is taken.

Listing short walks by hand

In graph G, the walks of length 2 from A to C go through a middle vertex that is adjacent to both A and C. A is adjacent to B, C and D, and C is adjacent to A, B and D, so the possible middle vertices are B and D. There are exactly two walks of length 2 from A to C: A–B–C and A–D–C.

Listing by hand works for very short walks, but the number of walks grows quickly. Graph G has 6 walks of length 4 from A to E and 10 walks of length 5 from A to E, and listing them all is slow and error-prone. Matrix multiplication counts them systematically.

Counting walks with powers of the adjacency matrix

Why the square of the matrix counts walks of length 2

A walk of length 2 from vertex $i$ to vertex $j$ has the form $i \to m \to j$ for some middle vertex $m$ . The number of ways to make the first step is the entry $a_{im}$

\text{walks of length 2 from } i \text{ to } j = a_{i1}a_{1j} + a_{i2}a_{2j} + \dots + a_{in}a_{nj} = \sum_{m=1}^{n} a_{im}\,a_{mj}

The right-hand side is exactly how an entry of a product is formed in matrix multiplication: row $i$ of the first matrix times column $j$ of the second. So the entry in row $i$ , column $j$ of $M^2$ is the number of walks of length 2 from $i$

Row A of graph G's matrix is 0 1 1 1 0; column C is 1 1 0 1 0; middle vertices A to E. Products 0×1, 1×1, 1×0, 1×1, 0×0 add to 0 + 1 + 0 + 1 + 0 = 2 walks: A–B–C and A–D–C. — Each product counts the walks through one middle vertex; adding the products is the row-by-column rule of matrix multiplication.

When there are multiple edges, the products count the different choices of edge at each step. In the Königsberg graph two bridges join the island A to bank B and two join A to bank C, so a walk B → A → C can be made in $2 \times 2 = 4$ ways, by choosing one bridge for each step.

Walks of any length

The same argument extends one step at a time. A walk of length 3 from $i$ to $j$ is a walk of length 2 from $i$ to some vertex $m$ , followed by one edge from $m$ to $j$ . The number of such walks is the sum over $m$

\text{the entry in row } i, \text{ column } j \text{ of } M^k = \text{the number of walks of length } k \text{ from vertex } i \text{ to vertex } j

The result holds for undirected and directed graphs, with loops and multiple edges, provided the adjacency matrix follows the conventions for loops, multiple edges and directions. For a directed graph the walks must follow the arrows, and the rows-from, columns-to convention makes the multiplication count them correctly.

For graph G the first few powers are

M^2 = \begin{pmatrix} 3 & 1 & 2 & 1 & 1 \\ 1 & 2 & 1 & 2 & 0 \\ 2 & 1 & 3 & 1 & 1 \\ 1 & 2 & 1 & 3 & 0 \\ 1 & 0 & 1 & 0 & 1 \end{pmatrix}, \qquad M^4 = \begin{pmatrix} 16 & 9 & 15 & 10 & 6 \\ 9 & 10 & 9 & 12 & 2 \\ 15 & 9 & 16 & 10 & 6 \\ 10 & 12 & 10 & 15 & 2 \\ 6 & 2 & 6 & 2 & 3 \end{pmatrix} .

The entry 2 in row A, column C of $M^2$ matches the two walks A–B–C and A–D–C found by hand. The entry 6 in row A, column E of $M^4$ says that there are six walks of length 4 from A to E.

The GDC method

Powers of a matrix larger than $2 \times 2$ are found with the GDC.

Open the matrix editor and define a matrix of the right order (for graph G, $5 \times 5$ ). On a TI-84 Plus CE the matrix menu is 2nd x⁻¹ (MATRIX), then EDIT; on a Casio fx-CG50 matrices are entered in the Run-Matrix application.
Type the entries row by row, in the vertex order chosen.
On the calculation screen, raise the matrix to the required power, for example [A]^4, and read the entry in the required row and column.

What to write down: the adjacency matrix (with its row and column labels if the order is not the one given), the power calculated (" $M^4$ "), and the entry used, for example "entry (A, E) of $M^4$ is 6". The whole of $M^4$ need not be copied out; the row or entry used is enough.

Closed walks and the diagonal

The diagonal entries of $M^k$ count closed walks: entry ( $i$ , $i$ ) is the number of walks of length $k$ from vertex $i$ back to vertex $i$

\text{total number of closed walks of length } k = \operatorname{tr}(M^k) = \sum_{i=1}^{n} (M^k)_{ii}

Two special cases are worth knowing.

In a simple undirected graph, the diagonal of $M^2$ gives the degrees. A closed walk of length 2 from $i$ goes out along one edge and straight back, and there is one such walk for each edge at $i$ . In graph G the diagonal of $M^2$ is 3, 2, 3, 3, 1, the degrees of A to E. (With multiple edges this fails: going out along one bridge and back along the other also counts.)
In a simple undirected graph, a closed walk of length 3 goes round a triangle. Each triangle gives 6 closed walks (3 starting vertices × 2 directions). Graph G has two triangles, ABC and ACD, and

Walks of length at most k

A question may ask for walks of length at most $k$ (or "no more than $k$ steps"), or less than $k$ . These include walks of every length up to the limit, so the matrices for each length are added.

\begin{aligned} \text{walks of length at most } k &: \quad M + M^2 + M^3 + \dots + M^k \\ \text{walks of length less than } k &: \quad M + M^2 + \dots + M^{k-1} \end{aligned}

On the GDC, type the sum directly, for example [A]+[A]^2+[A]^3+[A]^4, and read the entry. A walk of length 0 (staying put) is not normally counted, so the sum starts at $M$ , not at the identity matrix.

What a zero entry means

An entry of $M^k$ equal to 0 means there is no walk of length exactly $k$ between those two vertices. It does not mean the vertices are disconnected: a walk of a different length may exist. In graph G, entry (A, E) of $M$ is 0 but entry (A, E) of $M^2$ is 1.

The first power $k$ for which entry ( $i$ , $j$ ) becomes non-zero is the smallest number of edges needed to get from $i$ to $j$ . For A and E in graph G it is 2. If an entry of $M + M^2 + \dots + M^{n-1}$

A small change to the matrix tracks spreading processes. If every vertex is given a loop (a 1 on every diagonal entry), then a walker can "wait" at a vertex for a step. Entry ( $i$ , $j$ ) of the $k$ th power of this matrix is then non-zero exactly when $j$ can be reached from $i$ in at most $k$ steps. This models anything that, once it arrives, stays: pollution in a water network, a rumour, or an infection.

Six towns U, V, W, X, Y, Z joined by channels UV, VW, VZ, WX, ZX, XY. A spill starts at U: V is reached on day 1, W and Z on day 2, X on day 3 and Y on day 4. — Pollution starting at U spreads one channel a day. The day each town is reached is the first power of the matrix whose row U has a non-zero entry in that town's column.

Interpreting walk counts in context

The number of walks counts sequences of steps, and the same place or person can appear in many of them. This affects how results are interpreted.

In a friendship network (an undirected simple graph of who is friends with whom), entry ( $i$ , $j$ ) of $M^2$ , for $i \ne j$

Weighted adjacency tables

A weighted graph carries a number on each edge: a distance, a cost or a time. Its table form is laid out like an adjacency matrix, with each entry recording the weight of the edge in place of the number of edges.

A blank in a weighted table means "no edge". It must not be read as 0, which would mean an edge costing nothing. For an undirected graph the table is symmetric; for a directed graph rows are "from" and columns are "to", and the cost from X to Y can differ from the cost from Y to X.

From \ To	W	X	Y	Z
W		120	200
X	110			90
Y	210			150
Z	180		140

Costs in US dollars of direct flights between four cities (hypothetical). Rows are departure cities, columns are destinations; a blank means no direct flight.

Weighted tables are the input to the network algorithms of subtopic 3.16: Prim's algorithm has a version that works directly on the table, and the travelling salesman problem starts from a table of least distances.

Transition matrices for graphs

A random walk on a graph

Suppose a walker moves around a graph one step at a time and, at each vertex, chooses one of the edges leaving it at random, each equally likely. The walker's position after each step is uncertain, but the probabilities of being at each vertex can be calculated. This model is called a random walk on the graph.

If vertex $j$ has out-degree $d_j$ (its degree, for an undirected graph), each edge leaving $j$ is chosen with probability $\frac{1}{d_j}$

The transition matrix

The probabilities are collected in a transition matrix $T$ , using the convention of subtopic 4.19, Transition matrices and Markov chains: columns are "from" and rows are "to", so

T_{ij} = \mathrm{P}(\text{moving from vertex } j \text{ to vertex } i) ,

and each column of $T$ adds up to 1. The probabilities of being at each vertex after $n$ steps form a column vector $\boldsymbol{s}_n$ , with

\boldsymbol{s}_{n+1} = T\boldsymbol{s}_n, \qquad \boldsymbol{s}_n = T^n \boldsymbol{s}_0 .

The construction from the adjacency matrix $M$ depends on the type of graph.

Undirected graph. $M$ is symmetric, so column $j$ of $M$ lists the edges at vertex $j$ . Divide each column of $M$ by the degree of its vertex.
Directed graph. Row $j$

In both cases a quick check is that every column adds to 1.

A walker moves at random on graph G (vertices A to E, edges AB, AC, AD, BC, CD, DE), choosing each edge at the current vertex with equal probability.

(a) Construct the transition matrix $T$ .

(b) The walker starts at E. Find the probability that the walker is at D after 3 steps.

Show the solution

(a) The degrees are A 3, B 2, C 3, D 3, E 1. Divide each column of the adjacency matrix by the degree of the vertex that the column belongs to (the vertex the walker is leaving).

T = \begin{pmatrix} 0 & \frac{1}{2} & \frac{1}{3} & \frac{1}{3} & 0 \\ \frac{1}{3} & 0 & \frac{1}{3} & 0 & 0 \\ \frac{1}{3} & \frac{1}{2} & 0 & \frac{1}{3} & 0 \\ \frac{1}{3} & 0 & \frac{1}{3} & 0 & 1 \\ 0 & 0 & 0 & \frac{1}{3} & 0 \end{pmatrix}

The long run and strongly connected graphs

As the number of steps grows, $\boldsymbol{s}_n$ usually settles down to a fixed vector, the steady state, which gives the long-run proportion of time the walker spends at each vertex. On the GDC it is estimated by calculating $T^n \boldsymbol{s}_0$ for a large $n$

For graph G, starting anywhere, $T^{60}\boldsymbol{s}_0$ gives

\boldsymbol{s} \approx \begin{pmatrix} 0.25 \\ 0.167 \\ 0.25 \\ 0.25 \\ 0.0833 \end{pmatrix} = \begin{pmatrix} \frac{3}{12} \\ \frac{2}{12} \\ \frac{3}{12} \\ \frac{3}{12} \\ \frac{1}{12} \end{pmatrix} .

These are the degrees 3, 2, 3, 3, 1 divided by their sum, 12. This is true for every connected undirected graph whose random walk settles down: in the long run a random walker visits each vertex in proportion to its degree, because a vertex with more edges has more ways in.

The graph needs to be strongly connected (for an undirected graph, connected) for the long run to make sense for the whole network. If some vertex cannot be reached from another, the walker's long-run position depends on where it started. If a vertex has out-degree 0, the walker gets stuck there, and its column of $T$ cannot be filled in at all, since there is nothing to divide by. A strongly connected graph guarantees a single steady state that does not depend on the start. On some strongly connected graphs, such as a single directed cycle, $\boldsymbol{s}_n$ keeps cycling and never settles; subtopic 4.19 explains which chains, the regular ones, always settle.

PageRank

Ranking web pages by a random surfer

A search engine has to decide which of thousands of matching pages to show first. The idea behind PageRank is that a link from one page to another is a vote of confidence, and that votes from important pages should count for more. Page and Brin turned this into a random walk: a "random surfer" starts on some page and keeps clicking links chosen at random. Pages that the surfer visits often in the long run are ranked highly.

The web is modelled as a directed graph: each page is a vertex and each hyperlink is an edge from the page containing the link to the page it points to. The transition matrix is built exactly as for any directed graph, and the PageRank of each page is its entry in the steady state vector.

Four web pages A, B, C, D with links A→B, A→C, B→C, C→A, C→D, D→A. Transition probabilities: A→B ½, A→C ½, B→C 1, C→A ½, C→D ½, D→A 1. — A random surfer on four linked pages. Each page splits its probability equally among its outgoing links, so A sends ½ to B and ½ to C, while B, with one link, sends all of it to C.

The damping factor

The real web is not strongly connected. Some pages have no outgoing links, and some groups of pages link only to each other, so a surfer who only follows links would get stuck. PageRank solves this by letting the surfer sometimes jump to a completely random page.

With $N$ pages, the surfer moves from page $j$ to page $i$ with probability $d \times T_{ij}$ (following a link) plus $\frac{1 - d}{N}$

G = dT + \frac{1-d}{N}J ,

where $J$ is the $N \times N$ matrix of 1s. Every entry of $G$ is positive, so the surfer can get from any page to any other in one step: the modified graph is strongly connected, and a single long-run vector always exists.

Imperial College London, “M4ML - Linear Algebra - 5.7 Introduction to PageRank”: a link matrix built from a four-page web, the random surfer, repeated multiplication towards the long-run vector, and the damping factor.

Case study: the bridges of Königsberg as a matrix

The seven bridges of Königsberg, analysed by Leonhard Euler in 1736, joined four land masses: the island A, the two river banks B and C, and the eastern land D. Two bridges joined A to B, two joined A to C, and one bridge each joined A to D, B to D and C to D (subtopic 3.14 draws the graph). Because of the double bridges, the adjacency matrix has entries of 2.

K = \begin{pmatrix} 0 & 2 & 2 & 1 \\ 2 & 0 & 0 & 1 \\ 2 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix}, \qquad K^2 = \begin{pmatrix} 9 & 1 & 1 & 4 \\ 1 & 5 & 5 & 2 \\ 1 & 5 & 5 & 2 \\ 4 & 2 & 2 & 3 \end{pmatrix}, \qquad K^3 = \begin{pmatrix} 8 & 22 & 22 & 11 \\ 22 & 4 & 4 & 11 \\ 22 & 4 & 4 & 11 \\ 11 & 11 & 11 & 8 \end{pmatrix}

Bridges from Euler's 1736 figure (Wikipedia, "Seven Bridges of Königsberg", 2026); matrix powers calculated.

Two-bridge strolls. Entry (B, C) of $K^2$ is 5. A walker going from bank B to bank C across exactly two bridges can cross to the island and then to C, choosing one of 2 bridges each time ( $2 \times 2 = 4$ ways), or cross to D and then to C ( $1 \times 1 = 1$

Out and back. The diagonal of $K^2$ is 9, 5, 5, 3, not the degrees 5, 3, 3, 3. From the island there are 5 bridges out, and a walker who leaves by one of the two bridges to B can come back by either of them. Adding the squares of the entries in row A counts the out-and-back strolls:

2^2 + 2^2 + 1^2 = 9 .

The rule "diagonal of $M^2$ = degree" holds only for simple graphs.

Three-bridge strolls. Entry (A, A) of $K^3$ is 8: there are 8 ways to leave the island and return to it after crossing exactly three bridges, each going round a triangle such as A–B–D–A (2 choices of bridge to B, 1 each for the other two, in either direction).

A random stroller. A visitor crosses a bridge chosen at random from those at the current land mass, each equally likely. Dividing each column of $K$ by the number of bridges at that land mass (5, 3, 3, 3) gives the transition matrix.

T = \begin{pmatrix} 0 & \frac{2}{3} & \frac{2}{3} & \frac{1}{3} \\ \frac{2}{5} & 0 & 0 & \frac{1}{3} \\ \frac{2}{5} & 0 & 0 & \frac{1}{3} \\ \frac{1}{5} & \frac{1}{3} & \frac{1}{3} & 0 \end{pmatrix}

From the island, the visitor reaches bank B with probability $\frac{2}{5}$ , because 2 of its 5 bridges lead there. Raising $T$ to a high power ( $T^{50}\boldsymbol{s}_0$

\boldsymbol{s} \approx (0.357, 0.214, 0.214, 0.214)^{\mathrm{T}} = \left(\tfrac{5}{14}, \tfrac{3}{14}, \tfrac{3}{14}, \tfrac{3}{14}\right)^{\mathrm{T}} ,

the numbers of bridges at each land mass divided by the 14 bridge-ends. In the long run the stroller arrives on the island on about 36% of crossings, because it has 5 of the 14 bridge-ends.

What the model leaves out. The model assumes each bridge is equally likely to be chosen and ignores distances and the time spent on each land mass. One matrix holds the whole bridge structure of the city, and its row sums are the degrees. Euler's question, whether a walk can cross every bridge exactly once, depends only on those degrees and is answered in subtopic 3.16.

Exam focus

Adjacency matrices appear on HL Papers 1, 2 and 3, usually for 2–6 marks inside a network question. The recurring shapes are: write down the adjacency matrix of a drawn graph or table (often with a loop, multiple edges or directed edges), find the number of walks of a given length between two vertices or back to the start, find the number of walks of at most a given length, determine when something spreading through a network first reaches a vertex, and construct a transition matrix for a random walk, then use a high power for the long run. The formula booklet has no formulas for adjacency matrices or walks.

GDC working to write down: the matrix entered (with row and column labels if the order is not given), the power used (" $M^5$ "), and the entry or entries read. For a trace question the diagonal entries are enough. For a transition matrix, write the matrix and the power used, for example " $T^{50}\boldsymbol{s}_0$ ".

A delivery company uses drones to fly packages between five depots, A, B, C, D and E. The one-way drone routes are A → B, A → C, B → C, B → D, C → A, C → E, D → E, E → A and E → B.

(a) Write down the adjacency matrix $M$ for the routes, with rows and columns in the order A, B, C, D, E. [2]

(b) Find the number of different ways a package can travel from A to D using exactly 4 routes. [2]

(d) Determine the total number of ways a drone can leave a depot and return to the same depot using exactly 5 routes. [2]

A drone flies continually, choosing at random, with equal probability, one of the routes leaving its current depot.

(e) Construct the transition matrix $T$ , in which columns represent the depot the drone leaves. [2]

(f) Find the long-run proportion of flights that end at depot D. [2]

Show the markscheme

(a)

M = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \end{pmatrix}

A frequent loss of marks is an entry read from the wrong power or from a matrix with rows and columns swapped. Before reading any entry, check the matrix against two or three edges of the graph, and write the length of walk next to the power used.

Questions about spreading or reachability are answered best with a short table of the relevant row of each power, showing where each entry changes from zero to non-zero. Examiners have reported that candidates often calculate the powers correctly but cannot say what a zero entry means: it means no walk of exactly that length.

Practice questions

A graph has vertices A, B, C and D, with edges AB, AC, BC and CD and a loop at D. Write down its adjacency matrix. [2]
An undirected graph has adjacency matrix $\begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 2 & 0 \\ 1 & 2 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}$

Answers

$\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix}$

Summary

The adjacency matrix of a graph has entry ( $i$ , $j$ ) equal to the number of edges from vertex $i$ to vertex $j$ ; a loop adds 1 to the diagonal and multiple edges give entries above 1.
An undirected graph has a symmetric adjacency matrix whose row sums are the degrees (when there are no loops). For a directed graph rows are "from" and columns are "to": row sums are out-degrees and column sums are in-degrees.
A walk is a sequence of edges, each starting where the last ended, with repeats allowed; its length is the number of edges.
Entry ( $i$ , $j$

Self-check

To do:
I can write down the adjacency matrix of an undirected graph, including loops and multiple edges.
To do:
I can write down the adjacency matrix of a directed graph with rows as "from" and columns as "to", labelling them.
To do:
I can draw a graph from its adjacency matrix and find degrees, allowing for loops.
To do:
I can explain why the adjacency matrix of an undirected graph is symmetric.
To do:
I can find the length of a walk and tell a closed walk from an open one.
To do:
I can explain why entry ( $i$ , $j$ ) of $M^2$

Questions on 3.15

36 exam-style questions on this subtopic, written in the style of the IB papers. The first has its markscheme open. Counted on 20 October 2026

Question 1 · AI-0043914 marks

A ferry company serves five islands: Arlo (A), Brae (B), Cove (C), Dunn (D) and Eske (E). Ferries run in both directions on each of the following direct routes, and there are no other direct routes.

A–B, A–C, B–C, B–D, B–E, C–E, D–E

The adjacency matrix $\boldsymbol{M}$ of this network has rows and columns in the order A, B, C, D, E.

(a)
Write down $\boldsymbol{M}$ .
2 marks
Markscheme (a)
$\boldsymbol{M} = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \end{pmatrix}$ A2
Note: Award one mark for a symmetric matrix with zeros on the leading diagonal and at most two errors.
[2 marks]
(b)
Explain why $\boldsymbol{M}$ is equal to its transpose (it is symmetric about its leading diagonal).
1 mark
Markscheme (b)
every route runs in both directions, so the number of direct routes from X to Y equals the number from Y to X R1
[1 mark]
(c)
Find $\boldsymbol{M}^2$ .
2 marks
Markscheme (c)
$\boldsymbol{M}^2 = \begin{pmatrix} 2 & 1 & 1 & 1 & 2 \\ 1 & 4 & 2 & 1 & 2 \\ 1 & 2 & 3 & 2 & 1 \\ 1 & 1 & 2 & 2 & 1 \\ 2 & 2 & 1 & 1 & 3 \end{pmatrix}$
(d)
Interpret the element in row 2, column 2 of $\boldsymbol{M}^2$ in context.
1 mark
Markscheme (d)
there are 4 ways to start at Brae, make exactly two ferry journeys and finish back at Brae A1
[1 mark]
(e)
Find the number of ways of travelling from Arlo to Eske using exactly three ferry journeys.
2 marks
Markscheme (e)
row 1, column 5 of $\boldsymbol{M}^3$ (M1)
$3$ A1
[2 marks]
(f)
Find the total number of ways of making exactly four ferry journeys that start and finish at the same island.
2 marks
Markscheme (f)
sum of the leading diagonal of $\boldsymbol{M}^4$ : $11 + 26 + 19 + 11 + 19$
(g)
Find the number of ways of travelling from Arlo to Dunn using at most three ferry journeys.
3 marks
Markscheme (g)
$\boldsymbol{M} + \boldsymbol{M}^2 + \boldsymbol{M}^3$ (M1)
row 1, column 4: $0 + 1 + 3$
(h)
Explain why your answer to part (g) may be more than the number of sensible routes a passenger would take.
1 mark
Markscheme (h)
the count includes walks that revisit an island (e.g. A–B–A–... or B–C–B), which a passenger would not choose R1
[1 mark]

Question 2 · AI-004816 marks

A farm has six water storage tanks, $P$ , $Q$ , $R$ , $S$ , $T$ and $U$

Question 3 · AI-0049317 marks

A museum has six galleries, $A$ , $B$ , $C$ , $D$ , $E$ and $F$

Power	Row U (columns U, V, W, X, Y, Z)	Towns polluted
$N^1$	1, 1, 0, 0, 0, 0	U, V
$N^2$	2, 2, 1, 0, 0, 1	U, V, W, Z
$N^3$	4, 6, 3, 2, 0, 3	U, V, W, X, Z
$N^4$	10, 16, 11, 8, 2, 11	all six

$n$	1	2	3	10	50
A	0.375	0.3125	0.344	0.333	0.333
B	0.125	0.1875	0.156	0.167	0.167
C	0.375	0.3125	0.344	0.333	0.333
D	0.125	0.1875	0.156	0.167	0.167

	$P$	$Q$	$R$	$S$	$T$	$U$
$P$	–	34	51	28	46	60
$Q$	34	–	25	39	57	44
$R$	51	25	–	48	31	37
$S$	28	39	48	–	42	53
$T$	46	57	31	42	–	35
$U$	60	44	37	53	35	–

(a)
Write down the adjacency matrix $M$ for the doorways, with rows and columns in the order $A$ to $F$ .
2 marks
(b)
Find the number of different ways of walking from gallery $B$ to gallery $C$ by passing through exactly three doorways.
2 marks
(c)
A security guard, Ines, wants to walk through every doorway exactly once. Explain why this is possible, and state the galleries in which she must start and finish.
3 marks
(d)
The following table shows the least walking times, in minutes, between the galleries. Find the values of $p$ , $q$ , $r$ and $s$ .
$A$
$B$
(e)
A tour guide starts at the entrance gallery $A$ , visits every gallery and returns to $A$ . Use the nearest neighbour algorithm on the table to find an upper bound for the walking time of the tour.
3 marks
(f)
By deleting vertex $D$ and using Prim's algorithm starting at $A$ , find a lower bound for the walking time of the tour.
4 marks
(g)
Let $W$ be the least walking time of the tour. Write down an inequality for $W$ .
1 mark

	$P$	$Q$	$R$	$S$	$T$	$U$
$P$	–	34	51	28	46	60
$Q$	34	–	25	39	57	44
$R$	51	25	–	48	31	37
$S$	28	39	48	–	42	53
$T$	46	57	31	42	–	35
$U$	60	44	37	53	35	–

	$P$	$Q$	$R$	$S$	$T$	$U$
$P$	–	34	51	28	46	60
$Q$	34	–	25	39	57	44
$R$	51	25	–	48	31	37
$S$	28	39	48	–	42	53
$T$	46	57	31	42	–	35
$U$	60	44	37	53	35	–

Key terms introduced here

Carry on with 3.15 in Augment

Key terms introduced here

Carry on with 3.15 in Augment

Notes on 3.15 Adjacency matrices

Learning objectives

Introduction

Adjacency matrices

The adjacency matrix of an undirected graph

Loops and multiple edges

The adjacency matrix of a directed graph

Walks

Moving through a graph

Listing short walks by hand

Counting walks with powers of the adjacency matrix

Why the square of the matrix counts walks of length 2

Walks of any length

The GDC method

Closed walks and the diagonal

Walks of length at most k

What a zero entry means

Interpreting walk counts in context

Weighted adjacency tables

Transition matrices for graphs

A random walk on a graph

The transition matrix

The long run and strongly connected graphs

PageRank

Ranking web pages by a random surfer

The damping factor

Case study: the bridges of Königsberg as a matrix

Exam focus

Practice questions

Summary

Self-check

Questions on 3.15

Markscheme (a)

Markscheme (b)

Markscheme (c)

Markscheme (d)

Markscheme (e)

Markscheme (f)

Markscheme (g)

Markscheme (h)

	$P$	$Q$	$R$	$S$	$T$	$U$
$P$	–	34	51	28	46	60
$Q$	34	–	25	39	57	44
$R$	51	25	–	48	31	37
$S$	28	39	48	–	42	53
$T$	46	57	31	42	–	35
$U$	60	44	37	53	35	–