5.6. EXISTENCE FOR THE PLU FACTORIZATION 135

Let A be such an invertible matrix and consider the first column of A. If A11 ̸= 0, usethis to zero out everything below it. The entry A11 is called the pivot. Thus in this casethere is a lower triangular matrix L1 which has all ones on the diagonal such that

L1P1A =

(∗ ∗0 A1

)(5.2)

Here P1 = I. In case A11 = 0, let r be such that Ar1 ̸= 0 and r is the first entry for whichthis happens. In this case, let P1 be the permutation matrix which switches the first rowand the rth row. Then as before, there exists a lower triangular matrix L1 which has allones on the diagonal such that 5.2 holds in this case also. In the first column, this L1 haszeros between the first row and the rth row.

Go to A1. Following the same procedure as above, there exists a lower triangular matrixand permutation matrix L′

2, P′2 such that

L′2P

′2A1 =

(∗ ∗0 A2

)

Let

L2 =

(1 0

0 L′2

), P2 =

(1 0

0 P ′2

)Then using block multiplication, Theorem 3.5.2,(

1 0

0 L′2

)(1 0

0 P ′2

)(∗ ∗0 A1

)=

=

(1 0

0 L′2

)(∗ ∗0 P ′

2A1

)=

(∗ ∗0 L′

2P′2A1

) ∗ · · · ∗

0 ∗ ∗0 0 A2

 = L2P2L1P1A

and L2 has all the subdiagonal entries equal to 0 except possibly some nonzero entries inthe second column starting with position r2 where P2 switches rows r2 and 2. Continuingthis way, it follows there are lower triangular matrices Lj having all ones down the diagonaland permutation matrices Pi which switch only two rows such that

Ln−1Pn−1Ln−2Pn−2Ln−3 · · ·L2P2L1P1A = U (5.3)

where U is upper triangular. The matrix Lj has all zeros below the main diagonal exceptfor the jth column and even in this column it has zeros between position j and rj where Pj

switches rows j and rj . Of course in the case where no switching is necessary, you could getall nonzero entries below the main diagonal in the jth column for Lj .

The fact that Lj is the identity except for the jth column means that each Pk for k > jalmost commutes with Lj . Say Pk switches the kth and the qth rows for q ≥ k > j. Whenyou place Pk on the right of Lj it just switches the kth and the qth columns and leaves thejth column unchanged. Therefore, the same result as placing Pk on the left of Lj can beobtained by placing Pk on the right of Lj and modifying Lj by switching the kth and the qth

entries in the jth 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 = Pn−1 · · ·P1