Count routes using powers of a connection matrix practice questions | General Mathematics (Year 12, VCE Units 3 & 4, Matrices, Communication and dominance matrices)

Two-step routes and matrix powers

A connection matrix records direct connections in a fixed vertex order. Its square is found by matrix multiplication, and each entry of C squared counts routes that use exactly two connections

C^{2}=C \times C

Use the square for two steps Use the square of a connection matrix for routes with two connections and the cube for routes with three connections \(\displaystyle C^{2}=C \times C,\qquad C^{3}=C \times C \times C\)
Pair a row with a column For one entry of C squared, pair the matching entries in a row of C and a column of C \(\displaystyle \left(C^{2}\right)_{ij}=c_{i1}c_{1j}+c_{i2}c_{2j}+c_{i3}c_{3j}\)
Count each intermediate Each product represents routes through one intermediate vertex, and the products are added \(\displaystyle 1 \times 2+2 \times 1+1 \times 0=4\)
Read a leading diagonal entry A leading diagonal entry of C squared counts routes that start and end at the same vertex after exactly two connections. If a loop is present, the intermediate vertex may be the starting vertex \(\displaystyle \left(C^{2}\right)_{11}=2 \times 2+0 \times 0+1 \times 1=5\)

Worked example

The connection matrix for vertices P, Q and R is shown below. Find the number of two-step routes from P to R

C=\begin{bmatrix}0&1&1\\1&0&1\\1&1&0\end{bmatrix},\qquad \text{Find }\left(C^{2}\right)_{13}

\(\displaystyle \text{row }1(C)=(0,1,1),\qquad \text{column }3(C)=\begin{bmatrix}1\\1\\0\end{bmatrix}\)Use the row for P and the column for R
\(\displaystyle \left(C^{2}\right)_{13}=0 \times 1+1 \times 1+1 \times 0\)Multiply corresponding entries from the selected row and column
\(\displaystyle \left(C^{2}\right)_{13}=0+1+0=1\)Adding the three products gives the number of two-step routes from P to R

Common mistakes

Reading the direct matrix

✕\(\displaystyle C_{11}=0 \Rightarrow \text{0 two-step routes from P to P}\)✓\(\displaystyle \left(C^{2}\right)_{11}=0 \times 0+1 \times 1+1 \times 1=2\)

The original matrix records direct connections; two-step routes are counted in C squared

Squaring entries separately

✕\(\displaystyle \begin{bmatrix}0&2\\1&0\end{bmatrix}^{2}=\begin{bmatrix}0&4\\1&0\end{bmatrix}\)✓\(\displaystyle \begin{bmatrix}0&2\\1&0\end{bmatrix}^{2}=\begin{bmatrix}2&0\\0&2\end{bmatrix}\)

A matrix power is repeated matrix multiplication, so each entry comes from a row and a column rather than an entry being powered alone

Using the wrong power

✕\(\displaystyle \left(C^{3}\right)_{12}=3 \Rightarrow \text{three-step routes used for a two-step count}\)✓\(\displaystyle \left(C^{2}\right)_{12}=1 \Rightarrow \text{two-step routes used for a two-step count}\)

The exponent gives the number of connections in each route, so the square counts two steps and the cube counts three

Difficulty levels

introFind C squared and a named two-step count for a small undirected network

standardFind a named entry, count the routes and list their intermediate vertices in an undirected network

challengeUse a directed network to count two-step and three-step routes and find a fewest-step connection

examChoose the correct two-step count from values produced by direct, entrywise and three-step readings

Questions about this topic

Why does C squared count two-step routes?+

For a selected start and end, each term in the row-by-column product chooses one intermediate vertex. The product counts the two connections through that vertex, and adding the terms counts all such routes

What does a leading-diagonal entry of C squared mean?+

It counts routes that start and end at that vertex after exactly two connections. Vertices or connections may be revisited, and a loop can make the intermediate vertex the starting vertex. It does not count a single direct connection by itself

Why can a two-step entry be greater than 1?+

Different intermediate vertices can give different routes. Parallel direct connections also create separate routes, so a connection matrix records their multiplicity

Can I use a calculator?+

No. This topic is practised without a calculator

Which year level and chapter is this?+

Year 12, VCE Units 3 & 4, General Mathematics, chapter 10: Matrices

In this chapter

State the order of a matrix and locate its elements Identify row, column, square, symmetric and zero matrices Read information from a labelled data matrix Read, transpose and classify a matrix Construct a matrix from labelled information or an entry rule 10A Matrix notation, types and construction: Solve a matrix equation 10A Matrix notation, types and construction: Construct, apply and invert a permutation matrix Add and subtract matrices Find unknown entries in a matrix equation Multiply a matrix by a scalar Combine scalar multiples of matrices 10B Linear operations on matrices: Determine whether an inverse exists and calculate it Decide whether a matrix product is defined and give its order Multiply matrices Evaluate powers of a square matrix Identify and construct the identity matrix 10C Matrix products, powers and permutations: Construct, apply and invert a permutation matrix Find the determinant of a 2 × 2 matrix Find the inverse of a 2 × 2 matrix Write simultaneous equations as a matrix equation Solve simultaneous equations using the inverse matrix 10D Determinants, inverses and matrix equations: Determine whether an inverse exists and calculate it 10D Determinants, inverses and matrix equations: Solve a matrix equation Use matrix multiplication to answer an application question Use row and column matrices of ones to extract totals Represent a network in a matrix Identify the network a connection matrix describes Interpret connection sums and symmetry Count routes using powers of a connection matrix Construct and analyse relation matrices