Lesson 7 of 7 · 18 min

Communication and road networks

Write the matrix of a communication or road network and square it to count the ways to send a message through a third person or travel through one other town.

What you will be able to do

  • Write the matrix of a one-way (directed) communication network, rows for senders and columns for receivers.
  • Use A2A^2 to count the ways one person can send a message to another through exactly one other person.
  • Use A+A2A + A^2 to decide who can reach whom in one or two steps.
  • Use powers of a road network matrix to count routes through other towns.

Four friends — Ana, Ben, Chloe and Dev — are in a group project. Not everyone has everyone's number, so some can message others directly and some cannot. The arrows show who can send a message to whom. An arrow from Ana to Ben means Ana can message Ben, but not necessarily the other way.

Who can message whom. Ana and Chloe can message each other; every other link is one way.

Record the network in a communication matrix CC. Each row is a sender and each column is a receiver, in the same order (Ana, Ben, Chloe, Dev). Write 11 if the sender can message the receiver directly and 00 if not:

C=[0110001010010100]C = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{bmatrix}

Row 1 says Ana can message Ben and Chloe. The leading diagonal is all 0s because nobody messages themselves. Unlike a road network, this matrix is not symmetric: Ana can message Ben, but Ben cannot message Ana.

Using matrix CC, how many people can Chloe message directly?

Ana cannot message Dev directly, but she can message Chloe, who can pass it on to Dev. That is a two-step message, passed through a third person. Counting two-step messages by eye is fine for four people, but slow for twenty. Squaring the matrix counts them all at once.

Key idea

Squaring a communication matrix

If CC is a communication matrix, then element (i,j)(i, j) of C2C^2 is the number of ways person ii can send a message to person jj through exactly one other person.

C+C2C + C^2 counts the ways in one or two steps: directly, or through one other person.

Why does squaring count two-step messages?

Element (Ana, Dev) of C2C^2 is row Ana of CC times column Dev of CC:

0⏟A→A×0⏟A→D+1⏟A→B×0⏟B→D+1⏟A→C×1⏟C→D+0⏟A→D×0⏟D→D=1\underbrace{0}_{\mathrm{A} \to \mathrm{A}} \times \underbrace{0}_{\mathrm{A} \to \mathrm{D}} + \underbrace{1}_{\mathrm{A} \to \mathrm{B}} \times \underbrace{0}_{\mathrm{B} \to \mathrm{D}} + \underbrace{1}_{\mathrm{A} \to \mathrm{C}} \times \underbrace{1}_{\mathrm{C} \to \mathrm{D}} + \underbrace{0}_{\mathrm{A} \to \mathrm{D}} \times \underbrace{0}_{\mathrm{D} \to \mathrm{D}} = 1

Each product checks one possible go-between: "can Ana reach them, and can they reach Dev?" A product is 11 only when both links exist. Adding the products counts the go-betweens that work — here only Chloe.

Worked example

Count messages sent through a third person

  • Complex familiar

In a group of four friends, Ana can message Ben and Chloe; Ben can message Chloe; Chloe can message Ana and Dev; and Dev can message Ben.

(a) Write the communication matrix CC, with the rows and columns in the order Ana, Ben, Chloe, Dev.

(b) Calculate C2C^2.

(c) In how many ways can Chloe send a message to Ben through exactly one other person? Who passes it on?

3 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Rows are senders, columns are receivers; 1 for a direct link, 0 otherwise.

  2. Square the matrix.

  3. Read element (sender, receiver) of C2C^2 for messages through exactly one other person.

Watch out for

  • Reading column Chloe, row Ben instead — that counts messages from Ben to Chloe.

  • Squaring each element of CC, which just gives CC again.

Interactive

Powers of the communication matrix

Set n=2n = 2 to see C2C^2, and n=3n = 3 for messages through exactly two other people. Find (Dev, Ana): it is 00 in CC and in C2C^2. When does it first become positive?

For this network,

C+C2=[1121101112110110]C + C^2 = \begin{bmatrix} 1 & 1 & 2 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 2 & 1 & 1 \\ 0 & 1 & 1 & 0 \end{bmatrix}

Which person cannot get a message to Ana in one or two steps?

Choose one answer

Common mistake

The diagonal of C²

The diagonal of C2C^2 is not always zero. Element (Ana, Ana) of C2C^2 is 11, because Ana → Chloe → Ana is a two-step message from Ana back to herself. These are rarely useful. When a question asks about pairs of different people, ignore the diagonal.

The same idea works for road networks. In the road network matrix NN from the first lesson (towns A, B, C, D, with two roads between B and C), element (i,j)(i, j) of N2N^2 counts the routes from town ii to town jj that pass through exactly one other town:

N=[0110102012010010]N2=[2221251221601201]N = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 2 & 0 \\ 1 & 2 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \qquad N^2 = \begin{bmatrix} 2 & 2 & 2 & 1 \\ 2 & 5 & 1 & 2 \\ 2 & 1 & 6 & 0 \\ 1 & 2 & 0 & 1 \end{bmatrix}

Element (B, D) of N2N^2 is 22: you can drive B → C → D on either of the two roads from B to C. N3N^3 counts routes with exactly three roads, through two other towns.

Worked example

Who should start the phone tree?

  • Complex unfamiliar
  • Technology active

A sports club committee passes urgent news along a phone tree. The arrows show who has whose number.

The committee wants one person to start every message, so that it reaches all the other members in at most two steps. Use matrices to determine who could start the phone tree, and recommend one person.

Who can call whom on the committee.

5 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Write the communication matrix from the diagram.

  2. Use technology for K2K^2, then find K+K2K + K^2.

  3. A row with no zeros off the diagonal reaches everyone in one or two steps.

  4. Use the numbers of routes to compare the options and justify a choice.

Watch out for

  • Using only K2K^2: it misses direct calls, so Priya → Quinn would look like it needs a go-between.

  • Reading columns instead of rows: columns show who can reach a person, not who that person can reach.

Exam tip

In the exam

Say which matrix you used and why: "Element (Chloe, Ben) of C2C^2 is 2, so Chloe can send a message to Ben through a third person in 2 ways." Then name the go-betweens if the network is small enough to check: "through Ana or through Dev".

Summary

  • In a communication matrix, rows are senders and columns are receivers; 11 means a direct link.

  • Element (i,j)(i, j) of C2C^2 counts the ways ii can send a message to jj through exactly one other person.

  • C+C2C + C^2 counts the ways in one or two steps. A 00 off the diagonal means "cannot reach in two steps".

  • For road networks, N2N^2 counts routes through exactly one other town and N3N^3 routes through two.

  • Ignore the diagonal of C2C^2 for questions about pairs of different people.

Finished the lesson?

Try the 2 quick checks above and the lesson completes itself, or mark it complete now.

Lesson 7 of 70% read

Save your progress with a free account