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 to count the ways one person can send a message to another through exactly one other person.
- Use 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 . Each row is a sender and each column is a receiver, in the same order (Ana, Ben, Chloe, Dev). Write if the sender can message the receiver directly and if not:
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 , 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 is a communication matrix, then element of is the number of ways person can send a message to person through exactly one other person.
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 is row Ana of times column Dev of :
Each product checks one possible go-between: "can Ana reach them, and can they reach Dev?" A product is 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
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 , with the rows and columns in the order Ana, Ben, Chloe, Dev.
(b) Calculate .
(c) In how many ways can Chloe send a message to Ben through exactly one other person? Who passes it on?
Step 1: Write the communication matrix
Rows are senders, columns are receivers; 1 for a direct link:
Step 2: Square it
Multiply row by column. For example, row Chloe × column Ben is .
Each product in row Chloe × column Ben tests one go-between: "Chloe → them" times "them → Ben". The two 1 × 1 terms are Ana and Dev.
Step 3: Read the answer
Row Chloe (row 3), column Ben (column 2) of is . Chloe can get a message to Ben through one other person in 2 ways: Chloe → Ana → Ben and Chloe → Dev → Ben.
Try it yourself first, then check the working one step at a time.
Answer
(a) as above. (b) . (c) 2 ways: through Ana or through Dev.
Method
Rows are senders, columns are receivers; 1 for a direct link, 0 otherwise.
Square the matrix.
Read element (sender, receiver) of 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 , which just gives again.
Set to see , and for messages through exactly two other people. Find (Dev, Ana): it is in and in . When does it first become positive?
For this network,
Which person cannot get a message to Ana in one or two steps?
Common mistake
The diagonal of C²
The diagonal of is not always zero. Element (Ana, Ana) of is , 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 from the first lesson (towns A, B, C, D, with two roads between B and C), element of counts the routes from town to town that pass through exactly one other town:
Element (B, D) of is : you can drive B → C → D on either of the two roads from B to C. counts routes with exactly three roads, through two other towns.
Worked example
Who should start the phone tree?
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.
Step 1: Write the communication matrix
Order Priya, Quinn, Rosa, Sam, Tom; rows send, columns receive:
Step 2: Square it with technology
Step 3: Add to count one or two steps
An element of that is not 0 means the sender can reach that receiver directly or through one other person.
Step 4: Find the rows with no zeros off the diagonal
Ignoring the diagonal: Priya's row is and Sam's row is — no zeros. Quinn cannot reach Rosa, Rosa cannot reach Priya, and Tom cannot reach Quinn or Rosa in two steps.
So only Priya or Sam could start the phone tree.
Step 5: Recommend one
Priya's row adds to 5 and Sam's to 4, so Priya's message has more routes (two different ways to reach Quinn). If one call fails, her message is a little more likely to get through, so Priya is the better choice. Either meets the two-step requirement.
Try it yourself first, then check the working one step at a time.
Answer
Only Priya and Sam can reach every other member in at most two steps (their rows of have no zeros off the diagonal). Priya is recommended because her message has the most routes.
Method
Write the communication matrix from the diagram.
Use technology for , then find .
A row with no zeros off the diagonal reaches everyone in one or two steps.
Use the numbers of routes to compare the options and justify a choice.
Watch out for
Using only : 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 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; means a direct link.
Element of counts the ways can send a message to through exactly one other person.
counts the ways in one or two steps. A off the diagonal means "cannot reach in two steps".
For road networks, counts routes through exactly one other town and routes through two.
Ignore the diagonal of 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.