Adjacency Matrices Revision Notes for Leaving Cert Applied Maths

Adjacency Matrices

What is a matrix?

A matrix is a rectangular arrangement of numbers organised in rows and columns. Think of it like a table of data that mathematicians use to solve problems. These numerical arrays are particularly useful in computer science for storing and processing information.

infoNote

Matrices are fundamental structures in mathematics and computer science, providing a systematic way to organise and manipulate data in rows and columns.

The dimensions of a matrix are described as $m \times n$ , where:

$m$ = number of rows (horizontal lines)
$n$ = number of columns (vertical lines)

For example, a matrix with 2 rows and 3 columns would be called a $2 \times 3$ matrix.

What is an adjacency matrix?

An adjacency matrix is a special type of square matrix that represents the connections in a graph or network. It shows how many direct connections (edges) exist between different points (vertices or nodes) in the network.

In an adjacency matrix:

Each row and column represents a vertex in the graph
The numbers in the matrix show whether vertices are connected
For simple graphs: 1 means connected, 0 means not connected
For graphs with multiple edges: the number shows how many connections exist

chatImportant

The adjacency matrix shown above demonstrates how a graph with 6 vertices (A through F) can be represented mathematically. Notice that this is a $6 \times 6$ square matrix because there are 6 vertices in the graph.

Reading adjacency matrices

When reading matrices, we follow the "Lawn Tennis" rule - we read from left to top. This means:

Each row shows the connections FROM that vertex
Each column shows the connections TO that vertex
The entry in row $i$ , column $j$ tells us about connections between vertex $i$ and vertex $j$

chatImportant

Key properties of adjacency matrices:

They are always square matrices (same number of rows and columns)
For undirected graphs, they are symmetrical about the main diagonal
The main diagonal typically contains zeros (no self-loops) unless specified otherwise

Powers of adjacency matrices

One of the most powerful features of adjacency matrices is that their powers reveal important information about paths in the graph.

chatImportant

Key concept: If $A$ is an adjacency matrix, then $A^n$ gives the number of walks of length $n$ between vertices.

This diagram shows $A^3$ (A cubed), which counts all possible walks of exactly 3 steps between vertices.

lightbulbExample

Understanding $A^3$ Results:

There are 2 walks of length 3 between nodes A and B
There are 0 walks of length 3 between nodes D and B
There are 5 walks of length 3 between nodes D and F

Working with matrix powers

Let's look at a practical example using a simple network:

For this network with vertices P, Q, and R, we can:

Create the adjacency matrix $M$
Calculate $M^2$ to find walks of length 2
Calculate $M^3$ to find walks of length 3

lightbulbExample

Practical Matrix Power Applications:

$M^2$ shows indirect connections (2-step paths)
$M^3$ shows 3-step paths
Higher powers reveal longer routes through the network

Matrix operations basics

When working with adjacency matrices, you need to understand basic matrix operations:

infoNote

Matrix Operations:

Adding matrices: Add corresponding entries together
Multiplying matrices: Use the row-by-column method (more complex process)

chatImportant

Matrix multiplication is not commutative, meaning $AB \neq BA$ in general.

Practical applications

Adjacency matrices are used in:

Computer networks: Mapping connections between devices
Social networks: Showing relationships between people
Transportation: Planning routes and finding shortest paths
Internet routing: Determining how data packets travel

Exam tips

bookmarkSummary

Essential Exam Strategies:

Always check your matrix dimensions match the number of vertices
Remember that adjacency matrices for undirected graphs are symmetrical
Use the power property ( $A^n$ ) to count walks of specific lengths
Practice reading matrices using the "left to top" rule
When multiplying matrices, work systematically row by row

Remember!

bookmarkSummary

Key Points to Remember:

A matrix is a rectangular array of numbers used to organise data systematically
Adjacency matrices represent graph connections using 1s and 0s (or actual connection counts)
Read matrices "left to top" - each row shows connections from that vertex
$A^n$ counts walks of length $n$ between vertices in the graph
Adjacency matrices are always square and symmetrical for undirected graphs

Adjacency Matrices (Leaving Cert Applied Maths): Revision Notes