Case Study 2 — Traffic Flow: Reading a City's Streets Off the Pivots

DataField.Dev

Case Study 2 — Traffic Flow: Reading a City's Streets Off the Pivots

A city traffic engineer has a problem you can state in one sentence: sensors count cars entering and leaving a downtown grid, but only some street segments have sensors, and the budget won't cover instrumenting every block. Can the missing flows be deduced from the measured ones? Often, yes — and the tool is Gaussian elimination. A road network is a system of linear equations in disguise, and this case study shows how reducing that system reveals not just the unknown traffic volumes but the structure of what the sensors can and cannot determine. It is a clean, real demonstration of the infinite-solution case from §4.6, with a free variable that has a concrete meaning the engineer can act on.

Conservation of cars is a linear system

Consider a small one-way grid: four intersections — call them $A$, $B$, $C$, $D$ — connected in a loop by four internal street segments, with cars also entering and leaving the grid from outside at each intersection. Let the unknown flows on the internal segments (in cars per hour) be:

$x_1$ — flow from $A$ to $B$,
$x_2$ — flow from $B$ to $C$,
$x_3$ — flow from $C$ to $D$,
$x_4$ — flow from $D$ back to $A$.

The governing principle is the same conservation law that ruled the chemistry case study, now applied to vehicles: at every intersection, the flow in equals the flow out — no cars pile up or vanish at a corner. Suppose the external (sensor-measured) flows give, at each node, the following balances after rearranging "in = out":

$$\begin{array}{lll} \text{Node } A: & x_1 - x_4 = 100 & (\text{net } 100 \text{ more leaves toward } B \text{ than arrives from } D)\\ \text{Node } B: & x_1 - x_2 = 50 \\ \text{Node } C: & x_2 - x_3 = -100 \\ \text{Node } D: & x_3 - x_4 = 150. \end{array}$$

Four equations, four unknowns. Writing it as an augmented matrix with variable order $(x_1, x_2, x_3, x_4)$:

$$\left[\begin{array}{cccc|c} 1 & 0 & 0 & -1 & 100 \\ 1 & -1 & 0 & 0 & 50 \\ 0 & 1 & -1 & 0 & -100 \\ 0 & 0 & 1 & -1 & 150 \end{array}\right].$$

You might expect four equations in four unknowns to pin down a unique answer. They do not — and the reason they do not is the interesting part, which row reduction will expose.

Row-reducing the network

Forward-eliminate. The first pivot is the leading $1$ in row 1; clear the $1$ beneath it in row 2 with $R_2 \leftarrow R_2 - R_1$:

$$\left[\begin{array}{cccc|c} 1 & 0 & 0 & -1 & 100 \\ 0 & -1 & 0 & 1 & -50 \\ 0 & 1 & -1 & 0 & -100 \\ 0 & 0 & 1 & -1 & 150 \end{array}\right].$$

The second pivot is the $-1$ in row 2; clear the $1$ beneath it in row 3 with $R_3 \leftarrow R_3 + R_2$:

$$\left[\begin{array}{cccc|c} 1 & 0 & 0 & -1 & 100 \\ 0 & -1 & 0 & 1 & -50 \\ 0 & 0 & -1 & 1 & -150 \\ 0 & 0 & 1 & -1 & 150 \end{array}\right].$$

The third pivot is the $-1$ in row 3; clear the $1$ beneath it with $R_4 \leftarrow R_4 + R_3$:

$$\left[\begin{array}{cccc|c} 1 & 0 & 0 & -1 & 100 \\ 0 & -1 & 0 & 1 & -50 \\ 0 & 0 & -1 & 1 & -150 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right].$$

There it is: the fourth row vanished completely — $0 = 0$. Cleaning up to reduced row echelon form (scale rows 2 and 3 by $-1$, which already clears above since the pivot columns are otherwise empty) gives

$$\left[\begin{array}{cccc|c} 1 & 0 & 0 & -1 & 100 \\ 0 & 1 & 0 & -1 & 50 \\ 0 & 0 & 1 & -1 & 150 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right].$$

Pivots in columns $1, 2, 3$; column $4$ has no pivot, so $x_4$ is the free variable. The system has infinitely many solutions, parametrized by $x_4$. Let's verify and read off the answer.

# Reduce the traffic system and confirm the free-variable structure.
import numpy as np
A = np.array([[1,  0,  0, -1],
              [1, -1,  0,  0],
              [0,  1, -1,  0],
              [0,  0,  1, -1]], dtype=float)
b = np.array([100, 50, -100, 150], dtype=float)
print(np.linalg.matrix_rank(A))                          # 3
print(np.linalg.matrix_rank(np.column_stack([A, b])))    # 3  -> consistent
# general solution: set x4 = t, then x1=100+t, x2=50+t, x3=150+t
for t in (0.0, 50.0, 200.0):
    x = np.array([100 + t, 50 + t, 150 + t, t])
    print(t, A @ x)        # always [ 100.  50. -100. 150.] == b

The rank of both the coefficient matrix and the augmented matrix is $3$, not $4$ — so the system is consistent with one free variable. Reading the reduced rows, the complete solution is

$$x_1 = 100 + x_4,\qquad x_2 = 50 + x_4,\qquad x_3 = 150 + x_4,\qquad x_4 \text{ free},$$

or in the parametric vector form of §4.6, with $t = x_4$:

$$\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \begin{bmatrix} 100 \\ 50 \\ 150 \\ 0 \end{bmatrix} + t\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \qquad t \geq 0.$$

Why one equation was redundant — and what the free variable means

The vanished row was not an accident or a measurement error. The four node equations are linearly dependent: if you add up the net outflows over all intersections, every internal street is counted once as an outflow (from one node) and once as an inflow (to the next), so the four equations must sum to a statement about external flows alone. Concretely, $(x_1 - x_4) = (x_1 - x_2) + (x_2 - x_3) + (x_3 - x_4)$ — the first equation is the sum of the other three. One node's balance is always implied by the rest, so there are really only three independent constraints on four unknowns. Row reduction discovered this automatically by collapsing the fourth row to zero. (This redundancy is general: in any flow network, the conservation equations sum to a single global balance, which is why one node equation is always dependent.)

The free variable $x_4$ has a vivid physical meaning. Look at the direction vector $(1,1,1,1)$: it says you can add the same amount of flow to every internal segment and still satisfy conservation at every node. That is a circulating loop of traffic — cars going around the block $A \to B \to C \to D \to A$ — which enters and leaves no intersection on net, so it is invisible to the external sensors. The sensors fix the differences between segment flows but cannot see this overall circulation. The engineer has learned something precise: with only external counts, the network is determined up to one unknown — the loop flow.

From infinite possibilities to a single answer

Infinitely many solutions is not a dead end; it is a to-do list. To pin down the network, the engineer needs one more independent measurement — a sensor on any single internal segment. Say a sensor on the $D \to A$ segment reads $x_4 = 120$ cars/hour. Substituting fixes everything:

$$x_1 = 220,\qquad x_2 = 170,\qquad x_3 = 270,\qquad x_4 = 120.$$

# One internal sensor (x4 = 120) collapses the line to a single point.
import numpy as np
A = np.array([[1,0,0,-1],[1,-1,0,0],[0,1,-1,0],[0,0,1,-1]], dtype=float)
x = np.array([220, 170, 270, 120], dtype=float)   # using x4 = 120
print(A @ x)        # [ 100.  50. -100. 150.]  -> still satisfies every node

A single extra reading turned a one-parameter family into the one true traffic state — the geometric picture of a line being intersected by one more constraint to give a point. And even before that extra sensor, the reduced system is useful: the requirement that all flows be nonnegative (you can't have negative cars on a one-way street) forces $t = x_4 \geq 0$ and $x_2 = 50 + t \geq 0$, etc., so the engineer already knows every segment carries at least its baseline flow $(100, 50, 150, 0)$ and that the loop flow can only add traffic. Row reduction has converted a vague "we don't have enough sensors" into an exact accounting of what is known, what is free, and what one more measurement would buy.

What you should take away

A street map became a matrix the moment we wrote "flow in = flow out" at each corner, and Gaussian elimination did three things at once: it found the relationships among the unknown flows, it detected the redundant equation by collapsing a row to zero, and it identified the single genuine degree of freedom — the circulating loop — through the free variable. None of that required guessing; it fell out of the pivots.

This is the infinite-solution case of §4.6 with stakes attached. The same parametric solution form — a particular solution plus multiples of a direction vector — that described a line through space here describes "every traffic pattern consistent with the sensors," and the direction vector $(1,1,1,1)$ is the network's hidden loop. When you study the null space in Chapter 13, you will recognize that loop as a null-space vector of the flow matrix, and the count "one free variable" as the nullity. Whether the network is four downtown blocks or a continental power grid, the lesson is identical: reduce the conservation system, read the pivots, and the structure of what you can know reveals itself.

Forward references: free variables and parametric solutions (Chapter 6); the null space as the set of "invisible" flows (Chapter 13); rank, dependence, and the dimension of the solution set (Chapter 14); networks and graphs as matrices recur in the PageRank chapter (Chapter 29).