# 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 inserting $$Q^2$$ between $$L$$ and $$U$$, you arrive at $$A=U'L'$$ for some upper- and lower-triangular matrices $$U',L'$$
• It is not $A^T$ but $QAQ$ whose LU-factorization gives rise to $A=UL$. Jul 24, 2015 at 15:06