PA = LU Factorization with Pivoting

    The above theorem assumes that there are no row interchanges.  We have seen in Example 3 an example of a nonsingular matrix A could not be directly factored as A = LU.  If row interchanges are permitted then a factorization of a "permuted matrix" will be obtained.  A permutation of the first n positive integers  .  is an arrangement    of these integers in a definite order.  For example,    is a permutation of the five integers  .  The standard base vectors    for    are used in the next definition.  

Definition ( Permutation Matrix).  An n�n permutation matrix P is a matrix with precisely one entry whose value is "1" in each column and row, and all of whose other entries are "0."  The rows of  P  are a permutation of the rows of the identity matrix and  P  can be written as  

        .

The elements of    have the form