Gaussian elimination:
How to solve systems of linear equations
Marcel Oliver
Engineering and Science Mathematics 2B
Step 1: Write out the augmented matrix
A system of linear equation is generally of the form
Ax = b,
(1)
where A M (n m) and b Rn are given, and x = (x1 , . . . , xm )T is the
vector of unknowns. For example, the system
x2 + 2 x3 x4 = 1
x1 + x3 + x4 = 4
x1 + x2 x4 = 2
2 x2 + 3 x3 x4 = 7
can be written in the form (??)
0 1
1 0
A=
1 1
0 2
with
2 1
1 1
,
0 1
3 1
To simplify notation, we write A and
0 1
1 0
M =
1 1
0 2
1
4
b=
2 .
7
b into a single augmented matrix,
2 1 1
1 1 4
.
(2)
0 1 2
3 1 7
Step 2: Bring M into reduced row echelon form
The goal of this step is to bring the augmented matrix into reduced row
echelon form. A matrix is in this form if
the first non-zero entry of each row is 1, this element is referred to as
the pivot,
each pivot is the only non-zero entry in its column,
each row has at least as many leading zeros as the previous row.
For example, the following matrix is
any, possibly non-zero, number:
0 1
0 0 0
0 0 0
0 0 0
in row echelon form, where could be
0
1
0
0
0
0
0
0
0
0
1
0
Three types of elementary row operations are permitted in this process,
namely
(A) exchanging two rows of M ,
(B) multiplying a row by a non-zero scalar,.
(C) adding a multiple of one row to another row.
As an example, we row-reduce the augmented matrix (??):
1 0 1 1 4
0 1 2 1 1
1 0 1 1 4 reorder rows 1 1 0 1 2 R1+R2R2
1 1 0 1 2 0 1 2 1 1
0 2 3 1 7
0 2 3 1 7
1 0 1 1 4
1 0 1 1 4
R3R2R3
0 1 1 0 6 R42
0 1 1 0 6
R2R4
R4R3R4
0 0 1 1 5
0 1 2 1 1
0 0 1 1 5
0 2 3 1 7
1 0 0 2 9
1 0 1 1 4
0 1 1 0 6 R1R3R1
R2R3R2
0 1 0 1 11
0 0 1 1 5
0 0 1 1 5
0 0 0 0 0
0 0 0 0 0
2
Step 3: Zero, one, or many solutions?
There are two fundamentally different situations:
The matrix A is regular. In this case, the left-hand block of M has
been reduced to the identity matrix. There is exactly one solution,
independent of which vector b you started out with.
The matrix A is degenerate. In this case, the left-hand block of the
row-reduced augmented matrix has more columns than non-zero rows.
Then, dependent on which vector b you started out with, there is either
no solution at all (the system is inconsistent), or an infinite number
of solutions (the system is underdetermined ).
If the rightmost column of the row-reduced augmented matrix has a nonzero
entry in a row that is otherwise zero, the system is inconsistent.
Otherwise, the general solution has the following structure. It is the
sum of a particular solution of the inhomogeneous equation Ax = b and the
general solution of the homogeneous equation Ax = 0.
Step 4: Write out the solution
If the left-hand block of the row-reduced matrix is not square, make
it square by adding or removing rows of zeros. This has to be done
in such a way that the leading 1 in each row (the pivot) lies on the
diagonal!
The rightmost column of the row-reduced augmented matrix is a particular solution.
To find a basis for the general solution of the homogeneous system,
proceed as follows: Take every column of the row-reduced augmented
matrix that has a zero on the diagonal. Replace that zero by 1. The
set of these column vectors is the basis you need.
In the example above, a particular solution is (9, 11, 5, 0)T and the general
solution of the homogeneous equation is a one-dimensional subspace with
basis vector (2, 1, 1, 1)T . Therefore, the general solution to the inhomogeneous equation Ax = b is the line
9
2
11
1
x=
5 + 1 .
0
1
3
Another example: Assume that the row-reduced matrix is
0 0 1 3 0 4 3
.
0 0 0 0 1 6 7
Padding the matrix with the required
0 0 0 0
0 0 0 0
0 0 1 3
0 0 0 0
0 0 0 0
0 0 0 0
rows of zeros gives
0 0 0
0 0 0
0 4 3
,
0 0 0
1 6 7
0 0 0
and the general solution is
0
1
0
0
0
0
0
1
0
0
3
0
0
3
4
x = + 1 + 2 + 3 + 4
0.
0
0
0
1
7
0
0
0
6
0
0
0
0
1
Step 5: Check your solution
By multiplying A with the vectors representing the solution, you can easily
verify that the computation is correct. In our example,
1
9
0 1 2 1
9
11 1 0 1 1 11 4
A
5 = 1 1 0 1 5 = 2 = b ,
0
7
0 2 3 1
0
2
0 1 2 1
2
0
1 1 0 1 1 1 0
A
1 = 1 1 0 1 1 = 0 .
1
0 2 3 1
1
0
