# Finding the $LU$ decomposition of a matrix (Linear algebra)

Use elementary row operations to find the LU decomposition of the following matrix

$${\bf A} = \left[ {\begin{array}{cc} 1 & -1 & 0 \\ -1 & 2& 1 \\ 0 & -1 & 2 \end{array} } \right]$$

What i tried

I know that $\bf A=LU$, To find the $\bf U$ i do a row reduction to get $${\bf U} = \left[ {\begin{array}{cc} 1 & -1 & 0 \\ 0 & 1& -1 \\ 0 & 0 & 1 \end{array} } \right]$$ However i have problems finding $\bf L$ from $\bf U$. Could anyone explain. Thanks

Try tracing back the row operations you did. Those can be expressed as multiplying $\bf A$ by a series of elementary matrices. The product of those should be lower triangular, so its inverse, name it $\bf L$, satisfies $\bf A=LU$. For the $LU$ decomposition, you need $\bf L$ to be unitriangular, i.e. have 1 on the diagonal. The easiest way to achieve that is to extract the diagonal terms as a diagonal matrix and multiply $\bf L$ on the right by the inverse of that matrix, and $\bf U$ on the left by that matrix.

$${\bf A}=\left[\begin{array}{ccc} 1 & -1 & 0 \\ -1 & 2 & 1 \\ 0 & -1 & 2 \end{array}\right].$$

We sum the first row to the second. This equates to the following multiplication:

$$\left[\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right]\left[\begin{array}{ccc} 1 & -1 & 0 \\ -1 & 2 & 1 \\ 0 & -1 & 2 \end{array}\right]=\left[\begin{array}{ccc} 1 & -1 & 0 \\ 0 & 1 & 1 \\ 0 & -1 & 2 \end{array}\right].$$

Next, we sum the second row to the third one, which equates to:

$$\left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{array}\right]\left[\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right]\left[\begin{array}{ccc} 1 & -1 & 0 \\ -1 & 2 & 1 \\ 0 & -1 & 2 \end{array}\right]=\left[\begin{array}{ccc} 1 & -1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{array}\right]=:{\bf U}.$$

Now we multiply those two elementary matrixes and call their product ${\bf L}^{-1}$:

$${\bf L}^{-1}:=\left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{array}\right]\left[\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right]=\left[\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{array}\right].$$

I bet you can guess why I called this matrix ${\bf L}^{-1}$: the $\bf L$ you are looking for is its inverse. So:

$${\bf L}=({\bf L}^{-1})^{-1}=\left[\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{array}\right]^{-1}=\frac{1}{\det {\bf L}^{-1}}\left[\begin{array}{ccc} 1 & -1 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \end{array}\right]^T=\left[\begin{array}{ccc} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & -1 & 1 \end{array}\right].$$

And now we finally have $\bf A=LU$.

• Note: in this case we were lucky that $L$ came out lower triangular. In general, one might need to extract the diagonal terms. Or maybe not... the elementary matrix are all unitriangular I think, so their product also is, and the inverse of that all the same. So it'not just a coincidence that we got a unitriangular matrix over here. – MickG Sep 15 '15 at 10:23
• Since the $A=LU$ decomposition is mostly used for easily computing the inverse of $A$ (when it exists), computing $L$ with matrix inversion is not something I'd like. The advantage of $LU$ decomposition is that you don't have to compute any inverse for writing it. – egreg Sep 15 '15 at 11:25
• Or rather that the inverses are easy to compute @egreg. It's true, I could have avoided that by keeping the product and writing the inverse as the product of the inverses in reverse order, and those inverses are immediately computed. But I saw your answer below and cannot trace the origin of that 3 in $L$... Why do you need it? – MickG Sep 15 '15 at 11:31
• After all, isn't it $L$ that has to be unitriangular? Why make $U$ unitriangular and have $L$ with a diagonal 3 as a result? – MickG Sep 15 '15 at 11:33
• The inverse of a triangular matrix is very fast to compute as compared to the inverse of a "full" matrix. – mathreadler Sep 15 '15 at 11:35

The row operations you need are

1. Sum to the second column the first one multiplied by $1$ (I denote this by $\mathbf{E}_{21}(1)$)
2. Sum to the third column the second column multiplied by $1$ (I denote this by $\mathbf{E}_{31}(1)$)
3. Multiply the third column by $1/3$ (I denote this by $\mathbf{E}_{3}(1/3)$)

Since the elimination is performed without row switching and “going down all the way” with each pivot, the matrix $\mathbf{L}$ can be easily written

1. $\mathbf{L}$ has $-1$ at position $(2,1)$
2. $\mathbf{L}$ has $-1$ at position $(3,2)$
3. $\mathbf{L}$ has $3$ at position $(3,3)$

The other coefficients are determined by the rule “$1$ on the diagonal, $0$ off the diagonal”.

Why is this? Think to $\mathbf{E}_{i}(c)$ as the matrix obtained from the identity by multiplying the $i$-th row by $c$; to $\mathbf{E}_{ij}(d)$ as the matrix obtained from the identity by summing to the $i$-th row the $j$-th row multiplied by $d$. The elimination steps performed above are the same as writing $$\mathbf{U}=\mathbf{E}_{3}(1/3)\mathbf{E}_{32}(1)\mathbf{E}_{21}(1)\mathbf{A}= \begin{bmatrix} 1 & -1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}$$ (which is different from yours, though), so $$\mathbf{L}=\bigl(\mathbf{E}_3(1/3)\mathbf{E}_{32}(1)\mathbf{E}_{21}(1)\bigr)^{-1} =\mathbf{E}_{21}(-1)\mathbf{E}_{32}(-1)\mathbf{E}_3(3)$$ You can check (and you should find a proof in Strang's book) that you can simply fill in the coefficients: $\mathbf{E}_{ij}(d)$ corresponds to writing $d$ at place $(i,j)$ and $\mathbf{E}_{i}(c)$ corresponds to writing $c$ at place $(i,i)$.

However it's important that the elimination is performed in the specified way with no row swap. This guarantees $\mathbf{L}$ is lower triangular.

Finally $$\mathbf{L}=\begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & -1 & 3 \end{bmatrix}$$

Just rewrite it as ${\bf L} = {\bf AU}^{-1}$ and compute it, for instance by first computing ${\bf U}^{-1}$ and then just a matrix multiplication.

We can by 2 row operations find $${\bf U}^{-1} = \left[\begin{array}{ccc}1 &1&1\\0&1&1\\0&0&1\end{array}\right]$$ which is not surprising as the rows of $\bf U$ approximates a derivative filter, ${\bf U}^{-1}$ approximates an integral (sum) which is the inverse operation to differentiation.

Anyway computing $${\bf AU}^{-1} = \left[\begin{array}{rrr}1 &-1&0\\-1&2&1\\0&-1&2\end{array}\right] \left[\begin{array}{ccc}1 &1&1\\0&1&1\\0&0&1\end{array}\right] = \left[\begin{array}{rrr}1&0&0\\-1&1&2\\0&-1&2\end{array}\right]$$

But this is not lower triangular so something is wrong. Either $\bf A$ or $\bf L$ or the derivation of ${\bf U}^{-1}$.. what could it be?

Edit : I see now that given $\bf U$ in the question was wrong and the other answer derived the right one. Anyway the method still works if we input a valid (non-singular) $\bf U$.

• What if $A$ (and so $U$) is not invertible? – egreg Sep 15 '15 at 11:26
• Yes that would be an inconvenience. Maybe we could use a pseudo inverse then (?) But if we find U to have only non-zeros on the diagonal we can definitely do it. – mathreadler Sep 15 '15 at 11:30
• What is a pseudo inverse ? – Shailesh Sep 15 '15 at 11:38
• A pseudo inverse is something which approximates an inverse but is able to handle degeneracy ( i.e. when some eigenvalues = 0 ). For instance you have Moore-Penrose pseudoinverse en.wikipedia.org/wiki/Moore%E2%80%93Penrose_pseudoinverse – mathreadler Sep 15 '15 at 11:42
• @mathreadler Thanks for prompting the edit; but, please, if you edit some matrix name, do it for all; and note that \bf has been an obsolete and deprecated command in LaTeX for 20 years. – egreg Sep 15 '15 at 11:44