Permutation Matrix

**Makall** · January 31st 2010, 01:14 AM

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?

**wilbursmith** · January 31st 2010, 09:15 AM

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 \\ \noalign{\medskip}0&1&-1\end {array} \right] $

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

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 \\ \noalign{\medskip}1&2&-1\end {array} \right] $ 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.

**Makall** · January 31st 2010, 10:24 PM

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?

**wilbursmith** · January 31st 2010, 11:38 PM

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.

Thread: Permutation Matrix

LinkBack

Thread Tools

Display

Permutation Matrix

Don´t worry

Well

Similar Math Help Forum Discussions

Permutation matrix properties proof

permutation matrix question

Permutation Matrix

permutation matrix

Plot condition number of Hilbert matrix against matrix size n.

Search Tags