TABLE OF CONTENTS Gaussian elimination is undoubtedly familiar to the reader. It is the simplest way to solve linear systems of equations by hand, and also the standard method for solving them on computers. We first describe Gaussian elimination in its pure from, and then, in the next lecture, add the feature of row pivoting that is essential to stability.
Gaussian elimination transforms a full linear system into an upper-triangular one by applying simple linear transformations on the left. In this respect it is analogous to Householder triangularization for computing QR factorizations. The difference is that the transformations applied in Gaussian elimination are not unitary.
Let 
be a square matrix. (The algorithm can also be applied to rectangular matrices, but as this is rarely done in practice, we shall confine our attention to the square case.) The idea is to transform A into an m m upper-triangular matrix U by introducing zeros below the diagonal, first in column 1, then in column 2, and so on-just as in Householder triangularization. This is done by subtracting multiples of each row from subsequent rows. This "elimination" process is equivalent to multiplying A by a sequence of lower-triangular matrices L k on the left:
Setting L = L 1 ?1 L 2 -1... L m ?1 ?1 gives A = LU.
