Page 49 - Matrix Analysis & Applied Linear Algebra

42 Chapter 2 Rectangular Systems and Echelon Forms

Remember that a pivot must always be a nonzero number. For square sys-
tems possessing a unique solution, it is a fact (proven later) that one can al-
ways bring a nonzero number into each pivotal position along the main diag-
8
onal. However, in the case of a general rectangular system, it is not always
possible to have the pivotal positions lying on a straight diagonal line in the
coefficient matrix. This means that the final result of Gaussian elimination will
not be triangular in form. For example, consider the following system:

x 1 +2x 2 + x 3 +3x 4 +3x 5 =5,
+4x 4 +4x 5 =6,
2x 1 +4x 2
x 1 +2x 2 +3x 3 +5x 4 +5x 5 =9,
+4x 4 +7x 5 =9.
2x 1 +4x 2

Focus your attention on the coefficient matrix

12133
 
 , (2.1.1)
 24044 
12355
A = 
24047
and ignore the right-hand side for a moment. Applying Gaussian elimination to
A yields the following result:

1
2133 1 2 1 3 3
   
 2 4044   0 −2 −2 −2 
0
1 2355 0 0 2 2 2
  −→   .
2 4047 0 0 −2 −2 1
In the basic elimination process, the strategy is to move down and to the right
to the next pivotal position. If a zero occurs in this position, an interchange with
a row below the pivotal row is executed so as to bring a nonzero number into
the pivotal position. However, in this example, it is clearly impossible to bring
a nonzero number into the (2, 2) -position by interchanging the second row with
a lower row.
In order to handle this situation, the elimination process is modified as
follows.

8
This discussion is for exact arithmetic. If floating-point arithmetic is used, this may no longer
be true. Part (a) of Exercise 1.6.1 is one such example.