1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

LU factorization of matrices

  1. Sep 16, 2010 #1
    1. The problem statement, all variables and given/known data
    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.

    2. Relevant equations

    3. 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!
  2. jcsd
  3. Sep 17, 2010 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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'
  4. Sep 17, 2010 #3
    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).
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - factorization matrices Date
Finding an Integrating Factor Jun 18, 2017
Factorizing Problem May 1, 2017
Integrating factor to solve this? Mar 15, 2017
Rank, Co-factor matrices. Apr 1, 2012
Find Intersection of 3x2 Matrices Using QR Factorization Sep 22, 2010