Clark University

Dept. Math. & Comp. Sci.

D Joyce

BP 322, 793-7421.

In fact, any linear equation can be put in the form

where *n* is the number of variables, the variables are *x*_{1}, *x*_{2}, ... ,
*x _{n}*, and

A *system* is just a collection of such linear equations, and to solve a system look for the values of the variables which
make all the equations true simultaneously. For instance, if
*x* and *y* are the variables, then an example system of linear equations is

5x | – 2y | = 4 |

x | + 2y | = 8 |

There are various ways of solving this system, and they lead to the unique solution where *x* = 2 and
*y* = 3. We’ll look next at a common algorithm for solving systems of simultaneous
equations called *elimination*.

- There are three classes of corn, of which three bundles of the first class, two of the second and one of the third make 39
measures. Two of the first, three of the second and one of the third
make 34 measures. And one of the first, two of the second and three of the third make 26 measures. How many measures of grain
are contained in one bundle of each class?

3x | + 2y | + z | = 39 |

2x | + 3y | + z | = 34 |

x | + 2y | + 3z | = 26 |

This is very similar to the ancient Chinese method except they wrote in columns and did not use variables. In fact, the ancient
Chinese method uses what we would call matrices. The solution in the
*Jiuzhang suanshu* continues.

- Rule. Arrange the 3, 2, and 1 bundles of the three classes and the 39 measures of the grains at the right. Arrange other
conditions in the middle and at the left.

1 | 2 | 3 |

2 | 3 | 2 |

3 | 1 | 1 |

26 | 34 | 39 |

Putting the numbers in rows rather than columns, and starting at the top instead of the right, we get the matrix of coefficients of the system of simultaneous linear equations that appears above.

3 | 2 | 1 | 39 |

2 | 3 | 1 | 34 |

1 | 2 | 3 | 26 |

This matrix contains all the information of the system of equations so long as we remember what the rows and columns mean. But we don’t have to write down all the variables, so it’s more concise.

For the rest of the translation of the solution in the *Jiuzhang suanshu,*
I’ll use rows instead of columns to be consistent with the modern practice. The
solution proceeds:

- With the first class in the first row multiply currently the middle row,
and directly leave out.

3 | 2 | 1 | 39 |

0 | 5 | 1 | 24 |

1 | 2 | 3 | 26 |

The whole purpose of that operation is to get a 0 just where we got it.

- Again multiply the next, and directly leave out.

3 | 2 | 1 | 39 |

0 | 5 | 1 | 24 |

0 | 4 | 8 | 39 |

- Then with what remains of the second class in the second row, directly leave out.

3 | 2 | 1 | 39 |

0 | 5 | 1 | 24 |

0 | 0 | 36 | 99 |

This is what we call *echelon* form, a steplike form where the leading nonzero entries are further to the right in each row.
We’ve finished the first stage of the algorithm of elimination. The
next stage finds the answers starting with the third unknown and working backwards with back substitutions.

- Of the quantities that do not vanish, make the first the divisor and the next the dividend, that is, of the third class.

3 | 2 | 1 | 39 |

0 | 5 | 1 | 24 |

0 | 0 | 4 | 11 |

- To find the second class, with the divisor multiply the measure
in the middle row and leave out from it the dividends for the third
and second classes. The remainder being divided by the number
of bundles of the first class gives the dividend for the first class.

3 | 2 | 1 | 39 |

0 | 4 | 0 | 17 |

0 | 0 | 4 | 11 |

- To find the first class, also with the divisor multiply the measures in the first row and leave out from it the dividends for
the third and second classes. The remainder being divided by the
number of bundles of the first class gives the dividend for the first class.

12 | 0 | 0 | 111 |

0 | 4 | 0 | 17 |

0 | 0 | 4 | 11 |

- Divide the dividends of the three classes by the divisor and we get their respective measures.

- There are three kinds of corn. The grains contained in two, three and four
bundles, respectively, of these classes of corn, are not sufficient to make a
whole measure. If however we add to them one bundle of the second, third, and
first classes, respectively, then the grains would become full one measure in
each case. How many measures of grain does then each one bundle of the different
classes contain?

2x | + y | = 1 | |

3y | + z | = 1 | |

x | + 4z | = 1 |

As a matrix this looks like

2 | 1 | 0 | 1 |

0 | 3 | 1 | 1 |

1 | 0 | 4 | 1 |

First, we’ll put it in echelon form. There already is a 0 at the beginning of the second row. We need to get a 0 at the beginning of the third row. For this example, let’s follow the ancient Chinese method that avoids fractions as long as possible. Double the third row to get 2 0 8 2, and subtract the first row from it.

2 | 1 | 0 | 1 |

0 | 3 | 1 | 1 |

0 | –1 | 8 | 1 |

You might wonder how the ancient Chinese dealt with negative numbers like
the –1 that appears in the third row. They had no problem with them.
According to Lui Hui (c. 263 C.E.) who wrote about the
*Jiuzhang suanshu,* red rods were used for positive numbers and black
rods for negative numbers. He also explained how to add and subtract
positive and negative numbers.

For this problem, we can continue by tripling the third row to get 0 –3 24 3, and then adding the second row to it.

2 | 1 | 0 | 1 |

0 | 3 | 1 | 1 |

0 | 0 | 25 | 4 |

The matrix is now in echelon form. We know *z* = 4/25.
We can continue to avoid fractions if we multiply the second row by
25 to get 0 75 25 25 and subtracting the third from it.

2 | 1 | 0 | 1 |

0 | 75 | 0 | 21 |

0 | 0 | 25 | 4 |

We now have *y* = 21/75 = 7/25. Multiply the
first row by 25 to get
50 25 0 25,
and subtract the second row
0 25 0 7
from it.

50 | 0 | 0 | 18 |

0 | 25 | 0 | 7 |

0 | 0 | 25 | 4 |

Therefore, *x* = 18/50 = 9/25. We’ve solved the problem. The solution
is: one bundle of the first class contains *x* = 9/25 measures of grain,
one bundle of the second class contains *y* = 7/25 measures of grain, and
one bundle of the third class contains *z* = 4/25 measures of grain.

2x | + 5y | – 13 z | = 1000 |

3x | – 9y | + 3z | = 0 |

–5x | + 6y | + 8z | = –600 |

As a matrix this looks like

2 | 5 | –13 | 1000 |

3 | –9 | 3 | 0 |

–5 | 6 | 8 | –600 |

We can begin by putting a 1 at the beginning of the first row by dividing that row by 2.

1 | 2.5 | –6.5 | 500 |

3 | –9 | 3 | 0 |

–5 | 6 | 8 | –600 |

Now subtract 3 times the first row from the second, and add 5 times the first row to the third. That will make the first entries in the second and third rows both 0.

1 | 2.5 | –6.5 | 500 |

0 | –16.5 | 22.5 | –1500 |

0 | 18.5 | –24.5 | 1900 |

Next, divide the second row by –16.5 to put a 1 in its first nonzero entry. We can wait on the third row until later.

1 | 2.5 | –6.5 | 500 |

0 | 1 | –1.3636 | 90.909 |

0 | 18.5 | –24.5 | 1900 |

(Note that we’ve only kept five significant figures. You would think that would be enough, but we’ll see how that small roundoff error makes a larger error in the final answer.)

Now subtract 18.5 times the second row from the third.

1 | 2.5 | –6.5 | 500 |

0 | 1 | –1.3636 | 90.909 |

0 | 0 | .7266 | 218.18 |

(The error is building up. The .7266 should be .727272...)

Divide the third row by .7266 so its leading nonzero entry becomes 1.

1 | 2.5 | –6.5 | 500 |

0 | 1 | –1.3636 | 90.909 |

0 | 0 | 1 | 300.275 |

(The correct entry in the last row is 300, not 300.275.)

The matrix is now in echelon form where the first nonzero entry
in each row is a 1. We know what *z* is, 300.275. We can back
substitute. Add 1.3636 times the third row to the second row, and
add 6.5 times the third row to the first row.

1 | 2.5 | 0 | 2451.79 |

0 | 1 | 0 | 500.364 |

0 | 0 | 1 | 300.275 |

Subtract 2.5 times the second row from the first row.

1 | 0 | 0 | 1200.88 |

0 | 1 | 0 | 500.364 |

0 | 0 | 1 | 300.275 |

Thus, the solution is that *x* = 1200.88, *y* = 500.364, and *z* = 300.275.

The fractions are due to roundoff error. The actual
solution is *x* = 1200, *y* = 500,
and *z* = 300. Even though our computations were
done with five significant figures, our final answer is only
correct to three significant figures. Typical modern calculators keep
a couple extra digits of accuracy to hide the roundoff error. Usually
that’s enough, but not always. Perhaps the original method which
delays division to the end of the algorithm is a better method.

Of course, there are shortcuts and exceptions. The order of the rows in the matrix is irrelevant, so you can decide which one goes first. If there’s a 1 as the first entry of some row other than the first, you might just as well make that row the first and save yourself some division. For example, in the matrix

4 | 2 | –3 | 12 |

–3 | 0 | 5 | –4 |

1 | 5 | –8 | 0 |

start off by making the third row the first. You don’t actually have to exchange the rows; it’s enough to treat the third row as the first. You can do something similar with the columns, but you can get pretty confused if you do that. (You must remember which column refers to which variable.)

One time when you have to treat some other row as the first is when the first leads off with a 0. For instance, in the matrix

0 | 2 | 24 | 200 |

3 | –5 | –6 | 350 |

–4 | 4 | 7 | –600 |

you have to make either the second or the third row into the first row.

Now a wrinkle. In many applications, there is a unique solution, that is, there is only one way to assign values to the variables so that the equations are simultaneously true. But not in all applications. Sometimes, there are no solutions at all, and sometimes there are infinitely many solutions. Here’s a coefficient matrix for a system of linear equations that has no solution.

2 | –3 | 4 | 8 |

3 | 2 | 6 | 5 |

5 | –1 | 10 | 4 |

Note that if you sum the first two rows, then you get
5 –1 10 13.
That says
5*x* – *y* + 10*z* = 13.
But the third row says
5*x* – *y* + 10*z* = 4.
Since 13 does not equal 4, there is no solution. If you were to
go through the algorithm of elimination, you end up with the matrix

1 | 0 | 2 | 31/13 |

0 | 1 | 0 | –14/13 |

0 | 0 | 0 | 1 |

The important thing to notice is that the last row is a contradiction. It says 0 = 1. There are no values of *x,
y,* and *z* to make that true. So, there are no solutions to the system.
When one of the rows has all zeros in it except the final number, that means the system has no solutions.

Next, let’s look at a system where there are infinitely many solutions. Take the last example, but change the last entry in the last row to 13.

2 | –3 | 4 | 8 |

3 | 2 | 6 | 5 |

5 | –1 | 10 | 13 |

Note now how the third row is the sum of the previous two. If you follow through the method of elimination, you end up with the matrix

1 | 0 | 2 | 31/13 |

0 | 1 | 0 | –14/13 |

0 | 0 | 0 | 0 |

The last row says 0 = 0, and that is no condition whatsoever
on the values of *x, y,* and *z.* The question is: what do
you do at this point? The second row says *y* = –14/13,
and the first row says *x* –2*z* = 31/13,
that is to say, *x* = 2*z* + 31/13.
Those are the conditions on *x* and *y*, but there are no
conditions on *z*. That means you can take any value of *z*
you want, set *y* to –14/13, and set *x* to
2*z* + 31/13, and you get a solution to the system of
equations. There are infinitely many solutions. When the solutions
are described that way, we say that they are
*parameterized* by *z*.

Back to Math 105, History of Math, course page

Back to Math 130, Linear Algebra,
course page

D.E. Joyce

August, 1996