# How can LU factorization be used in non-square matrix?

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?

-
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

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.

-
"permutation matrices all satisfy the condition $P^2=I$" is incorrect. – sandwich Jan 16 at 22:09
@Normal for example ? Sorry, I can't see past swap then reverse swap does nothing... – James S. Cook Jan 16 at 22:28
A permutation can involve a $3$-cycle like $1\to 2\to 3$. – sandwich Jan 16 at 22:45
@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) – James S. Cook Jan 17 at 1:39