Linear systems in use: networks, chemical equations, fitting curves

When you reach for it

Reach for a linear system whenever a situation is described by quantities that must add up: cars into a corner equal cars out, atoms of each element before a reaction equal atoms after, and the height of a curve at each measured point equals the measurement. Each such requirement is one linear equation, and the whole situation is one system A\mathbf{x} = \mathbf{b}.

The work is in setting it up. Solving is already known: row reduce and write the answer as in Homogeneous systems and solutions in parametric vector form, one particular solution plus the homogeneous ones, \mathbf{x} = \mathbf{p} + \mathbf{v}_h. What is new is reading that answer back: a free variable is a real freedom in the network, the null space of a reaction is its set of balanced forms, and a unique solution is a curve the points pin down.

The procedure

Day 1: networks and chemical equations

Networks. A network is a set of junctions (nodes) joined by branches, with something flowing along each branch: cars, water, current. Give each branch an unknown flow x_1, x_2, \dots and a direction. The one law is conservation at each node: nothing is stored or created there, so

That is one linear equation per node, with the flows that enter or leave the network from outside as constants. Two features of the answer recur. First, in a connected network every branch leaves one node and enters another, so adding all the node equations cancels every unknown and leaves “total entering the network = total leaving it”. One node equation is therefore always a combination of the others: if the totals agree it reduces to 0 = 0, and if they do not, the system is inconsistent. Second, flow that runs around a closed loop enters and leaves every node equally, so it is invisible to the equations. Each independent loop shows up as a free variable, and the homogeneous solutions are exactly these circulations.

A one-way street cannot carry negative flow. That is an inequality, x_i \ge 0, not part of the linear system: solve the system first, then ask which values of the free variables keep every flow nonnegative.

Chemical equations. A reaction such as \mathrm{CO_2} + \mathrm{H_2O} \to \mathrm{C_6H_{12}O_6} + \mathrm{O_2} is balanced when each element has as many atoms on the left as on the right. Put an unknown coefficient x_i in front of each compound. Each element gives one equation, “atoms on the left = atoms on the right”, and moving everything to the left makes it homogeneous. So balancing means finding the null space of a matrix with one row per element and one column per compound, with a minus sign on the columns of the products.

The system is homogeneous, so it is always consistent, and when there are more compounds than elements it has nontrivial solutions automatically. In the usual case the null space is a line, \operatorname{span}\{\mathbf{v}\}: every balanced form is a multiple of one vector. The balanced equation chemists write is the multiple whose entries are positive whole numbers with no common factor. Positive, because the compounds stay on the sides they were written on; whole numbers, because the coefficients count molecules; and no common factor, because the equation records a ratio, and (12, 12, 2, 12) says nothing that (6, 6, 1, 6) does not.

Day 2: a polynomial through given points

Given points (x_1, y_1), \dots, (x_n, y_n), look for a polynomial

with p(x_i) = y_i for each i. The unknowns are the coefficients a_0, \dots, a_{n-1}, not x. Each x_i is a known number, so the condition p(x_i) = y_i reads

which is linear in the a’s even though p is not linear in x. The n conditions form a square system V\mathbf{a} = \mathbf{y} whose ith row is 1, x_i, x_i^2, \dots, x_i^{n-1}. This V is the Vandermonde matrix of the points. Other conditions that are linear in the coefficients join the system the same way; a required slope p'(x_0) = m, for instance, is the row 0, 1, 2x_0, 3x_0^2, \dots (Example 6).

Theorem. If x_1, \dots, x_n are distinct, then for any y_1, \dots, y_n there is exactly one polynomial of degree at most n - 1 with p(x_i) = y_i for every i.

Proof. First the homogeneous system. If V\mathbf{a} = \mathbf{0}, the polynomial with coefficients \mathbf{a} is 0 at the n distinct numbers x_1, \dots, x_n. A polynomial of degree at most n - 1 that is not the zero polynomial has at most n - 1 roots, since by the The remainder and factor theorems each root r contributes a factor x - r and the degrees of the factors add. So p is the zero polynomial and \mathbf{a} = \mathbf{0}. Since V\mathbf{a} = \mathbf{0} has only the trivial solution, there is no free variable, so all n columns of V have pivots. There are only n rows, so every row has a pivot, no row can reduce to 0 = c with c \neq 0, and V\mathbf{a} = \mathbf{y} is consistent for every \mathbf{y}. Its solution is unique because \mathbf{x} = \mathbf{p} + \mathbf{v}_h with \mathbf{v}_h = \mathbf{0} the only choice. \square

The same fact can be read from a number: the determinant of V is the product of all the differences x_j - x_i with i < j, which is nonzero exactly when the x_i are distinct. That formula is stated here without proof.

If two of the x_i are equal, two rows of V are equal and the theorem says nothing. Example 5 shows what happens then.

Worked examples

Boundaries

Networks need conservation. The node equations hold only if nothing is stored at a node; a parking garage at a corner breaks them. If the outside flows do not balance, the system has no solution. The equations never see flow around a closed loop, so outside counts alone cannot fix the flows in a network with a loop. Nonnegative flow on one-way branches is a separate inequality, applied after solving.

Balancing conserves atoms and nothing else. It says what ratio is consistent, not whether the reaction happens. For ions, charge must balance too, which is one more row. If the null space has dimension 2 or more, the compounds can take part in two independent reactions and no single balanced form exists; if no vector in the null space has all entries positive, the equation cannot be balanced as written.

One polynomial needs distinct x values and the right degree. With n distinct x values the degree-at-most-(n - 1) polynomial exists and is unique. Two equal x values give either no solution or a repeated condition (Example 5). Fewer coefficients than points (a line through three points) usually gives an inconsistent system; the best approximate answer is the subject of Least squares: the best approximate solution of Ax = b. More coefficients than conditions give infinitely many.

An exact fit can be a poor model. The polynomial passes through the points but may swing far from the data between them, and for many points the Vandermonde system is sensitive to rounding: small errors in the data can move the coefficients a great deal.

Where this goes next

The balanced forms of a reaction are the kernel of its element matrix, and the circulations of a network are the kernel of its node matrix. Fitting a polynomial is solving V\mathbf{a} = \mathbf{y} for a square V that is invertible exactly when the x_i are distinct, an instance of the The invertible matrix theorem, and its determinant makes that a single number to compute. The map from coefficients \mathbf{a} to values (p(x_1), \dots, p(x_n)) is a Linear transformation, which is why the problem is linear at all. When the data have more points than the model has coefficients, an exact fit is gone and Least squares: the best approximate solution of Ax = b finds the closest one.

Exercises

Day 1: networks

Exercises 1 to 3 use Csaba’s block from Example 1, with the same four one-way streets and new outside counts.

1. 500 cars an hour enter at P, 200 leave at Q, 100 enter at R and 400 leave at S. Find the general solution and the least flow on each street.
2. 300 enter at P, 400 leave at Q, 350 enter at R and 250 leave at S. Find the general solution, the least flow on each street, and which street could be closed.
3. 400 enter at P, 250 leave at Q, 300 enter at R and 400 leave at S. Show that no flows fit, and say why without row reducing.
4. In Gergo’s lab, one-way cooling pipes join junctions A, B, C, D, in liters per minute: x_1 from A to B, x_2 from B to C, x_3 from C to D, x_4 from D to A and x_5 from A to C. Water enters at A at 50 and leaves at B at 30, at C at 10 and at D at 10. Find the general solution in parametric vector form. If pipe x_4 is shut, what is the largest possible flow in pipe x_5?

Day 1: balancing chemical equations

Set up the homogeneous system, find its null space, and give the balanced equation.

5. x_1\,\mathrm{KClO_3} \to x_2\,\mathrm{KCl} + x_3\,\mathrm{O_2}
6. x_1\,\mathrm{Fe} + x_2\,\mathrm{O_2} \to x_3\,\mathrm{Fe_2O_3}
7. x_1\,\mathrm{C_2H_6} + x_2\,\mathrm{O_2} \to x_3\,\mathrm{CO_2} + x_4\,\mathrm{H_2O}
8. x_1\,\mathrm{Al} + x_2\,\mathrm{HCl} \to x_3\,\mathrm{AlCl_3} + x_4\,\mathrm{H_2}
9. x_1\,\mathrm{Cu} + x_2\,\mathrm{HNO_3} \to x_3\,\mathrm{Cu(NO_3)_2} + x_4\,\mathrm{NO} + x_5\,\mathrm{H_2O}

Day 2: polynomials through points

10. Find the quadratic through (-1, 8), (1, 2) and (2, 5).
11. Find the polynomial of degree at most 3 through (-1, 2), (0, 1), (1, 2) and (2, 11).
12. Find the polynomial of degree at most 3 through (1, 0), (2, 0), (3, 0) and (4, 6).
13. Is there a quadratic through (1, 1), (3, 5) and (3, 7)?
14. Find every quadratic through (0, 2) and (2, 6), as particular plus homogeneous.
15. Sirpa tries a second profile y = a_0 + a_1x + a_2x^2 + a_3x^3 that leaves the ground level, y(0) = 0 and y'(0) = 0, and passes through heights 0.5 meters at x = 2 and 2.4 meters at x = 4. Find it.
16. Is there a line y = a_0 + a_1x through (0, 1), (1, 3) and (2, 4)?

Reasoning

17. Explain why, in any connected network, the sum of all the node equations has no unknowns left in it, and what that says about the rank of the system.
18. Explain why a chemical equation with more compounds than elements always has a nonzero solution, and why that alone does not guarantee a balanced form with all coefficients positive.
19. Prove directly that two polynomials of degree at most n - 1 that agree at n distinct numbers are the same polynomial.
20. In Example 1, explain in terms of cars why adding (1, 1, 1, 1) to any solution gives another solution, and why no outside count could ever reveal t.
21. Explain why n points with distinct x values usually have no polynomial through them of degree less than n - 1, but infinitely many of degree at most n.