# Mathematics 1010 online

## Linear Systems of Equations

As we have seen before, a linear equation in one variable is an equation of the form where and are constants, and is the variable (also called the unknown in this context) whose value needs to be determined. There is one equation and one unknown.

It is possible to have several unknowns, but then we also have to have several equations. An equation in several unknowns is linear if the unknowns are multiplied with constants and those products add to a constant. A set of linear equations is called a linear system.

The most important and typical case is that the number of equations equals the number of unknowns.

Let's illustrate the concepts with the following simple system. Suppose there are two variables, and , and we have the two equations We begin by observing that both equations are satisfied if and . This is easy to check (and I know it because that's how I set up the system), but how would we know if nobody told us the solution?

The textbooks usually present two methods of solving a linear system, substitution and elimination. Substitution works by solving one equation for one variable, and substituting its value (in terms of the other variables) in the other equations. It works well for small systems (and it can sometimes be applied successfully to nonlinear systems). Elimination, or Gaussian Elimination, is essentially equivalent, but it's more systematic, and it's the basis of virtually all computer methods of solving large linear systems. This page focuses on elimination.

Consider again the above system. Let's do something that may appear mysterious at first, but that embodies the basic idea. Let's multiply with on both sides of the first equation. This gives the new system: The significance of this operation is that in the new system the variable has the same coefficient in both equations.

Next, let's subtract on both sides of the second equation. However, on the left side let's not call it . Let's call it . We can do this, according to the first equation. The second equation becomes or, after simplifying, Dividing by on both sides gives .

Now that we know we return to the first equation and substitute for . This gives the equation: which has the solution .

The first step (multiplying with ) and the second step (subtracting from the second equation) are usually combined and described, somewhat imprecisely, as subtracting twice the first equation from the second equation.

So in the above example we subtracted a suitable multiple of the first equation to get a new equation that has just one variable. We solved that equation, and then substituted its solution in the first equation which at that stage also turned into a single equation with a single unknown. We finished by solving that single equation.

Remember that at the end of the process we check our answers by substitution. Clearly, substituting and in the original equations shows that those equations are satisfied.

If we had more than two equations, say equations, we would pick a suitable equation (which may be the first, or any other equation) and a particular variable (which may be the first, or another) and subtract suitable multiples of our chosen equation from the other equations so that the chosen variable no longer shows up in the resulting equations in unknowns. At that stage, we have reduced our problem to a simpler problem of the same structure. We repeat the process until we get a single equation in a single unknown. The process so far is called Gaussian Elimination. We solve our single remaining equation, substitute its solution in an equation that has only two unknowns, solve that one, substitute the two now known variables into an equation with three unknowns, and in this manner work our way backwards until we have all the solutions. This second process is called Backward Substitution.

The method outlined here works in general. For work with paper and pencil it needs to be streamlined. Moreover, it is almost inevitable to avoid mistakes. Mistakes are harmless if they are recognized immediately. Let me describe a procedure that's efficient and that lets you discover errors immediately.

To begin with, we don't need to write down the unknowns all the time. It is sufficient to write down their coefficients. This will save time and effort. To check for errors we keep track of one more number, the row sum of each equation. It is simply the sum of the coefficients and the right hand side of each equation. For example the equation has the row sum To keep track of the equations we number them and also the new equations. To distinguish row numbers from coefficients let's write them in square brackets.

Let's illustrate the technique with an example. Consider the linear system The system and its processing are described in the following table: Equations , , and form the original system, augmented by the row sum (RS). RHS stands for the awkward phrase right hand side. (You could also write the right hand side on the left, or you could arrange your equations in columns and write the right hand sides on top or at the bottom, or a separate sheet of paper, if you like.)

Equation is obtained by subtracting twice the first equation from the second equation. You should check that you get indeed the equation described in row of the above table. Fully written out it means Of course we would normally omit the term and think of it as The sum of the coefficients and RHS in that row is The key to the effectiveness of the error detection is that this sum is computed in two ways: actually adding the entries in row , and also by applying to the preceding row sums the same operation as to the equations. In this case we get that the row sum in row equals the row sum in row minus twice the row sum in row : This is the key to many error checking techniques: compute the same thing twice and if you make a mistake in one of your computations it will show up as discrepancy in your two answers.

Row is obtained similarly, it equals row minus three times row . The whole purpose of the exercise is that rows (or equations) and contain only two variables, namely and . The new system is These two equations have the same coefficient of (i.e., ). If we subtract the second from the first, or in terms of the overall system, row from row we obtain the new equation This is row in the above table. It tells us that The table does not describe how we find and . Knowing we find an equation, e.g., that contains and . That equation becomes which has the solution Finally, substituting and in the first equation gives which implies that Checking these results by substituting in the original equations completes the solution of our system.

Notes

• It's not necessary that you carry out your computations exactly as it is described here. But it is necessary that you get the right answer, and you are probably well motivated to be efficient about your work. The scheme described here is fool proof, and about as efficient as a general purpose scheme can be. But use any scheme that works for you. To solve linear systems successfully you will need to organize your work in a manner that lets you go back and figure out what you did, and you will need to incorporate some error checking, e.g., by keeping track of row sums. When you are done, always check your answers! That's easy for linear systems, you just substitute your answers in the original equations and see that you get the correct right hand sides.

• The solution is independent of which row and which unknown we choose at each step of the elimination. So both the equation and the variable can be chosen conveniently, with a view towards reducing the work load. For example, it may be convenient to pick a variable corresponding to a column with as many zero entries as possible.

• The technique described here also work if some of the coefficients in the linear system, are themselves variables rather than specific numbers.

• Gaussian Elimination followed by backward substitution is the method used most widely for the solution of linear systems by computers. On the kind of workstation we have in our labs it takes a few seconds to solve a thousand equations in a thousand unknowns.

• There are linear systems that have no solution, or that have infinitely many solutions. This is discussed in more detail here .