into a product of upper and lower
triangular matrices (U and L, respectively).
Writing out the indices, this is equivalent to
This decomposition is useful, because the solution of triangular matrices is easily accomplished by successive substitution in the corresponding linear equations (starting with the corner of the triangle corresponding to a single non-zero term on the left side of the equation).
We begin by observing that the decomposition (1) is not unique, since the matrices
will do as well, if e is any non-singular diagonal matrix. We will make the choice
The equations 2 have the remarkable property, that we can scan
the elements 
of each row in turn, writing 
and 
into the locations as we go. At each position 
, we only
require the current and already calculated values of 
and 
. To see how this works, consider the first few rows.
If 
,
defining the first row of 
and 
. The 
are written
over the 
, which are no longer needed. If 
,
The first line gives 
, and the second 
, in terms of existing
elements of and . The and are written
over the 
(remember that 
by definition.) If 
,
yielding in turn 
,
and 
, which are written over
.
The algorithm should now be clear. At the 
row,
becomes very small. Now 
, while in general
. Thus the absolute values of 
are
maximized if the rows of (1) are rearranged so that the
absolutely largest elements of in each column lie on the diagonal.
A little thought shows that the solutions are unchanged by permuting the
rows (same equations - different order). This is
called pivoting.
