5
$\begingroup$

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?

1 Answers 1

5

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.

  • 1
    It is not $A^T$ but $QAQ$ whose LU-factorization gives rise to $A=UL$.2015-07-24