Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Yes. Let $A$ be $m \times n$ matrix, then $L$ is $m \times m$ and $U$ is $m \times n$. –  user2468 Aug 26 '12 at 4:17

1 Answer 1

up vote 6 down vote accepted

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^2=I$ the existence of a $PLU$-decomposition for $A$ naturally suggests that $PA = 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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