Adjacency Matrices

A drawing of a graph is great for people, but a computer (or your GDC) needs numbers. An adjacency matrix stores a graph as a square grid of numbers, and then ordinary matrix multiplication does something surprising: powers of the matrix count the routes through the graph. The same idea, turned into probabilities, is how search engines rank web pages.

Key ideas

The adjacency matrix

Label the vertices in a fixed order. The adjacency matrix $A$ has one row and one column for each vertex:

• Undirected graph: the entry in row $i$, column $j$ is the number of edges joining vertex $i$ and vertex $j$. The matrix is symmetric, and in a simple graph the main diagonal is all $0$s. Each row adds up to the degree of that vertex (in a graph without loops).
• Directed graph: the entry in row $i$, column $j$ is the number of arcs from vertex $i$ to vertex $j$. The matrix usually isn’t symmetric. Row sums are out-degrees and column sums are in-degrees.

The undirected graph G and the directed graph H used in the examples.

Walks and powers of the adjacency matrix

A walk is a sequence of edges where each edge starts at the vertex where the previous one ended. Vertices and edges may be repeated. The length of a walk is the number of edges in it, so A to B to A to C has length $3$.

If $A$ is the adjacency matrix, the entry in row $i$, column $j$ of $A^k$ is the number of walks of length $k$ from vertex $i$ to vertex $j$.

Why it works for $k = 2$: the $(i, j)$ entry of $A^2$ is $a_{i1}a_{1j} + a_{i2}a_{2j} + \dots$, and each product $a_{im}a_{mj}$ counts the ways to go from $i$ to $m$ and then from $m$ to $j$. Adding over every middle vertex $m$ counts every walk of length $2$. Higher powers repeat the argument.

To count walks of length up to $k$ (lengths $1, 2, \dots, k$), add the powers:

$$S = A + A^2 + A^3 + \dots + A^k$$

Read the wording carefully: “fewer than $4$ edges” means lengths $1$, $2$ and $3$, so you’d use $A + A^2 + A^3$. Use your GDC’s matrix functions to find powers and sums.

Weighted adjacency tables

For a weighted graph, a weighted adjacency table shows the weight of the edge joining each pair of vertices (a distance, cost or time), with a dash where there’s no edge. For example, travel times in minutes between four towns:

	A	B	C	D
A	–	12	–	20
B	12	–	9	15
C	–	9	–	7
D	20	15	7	–

There’s no direct road from A to C. Tables like this are the input for the minimum spanning tree and travelling salesman algorithms.

Transition matrices for a graph

Imagine a walker who, at each step, leaves the current vertex along one of its edges, chosen at random with equal probabilities. The transition matrix $T$ describes these moves, using the IB convention from Markov chains:

$$T_{ij} = \text{probability of moving from vertex } j \text{ to vertex } i$$

So column $j$ describes the moves out of vertex $j$: if vertex $j$ has $d$ edges (or out-arcs) leaving it, each of the vertices they lead to gets probability $\tfrac{1}{d}$ in column $j$. Every column adds up to $1$.

The graph should be strongly connected (every vertex can reach every other), so the walker can never get stuck in one part of the graph. Then the long-run proportion of time spent at each vertex is the steady state vector $\vec{s}$ with $T\vec{s} = \vec{s}$, found by raising $T$ to a high power on a GDC or by solving equations.

This is the core of the Google PageRank idea: vertices are web pages, arcs are links, and pages where the random surfer spends the most time are ranked highest.

Worked examples

Example 1: Writing an adjacency matrix

Write down the adjacency matrix of graph G in the figure, and use it to find the degree of each vertex.

Solution. Use the order A, B, C, D. A is joined to B and C; B to A, C and D; C to A, B and D; D to B and C:

$$A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}$$

The matrix is symmetric, as it must be for an undirected graph. The row sums give the degrees: A has degree $2$, B $3$, C $3$ and D $2$.

Example 2: Counting walks in G

Using the matrix from Example 1, find:

• (a) the number of walks of length $3$ from A to D,
• (b) the number of walks of length $2$ from B back to B,
• (c) the number of walks of length at most $3$ from A to B.

Solution. With a GDC:

$$A^2 = \begin{pmatrix} 2 & 1 & 1 & 2 \\ 1 & 3 & 2 & 1 \\ 1 & 2 & 3 & 1 \\ 2 & 1 & 1 & 2 \end{pmatrix}, \qquad A^3 = \begin{pmatrix} 2 & 5 & 5 & 2 \\ 5 & 4 & 5 & 5 \\ 5 & 5 & 4 & 5 \\ 2 & 5 & 5 & 2 \end{pmatrix}$$

(a) Row A, column D of $A^3$: there are $2$ walks. (Check: A to B to C to D, and A to C to B to D.)

(b) Row B, column B of $A^2$: there are $3$ walks (B to A to B, B to C to B, B to D to B). On the diagonal, $A^2$ always shows the degree of a vertex in a simple graph: out and back along each edge.

(c) Add the entries in row A, column B of $A$, $A^2$ and $A^3$:

$$1 + 1 + 5 = 7 \text{ walks}$$

Example 3: A directed graph

For the directed graph H in the figure:

• (a) Write down its adjacency matrix $M$.
• (b) Find the number of walks of length $3$ from A back to A, and list them.

Solution. (a) Rows are “from” and columns are “to”, in the order A, B, C, D. The arcs are A to B, A to C, B to C, C to A, C to D and D to A:

$$M = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}$$

(b) By GDC,

$$M^3 = \begin{pmatrix} 2 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 2 & 1 \\ 1 & 0 & 1 & 1 \end{pmatrix}$$

The row A, column A entry is $2$. The two walks are A to B to C to A, and A to C to D to A.

Example 4: Transition matrix and a ranking

Graph H represents four web pages and the links between them. A surfer follows one of the links on the current page at random, each equally likely.

• (a) Explain why H is strongly connected.
• (b) Write down the transition matrix $T$.
• (c) Find the steady state vector and rank the pages.

Solution. (a) A to B to C to D to A is a closed route through all four vertices, so every page can be reached from every other.

(b) Work column by column, in the order A, B, C, D. Page A links to B and C, so column A has $\tfrac{1}{2}$ in rows B and C. Page B links only to C. Page C links to A and D. Page D links only to A:

$$T = \begin{pmatrix} 0 & 0 & \tfrac{1}{2} & 1 \\ \tfrac{1}{2} & 0 & 0 & 0 \\ \tfrac{1}{2} & 1 & 0 & 0 \\ 0 & 0 & \tfrac{1}{2} & 0 \end{pmatrix}$$

Check: each column adds to $1$.

(c) On a GDC, $T^{n}$ for a large $n$ (say $n = 50$) has every column close to the same vector. Or solve $T\vec{s} = \vec{s}$ with the entries adding to $1$:

$$\vec{s} = \begin{pmatrix} \tfrac{1}{3} \\ \tfrac{1}{6} \\ \tfrac{1}{3} \\ \tfrac{1}{6} \end{pmatrix} \approx \begin{pmatrix} 0.333 \\ 0.167 \\ 0.333 \\ 0.167 \end{pmatrix}$$

Check: $T\vec{s}$ has first entry $\tfrac{1}{2} \cdot \tfrac{1}{3} + 1 \cdot \tfrac{1}{6} = \tfrac{1}{3}$, as required. In the long run the surfer is on pages A and C a third of the time each, and on B and D a sixth of the time each. So A and C rank equal first, then B and D equal third.

Common mistakes

Mixing up rows and columns for a directed graph. In the adjacency matrix, row $i$, column $j$ counts arcs from $i$ to $j$. For the transition matrix, the IB convention flips this: column $j$ holds the probabilities of moving from $j$. Write a “from/to” label on your matrix before filling it in.

Reading the wrong power. Walks of length $3$ come from $A^3$, not $A^2$. For “at most $k$” or “fewer than $k$”, add the right powers, starting from $A^1$.

Thinking walks can’t repeat. Walks may revisit vertices and reuse edges, so B to A to B counts as a walk of length $2$. That’s why $A^k$ can give large numbers.

Columns of the transition matrix that don’t add to 1. Each column splits probability $1$ equally over the edges leaving that vertex. If vertex B has three neighbours, each gets $\tfrac{1}{3}$ in column B.

Using a weighted table as an adjacency matrix. The weights are distances or costs, not counts of edges. Don’t raise a weighted table to a power to count walks.

Practice

1. (Warm-up) A graph has vertices P, Q, R, S and edges PQ, PS, QR, QS and RS. Write down its adjacency matrix and the degree of each vertex.

Solution

In the order P, Q, R, S:

$$\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix}$$

Row sums: P has degree $2$, Q $3$, R $2$, S $3$.

2. (Warm-up) An undirected graph with vertices P, Q, R, S has adjacency matrix

$$\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 2 & 0 \\ 0 & 2 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}$$

How many edges does the graph have? Is it a simple graph?

Solution

The entries add to $2 + 3 + 3 + 2 = 10$, and each edge is counted twice (once in each direction), so there are $\tfrac{10}{2} = 5$ edges.

It is not simple: the $2$ in row Q, column R means there are two edges joining Q and R.

3. (Warm-up) A directed graph with vertices X, Y, Z has adjacency matrix (rows “from”, columns “to”)

$$\begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$$

Find the out-degree and in-degree of each vertex.

Solution

Out-degrees are the row sums: X $2$, Y $1$, Z $1$.

In-degrees are the column sums: X $1$, Y $1$, Z $2$.

4. (Core) For graph G in the figure, use your GDC to find the number of walks of length $4$ from A to C.

Solution

$$A^4 = \begin{pmatrix} 10 & 9 & 9 & 10 \\ 9 & 15 & 14 & 9 \\ 9 & 14 & 15 & 9 \\ 10 & 9 & 9 & 10 \end{pmatrix}$$

Row A, column C: there are $9$ walks of length $4$.

5. (Core) For graph G, find the number of walks from A to D that use fewer than $4$ edges.

Solution

“Fewer than $4$” means lengths $1$, $2$ and $3$. Add the row A, column D entries of $A$, $A^2$ and $A^3$:

$$0 + 2 + 2 = 4 \text{ walks}$$

(There’s no edge AD; the walks of length $2$ are A to B to D and A to C to D.)

6. (Core) Use the weighted adjacency table of travel times (in minutes) in the Key ideas.

• (a) How many roads are there, and what is their total travel time?
• (b) Find the time for the route A to B to C to D, and compare it with the direct road from A to D.
• (c) Explain why the table is symmetric.

Solution

(a) Count the entries above the diagonal: AB, AD, BC, BD and CD, so $5$ roads. Total: $12 + 20 + 9 + 15 + 7 = 63$ minutes.

(b) $12 + 9 + 7 = 28$ minutes, which is $8$ minutes longer than the direct road (20 minutes).

(c) The roads are two-way, so the time from X to Y equals the time from Y to X: the entry in row X, column Y equals the entry in row Y, column X.

7. (Core) A walker moves randomly on graph G, choosing each edge at the current vertex with equal probability.

• (a) Write down the transition matrix $T$ (order A, B, C, D).
• (b) The walker starts at A. Find the probability that it is at D after two steps.
• (c) Find the long-run proportion of time the walker spends at each vertex.

Solution

(a) A has neighbours B and C, D has neighbours B and C (each $\tfrac{1}{2}$); B and C each have three neighbours (each $\tfrac{1}{3}$):

$$T = \begin{pmatrix} 0 & \tfrac{1}{3} & \tfrac{1}{3} & 0 \\ \tfrac{1}{2} & 0 & \tfrac{1}{3} & \tfrac{1}{2} \\ \tfrac{1}{2} & \tfrac{1}{3} & 0 & \tfrac{1}{2} \\ 0 & \tfrac{1}{3} & \tfrac{1}{3} & 0 \end{pmatrix}$$

(b) The row D, column A entry of $T^2$ is $\tfrac{1}{3}$. Check by listing: A to B to D has probability $\tfrac{1}{2} \times \tfrac{1}{3} = \tfrac{1}{6}$, and A to C to D also $\tfrac{1}{6}$, total $\tfrac{1}{3}$.

(c) Solving $T\vec{s} = \vec{s}$ (or using a high power of $T$ on a GDC):

$$\vec{s} = \begin{pmatrix} 0.2 \\ 0.3 \\ 0.3 \\ 0.2 \end{pmatrix}$$

So $20\%$ of the time at A and at D, and $30\%$ at B and at C. (Notice these are proportional to the degrees $2, 3, 3, 2$.)

8. (Challenge) Three web pages X, Y, Z have links X to Y, X to Z, Y to Z and Z to X. A surfer follows a random link on each page.

• (a) Show that the graph is strongly connected.
• (b) Write down the transition matrix and find the exact steady state vector by solving equations.

Solution

(a) X to Y to Z to X is a closed route through all three pages, so each page can reach every other.

(b) Order X, Y, Z. Column X splits between Y and Z; column Y goes to Z; column Z goes to X:

$$T = \begin{pmatrix} 0 & 0 & 1 \\ \tfrac{1}{2} & 0 & 0 \\ \tfrac{1}{2} & 1 & 0 \end{pmatrix}$$

Let $\vec{s} = (x, y, z)$. From $T\vec{s} = \vec{s}$: the first row gives $z = x$, the second gives $y = \tfrac{1}{2}x$. With $x + y + z = 1$:

$$x + \tfrac{1}{2}x + x = 1 \quad\Rightarrow\quad x = \tfrac{2}{5}$$

So $\vec{s} = \left(\tfrac{2}{5}, \tfrac{1}{5}, \tfrac{2}{5}\right)$. Check the third row: $\tfrac{1}{2} \cdot \tfrac{2}{5} + \tfrac{1}{5} = \tfrac{2}{5} = z$.

9. (Challenge) Let $A$ be the adjacency matrix of a simple undirected graph. Explain why the diagonal entry in row $i$ of $A^2$ equals the degree of vertex $i$.

Solution

The diagonal entry is $(A^2)_{ii} = a_{i1}a_{1i} + a_{i2}a_{2i} + \dots$. Because the graph is undirected, $a_{mi} = a_{im}$, so each term is $a_{im}^2$. In a simple graph each $a_{im}$ is $0$ or $1$, so $a_{im}^2 = a_{im}$. The sum is $a_{i1} + a_{i2} + \dots$, the row sum, which is the degree of vertex $i$. In walk language: each walk of length $2$ from $i$ back to $i$ goes out along one edge and straight back, so there’s one for each edge at $i$.