LU Factorization of Matrices: How to Prove Uniqueness and Compute L and U

[Dunkle]

Homework Statement

Most invertible matrices can be written as a product A=LU of a lower triangular matrix L and an upper triangular matrix U, where in addition all diagonal entries of U are 1.

a. Prove uniqueness, that is, prove that there is at most one way to write A as a product.
b. Explain how to compute L and U when the matrix A is given.
c. Show that every invertible matrix can be written as a product LPU, where L, U, are as above and P is a permutation matrix.

Homework Equations

\\

The Attempt at a Solution

b. The general process involves multiplying by a series of lower triangular matrices to "kill" entries under the diagonal of A. Eventually, A will be in upper triangular form. We will have

U = L_k...L_1A \Rightarrow A = LU where L = L_1^{-1}...L_k^{-1}

Notes: The product of lower triangular matrices is also triangular. Also, lower triangular matrices are invertible.

I'm stuck on parts a. and c.

Thanks in advance for any help!

 

[Office_Shredder]

For part a, a proof by contradiction should work.

Suppose that LU=L'U' where L, L' are lower triangular and U, U' are upper triangular. You need some way to prove that U=U' and L=L'

 

[Dunkle]

That was the approach I was attempting to take, but I couldn't figure out to show this explicitly. I think the key here is that all the diagonal entries of U are 1. It sort of makes sense that the algorithm I used in part b will give a unique upper triangular matrix, and then one would simply scale all the rows using elementary matrices (these scaling matrices are also lower diagonal) until the diagonal entries are 1. But, since part a should not rely on part b, it seems like there must be a better way (especially one not as sloppy).