Simultaneous linear equations

Simultaneous linear equations
Clark University
Dept. Math. & Comp. Sci.
D Joyce
BP 322, 793-7421.

Definition

What is a system of simultaneous linear equations? First, ask “what is a linear equation?” It is an equation in one or more variables where each term’s degree is not more than 1. That means a variable x may appear, but neither any higher power of x, such as x², nor any product of variables, such as xy, may appear. It has to be a pretty simple equation like

3x + 2y – 5z = 8.

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

c₁x₁ + c₂x₂ + ... + c_nx_n = c₀.

where n is the number of variables, the variables are x₁, x₂, ... , x_n, and c₀, c₁, ... , c_n are constants.

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.

Elimination: the first example

The algorithm of elimination for solving a system of simultaneous linear equations is not difficult and has been discovered more than once. The first time was by the ancient Chinese and appears in chapter 8 of the work Jiuzhang suanshu (Nine Chapters of the Mathematical Art, circa 100 B.C.E.–50 C.E.). Here’s the first problem from that chapter taken from The Development of Mathematics in China and Japan by Yoshio Mikami, 1913 (reprint Chelsea, 1974).

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? It is quite clear that this artificial problem was constructed just to illustrate the method. Each class of corn, or grain, is bundled in different sizes and the problem is to decide what sizes the different classes are bundled in. In modern algebraic notation, we can let x denote the number of measures of grain in the first class, y the number in the second class, and z the number in the third. Then we would have three equations in three unknowns that we would write as

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. This arrangement took place on a counting board using rods to indicate the numbers. It would look something like this.

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. This may be a little obscure, but the ancient Chinese method is a way of avoiding fractions. It means that you multiply the middle row by 3 (the first class in the first row) and subtract the first row from the second until a 0 is reached in the first entry of the second row. (Yes, the ancient Chinese had a 0 for this purpose; zero was just an empty space in that particular place on the counting board.) So we triple each entry of the second row to get 6 9 3 102, then subtract the first row from it twice, and the second row becomes 0 5 1 24. We now have this matrix.

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. In other words do the same thing with the first and third row in order to get a 0 at the beginning of the third row. So we multiply the third row by 3 to get 3 6 9 78, then subtract the first from it to get 0 4 8 39. We now have this matrix.

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. So we do the same thing with the second and third rows to get a 0 in the second entry of the third row. That is, multiply the third row by 5 to get 0 20 40 195, then subtract 4 times the second row from it to get 0 0 36 99.

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. So 99 divided by 36 will give z, the number of measures of grain in the third class. This quotient can be simplified to 11/4. We have

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. Multiply the second row 0 5 1 24 by 4 to get 0 20 4 96, then subtract the third row from it to get 0 20 0 85. Then y is 85 divided by 20, and that can be simplified to 17/4. The matrix is now

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. Multiply the first row 3 2 1 39 by 4 to get 12 8 4 156 and subtract the third row to get 12 8 0 145. Then subtract twice the second row from that to get 12 0 0 111. We have

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. We get the answers 9 1/4, 4 1/4, and 2 3/4, for the measures of grain in the three classes.

A second example

The first example was probably chosen because it doesn’t involve negative numbers. But sometimes the method involves negative numbers even when the final answer doesn’t.

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? This problem takes a little interpretation. If you take two bundles of the first class, it doesn’t make a measure of grain, but two bundles of the first plus one of the second does. Similarly, three of the second plus one of the third makes one whole measure, and four of the third plus one of the first makes a whole measure. That gives us three equations in three unknowns.

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.

Fractions earlier in the method

Modern computers have no difficulty with fractions (except roundoff error), so it’s not necessary to postpone using them until the end of the algorithm. They can be introduced in the first stage of finding the echelon form of the matrix. Just make sure the leading nonzero entry of a row is made to be 1. For example, begin with this system of linear equations (also from the Jiuzhang suanshu).

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.

Summary of the method, and wrinkles

There are two stages to the elimination algorithm. The first is to put the matrix into echelon form, a steplike form where the leading nonzero entries are further to the right in each row. If you want, you can make each of those nonzero entries equal to 1. The second stage is sometimes called “back substitution” and it makes sure there are only zeros above the leading nonzero entries. Both stages only use one operation, and that is to add or subtract a multiple of one row from another row. (It’s really only one operation since subtracting a multiple is the same as adding the negative multiple.) The final stage is a division (if it wasn’t done before) to make the leading nonzero entries all equal to 1. The answer is then evident.

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 5x – y + 10z = 13. But the third row says 5x – y + 10z = 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 –2z = 31/13, that is to say, x = 2z + 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 2z + 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.

Final summary

The method of elimination, discovered by the ancient Chinese, is an algorithm to solve a system of simultaneous linear equations. In many applications it leads to the unique solution, but for some systems it shows there are no solutions, and for other systems it produces infinitely many solutions.

Back to Math 105, History of Math, course page
Back to Math 130, Linear Algebra, course page

D.E. Joyce
August, 1996