Analysis of Algorithms : An Active Learning Approach

4.3 LINEAR EQUATIONS 117

One way to try to find the value for each x would be to do substitutions of
the equations. In other words, we could take the second equation and rewrite
it as x 1 = 45
5 x 2
3 x 3
2 x 4 and then substitute this into the other three
equations in place of x 1. This would give three equations with three
unknowns. We could then take one of the remaining three equations and do
the same for x 2 , which would give us two equations with two unknowns.
Doing this one more time with x 3 would give one equation with one
unknown (x 4 ). We would now know the value for x 4 and could substitute this
back into one of the two equations in the previous step, which would allow us
to solve for the value of x 3. Substituting x 3 and x 4 into one of the three equa-
tions we got after the first substitution would allow us to determine the value
ofx 2 , and then using these three values in one of our original equations would
give us the value of x 1.
This process works extremely well, but a lot of algebra is needed, and it
would be easy for a mistake to occur. As the number of equations and
unknowns increases, this algebra work can take quite a while to complete. This
process is not easily programmed as described, but it is the basis for the Gauss-
Jordan method, which will be described next.

■ 4.3.1 Gauss-Jordan Method
We could consider the system of linear equations as a matrix with N rows and
N + 1 columns. For the previous example, this would give the matrix

We can now do a series of operations based on the rows to reach the result.
When the first n rows and columns represent the identity matrix, the final col-
umn will have the x values that we want. This would look like the following:

271570

153245

324133

815356

1000 x 1

0100 x 2

0010 x 3

0001 x 4