Page 51 - A Course in Linear Algebra with Applications

2.1: Gaussian Elimination 35

solution of the original system is bound to be a solution of the
new system, and conversely, by invertibility of the operations,
any solution of the new system is also a solution of the original
system. Thus we can state the fundamental theorem:

Theorem 2.1.1

When an operation of one of the three types (a), (b), (c) is
applied to a linear system, the resulting linear system is equiv-
alent to the original one.

We shall now exploit this result and describe the proce-
dure known as Gaussian elimination. In this a sequence of
operations of types (a), (b), (c) is applied to a linear system
in such a way as to produce an equivalent linear system whose
form is so simple that we can quickly determine its solutions.
Suppose that a linear system of m equations in n un-
knowns xi, X2, ..., x n is given. In Gaussian elimination the
following steps are to be carried out.

(i) Find an equation in which x\ appears and, if necessary,
interchange this equation with the first equation. Thus we can
assume that x\ appears in equation 1.
(ii) Multiply equation 1 by a suitable non-zero scalar in
such a way as to make the coefficient of x\ equal to 1.
(iii) Subtract suitable multiples of equation 1 from equa-
tions 2 through m in order to eliminate x\ from these equa-
tions.
(iv) Inspect equations 2 through m and find the first equa-
tion which involves one of the the unknowns a?2, •••, x n , say
Xi 2. By interchanging equations once again, we can suppose
that Xi 2 occurs in equation 2.
(v) Multiply equation 2 by a suitable non-zero scalar to
make the coefficient of Xi 2 equal to 1.
(vi) Subtract multiples of equation 2 from equations 3
through m to eliminate Xi 2 from these equations.