1. ## 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?

2. ## 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
\\ \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.

3. 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?

4. ## Well

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.