Using Matrices to Model Road and Communication Networks Revision Notes for VCE SSCE General Mathematics

Using Matrices to Model Road and Communication Networks

What is a network?

A network consists of objects that are connected together. Common examples include:

Towns connected by roads
People connected through friendships or communication
Computer systems connected by cables or wireless links

infoNote

Networks are represented visually using network diagrams, where objects are shown as points called vertices and connections between them are shown as lines called edges.

For example, in a road network, each town is a vertex and each road is an edge connecting two vertices.

Representing road connections using matrices

Matrices provide a powerful way to record and analyse connections in a network. Each element in the matrix shows the number of direct connections between two objects.

Building a connection matrix

Let's work through how to create a connection matrix for a road network.

Consider a network showing road connections between three towns: $A$ , $B$ , and $C$ .

To create a matrix representing these connections:

Step 1: Create a square matrix with rows and columns equal to the number of towns (or objects). For three towns, we need a $3 \times 3$ matrix.

Step 2: Label the rows and columns with the names of the towns.

Step 3: Fill in the matrix elements by counting direct connections:

Use $0$ if there is no direct connection between two towns
Use $1$ if there is one direct road connection
Use $2$ (or higher) if there are multiple direct roads

infoNote

The diagonal elements (where row equals column) are typically $0$ because a town doesn't have a road to itself. If there were a loop road from a town back to itself, we would enter $1$ for that diagonal element.

Worked example: three towns

lightbulbExample

Worked Example: Building a Connection Matrix for Three Towns

Let's examine the complete process for towns $A$ , $B$ , and $C$ :

Starting with an empty $3 \times 3$ matrix with zeros on the diagonal:

$\begin{bmatrix} A & B & C \\ 0 & & \\ & 0 & \\ & & 0 \end{bmatrix}$

The diagonal contains zeros (town $A$ to $A$ , town $B$ to $B$ , town $C$ to $C$ ).

From the network diagram:

There is one road connecting $A$ and $B$ , so we enter $1$ in row $A$ , column $B$ and in row $B$ , column $A$
There are no roads connecting $A$ and $C$ , so we enter $0$ in row $A$ , column $C$ and row $C$ , column $A$
There are two roads connecting $B$ and $C$ , so we enter $2$ in row $B$ , column $C$ and row $C$ , column $B$

The completed matrix is:

$\begin{bmatrix} A & B & C \\ 0 & 1 & 0 \\ 1 & 0 & 2 \\ 0 & 2 & 0 \end{bmatrix}$

Interpreting column and row sums

The sum of elements in a column (or row) tells us the total number of direct road connections to that town.

For example, summing column $B$ : $1 + 0 + 2 = 3$

This means town $B$ has three direct road connections to other towns.

Practice example: four towns

For a network with four towns ( $A$ , $B$ , $C$ , $D$ ), you would create a $4 \times 4$ matrix following the same process. The sum of column $D$ would tell you how many roads connect directly to town $D$ .

Social networks and communication matrices

A social network models connections between people. In these networks:

Vertices represent individuals
Edges represent communication links between people

A line between two people in the diagram means they can communicate directly. This is represented by $1$ in the matrix. No line (and therefore $0$ in the matrix) means they cannot communicate directly.

One-step and two-step communication

One-step communication link: When two people communicate directly with each other. For example, if Vicki talks directly to Steven, this is a one-step link.

Two-step communication link: When two people communicate indirectly through a third person. For example, if Vicki wants to send a message to Paul but doesn't communicate with him directly, she could send it via Steven or Kathy.

Creating a communication matrix

Consider a social network with four people: Vicki, Steven, Kathy, and Paul.

To build the communication matrix:

Create a $4 \times 4$ square matrix
Label rows and columns with the first letter of each name ( $V$ , $S$ , $K$ , $P$ )
Enter $1$ where two people communicate directly
Enter $0$ where there is no direct communication
Enter $0$ on the diagonal (people don't communicate with themselves in one step)

Symmetry in communication matrices

chatImportant

Communication matrices are symmetric. This happens because communication is typically two-way. If Vicki communicates with Steven, then Steven communicates with Vicki. The matrix reflects this symmetry: the value in row $V$ , column $S$ equals the value in row $S$ , column $V$ .

Finding multi-step communications

To find two-step communication paths, we multiply the matrix by itself (square the matrix).

If $N$ is the communication matrix, then $N^2$ shows all two-step communications.

lightbulbExample

Worked Example: Finding Two-Step Communications

For the Vicki, Steven, Kathy, Paul example:

$N^2 = \begin{bmatrix} V & S & K & P \\ 2 & 1 & 1 & 2 \\ 1 & 3 & 2 & 1 \\ 1 & 2 & 3 & 1 \\ 2 & 1 & 1 & 2 \end{bmatrix}$

Reading from column $K$ (Kathy) to row $S$ (Steven), the value $2$ tells us there are two different two-step ways for Kathy to communicate with Steven:

Kathy $\to$ Vicki $\to$ Steven
Kathy $\to$ Paul $\to$ Steven

Understanding diagonal elements in $N^2$

In the $N^2$ matrix, diagonal elements show how many two-step ways a person can "communicate with themselves" through another person.

For example, if the value at row $S$ , column $S$ is $3$ , this means there are three two-step paths:

Steven $\to$ Vicki $\to$ Steven
Steven $\to$ Kathy $\to$ Steven
Steven $\to$ Paul $\to$ Steven

A practical interpretation: Steven could ring Vicki and ask her to ring him back later to remind him of an appointment.

Higher-order communications

Following the same pattern:

$N^3$ shows three-step communications (via two intermediaries)
$N^4$ shows four-step communications (via three intermediaries)

This matrix method can be applied to analyse friendships, travel routes between towns, and other two-way connections.

Key properties of connection matrices

chatImportant

Connection matrices are always square: If you have $n$ objects (towns, people, etc.), you need an $n \times n$ matrix.

Reading the matrix: To find connections from object $X$ to object $Y$ , look at row $X$ , column $Y$ .

Column/row sums: Adding all elements in a column (or row) gives the total number of direct connections for that object.

Symmetry: For two-way connections (like roads or mutual friendships), the matrix is symmetric - the value at row $i$ , column $j$ equals the value at row $j$ , column $i$ .

Remember!

bookmarkSummary

Key Points to Remember:

Networks consist of vertices (objects/points) and edges (connections/lines) that can be represented using matrices
In a connection matrix, each element shows the number of direct connections between two objects
For road networks, the matrix element indicates the number of direct roads between towns
For social networks, $1$ indicates direct communication and $0$ indicates no direct communication
Squaring the matrix ( $N^2$ ) reveals all two-step connections through one intermediary
Connection matrices are always square matrices with dimensions matching the number of objects
Column or row sums tell you the total number of direct connections for a particular object

Using Matrices to Model Road and Communication Networks (VCE SSCE General Mathematics): Revision Notes