Two equations, and then two thousand

Solving two equations in two unknowns is school algebra, and solving two thousand equations in two thousand unknowns is a different activity entirely, which is what this subject exists to make possible.

This course assumes the material of Mathematical Foundations: manipulating algebraic expressions, functions and their graphs, coordinates in the plane, and enough trigonometry to read $\cos \theta$ and $\sin \theta$ off a unit circle. Nothing else is assumed. In particular, calculus is never used, and where a connection to it exists it is signposted and skippable.

What makes an equation linear

An equation is linear in the unknowns $x_1,x_2,\dots ,x_n$ when it can be written as

with the coefficients $a_i$ and the constant $b$ being fixed numbers. Every unknown appears to the first power, alone, multiplied only by a number. That rules out $x^2$, it rules out $xy$, and it rules out $\sin x$, $1/x$ and $\sqrt{x}$. Note that $3x+4y=12$ qualifies, and so does $0x+0y=0$, and so does $7x_1-2x_2+0x_3=-1$, where the missing unknown is present with coefficient zero.

This looks like a severe restriction, and it is worth being clear that it is one. Most equations that describe the world are not linear. What makes the restricted class worth an entire subject is a combination of three facts. Linear systems can actually be solved, exactly, by a procedure that always terminates. Many genuinely non-linear problems are linear when examined closely enough, which is why a bridge deflecting slightly under load, a circuit at small signal, and a chemical mixture at low concentration are all handled linearly. And problems that are hopelessly non-linear are usually attacked by solving a linear system repeatedly, which is what Newton's method, every finite element package and every step of training a neural network are doing underneath.

A system of linear equations is several of them at once, sharing their unknowns. A solution is an assignment of numbers to the unknowns that satisfies every equation simultaneously, not merely one of them. The entire difficulty is that word: simultaneously.

Two unknowns, and two lines

With two unknowns the whole situation is visible. The equation $2x+3y=7$ is satisfied by infinitely many pairs $(x,y)$, and plotted in the plane they form a straight line, which is why the equations are called linear in the first place. A second equation gives a second line. A solution of the system is a point on both lines, so solving the system means intersecting them.

Two distinct lines in a plane intersect in exactly one point unless they are parallel, in which case they meet nowhere, unless they are the same line, in which case they meet everywhere along it. Those are the only three possibilities, and no fourth case exists: two lines cannot meet in exactly two points. That fact is worth holding on to, because it survives intact into two thousand dimensions where nothing can be drawn.

Example. Solve $2x+3y=7$ and $4x-y=7$.

Multiply the second equation by $3$ to get $12x-3y=21$, and add it to the first, so that the $y$ terms cancel: $14x=28$, giving $x=2$. Substituting back into the second equation, $8-y=7$, so $y=1$. Check both original equations: $2(2)+3(1)=7$ and $4(2)-1=7$. The lines cross at $(2,1)$.

Now you. Solve $3x+2y=16$ and $x-y=2$.

Elimination

The method in that example, adding a multiple of one equation to another so that an unknown vanishes, is the whole of it. Scaled up and made systematic it is called Gaussian elimination, though it appears in the Chinese Nine Chapters on the Mathematical Art around two thousand years before Gauss, worked with counting rods on a board.

Three operations are permitted, and each is reversible, which is what guarantees that they never gain or lose a solution. Any equation may be multiplied by a non-zero number. Any multiple of one equation may be added to another. Any two equations may be swapped. The goal is to reach a triangular form, in which the first equation involves all the unknowns, the second has lost the first unknown, the third has lost the first two, and so on down, at which point the last equation contains one unknown and the rest fall out by back substitution.

Take a system of three:

Use the first equation to remove $x$ from the other two. Adding $1.5$ times the first to the second gives $0x+0.5y+0.5z=1$. Adding the first to the third gives $0x+2y+z=5$. The first unknown is now confined to the first equation.

Now use the new second equation to remove $y$ from the third. Subtracting $4$ times $(0.5y+0.5z=1)$ from $(2y+z=5)$ gives $0y-z=1$, so $z=-1$.

Back substitute. From $0.5y+0.5z=1$ with $z=-1$: $0.5y=1.5$, so $y=3$. From the first equation, $2x+3-(-1)=8$, so $2x=4$ and $x=2$. The solution is $(2,3,-1)$, and substituting it into all three original equations gives $8$, $-11$ and $-3$ as required.

Two features of that calculation matter more than the answer. It was mechanical: at no point was ingenuity required, only a decision about which equation to use to clear which unknown. And it terminated: there is no possibility of the procedure wandering, because each step permanently removes one unknown from one equation and the supply of both is finite.

Example. Solve $x+2y+z=6$, $2x+y-z=1$ and $x-y+2z=5$ by elimination.

Subtract $2$ times the first from the second: $-3y-3z=-11$. Subtract the first from the third: $-3y+z=-1$. Now subtract the second of these from the third: $4z=10$, so $z=2.5$. Then $-3y=-1-z=-3.5$, so $y=7/6\approx 1.1667$, and $x=6-2y-z=6-2.3333-2.5=1.1667$. Check the second equation: $2(1.1667)+1.1667-2.5=1.0$, as required.

Now you. Solve $x+y+z=6$, $2y+5z=-4$ and $2x+5y-z=27$.

The three outcomes

Elimination cannot fail, but it can end somewhere other than a triangle, and there are exactly two ways for that to happen.

Take $x+2y=4$ and $2x+4y=7$. Subtracting twice the first from the second gives $0x+0y=-1$, which no assignment of $x$ and $y$ can satisfy. The system is inconsistent and has no solution. Geometrically the two lines have the same slope and different intercepts: they are parallel, and never meet.

Now change one digit: $x+2y=4$ and $2x+4y=8$. The same step gives $0x+0y=0$, which every pair satisfies. The second equation was the first one in disguise, carrying no information, and the system is left with one genuine equation in two unknowns. Setting $y$ to any value $t$ gives $x=4-2t$, so the solutions form a whole line: $(4,0)$, $(2,1)$, $(0,2)$ and infinitely many more. The system is underdetermined.

So a linear system has no solution, exactly one, or infinitely many. It can never have exactly two, or exactly seventeen. The reason is easy to see and worth seeing now: if $\mathbf{p}$ and $\mathbf{q}$ are both solutions then so is every point on the line joining them, because averaging two solutions of $a_1{x}_1+\cdots +a_n{x}_n=b$ in any weighted way that sums to one gives $b$ again. Two solutions therefore drag a continuum in with them. Later lessons make this precise, and give the solution set a name and a dimension.

Example. Classify $3x-6y=9$ and $-x+2y=-3$.

Add $3$ times the second to the first: $0=0$. The second equation is $-1/3$ times the first, so there is one genuine equation, $x-2y=3$, and infinitely many solutions: $x=3+2t$, $y=t$. Two of them are $(3,0)$ and $(5,1)$, and both satisfy the original pair.

Now you. Classify $4x-2y=5$ and $-6x+3y=1$.

What it costs

The reason a subject is needed rather than a technique is that $n$ grows. Clearing the first unknown from $n-1$ equations of $n+1$ numbers each costs roughly $n^2$ multiplications, and repeating for each unknown in turn totals about $n^3/3$ multiplications and as many additions. For $n=1000$ that is $3.3\times {10}^8$ operations, a fraction of a second on any laptop. For $n=5000$ it is $4.2\times {10}^{10}$, about forty seconds at a billion operations per second. For $n={10}^6$, the size of system a serious engineering simulation produces, it is $3.3\times {10}^{17}$, which is out of reach by brute force and is solved instead by methods that exploit the structure of the particular matrix, most of whose entries are zero.

Compare the alternative that school sometimes teaches for small systems, Cramer's rule, which expresses each unknown as a ratio of determinants. Computing an $n$ by $n$ determinant by the naive expansion costs about $n!$ multiplications. For $n=20$ that is $2.4\times {10}^{18}$ operations, seventy-seven years at a billion per second, against $2700$ operations for elimination. Cramer's rule is a theoretical statement, not an algorithm, and this course will treat it as one.

Example. Roughly how many multiplications does elimination need for $n=200$, and how does that compare with $n=2000$?

Using $n^3/3$: for $n=200$ it is $8\times {10}^6/3=2.7\times {10}^6$. For $n=2000$ it is $8\times {10}^9/3=2.7\times {10}^9$. Ten times the unknowns costs a thousand times the work, because the count is cubic.

Now you. A solver manages $2\times {10}^9$ multiplications per second. Roughly how long does it take on a system with $n=5000$?

The unknowns were never used

Look back at the elimination worked above and ask which symbols did any work. The letters $x$, $y$ and $z$ were carried through every line and never once entered a calculation. All the arithmetic happened to the coefficients, and the letters were placeholders keeping the columns aligned. Written without them, the first system is nothing but a rectangle of numbers, with rows $(2,1,-1)$, $(-3,-1,2)$ and $(-2,1,2)$, together with the right hand side $(8,-11,-3)$.

That rectangle is a matrix, and the course to come is largely about taking it seriously as an object in its own right rather than as shorthand for a system. Two conventions are fixed now and used for the rest of the subject. A vector is a column of numbers, written in round brackets as $(8,-11,-3)$. A matrix is written as the list of its columns, so $A=[(2,-3,-2),(1,-1,1),(-1,2,2)]$ is the coefficient matrix of that system, whose first column collects the coefficients of $x$ from all three equations. When elimination needs to talk about a row it will say so explicitly.

Writing the system by columns exposes something the row form hides. The three equations, taken together, say precisely that

where the multiplications and additions happen component by component. Solving is therefore asking what amounts of the three column vectors, added together, produce the target vector. That reading is the door into the geometry, and it turns the three outcomes above into three pictures rather than three algebraic accidents.

Honest limits

Exact arithmetic makes elimination flawless, and computers do not have exact arithmetic. If a pivot, the coefficient being divided by, is very small, dividing by it magnifies whatever rounding error the entry already carried, and the answer can come out wrong in every digit while the procedure reports no difficulty. The standard defence is partial pivoting: before clearing a column, swap in the row whose entry in that column is largest in absolute value. This costs almost nothing and, as James Wilkinson established in his backward error analysis around 1961, makes elimination reliable in practice, though contrived matrices that defeat it do exist. Every numerical library performs the swap by default.

There is also a limit worth naming at the start. Everything in this subject is exact and complete for the linear class, and the class really is a restriction. Nothing here will solve $x^2+y^2=1$. What the subject offers in exchange is that within its class, questions have answers and the answers can be computed and checked.

The next lesson takes up the column vectors that the coefficient matrix turned out to consist of, and asks what they are and what can be done to them.