3
$\begingroup$

I want to find an $LU$-factorization of the following matrix: \begin{align*} A = \begin{pmatrix} 3 & -6 & 9 \\ -2 & 7 & -2 \\ 0 & 1 & 5 \end{pmatrix} \end{align*} This matrix is invertible (the determinant is $33$), so I should be getting a $LU$ decomposition where $L$ is a lower triangular matrix with only $1s$ on the diagonal. But that's not what I'm getting. Here is what I did: \begin{align*} \begin{pmatrix} 3 & -6 & 9 \\ -2 & 7 & -2 \\ 0 & 1 & 5 \end{pmatrix} & \begin{matrix} \xrightarrow{R_1 \rightarrow 1/3 R_1} \end{matrix} \begin{pmatrix} 1 & -2 & 3 \\ -2 & 7 & -2 \\ 0 & 1 & 5 \end{pmatrix} \begin{matrix} \xrightarrow{R_2 \rightarrow R_2 + 2R_1} \end{matrix} \begin{pmatrix} 1 & -2 & 3 \\ 0 & 3 & 4 \\ 0 & 1 & 5 \end{pmatrix} \\ & \begin{matrix} \xrightarrow{R_2 \rightarrow 1/3 R_2} \end{matrix} \begin{pmatrix} 1 & -2 & 3 \\ 0 & 1 & \frac{4}{3} \\ 0 & 1 & 5 \end{pmatrix} \begin{matrix} \xrightarrow{R_3 \rightarrow R_3 - R_2} \end{matrix} \begin{pmatrix} 1 & -2 & 3 \\ 0 & 1 & \frac{4}{3} \\ 0 & 0 & \frac{11}{3} \end{pmatrix} = U. \end{align*} This matrix is now in echelon form. The elementary matrices corresponding to the operations are: \begin{align*} E_1 & = \begin{pmatrix} \frac{1}{3} & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \qquad (R_1 \rightarrow 1/3 R_1) \quad E_2 = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \qquad (R_2 \rightarrow R_2 + 2R_1) \\ E_3 &= \begin{pmatrix} 1 & 0 & 0 \\ 0 & \frac{1}{3} & 0 \\ 0 & 0 & 1 \end{pmatrix} \qquad (R_2 \rightarrow 1/3 R_2) \quad E_4 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -1 & 1 \end{pmatrix} \qquad (R_3 \rightarrow R_3 - R_2) \end{align*} Hence we have $E_4 E_3 E_2 E_1 A = U$. Now \begin{align*} E_4 E_3 E_2 E_1 = M = \begin{pmatrix} \frac{1}{3} & 0 & 0 \\ \frac{2}{9} & \frac{1}{3} & 0 \\ - \frac{2}{9} & - \frac{1}{3} & 1 \end{pmatrix} \end{align*} is a lower triangular matrix. Now we can write \begin{align*} A = (E_4 E_3 E_2 E_1)^{-1} U = M^{-1} U = LU, \end{align*} with \begin{align*} M^{-1} = L = \begin{pmatrix} 3 & 0 & 0 \\ -2 & 3 & 0 \\ 0 & 1 & 1 \end{pmatrix} \end{align*} But why does my matrix $L$ not have $1s$ on the diagonal? I thought an $LU$-factorization of an invertible matrix is unique, and that in that case $L$ is an unit lower triangular matrix? Did I overlook something or made a mistake? I haven't interchanged any rows. Please help!

$\endgroup$
  • $\begingroup$ An LU decomposition exists and can be found by rewriting $A=LU$ as $L=AU^{-1}$ and $U$ is certainly invertible $\endgroup$ – imranfat Aug 17 '15 at 19:54
4
$\begingroup$

In the framework of the Gaussian elimination procedure, you get $L$ with all $1$s on the diagonal by never truly rescaling rows. You rescale them in the intermediate step before you add them to another row, but then you "scale them back" so that you're only changing the row that you actually added to. You can always perform Gaussian elimination in this way. (By contrast, you may not always be able to perform Gaussian elimination without exchanging rows to obtain your next pivot, so an $LU$ decomposition may not always exist.)

$\endgroup$
  • $\begingroup$ I see. So if I want an $L$ with only $1s$ on the diagonal, I can never use elementary row operations of the form $R_i \rightarrow \lambda R_i$ ? $\endgroup$ – Kamil Aug 17 '15 at 19:53
  • $\begingroup$ @Kamil Correct. Alternately, you can keep track of those operations, and then "cancel" them at the end, as AlexR did. $\endgroup$ – Ian Aug 17 '15 at 19:54
3
$\begingroup$

Uniqueness is only for such $L$ that $L_{ii} = 1$ for all $i$. To achieve this, move the scaling factors to $U$ like this: $$A = LU = (LS)(S^{-1}U) = \tilde L \tilde U$$ Here you need $$S = \pmatrix{\frac13&&\\&\frac13&\\&&1}$$

$\endgroup$

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.