You're already familiar with solving pairs of simultaneous equations in two variables, such as
Just to recap: you might subtract three times the first equation from the second, thus eliminating x and obtaining
whence y=3. Then, substituting into the first equation gives
from which we get x=4.
One thing to notice is that during the elimination phase, we have no need to use the symbols x and y: the whole elimination problem can be solved in matrix form. We begin by forming what we call the augmented matrix; this consists of the matrix of coefficients, togther with an additional column representing the right-hand-sides:
Call the first row r_{1} and the second r_{2}. We then simply replace r_{2} with r_{2}-3r_{1}, to obtain
at which point the substitution process can begin.
(There might seem little point in getting rid of the symbols and working with matrices in this way. However, it has at least two advantages. The first is that for larger, more complicated systems, it prevents confusion and keeps things systematic. The second is that it lends itself to automation on computer.)
The way things work with larger systems is exactly the same, except that because more variables are involved, we have to take more care. Consider the problem
As with the 2 by 2 case, we start by forming the augmented matrix:
Call the three rows r_{1}, r_{2} and r_{3}.
Now, the rules of the game are as follows. We want to end up with one of our equations (usually the third) containing just z, with x and y having been eliminated. This will enable us to work out what z's value is. We also want one of our equations (usually the second) to contain just y and z, with x having been eliminated. Then, knowing the value of z, we can work out that of y. Finally, knowing the values of both y and z, we can work out that of x from the first equation.
In matrix terms, this means we want row 3 to be of the form
(where the question marks represent numbers) and row 2 of the form
Overall, then, the matrix we end up with after the elimination ought to be of the form
A matrix like this, with zeros below the leading diagonal, is said to be in row echelon form.
To get the matrix into row echelon form, we are allowed to perform what are called permitted row operations. These correspond to the kind of thing we're allowed to do with simultaneous equations. We may do the following things:
1. Given a row, subtract a multiple of another row from it.
2. Given a row, multiply or divide throughout by some number.
3. Swap the order of two rows.
Here's how it works with our example.
Starting with the augmented matrix,
we first try to create a matrix of the form
with zeros in column 1 of rows 2 and 3. To do this we:
(i) replace r_{2} by r_{2}-2r_{1};
(ii) replace r_{3} by r_{3}-3r_{1}.
This gives
We now try to complete the process, and create a matrix of the form
To do this we simply replace r_{3} by r_{3}-r_{2}.
This gives
We can now solve the system by back-substitution. Our final row gives us
from which we get z=3.
Our second row thus becomes
giving y=1.
Our first row is then
and thus x=4.
This process is known as Gaussian elimination. It's a very efficient way of solving one-off problems, and has one huge advantage over most other methods, in that it can also be used where the number of equations and the number of unknowns are not the same. It works like this. To solve the m by n system
1. Form the m by \left(n+1\right) augmented matrix
2. Set j=1.
3. For each i>j, replace row r_{i} with
This will zero all the entries in column j below the leading diagonal.
4. If j<m, set j=j+1 and return to 3, else stop the elimination process and move on.
5. Solve the system by back-substitution.
The process hits a hitch if, at any stage, one of the diagonal entries a_{j\,j} is zero. When this happens, this can usually be dealt with by swapping row r_{j} with one of the rows below it.