Topic 3.15 · Applications and Interpretation HL

The diagonal is not zero

The path 1–2–3 has no loops, so A has zeros down its diagonal. A² does not: its 1,1 entry is 1 and its 2,2 entry is 2. Both are correct, and both count walks that go out and come back.

A, the adjacency matrix
0entry 1,1
0entry 2,2
no loopswhat the diagonal says

A is about edges. Its powers are about walks, and a walk is allowed to leave a vertex and come straight back.

Writing a graph as a matrix

Label the vertices and put a 1 wherever two are joined and a 0 wherever they are not. For the path 1–2–3:

A = (0, 1, 0;   1, 0, 1;   0, 1, 0)

reading row by row, so row 2 says vertex 2 is joined to 1 and to 3. Three things follow:

  1. It is symmetric for an undirected graph, because "1 is joined to 2" and "2 is joined to 1" are the same fact. For a directed graph it is not.
  2. The diagonal is zero when there are no loops, because no vertex is joined to itself.
  3. Each row sums to that vertex's degree: row 1 sums to 1, row 2 to 2, row 3 to 1. Degree sum 4, so 2 edges, which is the handshake lemma again.

The matrix has no drawing in it. Two graphs with the SAME labelling are identical exactly when their matrices match, which is why this is the form every algorithm uses. Relabel the vertices and the matrix changes while the graph does not, so a matrix records a labelled graph rather than a shape.

Powers count walks

The i, j entry of Ak is the number of walks of length exactly k from vertex i to vertex j. A walk may repeat vertices and may repeat edges; it just has to use k edges.

Square it:

A² = (1, 0, 1;   0, 2, 0;   1, 0, 1)

and read the surprising entries:

  1. (A²)1,1 = 1. One walk of length 2 from 1 back to 1: 1 → 2 → 1. There is no loop at vertex 1, and there does not need to be.
  2. (A²)2,2 = 2. Two of them: 2 → 1 → 2 and 2 → 3 → 2. That 2 is the degree of vertex 2, and it always is: one two-step return for each edge you could step out along.
  3. (A²)1,2 = 0. No two-step walk joins 1 to 2, because every walk from 1 to 2 on this graph has odd length.
  4. (A²)1,3 = 1. The walk 1 → 2 → 3, which is the only route there at all.

Cube it and the pattern completes:

A³ = (0, 2, 0;   2, 0, 2;   0, 2, 0) = 2A

so (A³)1,2 = 2, the walks 1 → 2 → 1 → 2 and 1 → 2 → 3 → 2, and (A³)1,1 = 0, because an odd-length walk on this graph can never get home.

Do not "tidy" a non-zero diagonal. It is the commonest thing done to A² and it destroys exactly the information the question wanted. The zero diagonal is a property of A alone and it says "no loops". The diagonal of A² says something else entirely: how many ways there are to leave and return in two steps, which is the degree.

For walks of length k or less, add the powers. The syllabus asks for both. Walks of length at most 3 from vertex 1 to vertex 2 are counted by the 1,2 entry of

A + A² + A³ = (1, 3, 1;   3, 2, 3;   1, 3, 1)

whose 1,2 entry is 1 + 0 + 2 = 3: the single edge, nothing of length 2, and the two of length 3. Add the powers rather than raising A to a higher one, because Ak counts walks of exactly length k and nothing shorter.

Weighted tables and transition matrices

A weighted adjacency table puts the weight in place of the 1, and a dash or a blank where there is no edge. Powers of it give you products of weights summed over walks, which is not route length, so they answer no question anyone asks here. Weighted tables are for reading, not for powering.

A transition matrix is for a random walk. From each vertex, split the probability equally among its edges, and write each vertex's probabilities down a column:

T = (0, 0.5, 0;   1, 0, 1;   0, 0.5, 0)

Column 1 says: from vertex 1 you go to 2 with probability 1, because there is nowhere else. Column 2 says: from vertex 2 you go to 1 or to 3, each with probability 0.5. Every column sums to 1, and that is the check: if a column does not, the matrix is wrong.

On the GDC: matrix powers

Cubing a 3 by 3 matrix by hand is two products of 27 multiplications each, 54 in all, and the first slip is invisible. This is the one graph sub-topic where the machine does the real work, and A to the fifth or sixth power is a routine exam request.

When you may use it. Applications. A calculator is allowed in every paper. Enter A once, store it, and read off whichever power the question wants; the marks are for interpreting the entry, not for the arithmetic.

TI-Nspire CX II

  1. menu → Matrix & Vector → Create → Matrix, which asks for the number of rows and columns: enter 3 and 3, then fill it. ctrl × gives a fixed 2 by 2 template, which is no use here
  2. ctrl var to store it as a
  3. a^2 gives (1,0,1;0,2,0;1,0,1) and a^3 gives (0,2,0;2,0,2;0,2,0)
  4. For a transition matrix, enter the decimals directly; ctrl enter forces a decimal answer rather than a fraction

Casio fx-CG50

  1. MENU → Run-Matrix, F3 MAT/VCT, set Mat A to 3 by 3 and fill it, then EXIT
  2. Mat A ^ 2 then EXE; the caret key is ^ and it works on matrices
  3. Arrow around the answer to read entries beyond the first screenful; a 3 by 3 result does not all fit
  4. SHIFT MENU SET UP and set Input/Output to Linear before a transition matrix, or press S↔D on the answer, so thirds read as 0.333. The SET UP item called Mode is the number base, and setting it to Dec stops you entering a decimal at all

The mark people lose. Reading the wrong entry. The question asks for walks from 1 to 3 and the student gives the 3,1 entry, or counts rows from the bottom. On a symmetric matrix the first mistake is invisible because the two entries agree; on a directed graph it is wrong and looks fine. Write the vertex labels along the top and down the side of the matrix on your page, every time, before entering anything. It costs six characters and removes the entire error class.

Your turn

All four questions are about the path 1–2–3, with A = (0, 1, 0; 1, 0, 1; 0, 1, 0).

1. Find the 1,1 entry of A².

2. Find the 2,2 entry of A².

3. How many walks of length 3 run from vertex 1 to vertex 2?

4. How many walks of length 2 run from vertex 1 to vertex 2?

5. A has a zero diagonal and A² does not. Why?

Question 5. A has a zero diagonal and A squared does not. Why?
Where the marks go

1 markA written down correctly, with the vertices in the order the question gives.

1 markThe right power.

1 markThe right entry, named as a count of walks.

The third mark wants the sentence, not the number. "There are 2 walks of length 3 from vertex 1 to vertex 2" earns it; "2" on its own often does not, because the examiner cannot tell which entry you read.

Want a verdict on your own draft?

These pages are free and stay free, but they are general and your IA is not. Send me your research question, or whatever exists so far, and I will tell you in writing whether the topic has a ceiling on it, where the marks are going, and what to change first. That costs nothing and it comes back within 24 hours.

Written by a serving IB Diploma and Career-related Programme Coordinator and Head of Mathematics, who reads internal assessments across every subject group every year. If you then want the whole draft reviewed properly against all five criteria, that is the paid one, and it is refunded if it does not name at least three specific things to fix.

Send me your question, free

Already have a full draft? Have the whole thing reviewed against all five criteria, $99.