11
$\begingroup$

In my textbook, there is some information about LU factorization of square matrix $A$, but not about non-square matrix.

How can LU factorization be used to factorize non-square matrix?

$\endgroup$
  • 2
    $\begingroup$ Yes. Let $A$ be $m \times n$ matrix, then $L$ is $m \times m$ and $U$ is $m \times n$. $\endgroup$ – user2468 Aug 26 '12 at 4:17
17
$\begingroup$

I'll illustrate how to understand the LU-decomposition of a particular $3 \times 4$ matrix below. The method works just as well for other sizes since the LU-decomposition arises naturally from the study of Gaussian elimination via multiplication by elementary matrices.

$$ \begin{array}{ll} A \ = &\left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ 2 & 4 & 0 & 7 \\ -1 & 3 & 2 & 0 \end{array} \right] \ \underrightarrow{r_2-2r_1 \rightarrow r_2} \ \left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ 0 & 0 & 6 & 5 \\ -1 & 3 & 2 & 0 \end{array} \right] \ \underrightarrow{r_3+r_1 \rightarrow r_3} \\ & \\ &\left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ 0 & 0 & 6 & 5 \\ 0 & 5 & -1 & 1 \end{array} \right] \ \underrightarrow{r_2 \leftrightarrow r_3} \ \left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ 0 & 5 & -1 & 1 \\ 0 & 0 & 6 & 5 \end{array} \right] = \ U \end{array} $$ We have $U = E_3E_2E_1A$ hence $A = E_1^{-1}E_2^{-1}E_3^{-1}U$ and we can calculate the product $E_1^{-1}E_2^{-1}E_3^{-1}$ as follows: $$ \begin{array}{ll} I \ = &\left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right] \ \underrightarrow{r_2 \leftrightarrow r_3} \ \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array} \right] \ \underrightarrow{r_3-r_1 \rightarrow r_3} \\ & \\ &\left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 1 \\ -1 & 1 & 0 \end{array} \right] \ \underrightarrow{r_2+2r_1 \rightarrow r_2} \ \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 2 & 0 & 1 \\ -1 & 1 & 0 \end{array} \right] = PL \end{array} $$ I have inserted a "$P$" in front of the $L$ since the matrix above is not lower triangular. However, if we go one step further and let $r_2 \leftrightarrow r_3$ then we will obtain a lower triangular matrix: $$ \begin{array}{ll} PL \ = &\left[ \begin{array}{ccc} 1 & 0 & 0 \\ 2 & 0 & 1 \\ -1 & 1 & 0 \end{array} \right] \ \underrightarrow{r_2 \leftrightarrow r_3} \ \left[ \begin{array}{ccc} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & 0 & 1 \\ \end{array} \right] =L \end{array} $$ Therefore, we find that $E_1^{-1}E_2^{-1}E_3^{-1}=PL$ where $L$ is as above and $P = E_{2 \leftrightarrow 3}$. This means that $A$ has a modified $LU$-decomposition. Some mathemticians call it a $PLU$-decomposition, $$ A = \underbrace{\left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array} \right]}_{P} \underbrace{\left[ \begin{array}{ccc} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & 0 & 1 \\ \end{array} \right]}_{L}\underbrace{\left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ 0 & 5 & -1 & 1 \\ 0 & 0 & 6 & 5 \end{array} \right]}_{U} = \underbrace{\left[ \begin{array}{ccc} 1 & 0 & 0 \\ 2 & 0 & 1 \\ -1 & 1 & 0 \end{array} \right]}_{PL}\underbrace{\left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ 0 & 5 & -1 & 1 \\ 0 & 0 & 6 & 5 \end{array} \right]}_{U}. $$ Since permutation matrices all satisfy the condition $P^k=I$ (for some $k$) the existence of a $PLU$-decomposition for $A$ naturally suggests that $P^{k-1}A = LU$. Therefore, even when a $LU$ decomposition is not available we can just flip a few rows to find a $LU$-decomposable matrix. This is a useful observation because it means that the slick algorithms developed for $LU$-decompositions apply to all matrices with just a little extra fine print.

Much of the writing above can be spared if we adopt the notational scheme illustrated below. $$ \begin{array}{ll} A \ = &\left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ 2 & 4 & 0 & 7 \\ -1 & 3 & 2 & 0 \end{array} \right] \ \underrightarrow{r_2-2r_1 \rightarrow r_2} \ \left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ (2) & 0 & 6 & 5 \\ -1 & 3 & 2 & 0 \end{array} \right] \ \underrightarrow{r_3+r_1 \rightarrow r_3} \\ & \\ &\left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ (2) & 0 & 6 & 5 \\ (-1) & 5 & -1 & 1 \end{array} \right] \ \underrightarrow{r_2 \leftrightarrow r_3} \ \left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ (-1) & 5 & -1 & 1 \\ (2) & 0 & 6 & 5 \end{array} \right] = \ U \end{array} $$ We find if we remove the parenthetical entries from $U$ and ajoing them to $I$ then it gives back the matrix $L$ we found previously: $$ U = \left[ \begin{array}{cccc} 1 & 2 & -3 & 1\\ 0 & 5 & -1 & 1 \\ 0 & 0 & 6 & 5 \end{array} \right] \qquad L=\left[ \begin{array}{ccc} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & 0 & 1 \end{array} \right]. $$

Hope this helps.

$\endgroup$
  • 3
    $\begingroup$ "permutation matrices all satisfy the condition $P^2=I$" is incorrect. $\endgroup$ – user147263 Jan 16 '16 at 22:09
  • $\begingroup$ @Normal for example ? Sorry, I can't see past swap then reverse swap does nothing... $\endgroup$ – James S. Cook Jan 16 '16 at 22:28
  • 2
    $\begingroup$ A permutation can involve a $3$-cycle like $1\to 2\to 3$. $\endgroup$ – user147263 Jan 16 '16 at 22:45
  • $\begingroup$ @Normal right, that makes sense... but, there still must be some power for which $P^k=I$. So, something similar to what I have currently written is possible. I wonder, is this possible for $3 \times 3$ matrix examples. Great comment, I wish I could upvote comments ( for internet pts naturally) $\endgroup$ – James S. Cook Jan 17 '16 at 1:39
  • $\begingroup$ For all permutation matrices: $P \cdot P^{T} = I$ $\endgroup$ – Clip Feb 5 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.