20
$\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$
1
  • 3
    $\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, 2012 at 4:17

1 Answer 1

28
$\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$
5
  • 3
    $\begingroup$ "permutation matrices all satisfy the condition $P^2=I$" is incorrect. $\endgroup$
    – user147263
    Jan 16, 2016 at 22:09
  • $\begingroup$ @Normal for example ? Sorry, I can't see past swap then reverse swap does nothing... $\endgroup$ Jan 16, 2016 at 22:28
  • 2
    $\begingroup$ A permutation can involve a $3$-cycle like $1\to 2\to 3$. $\endgroup$
    – user147263
    Jan 16, 2016 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$ Jan 17, 2016 at 1:39
  • 4
    $\begingroup$ For all permutation matrices: $P \cdot P^{T} = I$ $\endgroup$
    – Friedrich
    Feb 5, 2019 at 8:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .