# Using permutation matrix to get LU-Factorization with $A=UL$

Let $Q$ be the $n$x$n$ permutation matrix

$$Q= \begin{bmatrix} 0&0&...&0&1\\ 0&0&...&1&0\\ .& \\ .&\\ .&\\ 0&0&...&0&0\\ 1&0&...&0&0\\ \end{bmatrix}$$

If $L \in \mathbb{R}$ is lower triangular, what is the structure of $QLQ$? Use this to show that one can factorize $A=UL$ where $U$ is unit upper triangular and $L$ is lower triangular.

I can see that $QLQ = L^T$

And $Q^2=I$

So here's what I am doing

$A=LU$

$QAQ=QLUQ = QLQ^2UQ =QLQQUQ = UL$

But now I am left with $QAQ = UL$ rather than $A=UL$

But does that matter?

It seems like it does as the factorization I get would be for solving $A^Tx=b$ rather than $Ax=b$

So have I missed something, is there a way to get the factorization $A=UL$ or have I actually got it but it's the case that I am misinterpreting my answer?

-

You know how to get $A=LU,$ so what if you instead do LU decomposition of $QAQ.$? Then, $QAQ=LU$ for some $L,U$ and by multiplying both sides with $Q$ from left and right, and doing the stuff above you did, you arrive at $A=U'L'$ for some $U',L'$
So, essentially, yes, you are doing $LU$-decomposition on $A^T$ and then transpose both sides in the decomposition.
It is not $A^T$ but $QAQ$ whose LU-factorization gives rise to $A=UL$. – hardmath Jul 24 '15 at 15:06