Topic 8B
The Gauss-Jordan Algorithm
Suppose that you have a system of linear equations, and you wish to obtain the solution
set. There are many ways in which you could attempt to do this, for example you could
begin by re-arranging them in your favorite order; you could then choose to solve the
first equation for a variable which you pick; then examine the second equation, and
manipulate it in order to solve it for the second variable of your choice, etc.
The Gauss-Jordan algorithm provides us with one particular strategy to use for solving
the system of equations, and it is the formal way of referring to the strategy that we have
already introduced in Topic 8A. It assumes that we have already agreed on some preferred
ordering of the variables. There is still some freedom in some of the steps that you take,
and/or the order in which you carry them out.
In addition to explaining the algorithm, we will be introducing some language and
notation in this section: it is crucial that you learn to use this language as soon as
possible.
We have labelled the original system of equations as system (
*
). We will also label the
augmented matrix corresponding to system (
*
) with a (
*
) as well.
It is important to remember that if at any point during our manipulations of the
augmented matrix, when we have a new augmented matrix labelled
M,
say, we can
pause and write down the system of equations which corresponds to this augmented
matrix
M.
We will refer to this system as the corresponding system
. The corresponding
system to
M
will be equivalent to the original system (
*
). If 1
≤
i
≤
m
and 1
≤
j
≤
n
,
then the (
i, j
)
th
entry of
M
, denoted by
m
ij
, will provide the coefficient of the
variable
x
j
in the
i
th
equation in this equivalent system of equations.
We assume that:
a) we have a system of
m
linear equations in
n
unknowns.
b) the equations are labelled in a specific order,
e
1
, e
2
,
· · ·
, e
m
.
c) the (unknown) variables are labelled as
x
1
, x
2
,
· · ·
, x
n
,
and we wish to solve the system
for the variables in this order.
d) the variable
x
1
appears in at least one of the equations, i.e. the (
i,
1)
th
entry of the

1

augmented matrix (
*
) is non-zero for some
i,
1
≤
i
≤
m.
If there were no
x
1
’s in any
of the equations, then the system provides no information about
x
1
,
and it is thus a free
variable (use a parameter for it): we could relabel the system with the old
x
2
being
the new
x
1
, etc.
We will address the issue of the matrix form of the system of equations, that is, we will
be referring to the augmented matrix of the system.
Note:
not all texts agree on the exact form of the algorithm.
The Gauss Part of the Algorithm.
Step 1, aim
: to obtain a non-zero entry in the augmented matrix in the (1
,
1) position.