Scribe logoScribeNotes & practice
Sign inStart free
  1. Notes
  2. ›IB Mathematics: Applications and Interpretation
  3. ›3 Geometry and trigonometry
  4. ›3.15 Adjacency matrices

IB Mathematics: Applications and Interpretation · Topic 3 · Geometry and trigonometry

3.15 Adjacency matrices

Construct an adjacency matrix from a graph, read its information, and use its powers to count walks between vertices.

  • 5 min read
  • 5 parts
  • 10 questions
  • Draft
  • HL only
Start a Quick 5 on this topic→Jump to the 10 questions
1/5An adjacency matrix records a graph as a table of numbers
  1. 1An adjacency matrix records a graph as a table of numbers
  2. 2Constructing the matrix means filling the table cell by cell
  3. 3Rows and columns reveal degrees and edge counts
  4. 4Directed graphs give matrices that are not symmetric
  5. 5Powers of the matrix count walks between vertices
  6. Check your recall
  7. Practice: 10 questions
1

Part 1 of 5: An adjacency matrix records a graph as a table of numbers

A graph is easy to draw but awkward to process when it is large. A table of numbers is easier to store and calculate with. Recall that a graph has vertices joined by edges.

An adjacency matrix lists the vertices along both the rows and the columns. The entry in row iii and column jjj counts the edges joining vertex iii to vertex jjj.

Two vertices joined directly by an edge are adjacent. For a simple graph, the entries are only 0 or 1. A 1 means the vertices are adjacent, and a 0 means they are not.

Key terms · tap one for its definition

adjacency matrix

An adjacency matrix is a square matrix whose entry in row iii and column jjj is the number of edges from vertex iii to vertex jjj.

adjacent

Two vertices are adjacent if an edge joins them directly.

Part 1 done

2

Part 2 of 5: Constructing the matrix means filling the table cell by cell

Start with a drawn graph and follow the same steps each time. Work one row at a time, because each row describes the edges at one vertex.

  • Label the rows and columns with the vertices in the same order.
  • Choose a row vertex and a column vertex.
  • Write the number of edges joining them.
  • Repeat until every cell is filled.

Each row of the finished matrix describes one vertex. Reading along it shows which vertices that vertex is joined to.

Figure 1. The graph has four vertices and four edges. Vertex R is joined to all the others.

Worked example

Building an adjacency matrix

Write the adjacency matrix for the graph with edges PQ, PR, QR and RS, using the order P, Q, R, S.
  1. 1
    Row P: P is joined to Q and R, giving 0,1,1,0.
  2. 2
    Row Q: Q is joined to P and R, giving 1,0,1,0.
  3. 3
    Row R: R is joined to P, Q and S, giving 1,1,0,1.
  4. 4
    Row S: S is joined to R only, giving 0,0,1,0.

Answer: M=(0110101011010010)\mathbf{M}=\begin{pmatrix}0&1&1&0\\1&0&1&0\\1&1&0&1\\0&0&1&0\end{pmatrix}M=​0110​1010​1101​0010​​.

Exam tip

Always state the order of the vertices. Without that order, the rows and columns have no meaning.

Part 2 done

Quick check

One question on the part you just read

Easy

A simple graph has an adjacency matrix with a 1 in row A and column B. Identify what this means.
Show answer and explanation

Answer: A · Worked explanation

An entry of 1 in a simple graph means exactly one edge joins the two vertices. It does not give a degree, because a degree is found by adding a whole row, not by reading one entry.
3

Part 3 of 5: Rows and columns reveal degrees and edge counts

Once the matrix is built, you can read facts from it directly. Add the entries in a row to find the degree of that vertex. In the matrix above, row R adds to 3.

Look at the main diagonal, which runs from top left to bottom right. For a simple graph, every entry there is 0. An undirected graph also gives a symmetric matrix, because each edge works in both directions.

The sum of all the entries is twice the number of edges. Each edge is counted once from each end.

Worked example

Reading a matrix

A simple graph has an adjacency matrix with row sums 2, 3, 3, 2 and 2. Find the number of edges and the degree of the second vertex.
  1. 1
    The row sums are the degrees. Add them: 2+3+3+2+2=122+3+3+2+2=122+3+3+2+2=12.
  2. 2
    The total is twice the number of edges, so edges =122=6=\frac{12}{2}=6=212​=6.
  3. 3
    The degree of the second vertex is its row sum, which is 3.

Answer: The graph has 6 edges, and the second vertex has degree 3.

Key terms · tap one for its definition

main diagonal

The main diagonal of a square matrix is the list of entries running from the top left to the bottom right.

symmetric matrix

A symmetric matrix is a square matrix in which the entry in row iii and column jjj equals the entry in row jjj and column iii.

Part 3 done

4

Part 4 of 5: Directed graphs give matrices that are not symmetric

Now suppose each edge has an arrow, like a one-way street. A directed graph has edges with direction, so it matters which way each edge points.

The entry in row iii and column jjj counts edges from vertex iii to vertex jjj. Read across a row to see where edges leave. Read down a column to see where they arrive.

Common mistake

Do not assume a symmetric matrix. In a directed graph, the entries in row iii, column jjj and in row jjj, column iii can differ.

Worked example

A directed matrix

A directed graph has edges P to Q, Q to R, R to P and P to R. Write its adjacency matrix in the order P, Q, R.
  1. 1
    Row P: edges leave P for Q and R, giving 0,1,1.
  2. 2
    Row Q: one edge leaves Q for R, giving 0,0,1.
  3. 3
    Row R: one edge leaves R for P, giving 1,0,0.

Answer: (011001100)\begin{pmatrix}0&1&1\\0&0&1\\1&0&0\end{pmatrix}​001​100​110​​.

Key term

directed graph

A directed graph is a graph in which each edge has a direction, shown by an arrow from one vertex to another.

Part 4 done

Quick check

One question on the part you just read

Easy

State the value of every entry on the main diagonal of the adjacency matrix of a simple undirected graph.
Show answer and explanation

Answer: A · Worked explanation

A simple graph has no loops, so no vertex has an edge to itself, and every diagonal entry is 0. The degree appears as a row sum, not as a diagonal entry. A diagonal entry records edges from a vertex to itself, and a simple graph has none.
5

Part 5 of 5: Powers of the matrix count walks between vertices

Suppose you want routes that use exactly two edges. A walk is a sequence of edges in which each edge begins where the previous one ended. Vertices and edges may repeat.

The length of a walk is its number of edges. The entry in row iii and column jjj of Mk\mathbf{M}^kMk is the number of walks of length kkk from vertex iii to vertex jjj.

Worked example

Counting walks of length 2

Use M=(0110101011010010)\mathbf{M}=\begin{pmatrix}0&1&1&0\\1&0&1&0\\1&1&0&1\\0&0&1&0\end{pmatrix}M=​0110​1010​1101​0010​​ for the graph with vertices P, Q, R, S. Find the number of walks of length 2 from P to S, and from R to R.
  1. 1
    The entry for P to S is row P of M\mathbf{M}M times column S: (0,1,1,0)⋅(0,0,1,0)=0+0+1+0=1(0,1,1,0)\cdot(0,0,1,0)=0+0+1+0=1(0,1,1,0)⋅(0,0,1,0)=0+0+1+0=1.
  2. 2
    The entry for R to R is row R times column R: (1,1,0,1)⋅(1,1,0,1)=1+1+0+1=3(1,1,0,1)\cdot(1,1,0,1)=1+1+0+1=3(1,1,0,1)⋅(1,1,0,1)=1+1+0+1=3.
  3. 3
    Check the first walk: P to R to S has length 2.

Answer: There is 1 walk from P to S, and 3 walks from R to R.

A positive entry in Mk\mathbf{M}^kMk means the two vertices are joined by a walk of length kkk. A zero means there is none. For a simple graph, the diagonal of M2\mathbf{M}^2M2 lists the degrees.

Exam tip

State the vertex order and the power kkk. Then read the entry from the correct row and column.

Key term

walk

A walk is a sequence of edges in which each edge begins at the vertex where the previous edge ended.

Note read

Check your recall[14 marks]

6 written questions. Answer each one in your head or on paper, then open the mark scheme.

  1. 1.Write down[2 marks]

    Write down the adjacency matrix for a graph with vertices A, B and C and edges AB and BC, using the order A, B, C.

    Show mark schemeHide mark scheme

    Model answer

    (010101010)\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}​010​101​010​​.

    • 1 mark for a matrix with zeros on the main diagonal
    • 1 mark for entries of 1 in the positions for AB and BC, in both directions
  2. 2.State[2 marks]

    State two features of the adjacency matrix of a simple undirected graph.

    Show mark schemeHide mark scheme

    Model answer

    The main diagonal contains only zeros. The matrix is symmetric.

    • 1 mark for stating that the main diagonal entries are zero
    • 1 mark for stating that the matrix is symmetric
  3. 3.Determine[3 marks]

    The adjacency matrix of a simple graph has row sums 3, 2, 2 and 1. Determine the number of edges and the degree of the first vertex.

    Show mark schemeHide mark scheme

    Model answer

    The sum of the row sums is 3+2+2+1=83+2+2+1=83+2+2+1=8, which is twice the number of edges, so there are 4 edges. The first vertex has degree 3.

    • 1 mark for adding the row sums to obtain 8
    • 1 mark for halving to obtain 4 edges
    • 1 mark for stating that the degree of the first vertex is 3
  4. 4.Explain[2 marks]

    Explain why the adjacency matrix of a directed graph may not be symmetric.

    Show mark schemeHide mark scheme

    Model answer

    Each entry counts edges from the row vertex to the column vertex. An edge from one vertex to another need not have a return edge, so the two entries can differ.

    • 1 mark for stating that entries count edges from the row vertex to the column vertex
    • 1 mark for explaining that an edge in one direction need not have a return edge
  5. 5.Calculate[3 marks]

    A graph has adjacency matrix M=(011101110)\mathbf{M}=\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}M=​011​101​110​​. Calculate the number of walks of length 2 from vertex 1 to vertex 2.

    Show mark schemeHide mark scheme

    Model answer

    The entry is row 1 times column 2 of M\mathbf{M}M: (0,1,1)⋅(1,0,1)=0+0+1=1(0,1,1)\cdot(1,0,1)=0+0+1=1(0,1,1)⋅(1,0,1)=0+0+1=1. There is 1 walk of length 2.

    • 1 mark for using row 1 and column 2 of M\mathbf{M}M
    • 1 mark for multiplying and adding 0+0+10+0+10+0+1
    • 1 mark for obtaining 1 walk
  6. 6.Deduce[2 marks]

    The matrix M2\mathbf{M}^2M2 of a simple graph has diagonal entries 3, 2, 2 and 1. Deduce the degree of each vertex, giving a reason.

    Show mark schemeHide mark scheme

    Model answer

    Each diagonal entry of M2\mathbf{M}^2M2 counts walks of length 2 from a vertex back to itself, which equals its degree. The degrees are 3, 2, 2 and 1.

    • 1 mark for stating that the diagonal entries equal the degrees
    • 1 mark for giving the degrees 3, 2, 2 and 1

Practice this topic

10 quick-fire multiple-choice questions, easy to hard. Tap an answer to see if you're right and the worked explanation. (The written questions with mark schemes are under “Check your recall” above.)

0 right0 of 10 answered

Includes the 2 quick checks in the note above.

3.

Easy·State[1 mark]

A graph has 5 vertices. State the size of its adjacency matrix.
Show answer and explanation

Answer: A · Worked explanation

The vertices are listed along both the rows and the columns, so the matrix has 5 rows and 5 columns. A 5×15\times15×1 matrix would list the vertices only once. A 10×1010\times1010×10 matrix would count the vertices twice over.
4.

Medium·Determine[1 mark]

The row sums of the adjacency matrix of a simple graph are 3, 2, 2, 2 and 1. Determine the number of edges.
Show answer and explanation

Answer: B · Worked explanation

The row sums add to 10, and this equals twice the number of edges, so there are 5 edges. The value 10 is the sum of the degrees, which counts each edge from both ends.
5.

Medium·Determine[2 marks]

A graph has vertices in the order X, Y, Z, W and edges XY, YZ, ZW and XZ. Determine the row for Z.
Show answer and explanation

Answer: D · Worked explanation

Z is joined to X, Y and W, but not to itself. In the order X, Y, Z, W this gives 1, 1, 0, 1. A 1 in the Z position would show a loop at Z, which a simple graph does not have.
6.

Medium·Identify[2 marks]

A directed graph has adjacency matrix (010001100)\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}​001​100​010​​. Identify the edges it describes.
Show answer and explanation

Answer: B · Worked explanation

Rows give where edges leave, so a 1 in row 1, column 2 is an edge from 1 to 2. The same reading gives 2 to 3 and 3 to 1. Reading columns as rows reverses the directions, and an undirected triangle would give a symmetric matrix.
7.

Medium·Calculate[2 marks]

A path graph with vertices A, B, C has M=(010101010)\mathbf{M}=\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}M=​010​101​010​​. Calculate the number of walks of length 2 from A to C.
Show answer and explanation

Answer: A · Worked explanation

The entry is row A times column C: (0,1,0)⋅(0,1,0)=1(0,1,0)\cdot(0,1,0)=1(0,1,0)⋅(0,1,0)=1, the walk A, B, C. The value 0 would follow from checking only for a direct edge, which tests walks of length 1. The value 2 would suggest two different routes, but only vertex B links A to C.
8.

Hard·Deduce[2 marks]

In a simple undirected graph, the entry in row B and column B of M2\mathbf{M}^2M2 is 4. Deduce the correct statement.
Show answer and explanation

Answer: D · Worked explanation

A walk of length 2 from B to B goes out along one edge and back along the same edge, so the entry equals the degree of B. The value 2 comes from halving the entry, but every edge at B gives a separate walk out and back.
9.

Hard·Calculate[2 marks]

A graph has edges PQ, PR, QR and RS. Row P of M2\mathbf{M}^2M2 is (2,1,1,1)(2,1,1,1)(2,1,1,1) and column S of M\mathbf{M}M is (0,0,1,0)(0,0,1,0)(0,0,1,0). Calculate the number of walks of length 3 from P to S.
Show answer and explanation

Answer: C · Worked explanation

The entry of M3\mathbf{M}^3M3 is row P of M2\mathbf{M}^2M2 times column S of M\mathbf{M}M: 2×0+1×0+1×1+1×0=12\times0+1\times0+1\times1+1\times0=12×0+1×0+1×1+1×0=1. The value 5 comes from adding the whole row, which ignores that only R is adjacent to S. The value 2 uses the entry for P to P, but P is not next to S.
10.

Hard·Determine[2 marks]

A directed graph has M=(011001100)\mathbf{M}=\begin{pmatrix}0&1&1\\0&0&1\\1&0&0\end{pmatrix}M=​001​100​110​​. Determine the number of edges that arrive at vertex 3.
Show answer and explanation

Answer: D · Worked explanation

Edges arriving at a vertex are counted down its column. Column 3 holds 1+1+0=21+1+0=21+1+0=2, from vertices 1 and 2. The value 1 is the row 3 sum, which counts edges leaving vertex 3. The value 4 is the total number of edges, which is the sum of every entry.

Keep going

Next topic3.16 Tree and cycle algorithmsPrevious topic3.14 Graph theory

More in Topic 3 · Geometry and trigonometry

  1. 3.8Unit circle and identitiesNotes · 10 questions· HL only
  2. 3.9Matrix transformationsNotes · 10 questions· HL only
  3. 3.10Vector conceptsNotes · 10 questions· HL only
  4. 3.11Vector equation of a lineNotes · 10 questions· HL only
  5. 3.12Vectors in kinematicsNotes · 10 questions· HL only
  6. 3.13Scalar and vector productsNotes · 10 questions· HL only
  7. 3.14Graph theoryNotes · 10 questions· HL only
  8. 3.15Adjacency matricesNotes · 10 questions· HL only
  9. 3.16Tree and cycle algorithmsNotes · 10 questions· HL only

All IB Mathematics: Applications and Interpretation topics →

Draft: written by Scribe and checked automatically, not yet by a subject reviewer.

Practice questions are original, written by Scribe and checked automatically for correctness.

Topic codes follow the official numbering. Not endorsed by IB Diploma Programme or any exam board.

On this page

0/5 read

  1. 1An adjacency matrix records a graph as a table of numbers
  2. 2Constructing the matrix means filling the table cell by cell
  3. 3Rows and columns reveal degrees and edge counts
  4. 4Directed graphs give matrices that are not symmetric
  5. 5Powers of the matrix count walks between vertices
  6. Check your recall
  7. Practice: 10 questions
All coursesScribeHow it worksPricingPrivacyTerms

Notes and questions are written by Scribe in our own words. Topic codes follow the official course numbering so you can find your place. Not produced or endorsed by the IB, College Board, AQA, OCR, Pearson Edexcel or any exam board.

© 2026 Scribe