Topic 3.18 · HL only

Adjacency matrices (incl. weighted) + building transition matrices: notes and practice questions

Summary

Adjacency Matrix: Represents graph connections between vertices.
Complete Graph: Each vertex connected to every other vertex by a single edge.
Directed Graph: Edges have a specific travel direction.
In-degree: Number of edges leading into a specific vertex.
Strongly Connected Graph: Directed graph allowing walks in either direction between any two vertices.
Weighted Graph: Edges assigned numerical values (e.g., distance, time).
Weighted Adjacency Table: Shows exact edge weights; empty cells mean no direct connection.
Undirected Weighted Graph: Table of least values has symmetry along the leading diagonal.
Markov Chain States: Mutually exclusive events that change over time.
Transition State Diagram: Visual representation of a Markov Chain; edges show transition probabilities.
Markov Chain Probability Rule: Probabilities on arrows out of a single state sum to 1.
Transition Matrix ( $T$ ): Shows transition probabilities. Columns = current states, Rows = next states. Column probabilities sum to 1.
Walks of length $n$ : Number of walks found by raising adjacency matrix $M$ to power $n$ : $M^n$
Walks of length $n$ or less: Total walks found by summing successive powers of $M$ : $S_n = M + M^2 + M^3 + \dots + M^n$
Future States (Markov Chains): Probability vector for next state ( $s_1$ ) found by multiplying transition matrix ( $T$ ) by initial state vector ( $s_0$ ): $s_1 = T s_0$
Matrix Diagonalisation (for $T^n$ ): $T^n = P D^n P^{-1}$ where $D$ is a diagonal matrix of eigenvalues and $P$ is a matrix of corresponding eigenvectors.
Steady State Limits: As $n \to \infty$ , $T^\infty$ has identical columns; every transition matrix has an eigenvalue of 1.
Shortest Route Method: Fill direct connections, then check for shorter paths via intermediate vertices.
Expected Populations (Markov Chains): Multiply $T s_0$ by total population $N$ to find expected numbers in each state.
Graph Theory (adjacency matrices, walks) and Markov Chains (transition matrices, steady states, diagonalisation) are HL topics.
GDC: Store matrices, calculate $M^n$ or $M + M^2 + \dots$ , check transition matrix column sums (must be 1).
Exam Tip: Draw transition state diagrams to visualise problems.
Exam Tip: For undirected graphs, use symmetry of least values table.
Exam Tip: Verify steady state calculations by checking for identical columns in $T^\infty$ .
Exam Tip: Always check for hidden shorter routes via intermediate nodes in least weights tables.

How it is examined

The $A^k$ result is the reliable question: raise the matrix to a power on the GDC, read one entry. "Walks of less than $k$ length" means summing $A + A^2 + \dots + A^k$ , and students often forget the sum and give only $A^k$ . Building a transition matrix from a graph is the bridge into AHL 4.19, and the column-versus-row convention has to be stated in the question or the answer is ambiguous.

Key ideas

Adjacency matrices.
Walks.
The number of $k$ -length walks, or walks of less than $k$ length, between two vertices.
Weighted adjacency tables.

Linking questions

International-mindedness: the "Bridges of Konigsberg" problem.
Links to websites: adjacency matrices and airlines. PageRank is one method for determining the importance rank of a webpage, simulation at www.eprisner.de/MAT103/PageRank.html

Practice questions

2 questions · 1 medium · 1 hard

Showing 2 of 2

Question 1

MediumPaper 1 · calculator7 marks

(a)

A streaming service offers two subscription plans: Premium and Basic. The service has found that customers' choices follow a pattern. If a customer has the Premium plan in a given month, the probability they will keep the Premium plan the next month is 0.8. If a customer has the Basic plan in a given month, the probability they will upgrade to the Premium plan the next month is 0.1.

(a) Let the states be Premium (State 1) and Basic (State 2). Write down the transition matrix, T, for this Markov chain.

[2]

(b)

(b) A new customer subscribes to the Premium plan in their first month, January. Find the probability that this customer will have the Premium plan in March of the same year.

[2]

(c)

[3]

Question 2

HardPaper 2 · calculator27 marks

(a)

(a) A single data packet can be transferred between three servers, S1, S2, and S3, in a network. The possible direct transfers are:

From S1, the packet can be sent to S2 or stay in S1.

From S2, the packet can be sent to S1 or S3.

From S3, the packet can be sent to S2 or stay in S3.

Write down the adjacency matrix for the directed graph representing these possible direct data transfers, ordering the servers S1, S2, S3.

[2]

(b)

(b) Find the total number of distinct data paths of length 5 from server S1 to server S2.

[3]

(c)(i)

(c.i) Every possible sequence of 5 data transfers has the same probability of occurring. State this probability.

[3]

(c)(ii)

(c.ii) Use your answer to part (b) to find the probability that if a data packet was initially on server S1, it will be on server S2 after 5 transfers.

[3]

(d)(i)

(d.i) A network administrator monitors the movement of two data packets. The possible combined states of the two packets (assuming they occupy distinct servers) are $S_{12}$ (packets on S1 and S2), $S_{13}$ (packets on S1 and S3), and $S_{23}$ (packets on S2 and S3).

The transitions between these states are modelled by the following transition matrix $T$ , where rows represent the current state and columns represent the next state, in the order $S_{12}, S_{13}, S_{23}$ :

$T = \begin{pmatrix} 0 & 0.25 & 0.4 \\ 0.6 & 0.5 & 0.6 \\ 0.4 & 0.25 & 0 \end{pmatrix}$

State the probability that if the packets are currently in state $S_{12}$ , they will be in state $S_{13}$ after one transfer.

[3]

(d)(ii)

(d.ii) Using the transition matrix $T$ from part (d.i), state the probability that if the packets are currently in state $S_{13}$ , they will be in state $S_{23}$ after one transfer.

[3]

(d)(iii)

(d.iii) Using the transition matrix $T$ from part (d.i), state the probability that if the packets are currently in state $S_{23}$ , they will be in state $S_{12}$ after one transfer.

[3]

(e)

(e) Given that the two data packets are initially in state $S_{12}$ (on servers S1 and S2), find the probability that they will be in state $S_{23}$ (on servers S2 and S3) after 5 transfers.

[4]

(f)

(f) The data packets continue this pattern of transfers for a long period. Find the server that is occupied least and the proportion of the time it is free.

[3]

Every Adjacency matrices (incl. weighted) + building transition matrices question, marked for you

Every answer is marked mark by mark, IB-style, and the AI tutor helps when you are stuck.

Where marks are lost

Leaving an answer in calculator notation. Never accepted in a final answer, and AI's constant calculator use makes this the easiest slip in the whole subject.

FAQ

Questions,
answered.

Can't find what you're looking for? Email our student team.

What does Adjacency matrices (incl. weighted) + building transition matrices cover in IB Maths AI?

Adjacency Matrix: Represents graph connections between vertices. Complete Graph: Each vertex connected to every other vertex by a single edge. Directed Graph: Edges have a specific travel direction.

Is Adjacency matrices (incl. weighted) + building transition matrices SL or HL?

Adjacency matrices (incl. weighted) + building transition matrices is HL only. SL students are not examined on it.

How do I revise Adjacency matrices (incl. weighted) + building transition matrices for IB Maths AI?

Start from the core idea: adjacency Matrix: Represents graph connections between vertices. In the exam: the A^k result is the reliable question: raise the matrix to a power on the GDC, read one entry. "Walks of less than k length" means summing A + A^2 + ... Then practise exam-style questions, easiest first, writing out every step of your working before you check it.

How does FourtyFive help me practise Adjacency matrices (incl. weighted) + building transition matrices?

FourtyFive has 2 Adjacency matrices (incl. weighted) + building transition matrices questions. Every answer you write is marked mark by mark, IB-style, and you see where each mark was won or lost. Every part has a hint, the AI tutor helps you through the step you are stuck on, and your Study Profile picks what to practise next.

Is FourtyFive free for Adjacency matrices (incl. weighted) + building transition matrices practice?

Yes. A free account gives you 50 marked answers a month, and you do not need a card to sign up.

Can I handwrite Adjacency matrices (incl. weighted) + building transition matrices answers on an iPad?

Yes. In the FourtyFive iPad app you write your working by hand with Apple Pencil, the way you would on paper, and it is marked the same way.

Adjacency matrices (incl. weighted) + building transition matrices: notes and practice questions

How it is examined

Linking questions

Practice questions

Question 1

Question 2

Every Adjacency matrices (incl. weighted) + building transition matrices question, marked for you

Where marks are lost

Practise this topic as a session

Questions,
answered.

Start with the IB question
bank built for you.

How it is examined

Linking questions

Practice questions

Question 1

Question 2

Every Adjacency matrices (incl. weighted) + building transition matrices question, marked for you

Where marks are lost

Questions,answered.

Start with the IB questionbank built for you.

Questions,
answered.

Start with the IB question
bank built for you.