0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

Let me show you how to proceed in your case. We start with:

$${\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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – MickG Sep 15 '15 at 10:23
  • $\begingroup$ 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. $\endgroup$ – egreg Sep 15 '15 at 11:25
  • $\begingroup$ 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? $\endgroup$ – MickG Sep 15 '15 at 11:31
  • $\begingroup$ 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? $\endgroup$ – MickG Sep 15 '15 at 11:33
  • $\begingroup$ The inverse of a triangular matrix is very fast to compute as compared to the inverse of a "full" matrix. $\endgroup$ – mathreadler Sep 15 '15 at 11:35
2
$\begingroup$

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} $$

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ What if $A$ (and so $U$) is not invertible? $\endgroup$ – egreg Sep 15 '15 at 11:26
  • $\begingroup$ 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. $\endgroup$ – mathreadler Sep 15 '15 at 11:30
  • $\begingroup$ What is a pseudo inverse ? $\endgroup$ – Shailesh Sep 15 '15 at 11:38
  • $\begingroup$ 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 $\endgroup$ – mathreadler Sep 15 '15 at 11:42
  • $\begingroup$ @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. $\endgroup$ – egreg Sep 15 '15 at 11:44

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.