Solving Systems of Linear Equations

Ancient Methods

As early as 200 B.C. the Chinese had devised a clever method for solving systems of two linear equations with two unknowns. The method is illustrated in Chapter 7 of the Jiuzhang suanshu (Nine Chapters in the Mathematical Art), one of the earliest surviving mathematical texts from China. Below is a sample problem from the Nine Chapters:

One pint of good wine costs 50 gold pieces, while one pint of poor wine costs 10. Two pints of wine are bought for 30 gold pieces. How much of each kind of wine was bought?

Solution: If $x$ and $y$ are amounts of each kind of wine bought, then the equations to be solved are $x+y=2$ and $50x+10y=30$. The Chinese would first make a couple of guesses as follows.

If $x=1/2$, then $y=2-1/2=3/2$, but then $50x+10y=25+15=40$, so $x_1=1/2$ results in a value for $50x+10y$ that exceeds 30 by $b_1=10$.

If $x=1/5$, then $y=2-1/5=9/5$, but then $50x+10y=10+18=28$, so $x_2=1/5$ results in a value for $50x+10y$ that is deficient by $b_2=2$.

The answer can then be computed by setting up the proportion

\begin{align} \frac{b_1}{x_1-x}=\frac{b_2}{x-x_2} \end{align}

In this case:

\begin{align} \frac{10}{1/2-x}=\frac{2}{x-1/5} \end{align}

Solving for $x$ we get $x=\frac14$ and hence $y=\frac74$.

For solving larger systems of equations, the Chinese developed a method essentially equivalent to Gaussian elimination (and this was 2000 years before Gauss came up with it!).

Linear Systems in Europe - Cramer's Method

In 1750, Gabriel Cramer (1704-1752) published the famous rule for solving systems of linear equations that bears his name. The rule appears in his Introduction to the Analysis of Algebraic Curves and deals with the problem of finding the equation of an algebraic plane curve passing through some fixed points.

An algebraic plane curve is one whose equation is of the form $f(x,y)=0$ where $f(x,y)$ is the sum of terms of the form $c_{ij}x^iy^j$, where $i$ and $j$ are non-negative integers. The degree of the curve is the largest value of $i+j$ among all the terms. So for example, the equation of a second-degree algebraic plane curve is

\begin{align} A\cdot x^2+B\cdot y^2+C\cdot x\cdot y+D\cdot x +E\cdot y+F=0 \end{align}

where not all of $A$, $B$, and $C$ are zero. If we assume $A\neq 0$, we can divide the equation by $A$ and obtain the equivalent equation

\begin{align} b\cdot y^2 +c\cdot x\cdot y+d\cdot x+e\cdot y+f=-x^2 \end{align}

where $b=\frac{B}{A}$, $c=\frac{C}{A}$, etc. . Since there are five constants to be determined ($b,c,d,e,f$), five points are needed to completely determine the curve.

Similarly, the equation of a plane algebraic curve of degree three has equation

\begin{align} A\cdot x^3+B\cdot y^3+C\cdot x^2y+D\cdot xy^2+E\cdot x\cdot y +F\cdot x^2+G\cdot y^2+H\cdot x+I\cdot y+J=0 \end{align}

where not all of $A$, $B$, $C$, and $D$ are zero. The above equation has 10 arbitrary constants, but as before we can divide through by one of the non-zero constants and reduce the number of constants to 9. So nine points are necessary to specify an equation of degree 3. Cramer showed that, in general, the number of points necessary to specify a curve of degree $n$ is $\frac{n(n+3)}{2}$.

Cramer's Paradox

To illustrate, there are infinitely many second-degree algebraic plane curves that go through the four points $(\pm 1,\pm 1)$. But if we specify an additional point $E$, there is only one second-degree curve that goes through all five points, as shown below for various choices of $E$.

The situation is somewhat different for third-degree equations. As noted above, nine points are necessary to specify a third-degree algebraic curve, but it turns out that nine points may not be sufficient. The animation below shows many different third-degree algebraic curves that go through the nine points $(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1)$.

Cramer found this situation paradoxical and wrote to Euler about it. Euler easily resolved the paradox by explaining how in a system of $n$ linear equations with $n$ unknowns, the coefficients can be chosen to make some of the equations dependent on others and hence redundant. This set the stage for the invention of linear algebra.

Gauss, Jordan, and the Gauss-Jordan Elimination Method

In 1801, 23-year-old Carl Frederick Gauss (1777-1855) became instantly famous when he was able to compute the orbit of the newly discovered planetoid Ceres from just a few observations. The Italian astronomer Piazzi had discovered this new planetoid at the beginning of 1801 and then lost sight of it. Using Gauss's computed orbit, the planetoid was rediscovered at the end of the year in almost exactly the position forecast by Gauss.

Later in 1810, Gauss became interested in discovering the orbit of Pallas, the second-largest asteroid of the solar system. His work led him to a system of six linear equations in six unknowns. In order to solve this system, Gauss invented the method of Gaussian elimination which we still use today. The method consists of performing row-operations on the coefficient matrix to obtain an equivalent system of equations whose coefficient matrix is upper-triangular. This means that the last equation will involve only one unknown and can be easily solved. Substituting that solution into the second-to-last equation, one can then solve for another unknown. Continuing in this manner, one can eventually solve for all the variables.

In 1873, Wilhelm Jordan (1842-1899) published a book entitled Handbuch der Vermessungkunde (Handbook of Geodesy) in which he discussed Gauss' method of elimination to convert a given system of linear equations to a triangular system. In this book he explained how the triangular system can then be further reduced to a diagonal one, which can be solved directly. This algorithm is the Gauss-Jordan method which we use today.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License