A network (graph) can be represented as an adjacency matrix. For $n$ vertices, the matrix is $n \times n$ where entry $a_{ij}$ = number of edges from vertex $i$ to vertex $j$.
Consider 3 towns: A, B, C with roads: A–B, A–C, B–C, B–B (loop).
$$\text{Adjacency matrix} = \begin{array}{c|ccc} & A & B & C \ \hline A & 0 & 1 & 1 \ B & 1 & 1 & 1 \ C & 1 & 1 & 0 \end{array}$$
The $(i,j)$ entry of $A^n$ gives the number of walks of length $n$ from vertex $i$ to vertex $j$.
$$A^2 = A \times A \quad \Rightarrow \quad (A^2)_{ij} = \text{number of 2-step walks from } i \text{ to } j$$
A transition matrix $T$ models movement between states over time. Each column sums to 1 (column-stochastic).
$$T = \begin{pmatrix} 0.7 & 0.3 \ 0.4 & 0.6 \end{pmatrix}$$
Column 1: From State 1, probability 0.7 of staying, 0.4 of moving to State 2 (columns sum to 1.1 — this example is for illustration; valid matrices have columns summing to 1).
The state vector $S_n$ gives the distribution across states at step $n$:
$$S_n = T \times S_{n-1} = T^n \times S_0$$
At week 0: 80% of customers use Brand X, 20% use Brand Y.
$$S_0 = \begin{pmatrix} 0.8 \ 0.2 \end{pmatrix}, \quad T = \begin{pmatrix} 0.9 & 0.2 \ 0.1 & 0.8 \end{pmatrix}$$
Week 1:
$$S_1 = TS_0 = \begin{pmatrix} 0.9(0.8)+0.2(0.2) \ 0.1(0.8)+0.8(0.2) \end{pmatrix} = \begin{pmatrix} 0.76 \ 0.24 \end{pmatrix}$$
76% Brand X, 24% Brand Y after one week.
KEY TAKEAWAY: Adjacency matrices encode graph structure; transition matrices encode probabilistic movement. Both rely on matrix multiplication to compute multi-step results.
VCAA FOCUS: Be able to set up a transition matrix from a verbal description, identify the state vector, and compute $S_1$ or $S_2$ by hand.
