3.15 · AHL · HL onlyPaper 1Paper 2Paper 3

Adjacency matrices and walks

In a minute

An stores a graph as a grid of numbers, and its powers count : entry (i,j)(i, j) of AkA^{k} is the number of walks of length kk from ii to jj. You also use and build the behind Google's PageRank.

You'll be able to

  • Write the adjacency matrix of a graph, and read a graph from its .
  • Describe a walk and its length.
  • Count walks of exactly kk, or at most kk, edges with powers of the adjacency matrix, and decide which vertices can be reached.
  • Use a weighted adjacency table of costs, distances or times.
  • Construct the transition matrix for a random walk on a , as in PageRank.
Before you start2 quick questions on what this builds on
Check yourself
A=(3124)A = \begin{pmatrix}3 & 1\\2 & 4\end{pmatrix} and B=(0512)B = \begin{pmatrix}0 & 5\\1 & 2\end{pmatrix}. Find the element in row 22, column 22 of ABAB.
Check yourself
A has edges J → K, J → L, J → M, K → L, L → J and M → L. What is the in-degree of L?

Revise first: 1.14 Matrices, determinants and inverses and 3.14 Graph theory basics

Adjacency matrices

A drawing of a graph is easy to read but hard to calculate with. An adjacency matrix holds the same information as numbers.

Label the rows and columns in the same order, usually alphabetical. A 00 means no direct edge, and two separate edges give a 22.

Undirected graph: each edge works both ways, so aij=ajia_{ij} = a_{ji} and the matrix is symmetric about the leading diagonal. With no loops, each row adds up to the of its vertex.

: an edge from ii to jj adds 11 to row ii, column jj only. Rows add up to out-degrees and columns to in-degrees.

A loop at ii puts 11 on the leading diagonal: going round it is one step from ii back to ii. A has only 00s and 11s, with 00s on the diagonal.

An undirected graph with five vertices F, G, K, L and V. Edges: F to G, F to K, F to L, G to K, K to L, K to V and L to V. F G K L V
Paths in a park between the fountain F, gate G, kiosk K, lake L and viewpoint V.
Worked exampleWrite down the adjacency matrix AA for the park paths in the figure. Use the order F, G, K, L, V.

Try it first, then reveal one step at a time.

  1. F is joined to G, K and L, so row F is 0,1,1,1,00, 1, 1, 1, 0. G is joined to F and K: 1,0,1,0,01, 0, 1, 0, 0.
A directed graph with four vertices P, Q, R and S. Arrows: P to Q and Q to P (two separate edges), Q to R, R to S, S to P, and R to P along the diagonal. P Q R S
Lifts and runs in a ski area. The gondola between P and Q runs both ways; every other link is one way.
Worked exampleEach arrow in the ski area is a lift or a run, used only in its direction. Write down its adjacency matrix MM (order P, Q, R, S). How many lifts and runs arrive at P?

Try it first, then reveal one step at a time.

  1. Rows are “from”, columns are “to”. Row P: 0,1,0,00, 1, 0, 0. Row Q: 1,0,1,01, 0, 1, 0. Row R: 1,0,0,11, 0, 0, 1. Row S: 1,0,0,01, 0, 0, 0.
Check yourself
An undirected graph with no loops has adjacency matrix (0120101121010110)\begin{pmatrix}0 & 1 & 2 & 0\\1 & 0 & 1 & 1\\2 & 1 & 0 & 1\\0 & 1 & 1 & 0\end{pmatrix}. How many edges does it have?
Check yourself
In the adjacency matrix of a directed graph, rows are “from”. What does the sum of row Q give?

Walks and powers of the adjacency matrix

Write a walk as a list of vertices. F–K–L–K has length 33 and visits K twice. In a directed graph a walk follows the arrows. 3.16 adds trails, which never repeat an edge, and paths, which never repeat a vertex.

Count the walks of length 22 from ii to jj. Each is i→m→ji \to m \to j for some middle vertex mm, and there are aimamja_{im}a_{mj} of them through mm.

Adding over every mm gives ai1a1j+⋯+ainanja_{i1}a_{1j} + \dots + a_{in}a_{nj}: row ii of AA times column jj of AA. That is entry (i,j)(i, j) of A2A^{2}.

The leading diagonal of AkA^{k} counts closed walks: entry (i,i)(i, i) counts the walks of length kk from ii back to ii.

Worked exampleWithout a calculator, use the park matrix AA to find the number of walks of length 22 from F to V. List them to check.

Try it first, then reveal one step at a time.

  1. You need entry (F, V) of A2A^{2}: row F of AA times column V of AA.
Worked exampleA skier starts at Q, uses exactly 66 lifts or runs and finishes at P. Use your calculator to find the number of possible walks, and write down one.

Try it first, then reveal one step at a time.

  1. Write down what you need: entry (Q, P) of M6M^{6}. This earns the method mark.
Check yourself
For the ski area, M4=(2110221121111101)M^{4} = \begin{pmatrix}2 & 1 & 1 & 0\\2 & 2 & 1 & 1\\2 & 1 & 1 & 1\\1 & 1 & 0 & 1\end{pmatrix} (order P, Q, R, S). Can a skier go from P to S using exactly 44 lifts or runs?
Check yourself
Use your calculator to find A3A^{3} for the park. How many walks of length 33 start and end at the same place, counting all five places?

Walks of at most k edges, and reaching every vertex

When any number of edges up to a limit is allowed, add the counts for each length.

Learn this
walks of length 1 to k from i to j=entry (i,j) of A+A2+⋯+Ak\text{walks of length } 1 \text{ to } k \text{ from } i \text{ to } j = \text{entry } (i, j) \text{ of } A + A^{2} + \dots + A^{k}

“At most kk” means lengths 11 to kk. “Fewer than kk” stops at k−1k - 1.

A 00 in entry (i,j)(i, j) of AkA^{k} means no walk of exactly kk edges goes from ii to jj. If every entry off the leading diagonal of A+A2+⋯+AkA + A^{2} + \dots + A^{k} is non-zero, every vertex can reach every other in at most kk steps.

Worked exampleFind the number of walks from G to V in the park that use at most 33 paths.

Try it first, then reveal one step at a time.

  1. Add entry (G, V) of AA, A2A^{2} and A3A^{3}: 0+1+30 + 1 + 3.
Worked exampleFor the ski area, use M+M2M + M^{2} and M+M2+M3M + M^{2} + M^{3} to decide whether a skier can get from every point to every other using (a) at most 22, (b) at most 33 lifts or runs.

Try it first, then reveal one step at a time.

  1. (a) M+M2=(1110211121011100)M + M^{2} = \begin{pmatrix}1 & 1 & 1 & 0\\2 & 1 & 1 & 1\\2 & 1 & 0 & 1\\1 & 1 & 0 & 0\end{pmatrix}. Off the diagonal, row S, column R is 00 (and so is row P, column S).
Check yourself
You need the number of walks from X to Y with fewer than 44 edges. Which matrix do you read?
Check yourself
M+M2+M3M + M^{2} + M^{3} has a 00 in row E, column B, and no other zeros off the leading diagonal. Which is correct?

Weighted adjacency tables

Never write 00 for a missing edge: 00 would mean a link that is free or instant. Undirected weights give a symmetric table; for directed weights, rows are “from”.

The table shows only direct edges, so the cheapest way between two vertices may go through others. Raising a table of weights to a power doesn't count walks.

Worked exampleCrossing times, in minutes, between five islands are shown; – means no direct ferry. VWXYZV–2540––W25–1032–X4010–2055Y–3220–15Z––5515–\begin{array}{c|ccccc} & \mathrm{V} & \mathrm{W} & \mathrm{X} & \mathrm{Y} & \mathrm{Z} \\ \hline \mathrm{V} & \text{–} & 25 & 40 & \text{–} & \text{–} \\ \mathrm{W} & 25 & \text{–} & 10 & 32 & \text{–} \\ \mathrm{X} & 40 & 10 & \text{–} & 20 & 55 \\ \mathrm{Y} & \text{–} & 32 & 20 & \text{–} & 15 \\ \mathrm{Z} & \text{–} & \text{–} & 55 & 15 & \text{–} \end{array} (a) Draw the weighted graph. (b) Ignoring waiting times, find the quickest journey time from V to Z.

Try it first, then reveal one step at a time.

  1. (a) One vertex per island, and one edge for each entry above the leading diagonal, labelled with its time (figure below).
A weighted graph with five vertices V, W, X, Y and Z. Edge weights in minutes: V to W 25, V to X 40, W to X 10, W to Y 32, X to Y 20, X to Z 55 and Y to Z 15. 25 40 10 32 20 55 15 V W X Y Z
The ferry table as a weighted graph, in minutes. Not to scale.
Worked exampleCycling times, in minutes, between three hillside villages are shown, rows as the start. from\toFGHF–1830G12–14H229–\begin{array}{c|ccc} \text{from} \backslash \text{to} & \mathrm{F} & \mathrm{G} & \mathrm{H} \\ \hline \mathrm{F} & \text{–} & 18 & 30 \\ \mathrm{G} & 12 & \text{–} & 14 \\ \mathrm{H} & 22 & 9 & \text{–} \end{array} (a) Explain why the table is not symmetric. (b) A cyclist leaves F, visits G and H, and returns to F. Find the shorter total time.

Try it first, then reveal one step at a time.

  1. (a) Uphill is slower than downhill, so times depend on direction: F to H takes 3030 minutes, H to F only 2222.
Check yourself
In a weighted table of bus fares, row B, column D is blank. What does this mean?
Check yourself
An inspector sails every ferry route in the island table once. Find the total crossing time, in minutes.

Transition matrices for a random walk

Picture a visitor who keeps moving along an edge chosen at random. A transition matrix holds the probability of each move.

For an undirected graph, the out-degree is the degree. Each column adds up to 11. Columns are “from”, as in 4.19: the other way round from AA, so TT is AA transposed with each column divided by its total.

The graph must be strongly connected: a vertex with no edge out would give a column of zeros, and a walker could get stuck in one part of the graph.

An undirected graph with four vertices A, B, C and D. Edges: A to B, A to C, B to C and C to D. A B C D
Four museum rooms; each edge is a doorway.
Worked exampleA visitor moves round the museum rooms, each time choosing a doorway of their room at random. Construct the transition matrix TT (order A, B, C, D).

Try it first, then reveal one step at a time.

  1. Degrees: A 22, B 22, C 33, D 11.

Google's PageRank works this way. Pages are vertices and links are directed edges. A surfer clicks a random link on each page, and the pages visited most in the long run rank highest. The full algorithm also adds random jumps; 4.19 finds the long-run proportions.

A directed graph with four vertices H, N, S and W. Arrows: H to N and N to H, H to S and S to H (each pair as two separate edges), N to S, H to W, and W to S. H N S W
Links between four web pages: home H, news N, sport S and weather W.
Worked exampleA surfer clicks one of the links on their page at random. Construct the transition matrix TT for the website (order H, N, S, W).

Try it first, then reveal one step at a time.

  1. Out-degrees: H 33 (to N, S, W), N 22 (to H, S), S 11 (to H), W 11 (to S). Every page can reach every other, so the graph is strongly connected.
Check yourself
Which is true for every column of the transition matrix of a strongly connected graph?
Check yourself
A surfer starts on page H. Find the probability that they are on page S after exactly 22 clicks.

Common mistakes

  • A matrix of the wrong size or with no labels. nn vertices give an n×nn \times n matrix; label the rows and columns.
  • Reading the wrong entry. Row is the start, so walks from E to B are in row E, column B.
  • Using AkA^{k} alone when shorter walks count. “At most kk” needs A+⋯+AkA + \dots + A^{k}; “fewer than kk” stops at Ak−1A^{k-1}.
  • Treating walks as real routes. A walk can pass its end vertex early or repeat edges, so if the journey must stop at the target, the true count may be smaller.

Exam tips

  • “Find the number of walks”: write the entry you need, such as “row Q, column P of M6M^{6}”, before the number. That earns the method mark.
  • “State, with justification” whether every vertex can be reached: quote the zero or non-zero entries and say what they mean, such as “no walk from S to R in 22 steps”.
  • “Hence”: use your own matrix from the earlier part. A wrong matrix used correctly can still earn follow-through marks.

Key takeaways

Learn thisAdjacency matrix: entry (i,j)(i, j) is the number of edges directly from ii to jj. Symmetric for an undirected graph; for a directed graph, rows are “from”.
Learn thisA walk is a sequence of edges, each starting where the last ended; vertices and edges may repeat. Its length is its number of edges.
Learn thisentry (i,j) of Ak=number of walks of length k from i to j\text{entry } (i, j) \text{ of } A^{k} = \text{number of walks of length } k \text{ from } i \text{ to } j
Learn thiswalks of length 1 to k from i to j=entry (i,j) of A+A2+⋯+Ak\text{walks of length } 1 \text{ to } k \text{ from } i \text{ to } j = \text{entry } (i, j) \text{ of } A + A^{2} + \dots + A^{k}
Learn thisThe leading diagonal of AkA^{k} counts closed walks of length kk. No zero off the diagonal of A+⋯+AkA + \dots + A^{k} means every vertex reaches every other in at most kk steps.
Learn thisWeighted adjacency table: entries are weights of direct edges; blank (not 00) means no direct edge.
Learn thisTransition matrix of a strongly connected directed graph, or a connected undirected one: TijT_{ij} is the probability of moving from jj to ii, so columns add to 11. With equally likely edges in a simple graph, Tij=1out-degree of jT_{ij} = \frac{1}{\text{out-degree of } j} when j→ij \to i is an edge, and 00 otherwise.

Practise this

13 past-paper questions on Adjacency matrices and walks in the AI HL bank, each with a mark scheme and a worked explanation.

Practise Adjacency matrices and walks →