Here I will consider an invertible n × n matrix and show that such a matrix always has a
PLU factorization. More general matrices could also be considered but this is all I will
present.
Let A be such an invertible matrix and consider the first column of A. If A_{11}≠0,
use this to zero out everything below it. The entry A_{11} is called the pivot. Thus in
this case there is a lower triangular matrix L_{1} which has all ones on the diagonal such
that
( )
L1P1A = ∗ ∗ (5.2)
0 A1
(5.2)
Here P_{1} = I. In case A_{11} = 0, let r be such that A_{r1}≠0 and r is the first entry for which this
happens. In this case, let P_{1} be the permutation matrix which switches the first row and the r^{th}
row. Then as before, there exists a lower triangular matrix L_{1} which has all ones on the diagonal
such that 5.2 holds in this case also. In the first column, this L_{1} has zeros between the first row
and the r^{th} row.
Go to A_{1}. Following the same procedure as above, there exists a lower triangular matrix and
permutation matrix L_{2}^{′},P_{2}^{′} such that
and L_{2} has all the subdiagonal entries equal to 0 except possibly some nonzero entries in the
second column starting with position r_{2} where P_{2} switches rows r_{2} and 2. Continuing this way, it
follows there are lower triangular matrices L_{j} having all ones down the diagonal and permutation
matrices P_{i} which switch only two rows such that
Ln−1Pn−1Ln− 2Pn −2Ln−3⋅⋅⋅L2P2L1P1A = U (5.3)
(5.3)
where U is upper triangular. The matrix L_{j} has all zeros below the main diagonal except for the
j^{th} column and even in this column it has zeros between position j and r_{j} where P_{j} switches rows
j and r_{j}. Of course in the case where no switching is necessary, you could get all nonzero entries
below the main diagonal in the j^{th} column for L_{j}.
The fact that L_{j} is the identity except for the j^{th} column means that each P_{k} for k > j almost
commutes with L_{j}. Say P_{k} switches the k^{th} and the q^{th} rows for q ≥ k > j. When you place P_{k} on
the right of L_{j} it just switches the k^{th} and the q^{th} columns and leaves the j^{th} column unchanged.
Therefore, the same result as placing P_{k} on the left of L_{j} can be obtained by placing P_{k} on the
right of L_{j} and modifying L_{j} by switching the k^{th} and the q^{th} entries in the j^{th} column.
(Note this could possibly interchange a 0 for something nonzero.) It follows from 5.3
there exists P, the product of permutation matrices, P = P_{n−1}
⋅⋅⋅
P_{1} each of which
switches two rows, and L a lower triangular matrix having all ones on the main diagonal,
L = L_{n−1}^{′}
⋅⋅⋅
L_{2}^{′}L_{1}^{′}, where the L_{j}^{′} are obtained as just described by moving a succession of
P_{k} from the left to the right of L_{j} and modifying the j^{th} column as indicated, such
that
LP A = U.
Then
A = PT L−1U
It is customary to write this more simply as
A = P LU
where L is an upper triangular matrix having all ones on the diagonal and P is a permutation
matrix consisting of P_{1}
⋅⋅⋅
P_{n−1} as described above. This proves the following theorem.
Theorem 5.6.1Let A be any invertible n×n matrix. Then thereexists a permutation matrix Pand a lower triangular matrix L having all ones on the main diagonal and an upper triangularmatrix U such that