Results 1 to 4 of 4

Math Help - Permutation Matrix

  1. #1
    Junior Member
    Joined
    Jan 2010
    Posts
    30

    Permutation Matrix

    Find the permutation matrix P so that PA can be factored into the product LU, where L is lower triangular with 1's on its diagonal and U is upper triangular for these matrices.

    A = \left[ \begin{array}{cccc} 1 & 2 & -1 \\ 2 & 4 & 0 \\ 0 & 1 & -1 \end{array} \right]

    So the back of the book shows: P = \left[ \begin{array}{cccc} 1 & 0 & 0 \\ 0 & 0  & 1 \\ 0 & 1 & 0 \end{array} \right]

    Which I tried working out and got the same answer. I didn't interchange the first and second row which I assume the book didn't either.

    But MATLAB shows this: U = \left[ \begin{array}{cccc} 2 & 4 & 0 \\ 0 & 1  & -1 \\ 0 & 0 & -1 \end{array} \right] P = \left[ \begin{array}{cccc} 0 & 1 & 0 \\ 0 & 0  & 1 \\ 1 & 0 & 0 \end{array} \right]

    The other one I did was A = \left[ \begin{array}{cccc} 1 & 1 & -1 & 2 \\ -1 & -1  & 1 & 5 \\ 2 & 2 & 3 & 7 \\ 2 & 3 & 4 & 5 \end{array} \right] and got A = \left[ \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0  & 0  & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1  & 0 & 0 \end{array} \right] but MATLAB shows U = \left[\begin{array}{cccc} 2 & 2 & 3 & 7\\ 0 & 1 & 1 & -2\\ 0 & 0 & - \frac{5}{2} & - \frac{3}{2}\\ 0 & 0 & 0 & 7 \end{array}\right] P = \left[\begin{array}{cccc} 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 \end{array}\right]

    All the other questions, the P in the back of the book and MATLAB are the same. I noticed in MATLAB, it chooses biggest number in the first column and sets that as the first row.

    So is the book wrong and am I supposed to choose the biggest number in the first column and set that as the first row before I start row reducing? But how do I know if [2 2 3 7] or [2 3 4 5] is bigger?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jan 2010
    Posts
    28

    Donīt worry

    Donīt worry. Your calculations are correct and so is the book.

    A=\left[ \begin {array}{ccc} 1&2&-1\\ \noalign{\medskip}2&4&0<br />
\\ \noalign{\medskip}0&1&-1\end {array} \right] <br />

    PA=LU where P=\left[ \begin {array}{ccc} 1&0&0\\ \noalign{\medskip}0&0&1<br />
\\ \noalign{\medskip}0&1&0\end {array} \right] , L= \left[ \begin {array}{ccc} 1&0&0\\ \noalign{\medskip}0&1&0<br />
\\ \noalign{\medskip}2&0&1\end {array} \right] <br /> <br />
and U= \left[ \begin {array}{ccc} 1&2&-1\\ \noalign{\medskip}0&1&-1<br />
\\ \noalign{\medskip}0&0&2\end {array} \right] <br />

    Factorising A to LU is simple if you only use BO1+, which means subtracting a multiple of a row from a latter one. Sometimes you will not get U by simply using BO1+. You might need to switch rows in the process, by (BO2). Now you can do this two ways, either by using a permutation matrix P or by just switching the rows first as if they were like that in the beginning. It seems that this is just what matlab did since it started out with A= \left[ \begin {array}{ccc} 2&4&0\\ \noalign{\medskip}0&1&-1<br />
\\ \noalign{\medskip}1&2&-1\end {array} \right] <br />
which bothers me. I donīt know how you made your calculations but I always write down the basic operation steps. It took me only one row change whereas matlab seemed to do it twice.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2010
    Posts
    30
    BO1+, BO2? I'm not sure what those are.

    I'm not sure if I'm supposed to interchange [2 2 3 7] with the first row, then row reduce. And if I do, why do I interchange the first row with [2 2 3 7] and not [2 3 4 5]? Since the row interchanges determine how I get P...

    I thought you only interchange the first row only if A_{11} = 0 but then which row do you choose to interchange it with?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jan 2010
    Posts
    28

    Well

    I can not help you with the matlab issue but Iīm positive that you have made the correct answers.

    When you convert a matrix into an echelon matrix you go through a few reduction steps, right? The most common is BO1+, which stands for a basic operation where you row reduce, letīs say you take row 2 minus three times row 1. If you can convert a matrix A into U which is an echelon matrix simply by BO1+ then you donīt need a permutation matrix. This way A can be factorised into LU.

    However sometimes other operations are necessary, like BO1- which is a basic operation where you reduce from a later row. Letīs say you take row 3 minus one times row 4. This is used when converting into reduced echelon. BO2 stands for interchanging two rows and BO3 stands for multiplying a row with a scalar. So if you need BO2 anywhere in the process then A can not be factorised into LU simply by row reduction but PA can. P interchange the rows in A before you even start.

    What I do when I solve those problems you presented is that I look into A_{11} as you said, note that nothing needs to be done. Then I start reducing systematically with BO1+ and when I end up in a situation where interchanging rows (BO2) is needed, I do that. When Im done and have my echelon matrix I write down my permutation matrix P. All I have to do is look which rows I interchanged in the process and change those rows respectively in P.

    Now this is the way Iīve been taught in my university and Iīm sure there are other ways.

    As soon as you realize that youīll need to interchange rows, thatīs when you know that a permutation matrix P is needed in order to factorise A into LU.

    If you multiply P with A in one of your problems you get a product which is factoriseable into LU with only row reduction.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Permutation matrix properties proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 6th 2011, 04:17 AM
  2. permutation matrix question
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: March 7th 2011, 02:59 AM
  3. Permutation Matrix
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 17th 2010, 07:37 AM
  4. permutation matrix
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: May 26th 2009, 12:30 AM
  5. Replies: 3
    Last Post: March 17th 2009, 11:10 AM

Search Tags


/mathhelpforum @mathhelpforum