Route Planning and Matrices: Applied Math for Grade 11

Quick answer: Draw four towns with roads between them, write the adjacency matrix, and square it. Each entry of the squared matrix counts the walks of length two between two towns. Students can verify every number by tracing routes on the drawing, which is the rare case where matrix multiplication has a meaning they can check themselves.

What does the opening example look like?

Four towns, labeled A, B, C and D. Roads connect A to B, A to C, B to C, and C to D. Draw it once on the board and leave it up for the whole lesson.

The adjacency matrix M lists towns in the order A, B, C, D across the columns and down the rows. Entry (i, j) is 1 if there is a road, 0 if not. Roads run both ways, so the matrix is symmetric and the diagonal is all zeros.

Row A reads 0, 1, 1, 0. Row B reads 1, 0, 1, 0. Row C reads 1, 1, 0, 1. Row D reads 0, 0, 1, 0.

Ask what the row sums tell you before moving on. Row A sums to 2, row C sums to 3, row D sums to 1. Those are the number of roads leaving each town, the degree of each vertex. Students who see that connection accept the matrix as a description of the picture rather than an unrelated grid of numbers.

Why does squaring the matrix count two-step routes?

Entry (A, D) of M squared is the sum over all towns X of M(A, X) times M(X, D). Each product is 1 only when there is a road from A to X and a road from X to D, so the sum counts exactly the intermediate towns that complete a two-step route. That sentence is the proof, and it is short enough to put on the board.

Compute it with the class. M squared comes out as: row A is 2, 1, 1, 1. Row B is 1, 2, 1, 1. Row C is 1, 1, 3, 0. Row D is 1, 1, 0, 1.

Now verify by hand from the drawing. Entry (A, D) is 1, and the only two-step route is A to C to D. Entry (C, D) is 0, because a route C to X to D needs X adjacent to both, and D's only neighbor is C, which is not adjacent to itself. Entry (C, C) is 3, because C has three neighbors and each gives one there-and-back walk of length two. Entry (A, A) is 2 for the same reason.

Two warnings worth stating aloud. These are walks, not paths, so going out and back counts. And the diagonal of M squared is always the degree sequence for an undirected graph with no loops, which makes a fast check that a student's arithmetic is right.

How do you get from counting routes to finding the shortest one?

Add weights to the same drawing. Distances in kilometers: A to B is 4, A to C is 2, B to C is 1, C to D is 5. Now the matrix holds distances instead of ones, with a blank or infinity where no road exists.

The first question is deliberately provocative. What is the shortest route from A to B. Students say 4, because there is a direct road. But A to C to B costs 2 plus 1, which is 3. The direct road is not the shortest route, and that single fact justifies the rest of the topic.

Then run Dijkstra's algorithm by hand, keeping a table of tentative distances. Start at A with tentative distances C equals 2 and B equals 4. Settle C at 2, which improves B to 2 plus 1 equals 3 and sets D to 2 plus 5 equals 7. Settle B at 3, which offers no improvement to D because there is no B to D road in this graph. Settle D at 7. The shortest route from A to D is A, C, D at 7 kilometers.

Keep the table visible and cross off settled towns as you go. The habit of settling the smallest tentative distance and never revisiting it is the whole algorithm, and students who write it as a table get it right far more often than students who work on the diagram.

How do you differentiate?

Approaching: give the adjacency matrix already written and ask only for M squared for a three-town graph, then verification against the picture. Three-by-three multiplication by hand is achievable and the meaning is identical.

On level: the four-town example above, built from the drawing by the student, squared, verified, then the weighted shortest path with a table you provide.

Above level: a directed graph, where the matrix is no longer symmetric and one-way streets change the answer. Then ask for M cubed and what it counts, and whether a zero entry in M plus M squared plus M cubed proves two towns are unreachable within three steps. Students confident with coordinates and vectors can extend the same work into geometry, which is where Vectors: Basics and Calculation picks up.

What goes wrong?

Row and column confusion. Half the class will multiply row by row. Have them physically trace with two fingers, one moving across the row and one moving down the column, for the first four entries. It looks childish and it fixes the error.

Arithmetic drift. Six-town graphs produce thirty-six multiply-and-add operations per matrix, and errors compound silently. Stay at four towns for the hand calculation and move to a bigger graph only once students know what the answer should look like.

The word graph. Students hear graph and think of axes. Say vertex and edge from the first minute, and use network when speaking casually.

Frequently asked questions

Do students need matrix multiplication beforehand?

One prior lesson on the mechanics is enough. This unit gives the mechanics a purpose, which is a better order than teaching the rule and applying it a month later.

Is Dijkstra's algorithm on the syllabus?

It varies by state and board. Even where it is not, it is defensible as an application of systematic reasoning and students remember it.

How long is the unit?

Four to five periods: matrices from diagrams, squaring and interpretation, weighted graphs, shortest path, and one assessment task.

Can this be done without technology?

Entirely. Four towns and a pencil is the whole equipment list. Spreadsheets are useful only for the extension to larger networks.

Related posts

• Statistics With Real Data: Sports, Weather, Prices
• Probability Experiments Students Can Run in One Period
• Debugging as a Thinking Skill: Unplugged Activities