LU factorization of matrices

  • Thread starter Dunkle
  • Start date
  • #1
56
0

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

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

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!
 

Answers and Replies

  • #2
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,536
578
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'
 
  • #3
56
0
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).
 

Related Threads on LU factorization of matrices

  • Last Post
Replies
8
Views
4K
  • Last Post
Replies
0
Views
5K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
7K
Replies
1
Views
4K
Replies
2
Views
10K
  • Last Post
Replies
0
Views
8K
  • Last Post
Replies
5
Views
725
Replies
2
Views
5K
Top