Mini-Lesson

Matrices & Graph Theory (AI HL)

4 missions. Guess, learn, then check. Your place is saved.

Mission 1Three receipts, three unknown prices: how does one matrix find them?
Mission 2The city loses 10% a year and gains 5% of the country. Final split?
Mission 3Can you cross all seven bridges of Königsberg exactly once?
Mission 4A postman must walk every street. What's the shortest route?

The specification points and sources are listed under the lesson: see Sources.

Mission 1

Three receipts, three unknown prices: how does one matrix find them?

Make a guess: Three receipts, three unknown prices: how does one matrix find them?

Number and algebra · matrices

Matrices and multiplication

A matrix with $m$ m rows and $n$ n columns has order $m \times n$ m × n. The element $a_{ij}$ a_ij is in row $i$ i, column $j$ j.
Add, subtract or compare same-order matrices element by element. $k A$ kA multiplies every element by $k$ k.
Multiply row by column: row $i$ i of $A$ A times column $j$ j of $B$ B, summed, gives element $ij$ ij of $A B$ AB.
$A B$ AB exists only if columns of $A$ A = rows of $B$ B: $(m \times n) (n \times p)$ (m × n)(n × p) gives $m \times p$ m × p.
$I$ I is the identity matrix ( $A I = I A = A$ AI = IA = A); $0$ 0 is the zero matrix.

Worked example Number and algebra · matrices

Multiplying in both orders

Question

A = (2013)

and

B = (12 4 - 1)

. Find

A B

and

B A

.

1
Row 1 of $A$ A with each column of $B$ B: $2 \times 1 + 1 \times 2 = 4$ 2 × 1 + 1 × 2 = 4 and $2 \times 4 + 1 \times (- 1) = 7$ 2 × 4 + 1 × (−1) = 7
2
Row 2 of $A$ A with each column of $B$ B: $0 \times 1 + 3 \times 2 = 6$ 0 × 1 + 3 × 2 = 6 and $0 \times 4 + 3 \times (- 1) = - 3$ 0 × 4 + 3 × (−1) = −3
3
So $A B = (46 7 - 3)$ AB = ( 4 , 7 ; 6 , −3 )
4
The same method the other way round gives $B A = (24 13 - 1)$ BA = ( 2 , 13 ; 4 , −1 )

Answer

A B = (46 7 - 3)

and

B A = (24 13 - 1)

, so

A B \neq = B A

.

⚠️ Watch out

matrix multiplication is not commutative. Multiplying matching elements (giving

(20 4 - 3)

) is not matrix multiplication.

Quick check

?

P

has order

2 \times 3

and

Q

has order

3 \times 4

. What is the order of

PQ

?

Number and algebra · matrices

Determinant and inverse of a $2 \times 2$ 2 × 2 matrix

For $A = (a c b d)$ A = ( a , b ; c , d ), the determinant is $det A = ∣ A ∣ = a d - b c$ det A = |A| = ad − bc.
If $det A \neq = 0$ det A ≠ 0, the inverse is $A^{- 1} = \frac{1}{a d - b c} (d - c - b a)$ A⁻¹ = 1/(ad − bc)( d , −b ; −c , a ), and $A A^{- 1} = A^{- 1} A = I$ AA⁻¹ = A⁻¹A = I.
Swap $a$ a and $d$ d, change the signs of $b$ b and $c$ c, divide by the determinant.
If $det A = 0$ det A = 0 the matrix is singular: it has no inverse.
For $3 \times 3$ 3 × 3 and larger matrices, find determinants and inverses with your GDC.

Calculate

?

A = (5432)

. Find the element in row 1, column 2 of

A^{- 1}

, as a decimal.

Number and algebra · matrices

Systems of equations as $A x = b$ Ax = b

A system of linear equations can be written as $A x = b$ Ax = b: $A$ A holds the coefficients, $x$ x the unknowns, $b$ b the constants.
If $A$ A is invertible, multiply both sides on the left by $A^{- 1}$ A⁻¹: $x = A^{- 1} b$ x = A⁻¹b.
Order matters: $b A^{- 1}$ bA⁻¹ is not the same (and here is not even defined).
For three or more unknowns, enter $A$ A and $b$ b in your GDC and calculate $A^{- 1} b$ A⁻¹b.

Worked example Number and algebra · matrices

A $2 \times 2$ 2 × 2 system by hand

Question

Use an inverse matrix to solve

3 x + 2 y = 12

and

x + 4 y = 14

.

1
Write in matrix form: $(3124) (x y) = (1214)$ ( 3 , 2 ; 1 , 4 )( x ; y ) = ( 12 ; 14 )
2
Determinant: $3 \times 4 - 2 \times 1 = 10$ 3 × 4 − 2 × 1 = 10
3
Inverse: $A^{- 1} = \frac{1}{10} (4 - 1 - 2 3)$ A⁻¹ = 1/10( 4 , −2 ; −1 , 3 )
4
Multiply: $\frac{1}{10} (4 \times 12 - 2 \times 14 - 1 \times 12 + 3 \times 14) = \frac{1}{10} (2030)$ 1/10( 4 × 12 − 2 × 14 ; −1 × 12 + 3 × 14 ) = 1/10( 20 ; 30 )

Answer

x = 2

,

y = 3

. Check:

3 (2) + 2 (3) = 12

and

2 + 4 (3) = 14

.

⚠️ Watch out

write the coefficients in the same order (

x

then

y

) in every row.

Calculate

?A shop sells pens, notebooks and folders. Three receipts show: 3 pens, 2 notebooks and 1 folder cost £12.40; 1 pen, 4 notebooks and 2 folders cost £18.80; 5 pens, 1 notebook and 3 folders cost £19.90. Write the system as

A x = b

and use your GDC to find the exact price of one notebook.

£

Sort it

?Is each statement about

2 \times 2

matrices always true?

Tap a statement, then tap the group it belongs in. Then press Check.

Mission check

?Three receipts, three unknown prices: how does one matrix find them?

Mission 2

The city loses 10% a year and gains 5% of the country. Final split?

Make a guess: The city loses 10% a year and gains 5% of the country. Final split?

Number and algebra · matrices

Eigenvalues and eigenvectors

A non-zero vector $v$ v is an eigenvector of $M$ M if $M v = λ v$ Mv = λv: $M$ M only scales it. The scale factor $λ$ λ is the eigenvalue.
Eigenvalues solve the characteristic polynomial: $det (M - λ I) = 0$ det (M − λ I) = 0.
For $M = (a c b d)$ M = ( a , b ; c , d ) this is $λ^{2} - (a + d) λ + (a d - b c) = 0$ λ² − (a + d)λ + (ad − bc) = 0.
For each $λ$ λ, solve $(M - λ I) v = 0$ (M − λ I)v = 0 to find an eigenvector (any non-zero multiple also works).

Worked example Number and algebra · matrices

Eigenvalues and eigenvectors of a $2 \times 2$ 2 × 2 matrix

Question

Find the eigenvalues and corresponding eigenvectors of

M = (4213)

.

1
Characteristic polynomial: $λ^{2} - 7 λ + (12 - 2) = λ^{2} - 7 λ + 10 = 0$ λ² − 7λ + (12 − 2) = λ² − 7λ + 10 = 0
2
Factorise: $(λ - 5) (λ - 2) = 0$ (λ − 5)(λ − 2) = 0, so $λ = 5$ λ = 5 or $λ = 2$ λ = 2
3
For $λ = 5$ λ = 5: $(- 1 2 1 - 2) (x y) = 0$ ( −1 , 1 ; 2 , −2 )( x ; y ) = 0 gives $y = x$ y = x, so $v = (11)$ v = ( 1 ; 1 )
4
For $λ = 2$ λ = 2: $(2211) (x y) = 0$ ( 2 , 1 ; 2 , 1 )( x ; y ) = 0 gives $y = - 2 x$ y = −2x, so $v = (1 - 2)$ v = ( 1 ; −2 )

Answer

λ = 5

with

(11)

;

λ = 2

with

(1 - 2)

. Check:

M (1 - 2) = (2 - 4)

.

⚠️ Watch out

the two equations in each step are multiples of each other. That is expected: it is why

det (M - λ I) = 0

.

Calculate

?Find the larger eigenvalue of

(5142)

.

Number and algebra · matrices

Diagonalisation and powers

If $M$ M has distinct real eigenvalues $λ_{1}$ λ₁, $λ_{2}$ λ₂ with eigenvectors $v_{1}$ v₁, $v_{2}$ v₂, then $M = P D P^{- 1}$ M = PDP⁻¹.
$P = (v_{1} v_{2})$ P = ( v₁ , v₂ ) has the eigenvectors as columns; $D = (λ_{1} 0 0 λ_{2})$ D = ( λ₁ , 0 ; 0 , λ₂ ), in the same order.
Powers: $M^{n} = P D^{n} P^{- 1}$ Mⁿ = PDⁿP⁻¹, and $D^{n} = (λ_{1 n} 0 0 λ_{2 n})$ Dⁿ = ( λ₁ⁿ , 0 ; 0 , λ₂ⁿ ). The inner $P^{- 1} P$ P⁻¹P pairs cancel.
This gives a formula for $M^{n}$ Mⁿ for every $n$ n, not just one power.

Worked example Number and algebra · matrices

A formula for $M^{n}$ Mⁿ

Question

For

M = (4213)

, find an expression for

M^{n}

.

1
From the eigenvectors: $P = (11 1 - 2)$ P = ( 1 , 1 ; 1 , −2 ) and $D = (5002)$ D = ( 5 , 0 ; 0 , 2 )
2
Invert $P$ P: $det P = - 3$ det P = −3, so $P^{- 1} = \frac{1}{3} (21 1 - 1)$ P⁻¹ = 1/3( 2 , 1 ; 1 , −1 )
3
Multiply $P D^{n}$ PDⁿ: $(5^{n} 5^{n} 2^{n} - 2 \cdot 2^{n})$ ( 5ⁿ , 2ⁿ ; 5ⁿ , −2 · 2ⁿ )
4
Multiply by $P^{- 1}$ P⁻¹: $M^{n} = \frac{1}{3} (2 \cdot 5^{n} + 2^{n} 2 \cdot 5^{n} - 2 \cdot 2^{n} 5^{n} - 2^{n} 5^{n} + 2 \cdot 2^{n})$ Mⁿ = 1/3( 2 · 5ⁿ + 2ⁿ , 5ⁿ − 2ⁿ ; 2 · 5ⁿ − 2 · 2ⁿ , 5ⁿ + 2 · 2ⁿ )

Answer

M^{n} = \frac{1}{3} (2 \cdot 5^{n} + 2^{n} 2 \cdot 5^{n} - 2^{n + 1} 5^{n} - 2^{n} 5^{n} + 2^{n + 1})

. Check

n = 1

:

\frac{1}{3} (12639) = M

.

⚠️ Watch out

M^{n} \neq = P D^{n} P

. Keep

P^{- 1}

on the right, or the check at

n = 1

fails.

Calculate

?Use the formula for

M^{n}

from the previous example to find the element in row 1, column 1 of

M^{4}

.

Number and algebra · matrices

Transition matrices and steady states

In a transition matrix $T$ T, the element $T_{ij}$ T_ij is the probability of moving from state $j$ j to state $i$ i, so each column adds to 1.
With a column state matrix $s_{0}$ s₀, the state after $n$ n steps is $s_{n} = T^{n} s_{0}$ sₙ = Tⁿs₀.
A steady state $s$ s satisfies $T s = s$ Ts = s with entries adding to 1: the eigenvector for eigenvalue 1.
For a regular chain (some power of $T$ T has all entries positive), $s_{n}$ sₙ tends to this steady state from any starting state.

Worked example Number and algebra · matrices

A commuter's travel choices

Question

Each day a commuter takes the bus or cycles. After a bus day, the next day is a bus day with probability 0.7. After a cycling day, the next day is a bus day with probability 0.4. Today they took the bus. Find the probability they take the bus in 2 days' time, and the long-term probability of a bus day.

1
Columns are "from": $T = (0.7 0.3 0.4 0.6)$ T = ( 0.7 , 0.4 ; 0.3 , 0.6 ) (bus first), $s_{0} = (10)$ s₀ = ( 1 ; 0 )
2
Two steps: $T s_{0} = (0.7 0.3)$ Ts₀ = ( 0.7 ; 0.3 ), then $T^{2} s_{0} = (0.61 0.39)$ T²s₀ = ( 0.61 ; 0.39 )
3
Steady state $(b c)$ ( b ; c ): $T s = s$ Ts = s gives $0.3 b = 0.4 c$ 0.3b = 0.4c, with $b + c = 1$ b + c = 1
4
Solve: $b = \frac{4}{7}$ b = 4/7, $c = \frac{3}{7}$ c = 3/7

Answer

P (bus in 2 days) = 0.61

; long-term

P (bus) = \frac{4}{7} \approx 0.571

.

⚠️ Watch out

a

T

whose rows add to 1 is the transpose of the IB convention and gives wrong answers with

T^{n} s_{0}

.

Calculate

?Each year 20% of the people in town A move to town B, and 10% of the people in town B move to town A. Nobody else arrives or leaves. Today 6,000 people live in A and 4,000 in B. Find the population of town A after 2 years.

Mission check

?The city loses 10% a year and gains 5% of the country. Final split?

Mission 3

Can you cross all seven bridges of Königsberg exactly once?

Make a guess: Can you cross all seven bridges of Königsberg exactly once?

Graph theory · walks and adjacency matrices

Graph vocabulary

A graph is a set of vertices joined by edges. Two vertices joined by an edge are adjacent; two edges sharing a vertex are adjacent edges.
The degree of a vertex is the number of edges meeting it. Each edge adds 2 to the total, so the sum of degrees is $2 \times$ 2 × the number of edges.

Term	Meaning
simple graph	no loops and no multiple edges between the same pair
complete graph $K_{n}$ Kₙ	simple, every pair of the $n$ n vertices adjacent
weighted graph	each edge carries a number (distance, cost, time)
directed graph	edges have directions; each vertex has an in degree and an out degree
connected	a route exists between any two vertices (directed: strongly connected if you can follow the arrows from any vertex to any other)
subgraph / tree	part of a graph / a connected graph with no cycles

Quick check

?How many edges does the complete graph

K_{6}

have?

Graph theory · walks and adjacency matrices

Walks, trails, paths, Euler and Hamilton

Name	Rule	Closed version
walk	any sequence of adjacent edges
trail	no edge repeated	circuit
path	no vertex repeated	cycle

An Eulerian trail uses every edge exactly once; an Eulerian circuit does so and ends where it starts.
In a connected graph: all degrees even means an Eulerian circuit exists; exactly two odd vertices means an Eulerian trail exists, starting at one odd vertex and ending at the other. Otherwise, neither.
A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle also returns to the start. There is no simple degree test for these.

Worked example Graph theory · walks and adjacency matrices

Is there an Eulerian trail?

Question

For the graph shown, with edges

A B

,

A C

,

BC

,

B D

,

C D

,

CE

and

D E

, determine whether an Eulerian circuit or an Eulerian trail exists. If one does, write one down.

1
List the degrees: $A = 2$ A = 2, $B = 3$ B = 3, $C = 4$ C = 4, $D = 3$ D = 3, $E = 2$ E = 2 (sum 14, so 7 edges)
2
Count the odd vertices: $B$ B and $D$ D, exactly two, so no Eulerian circuit but an Eulerian trail exists
3
Start at one odd vertex and end at the other: $B A C B D C E D$ B A C B D C E D
4
Check: 7 edges, each used once

Answer

an Eulerian trail exists, for example

B A CB D CE D

; there is no Eulerian circuit.

⚠️ Watch out

a trail must start and finish at the two odd vertices. Starting at

A

leaves you stuck with an edge unused.

Sort it

?Each graph is connected. Sort it by what it contains.

Tap a statement, then tap the group it belongs in. Then press Check.

Graph theory · walks and adjacency matrices

Adjacency matrices

Adjacency matrix $A$ A: entry $a_{ij}$ a_ij = number of edges from vertex $i$ i to vertex $j$ j.
The $(i, j)$ (i, j)th entry of $A^{k}$ A^k = number of walks of length $k$ k from $i$ i to $j$ j. For lengths up to $k$ k, add the entries of $A, A^{2}, \dots, A^{k}$ A, A², …, A^k.
A weighted adjacency table stores weights instead of 1s.
Transition matrix $T$ T: $T_{ij}$ T_ij = probability of moving from $j$ j to $i$ i, so column $j$ j holds $\frac{1}{d e g ( j )}$ 1/(deg(j)) in each adjacent row and sums to 1.

Worked example Graph theory · walks and adjacency matrices

Counting walks with $A^{3}$ A³

Question

The graph has vertices

P

,

Q

,

R

,

S

and edges

PQ

,

PR

,

QR

,

RS

. Find the number of walks of length 3 from

P

to

R

.

1
Write the adjacency matrix in the order $P, Q, R, S$ P, Q, R, S: $A = 0110101011010010$ A = ( 0 , 1 , 1 , 0 ; 1 , 0 , 1 , 0 ; 1 , 1 , 0 , 1 ; 0 , 0 , 1 , 0 )
2
Use your GDC to find $A^{3} = 2341324144231130$ A³ = ( 2 , 3 , 4 , 1 ; 3 , 2 , 4 , 1 ; 4 , 4 , 2 , 3 ; 1 , 1 , 3 , 0 )
3
Read row $P$ P, column $R$ R: the entry is 4
4
Check by listing: $PQPR$ PQPR, $PRPR$ PRPR, $PRQR$ PRQR, $PRSR$ PRSR

Answer

4 walks of length 3.

⚠️ Watch out

walks may repeat vertices and edges, so

PRPR

counts. The

(P, R)

entry of

A^{2}

is 1, which counts walks of length 2 only.

Calculate

?An airline flies both ways on the routes shown by the adjacency matrix, with airports in the order

V, W, X, Y, Z

. A journey is a walk along routes. Use your GDC to find the number of journeys from

V

to

Z

that use at most 3 flights.

M = 0110010110110110110100110

Calculate

?A random walker on the graph with edges

PQ

,

PR

,

QR

,

RS

moves at each step along one of the edges at its current vertex, each equally likely. It starts at

P

. Using the transition matrix

T

, find the probability that it is at

R

after exactly two steps. Give your answer as a decimal.

Mission check

?Can you cross all seven bridges of Königsberg exactly once?

Mission 4

A postman must walk every street. What's the shortest route?

Make a guess: A postman must walk every street. What's the shortest route?

Graph theory · trees and algorithms

Minimum spanning trees

A tree is a connected graph with no cycles; on $n$ n vertices it has $n - 1$ n − 1 edges.
A spanning tree is a subgraph that is a tree containing every vertex. A minimum spanning tree (MST) has least total weight.

Algorithm	Method
Kruskal	List edges by weight. Add the smallest edge that does not form a cycle. Stop at $n - 1$ n − 1 edges.
Prim	Start at any vertex. Add the shortest edge from a vertex in the tree to one not yet in it.
Prim, table form	Cross out the new vertex's row; search the columns of all tree vertices for the smallest entry.

Worked example Graph theory · trees and algorithms

Kruskal's algorithm

Question

Use Kruskal's algorithm to find a minimum spanning tree for the network shown, and state its weight.

1
Order the edges: $D E 3$ DE 3, $BC 4$ BC 4, $A C 5$ AC 5, $D F 5$ DF 5, $B D 6$ BD 6, $EF 6$ EF 6, $A B 7$ AB 7, $C D 8$ CD 8, $CE 9$ CE 9
2
Add $D E$ DE, $BC$ BC, $A C$ AC and $D F$ DF: no cycles are formed
3
Add $B D$ BD (6): it joins ${A, B, C}$ {A, B, C} to ${D, E, F}$ {D, E, F}
4
Stop: 6 vertices need $6 - 1 = 5$ 6 − 1 = 5 edges. ( $EF$ EF would have closed the cycle $D EF$ DEF.)

Answer

MST edges

D E

,

BC

,

A C

,

D F

,

B D

; total weight

3 + 4 + 5 + 5 + 6 = 23

.

⚠️ Watch out

rejecting an edge that only touches the tree is wrong. Reject it only when both its ends are already connected.

Calculate

?The table gives the costs, in thousands of dollars, of laying cable between five buildings. Use Prim's algorithm, starting at

P

, to find the minimum total cost of connecting all five buildings.

	P	Q	R	S	T
P	–	8	5	9	12
Q	8	–	4	7	6
R	5	4	–	10	11
S	9	7	10	–	3
T	12	6	11	3	–

Graph theory · trees and algorithms

The Chinese postman problem

Goal: the shortest closed route using every edge at least once.
All vertices even: an Eulerian circuit exists; the answer is the total weight.
Two odd vertices: add the shortest path between them; those edges are walked twice.
Four odd vertices: list the 3 pairings, total the shortest paths for each, and repeat the least.
Why it works: repeating a path adds 1 to the degree of each end, so every vertex becomes even and an Eulerian circuit exists.

Worked example Graph theory · trees and algorithms

Four odd vertices

Question

For the network shown (total weight 47), find the length of the shortest route that starts and ends at

A

and travels along every edge at least once.

1
Degrees: $A = 3$ A = 3, $B = 3$ B = 3, $C = 4$ C = 4, $D = 3$ D = 3, $E = 3$ E = 3, so the odd vertices are $A$ A, $B$ B, $D$ D, $E$ E
2
Pairing $A B + D E$ AB + DE: $4 + 9 = 13$ 4 + 9 = 13 ( $D$ D to $E$ E is shortest via $C$ C: $5 + 4$ 5 + 4)
3
Pairing $A D + BE$ AD + BE: $7 + 7 = 14$ 7 + 7 = 14 ( $B$ B to $E$ E via $C$ C: $3 + 4$ 3 + 4)
4
Pairing $A E + B D$ AE + BD: $10 + 8 = 18$ 10 + 8 = 18
5
Repeat the least pairing: $47 + 13 = 60$ 47 + 13 = 60

Answer

60, repeating

A B

,

D C

and

CE

.

⚠️ Watch out

use the shortest path, not the direct edge. The edge

D E

is 10, longer than

D \to C \to E = 9

.

Calculate

?Return to the network from the Kruskal example, whose edges have total weight 53. A road inspector must drive along every road at least once, starting and finishing at

A

. Find the length of the shortest possible route.

Graph theory · trees and algorithms

The travelling salesman problem

Goal: the least-weight Hamiltonian cycle in a weighted complete graph. First make a table of least distances.
Nearest neighbour (upper bound): always go to the nearest unvisited vertex, then return to the start.
Deleted vertex (lower bound): MST of the other vertices, plus the two shortest edges from the deleted one.
$lower \leq optimal \leq upper$ lower ≤ optimal ≤ upper.
Choosing: every edge → Chinese postman; every vertex once and back → travelling salesman; connect all vertices cheaply → MST.

Worked example Graph theory · trees and algorithms

Bounds for a delivery round

Question

The table gives the least travel times, in minutes, between five towns. Find an upper bound using nearest neighbour from

A

, and a lower bound by deleting

A

.
| | A | B | C | D | E |
|---|---|---|---|---|---|
| A | – | 12 | 10 | 19 | 8 |
| B | 12 | – | 3 | 7 | 13 |
| C | 10 | 3 | – | 9 | 11 |
| D | 19 | 7 | 9 | – | 14 |
| E | 8 | 13 | 11 | 14 | – |

1
Nearest neighbour from $A$ A: $A \to E \to C \to B \to D \to A$ A → E → C → B → D → A, with times 8, 11, 3, 7, 19
2
Upper bound: $8 + 11 + 3 + 7 + 19 = 48$ 8 + 11 + 3 + 7 + 19 = 48
3
Delete $A$ A; MST of $B$ B, $C$ C, $D$ D, $E$ E: $BC 3$ BC 3, $B D 7$ BD 7, $CE 11$ CE 11, weight 21
4
Add the two shortest edges from $A$ A: $A E = 8$ AE = 8 and $A C = 10$ AC = 10, giving $21 + 18 = 39$ 21 + 18 = 39

Answer

39 \leq optimal time \leq 48

minutes.

⚠️ Watch out

the nearest neighbour tour must return to

A

. Forgetting

D A = 19

gives 29, which is not a tour.

Sort it

?Which algorithm fits each task? Justify it by asking what must be covered.

Tap a statement, then tap the group it belongs in. Then press Check.

Mission check

?A postman must walk every street. What's the shortest route?

Recap

Big ideas

$(m \times n) (n \times p)$ (m × n)(n × p) gives $m \times p$ m × p, row by column; matrix multiplication is associative and distributive but not commutative.
For a $2 \times 2$ 2 × 2 matrix, $det A = a d - b c$ det A = ad − bc and $A^{- 1} = \frac{1}{a d - b c} (d - c - b a)$ A⁻¹ = 1/(ad − bc)( d , −b ; −c , a ); if $det A = 0$ det A = 0 there is no inverse.
A linear system is $A x = b$ Ax = b, solved by $x = A^{- 1} b$ x = A⁻¹b (by hand for $2 \times 2$ 2 × 2, GDC for larger).
Eigenvalues solve $det (M - λ I) = 0$ det (M − λ I) = 0; an eigenvector satisfies $M v = λ v$ Mv = λv.
With distinct real eigenvalues, $M = P D P^{- 1}$ M = PDP⁻¹ and $M^{n} = P D^{n} P^{- 1}$ Mⁿ = PDⁿP⁻¹.
In a transition matrix the columns are "from" and add to 1; $s_{n} = T^{n} s_{0}$ sₙ = Tⁿs₀, and the steady state solves $T s = s$ Ts = s (eigenvalue 1).
Degree = edges at a vertex; the degree sum is twice the number of edges. $K_{n}$ Kₙ has $\frac{n ( n - 1 )}{2}$ (n(n−1))/2 edges.
Connected graph: all degrees even means an Eulerian circuit; exactly two odd means an Eulerian trail between them; otherwise neither.
The $(i, j)$ (i, j)th entry of $A^{k}$ A^k counts walks of length $k$ k from $i$ i to $j$ j; in a transition matrix, $T_{ij}$ T_ij is the probability of moving from $j$ j to $i$ i.
Kruskal: cheapest edges first, skip any that make a cycle. Prim: grow one tree, adding the cheapest edge to a new vertex. An MST on $n$ n vertices has $n - 1$ n − 1 edges.
Chinese postman: total weight plus the least-weight pairing of odd vertices by shortest paths (up to four odd vertices).
Travelling salesman: nearest neighbour gives an upper bound; deleted vertex (MST of the rest plus the two shortest edges) gives a lower bound.

🏆

Mini-lesson complete!

⭐⭐⭐

You've worked through Matrices & Graph Theory (AI HL) for IB Diploma Mathematics: Applications & Interpretation HL. 🎉

Mission 1Three receipts, three unknown prices: how does one matrix find them?
Mission 2The city loses 10% a year and gains 5% of the country. Final split?
Mission 3Can you cross all seven bridges of Königsberg exactly once?
Mission 4A postman must walk every street. What's the shortest route?

Your stars: 0 / 0

Next: more IB Mathematics: Applications & Interpretation · HL lessons and games on the IB Mathematics: Applications & Interpretation · HL page.

📣 Smashed it? Share your score

Challenge a mate to beat your stars, or show a parent how you got on.

→ Back to IB Mathematics: Applications & Interpretation · HL

Specification points and sources for this lesson are listed at the bottom of the page.

Matrices & Graph Theory (AI HL)

Three receipts, three unknown prices: how does one matrix find them?

Matrices and multiplication

Multiplying in both orders

Determinant and inverse of a 2×22 × 2 matrix

Systems of equations as Ax=bAx = b

A 2×22 × 2 system by hand

The city loses 10% a year and gains 5% of the country. Final split?

Eigenvalues and eigenvectors

Eigenvalues and eigenvectors of a 2×22 × 2 matrix

Diagonalisation and powers

A formula for MnMⁿ

Transition matrices and steady states

A commuter's travel choices

Can you cross all seven bridges of Königsberg exactly once?

Graph vocabulary

Walks, trails, paths, Euler and Hamilton

Is there an Eulerian trail?

Adjacency matrices

Counting walks with A3A³

A postman must walk every street. What's the shortest route?

Minimum spanning trees

Kruskal's algorithm

The Chinese postman problem

Four odd vertices

The travelling salesman problem

Bounds for a delivery round

Big ideas

Mini-lesson complete!

📣 Smashed it? Share your score

Determinant and inverse of a $2 \times 2$ 2 × 2 matrix

Systems of equations as $A x = b$ Ax = b

A $2 \times 2$ 2 × 2 system by hand

Eigenvalues and eigenvectors of a $2 \times 2$ 2 × 2 matrix

A formula for $M^{n}$ Mⁿ

Counting walks with $A^{3}$ A³