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: Permutation matrix and PA = LDU

  1. Jul 28, 2009 #1
    1. The problem statement, all variables and given/known data
    Find the PA = LDU factorizations for:

    A = [tex]\left[ \begin{array}{ccc} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 2 & 3 & 4 \end{array} \right] [/tex]

    The author chooses a permutation matrix :

    P = [tex]\left[ \begin{array}{ccc} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{array} \right] [/tex]

    If I do the same I obviously get the same factorization as in the book.

    If I choose a permutation matrix,

    P = [tex]\left[ \begin{array}{ccc} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{array} \right] [/tex]

    I do not get the same factorization. Should I get the same answers even though I'm arranging the equations somewhat different, or am I missing something here?

    Help is greatly appreciated, thanks!
  2. jcsd
  3. Jul 29, 2009 #2


    User Avatar
    Homework Helper

    If LU decomposition is performed with pivoting, P is the outcome of the decomposition process depending on pivoting. So, it seems odd that you or the author would be choosing P up front.

    Maybe you are trying to study the affect on LU w/o pivoting by swapping rows of the original matrix? In any event, I would think using different P's would result in different LU factorizations because the matrix to be factored changes. I don't think two different matrices can have the same LU decomposition.
  4. Jul 30, 2009 #3

    Say that I want to do elimination on the above matrix A.
    As one possibility, I could start by exchanging row 1 with row 3 such that the integer 2 is in the first pivot position.

    I would then perform elimination until I have a upper triangular matrix U.
    I get the matrix U by multiplying A with a permutation matrix P, and two elementary matrices, say E and F.

    [tex] U = FEPA [/tex]

    Then L would be the product of the inverse of E and F.

    [tex]L= E^{-1}F^{-1}[/tex]

    I could also have started the elimination process by exchanging row 1 with row 2, which would have yielded a different permutation matrix, and also a different factorization LDU.

    Am I totally off here?

    Thank you for your time!
  5. Jul 31, 2009 #4


    User Avatar
    Homework Helper

    Correct, you'd have two different LDU factorizations because you are factoring two different matrices. Even though you are starting from the same matrix in your two scenarios, the input to the LDU factorization algorithm is a different permutation of the original matrix in each case.

    What makes this a bit confusing is your use of the permutation matrix P. Like I said, P is usually determined by the LU decomposition algorithm with pivoting, not something you choose ahead of time. Though perfectly valid, what you are doing is permuting the matrix with a P of your choice before performing LU decomposition w/o pivoting.
    Last edited: Jul 31, 2009
  6. Aug 1, 2009 #5
    I understand, thank you :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook