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!

Homework Help: LU factorisation

  1. Mar 8, 2016 #1
    1. The problem statement, all variables and given/known data

    A =

    4 -4 -1
    4 -4 0
    4 0 0

    Use the criterion from the lectures to show that A does not have an LU factorisation such that A = LU with lower and upper triangular matrices L and U.

    How can you re-arrange the matrix rows such that it is evident without much computation that the permuted matrix does have an LU factorisation.

    2. Relevant equations

    A = LU

    L =
    I11 0 0
    I21 I22 0
    I31 I32 I33

    U =
    U11 U12 U13
    0 U22 U22
    0 0 U33

    3. The attempt at a solution

    I solved part 1, but taking a 2x2 sub-matrix and showing that its determinant is zero. [-4 0 ; 0 0] ----> det =0

    The second part where I have to show that A has an LU factorisation, I merely took A = LU and expanded upon that...

    4 -4 -1 = I11 0 0 U11 U12 U13
    4 -4 0 I21 I22 0 x 0 U22 U23
    4 0 0 I31 I32 I32 0 0 U33

    = I11U11 I11U12 U13
    I21U11 I21U12 + I22U22 I21U13 + U22
    I21U11 I31U12 + I32U22 I31U13 + I32U23 + U33

    Let I11 = I22 = I33 = 1

    = U11 I11U12 U13
    I21U11 I21U13 + U22 I21U13 + U22
    I31U11 I31U12 + I32U22 I31U13 + I32U23 + I33U33

    Substituting the values of A into the LU, we get

    U11 = 4 I11U12 = -4 U13 = -1
    I21U11 = 4 I21U13 + U22 = -4 I21U13 + U22 = 0
    I31U11 = 4 I31U12 + I32U22 = 0 I31U13 + I32U23 + I33U33 = 0

    Now at this form, it's becoming obvious that row 1 and row 3 needs to be swapped. There is a single pivot on the left-most side of the third row, and that'll allow for an LU factorisation. Unfortunately, I can't really rationalise my position outside of that...
  2. jcsd
  3. Mar 9, 2016 #2


    User Avatar
    Homework Helper

    The second part asks how you can rearrange the matrix rows to make it clear.
    You have found that you need to swap rows 1 and 3, looking at the original matrix, does that make sense?
    ##A= \begin{bmatrix} 4&-4&-1\\4&-4&0\\4&0&0\end{bmatrix}, \hat A = \begin{bmatrix} 4&0&0\\4&-4&0\\4&-4&-1\end{bmatrix},##
    By making that switch, you have made A into a lower triangular matrix from the outset. Your U in this case would just be the identity.
  4. Mar 9, 2016 #3
    Yes, I get that. It seems like the rest of the stuff I did earlier is probably not required.

    Thanks RUber!
  5. Mar 9, 2016 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Actually, it MAY be required. What you have shown so far is that if you permute the rows there is, indeed, an LU factorization. The first part asks you to show the opposite: if you do not change the matrix (eg., do not permute the rows) there is no LU decomposition. That seems much harder.
  6. Mar 9, 2016 #5
    Yes, for the first part, I essentially grabbed a sub-matrix and showed that its determinant is zero. To go any further than that would probably be quite tricky.

    Thanks Ray
  7. Mar 9, 2016 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    I could not follow the argument you presented.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted